S3U

Math / Calculus / Graduate / mce01

KKT Conditions and Constraint Sensitivity

Solve a constrained convex problem and interpret its multiplier.

All worksheets
5 questions0m 0s

Prerequisites

Convex functions, Lagrangians, derivatives, and inequality constraints.

Learn the skill

For minimization with g(x)<=0, use L=f+lambda*g and lambda>=0. KKT combines feasibility, stationarity, and complementary slackness. For a differentiable convex problem, a feasible KKT point is globally optimal; necessity needs appropriate conditions.

Worked example

Minimizing (x-4)^2 subject to x<=2 gives x=2. Stationarity 2(x-4)+lambda=0 gives lambda=4: the objective locally decreases by about 4 per unit relaxation of the bound.

Model and Assumptions

Minimize f(x)=(x-3)^2 subject to x<=b, with no lower bound. Write g=x-b and L=(x-3)^2+lambda(x-b). First use b=1. The objective is strictly convex and strictly feasible points exist.

1. What is the optimal x when b=1?
2. What nonnegative multiplier satisfies stationarity at that point?
3. What is the optimal objective value when b=1?
4. What is the derivative of the optimal value with respect to b at b=1?
5. If b=4, what are the optimal x and multiplier?

Further inquiry

Derive the optimal value and multiplier as functions of b, including the transition at b=3. Derive the dual function and verify equality of primal and dual optima at b=1.

Review criteria

  • Obtain x*=min(3,b), with lambda*=max(0,6-2b).
  • Show the dual function lambda(3-b)-lambda^2/4 for lambda>=0.
  • Explain why the local sensitivity is not a constant prediction for every finite relaxation.