Past exam of the continuous optimisation course of the University of Oxford / 2011 / 3

Take the usual symmetric meaning of positive definite $Q$. To include all data allowed by the source, first check feasibility. PutFull row rank makes $B$ positive definite. Every $x$ satisfying $Ax=b$ is uniquely $x_0+z$ with $Az=0$, and $z^{T}Q{x}_0=0$. ThusIf ${\rho }^2>1$, there is no feasible point. If ${\rho }^2=1$, the only feasible point is $x_0$, and $x_0$ is optimal for every $c$. If ${\rho }^2<1$, the Slater condition holds, and the following KKT conditions are necessary and sufficient:Necessity follows from the constraint qualification proved in (ii). Sufficiency follows from convexity: the stationary optimization Lagrangian $c^{T}x+y^T(b-Ax)+\gamma (x^{T}Qx-1)$ is minimized at $x$, while its feasible values never exceed the objective, and complementary slackness makes its value at $x$ equal the objective.

The singleton case cannot be silently covered by ordinary KKT necessity. For example, let $Q=I$, $A=(10)$, $b=1$, $c=(0,1{)}^T$. The sole feasible point $(1,0)$ is optimal, but stationarity would require $(0,1)$ to lie in the span of $(1,0)$, which is impossible. The feasibility split above supplies genuinely necessary and sufficient conditions without assuming an unprinted regularity hypothesis.

The equality gradients are independent everywhere. At an interior point of the ellipsoid, there is no active inequality, so the Mangasarian–Fromovitz constraint qualification holds. At a boundary point $x=x_0+z$, a qualifying direction must satisfy $Av=0$ and $2x^{T}Qv<0$.

If ${\rho }^2<1$, choose $v=x_0-x=-z$. At a boundary point $z^{T}Qz=1-{\rho }^2>0$, andThus the qualification holds at every feasible point. If ${\rho }^2=1$, the only feasible point is $x_0$; for every $v\in \ker A$, $x_0^{T}Qv=0$, so no strict direction exists. This provesThe equivalence also identifies this case with strict feasibility of the inequality on the affine equality space.

For $y\in {\mathbb{R}}^m$ and $\gamma \ge 0$, define the optimization LagrangianThe Lagrangian primal isFor feasible $x$, the supremum is $c^{T}x$: equality terms vanish and the nonpositive inequality term has maximum zero at $\gamma =0$. If $Ax\ne b$, scale $y$ in the direction $b-Ax$ to make the supremum infinite. If the inequality fails, send $\gamma \to \infty$. Thus the inner supremum is exactly the objective extended to $+\infty$ off the feasible set. This proves equivalence with the original problem, including its infeasible case.

Reverse the order of the two optimizations to obtain the Lagrangian dualPut $s=c-A^{T}y$ and $r=\sqrt{s^T{Q}^{-1}s}$. For $\gamma >0$, completing the square givesAt $\gamma =0$ the infimum is finite precisely if $s=0$, when it equals $b^{T}y$. For $r>0$, the expression $\gamma +r^2/(4\gamma )$ is minimized at $\gamma =r/2$, with value $r$. The same optimized value holds when $r=0$, choosing $\gamma =0$. Eliminating $\gamma$ therefore gives ${\sup }_y\{b^{T}y-\sqrt{s^T{Q}^{-1}s}\}$. Introducing $\theta =r$ yieldsThe nonnegative square root is enforced by $\theta \ge 0$. Optimizers correspond by $\gamma =\theta /2$, including the zero case.

For fixed $y$, $s=c-A^{T}y$ is fixed. The relaxed inequality and $\theta \ge 0$ say preciselyThe objective $b^{T}y-\theta$ strictly decreases with $\theta$, so its best choice is always equality. Replacing any feasible relaxed point by that choice preserves feasibility and improves or leaves unchanged the objective. Conversely every point satisfying equality is feasible for the relaxed problem. Thus the two dual formulations have the same optimal value and the same optimal $y,s$, with equality at any optimizer.

This algebraic equivalence in fact does not require Slater's condition. Under the stipulated condition, strong duality additionally identifies their attained optimum with the primal optimum. With $Q^{-1/2}s$ as a linear coordinate, the relaxed constraint is $\Vert Q^{-1/2}s{\Vert }_2\le \theta$, so the relaxed formulation is a second-order cone program.