Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 42 / 1

For a minimization problem on a domain $D$, write the equality constraints as $h(x)=0$ and the inequality constraints as $g(x)\le 0$. Define the optimization LagrangianThe Lagrangian sufficiency theorem states that a feasible $x^{\ast }$ is globally optimal if it globally minimizes $L(\cdot ,{\lambda }^{\ast },{\mu }^{\ast })$ on $D$ for some multipliers with ${\mu }^{\ast }\ge 0$ and satisfies complementary slackness, ${\mu }_j^{\ast }{g}_j(x^{\ast })=0$ for every $j$. Equality multipliers have unrestricted signs.

For any feasible $x$, the multiplier sign gives $L(x,{\lambda }^{\ast },{\mu }^{\ast })\le f(x)$. Feasibility and complementary slackness at $x^{\ast }$ give $L(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })=f(x^{\ast })$. HenceThis proves sufficiency. Global Lagrangian minimization, rather than stationarity alone, is the certificate. No convexity or constraint qualification is needed for this implication; convexity is one way to verify the required global minimum.

Use the Lagrange multiplier with the sign conventionFor every $\lambda >0$, this is a strictly convex quadratic in $x$, with unique global minimizerThese formulas follow by setting the three partial derivatives of the optimization Lagrangian to zero; its Hessian is $\mathrm{diag}(2\lambda ,2\lambda ,4)$, which is positive-definite.

Choose $\lambda >0$ to make this minimizer feasible. Its constraint value is $5/(2{\lambda }^2)-\lambda /4$, so the scalar equation isThe left side of the first equation is strictly decreasing on $(0,\infty )$, with limits $+\infty$ and $-\infty$. Thus exactly one positive multiplier exists and can be obtained by a bracketed scalar root search. The Lagrangian sufficiency theorem proves that its associated feasible point is the global optimum; strict Lagrangian convexity makes that optimum unique.

Consequently the unique solution isIts objective value is $-5/\lambda +{\lambda }^2/8$. This scalar multiplier certificate for a quadratic equality constraint does not require finding the multiplier in radicals, and does not mistake the nonconvex equality surface for a convex set.

Introduce a free scalar $t$. The epigraph reformulation is the linear programFor each fixed $x$, the smallest feasible $t$ equals the maximum of the affine expressions, so the reformulation preserves the optimum.

Associate nonnegative multipliers $y_i$ with these inequalities. Its optimization Lagrangian isBecause $x$ and $t$ are unrestricted, the infimum is finite precisely when the coefficients of both vanish. Therefore the Lagrangian dual problem isA feasible dual vector is a convex combination of the slopes whose mean slope is zero. It gives a constant lower bound on the maximum of the affine functions. The primal is always feasible, by taking $x=0$ and sufficiently large $t$. If it has a finite optimum, linear programming duality gives attainment and equality with this dual; otherwise the dual is infeasible and the primal is unbounded below.