ISEGORIA / MATH ENCYCLOPEDIA
Optimization: the geometry of the best choice
Descent, conditioning, constraints, and shadow prices.
Before you begin: Derivatives, vectors, and matrices
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Gradient descent and conditioning
Follow constant-step gradient descent across the elliptical contours of f, starting from a point you can drag. Each coordinate is multiplied by its own factor every step, so strongly unequal curvatures force a small step and make the fast direction zigzag. The right panel shows f on a log scale: the iterates fall along a straight line whose slope is set by ρ. Newton’s exact step, dashed, reaches this quadratic minimum at once.
Worked example. For κ = 4, constant-step gradient descent converges when 0 < η < 0.5, and η = 2/(1 + κ) = 0.4 gives the fastest rate ρ = 0.6.
Watch out. Newton’s one-step result is special to an invertible quadratic Hessian. It is not a general guarantee.
Why can increasing the step size make progress worse?
An update multiplier can have magnitude above one, amplifying errors.
2. Moving the constraint
Drag the constraint line x + y = b across the circular contours of x² + y², and slide a trial point along it. The optimum is where the smallest reachable circle just touches the line; any other point lies on a larger circle, as the right panel shows. Switch to the inequality x + y ≥ b to see the constraint become inactive when the origin is feasible.
Worked example. For b=2, the best point is (1,1), with objective value 2.
Watch out. This is an equality constraint. Replacing it with an inequality changes the feasible region and sometimes the optimum.
Why must x and y be equal at the optimum?
Because x²+y²=b²/2+(x-y)²/2, minimized at x=y.
3. Multipliers and sensitivity
On the left, the optimal value \(f_*(b)=b^2/2\) with its tangent: the slope is the multiplier \(\lambda_*\). On the right, the dual function \(g(\lambda)\), obtained by minimizing the Lagrangian for each fixed \(\lambda\). It never rises above \(f_*\) (weak duality), and its maximum at \(\lambda=b\) touches \(f_*\) exactly. Drag b on the left and λ on the right.
Worked example. At b=2, increasing b by 0.01 raises the optimum by about 0.02.
Watch out. Multiplier signs depend on the chosen constraint convention. Sensitivity is a local approximation.
What is the duality gap at λ=b?
Zero: the primal minimum and dual maximum both equal b²/2.