Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 / B / 6

The contingent tangent cone consists of feasible first-order velocities:If $x_{\ast }$ is a local minimizer, then $\boxed{\nabla f(x_{\ast }{)}^{T}d\ge 0\text{ for every }d\in T_{\Omega }(x_{\ast })}$. Indeed, $x_n\to x_{\ast }$ along the defining sequence, so eventually $f(x_n)-f(x_{\ast })\ge 0$. Differentiability givesThis proves the inequality. Using feasible limiting velocities avoids assuming that every tangent direction is realized by a straight segment staying in the feasible set.

The active constraint set is $\boxed{\mathcal{A}(x)=\{j:c_j(x)=0\}}$, and the linearized tangent cone isDifferentiating each active feasibility inequality along a tangent sequence gives $T_{\Omega }(x)\subseteq F(x)$. A sufficient condition for equality is the linear independence constraint qualification: the active constraint gradients are linearly independent. The weaker Mangasarian–Fromovitz constraint qualification also suffices in this inequality-only setting.

Under the stated independence condition, the necessary first-order conditions become the Karush-Kuhn-Tucker conditions: there are multipliers ${\lambda }_j$ withUse the allowed span assertion to write $\nabla f(x_{\ast })={\sum }_{j\in \mathcal{A}}{\lambda }_j\nabla c_j(x_{\ast })$. Independence gives vectors ${\phi }_i$ with $\nabla c_j(x_{\ast }{)}^T{\phi }_i={\delta }_{ji}$ for the active indices. Each ${\phi }_i$ lies in $F=T_{\Omega }$, so part (a) gives ${\lambda }_i=\nabla f(x_{\ast }{)}^T{\phi }_i\ge 0$. Assign zero multipliers to inactive constraints. This proves all displayed conditions, including complementarity. Conversely, their stationarity and sign conditions imply $\nabla f(x_{\ast }{)}^{T}d={\sum }_{j\in \mathcal{A}}{\lambda }_j\nabla c_j(x_{\ast }{)}^{T}d\ge 0$ for every $d\in F$. Thus they reformulate the first-order inequality; they do not alone prove a minimum for a nonconvex problem.

On the strictly feasible set ${\Omega }_c^{\circ }=\{x:c_j(x)>0\text{ for all }j\}$, use the logarithmic barrierChoose a strictly feasible starting point and parameters ${\mu }_n\downarrow 0$. For each parameter minimize the barrier functional by an unconstrained method confined to ${\Omega }_c^{\circ }$, warm-starting from the preceding point. In the exact version take a stationary point $x_n$ of the barrier subproblem. The stationarity equation isThese are the natural Lagrange multiplier estimates; the basic method need not perform a separate primal-dual correction.

The barrier method KKT convergence theorem is a global stationarity result: if the exact barrier stationary points form a bounded sequence, then every cluster point satisfying the linear independence constraint qualification is a KKT point. To prove it, take any subsequence $x_n\to x_{\ast }$. Continuity gives feasibility of $x_{\ast }$. For an inactive index, $c_j(x_{\ast })>0$ and therefore ${\lambda }_{n,j}={\mu }_n/c_j(x_n)\to 0$.

The active gradients at $x_{\ast }$ are independent. The supplied dual-basis result gives bounded vectors ${\phi }_{n,i}$, converging as $n\to \infty$, with $\nabla c_j(x_n{)}^T{\phi }_{n,i}={\delta }_{ji}$ for active $i,j$. Pair stationarity with these vectors:Thus all active multipliers are bounded as well. Extract a convergent multiplier subsequence. Its limit is nonnegative, satisfies stationarity by continuity, and satisfies complementarity because ${\lambda }_{n,j}{c}_j(x_n)={\mu }_n\to 0$. This proves the claimed KKT conclusion. The same proof permits approximate barrier stationary points whose stationarity residual tends to zero. Bounded iterates and the constraint qualification are substantive hypotheses, not automatic consequences of writing a barrier functional.

For a global-minimum conclusion one needs global minimization of the barrier subproblems and appropriate access to every feasible point. Specifically, suppose $x_n$ globally minimizes ${\Phi }_{{\mu }_n}$, has a cluster point $x_{\ast }$, and $\overline{{\Omega }_c^{\circ }}=\Omega$. For any fixed strictly feasible $z$,Along the convergent subsequence the $c_j(x_n)$ are bounded above, so taking the upper limit gives $f(x_{\ast })\le f(z)$. Density of strictly feasible points and continuity of $f$ extend the inequality to every feasible $z$. Hence $x_{\ast }$ is a global minimizer under these stronger hypotheses.