Nonlinear and Dynamic Programming
This domain tests nonlinear optimization and sequential decision models. Expect convexity, Lagrange multipliers, KKT conditions, local versus global optima, Bellman's principle, stages, states, decisions, and recursive dynamic programming.
Core rules
- For equality-constrained NLP, set gradients of objective and constraints proportional through multipliers.
- KKT conditions add nonnegative multipliers and complementary slackness for inequalities.
- Convex objective and convex feasible region make a local optimum global; KKT sufficiency needs appropriate convexity and constraint qualification.
- Dynamic programming requires optimal substructure: an optimal policy uses optimal decisions from every later state.
- Define state carefully; too coarse loses information, too fine causes state explosion.
Worked example
Maximize 4√x+2√y subject to x+y≤9, x,y≥0. Form L=4√x+2√y-λ(x+y-9). Derivatives give 2/√x=λ and 1/√y=λ, so 2/√x=1/√y, hence √x=2√y and x=4y. The budget binds: 4y+y=9, so y=1.8 and x=7.2. The objective is about 13.42, better than the boundary values 12 and 6. The binding budget and positive variables satisfy complementary slackness.
Traps
Assuming every NLP is convex, ignoring constraint qualification, accepting a local optimum as global, and defining DP states that omit necessary history.
Key points
- Lagrange multipliers link gradients.
- KKT adds inequality conditions.
- Convexity affects global optimality.
- DP needs optimal substructure.
- State definition controls correctness and size.