Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / B / 8

With $L(x,y)=f(x)-y^{T}c(x)$, the Karush-Kuhn-Tucker conditions areUnder a suitable constraint qualification, such as the linear independence constraint qualification on active constraint gradients, they are necessary for a local minimum. Smoothness alone is insufficient. The sign convention here corresponds to constraints written as $c_i\ge 0$ and a minus sign in the optimization Lagrangian.

Write the constraint as $c(x)=1-x^{T}x\ge 0$ and its multiplier as $y\ge 0$. The KKT conditions becomeIf $A$ is positive definite, $A+yI$ is positive definite for every $y\ge 0$, so $\boxed{x=0,y=0}$ is the only critical point.

For indefinite $A$, the origin remains a critical point, contrary to an unqualified reading of the question. Every nonzero critical point is an eigenvector with $\boxed{Ax=-yx}$, so its eigenvalue is nonpositive. A negative-eigenvalue vector must lie on the unit sphere, with multiplier equal to the negative of that eigenvalue. A nonzero vector in $\ker A$ may have any norm at most one and has multiplier zero. Positive-eigenvalue directions do not satisfy the multiplier sign condition. These first-order critical points include saddles; the global minimum selects a unit vector in the lowest-eigenvalue eigenspace.

The logarithmic barrier isIts gradient is $2Ax+2\mu x/(1-x^{T}x)$. Thus every nonzero stationary point satisfiesA fixed negative-eigenvalue branch exists for $0<\mu <-{\lambda }_1$. The zero point is stationary for every $\mu$ as well, and it is not an eigenvector; at zero the displayed scalar $-\mu$ need not be an eigenvalue of $A$. Thus the claimed eigenvalue conclusion requires the nonzero-point qualification. This distinction is essential for the following Hessian analysis.

Put $d=1-x^{T}x>0$. Differentiating the barrier gradient givesAt a nonzero stationary point on the branch $Ax={\lambda }_{1}x$, $\mu /d=-{\lambda }_1$. Choose an orthonormal eigenbasis of the symmetric matrix $A$ whose first vector is $x/\Vert x{\Vert }_2$. On each of the remaining eigenvectors the rank-one term vanishes, so the corresponding Hessian eigenvalues areAlong $x$, the first two terms cancel and the remaining eigenvalue isIf ${\lambda }_1$ repeats, a transverse eigenvalue can be zero. If a lower eigenvalue than ${\lambda }_1$ exists, a transverse eigenvalue is negative, identifying this stationary branch as a saddle rather than a minimum.

Along a fixed nonzero branch, $\Vert x(\mu ){\Vert }_2^2=1+\mu /{\lambda }_1\to 1$ and the radial Hessian eigenvalue grows like $4{\lambda }_1^2/\mu$. The nonzero transverse eigenvalues $2({\lambda }_i-{\lambda }_1)$ stay fixed. If ${\lambda }_1$ is simple, the ratio of the largest to smallest absolute eigenvalue therefore tends to infinity. If it repeats, the Hessian is already singular because of the zero transverse directions; there is no finite spectral condition number to begin with. These conclusions concern the nonzero branches: at the stationary origin $H=2(A+\mu I)$, and the same blowup is not implied.

Ill-conditioning does not invalidate barrier minimizers as approximations to the constrained solution. Let ${\lambda }_{\min }<0$. At radius $r$, the smallest possible quadratic value is ${\lambda }_{\min }{r}^2$, so global barrier minimization reduces to minimizing ${\lambda }_{\min }t-\mu \log (1-t)$ for $0\le t<1$. For $0<\mu <-{\lambda }_{\min }$ its unique minimizing radius satisfiesThus every limiting unit vector in that eigenspace solves the original problem, with objective ${\lambda }_{\min }$. For $\mu \ge -{\lambda }_{\min }$ the barrier minimizer is the origin instead. The increasing condition number concerns the numerical difficulty of small-parameter subproblems, which can call for scaling or a primal-dual interior-point method; it does not prevent the mathematical convergence just established. This is the quadratic-ball barrier eigenvalue branch.