Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 3 / 21H (Optimization)

For a minimization problem over a domain $D$ with inequality constraints $g_j(x)\le 0$ and equality constraints $h_{\ell }(x)=0$, letThe Lagrangian sufficiency theorem states: if $x_{\ast }$ is feasible, ${\lambda }_j\ge 0$, ${\lambda }_j{g}_j(x_{\ast })=0$, and $x_{\ast }$ globally minimizes $\mathcal{L}(\cdot ,\lambda ,\mu )$ on $D$, then $x_{\ast }$ globally minimizes the constrained objective. Equality multipliers have no sign restriction.

For any feasible $x$, the sign of the inequality multipliers gives $\mathcal{L}(x,\lambda ,\mu )\le f(x)$. Feasibility and complementary slackness give $\mathcal{L}(x_{\ast },\lambda ,\mu )=f(x_{\ast })$. ThereforeThis proves the theorem. No convexity is necessary if the global minimization of the Lagrangian is already known. In a differentiable convex optimization problem with convex inequalities and affine equalities, a stationary point of this convex Lagrangian is automatically a global minimizer, which gives the familiar sufficiency of the Karush-Kuhn-Tucker conditions.

Put $x_0=1$. The constraints are equivalent to $y_i=x_i-x_{i-1}$, so the objective becomes the strictly convex quadraticIts derivative at an interior index gives $5x_i-2x_{i-1}-2x_{i+1}=0$, $1\le i<n$. The terminal derivative gives $3x_n-2x_{n-1}=0$. The characteristic equation $2r^2-5r+2=0$ has roots $2$ and $1/2$, soThe conditions $x_0=1$ and $3x_n=2x_{n-1}$ give $a+b=1$ and $b=2\cdot 4^{n}a$. ThusThese formulas also cover $n=1$, giving $x_1=2/3$, $y_1=-1/3$.

For a direct application of Lagrangian sufficiency theorem, use equality constraints $h_i=x_i-1-{\sum }_{k=1}^i{y}_k$ and multipliers ${\mu }_i=-2x_i^{\ast }$. The Lagrangian derivatives in $x_i$ vanish. Its derivative in $y_j$ is $4y_j^{\ast }+2{\sum }_{i=j}^n{x}_i^{\ast }$, which also vanishes: putting $S_j=2y_j^{\ast }+{\sum }_{i=j}^n{x}_i^{\ast }$, the interior recurrence gives $S_j-S_{j+1}=0$, and the terminal condition gives $S_n=0$. The Lagrangian has positive-definite quadratic part ${\sum }_i(x_i^2+2y_i^2)$, so this stationary point is its unique global minimum. The candidate is feasible, and the theorem proves it is the unique constrained optimal solution. Equivalently, strict convexity of the eliminated objective proves the same global conclusion.