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

A descent direction $s$ satisfies $g^{T}s<0$, where $g=\nabla f(x)$; the first-order Taylor expansion then gives $f(x+\alpha s)<f(x)$ for sufficiently small $\alpha >0$. To compare directions one must fix their scale. Among Euclidean unit vectors, the Cauchy-Schwarz inequality givesThis is the unit steepest descent direction. The conventional unnormalized direction used in the algorithm is the same ray, $\boxed{s=-g}$. Equivalently it is the unique minimizer of $g^{T}s+\frac{1}{2}\Vert s{\Vert }_2^2=\frac{1}{2}\Vert s+g{\Vert }_2^2-\frac{1}{2}\Vert g{\Vert }_2^2$. If $g=0$ there is no strict first-order descent direction, and the conventional update is zero.

A line search chooses a positive step size giving useful decrease along the chosen direction. Fix $\sigma ,\beta \in (0,1)$ and a trial step $\bar{\alpha }>0$. The Armijo condition isThe backtracking line search tests $\bar{\alpha },\beta \bar{\alpha },{\beta }^2\bar{\alpha },\dots$ and takes the first accepted value. A Lipschitz gradient has $\Vert \nabla f(y)-\nabla f(x){\Vert }_2\le L\Vert y-x{\Vert }_2$ with a constant $L$ independent of $x,y$.

Integrating the gradient along a segment gives the descent lemmaFor $s=-g$, every $0<\alpha \le \tau =2(1-\sigma )/L$ satisfies the Armijo condition. Thus backtracking terminates. If the trial step is accepted, $\alpha =\bar{\alpha }$; otherwise the immediately preceding step $\alpha /\beta$ failed, so it exceeded $\tau$. ConsequentlyThe same global Lipschitz constant and fixed search parameters make $c$ independent of $x$. If $g=0$, the zero direction passes the first test. If $L=0$, the gradient is constant and the first test passes, so take $c=\bar{\alpha }$.

Choose $x_0$, fixed $\bar{\alpha }>0$, $\sigma ,\beta \in (0,1)$, and repeat for every $n\ge 0$: compute $g_n=\nabla f(x_n)$, choose ${\alpha }_n$ by the backtracking line search in part (b) with $s_n=-g_n$, and set $x_{n+1}=x_n-{\alpha }_n{g}_n$. At a stationary point keep the sequence constant.

Assume $f\in C^1$ has a globally Lipschitz gradient and is bounded below on its initial sublevel set $\{x:f(x)\le f(x_0)\}$. Then the steepest descent method satisfies $\boxed{\nabla f(x_n)\to 0}$. Indeed, the Armijo condition and the uniform lower step bound giveThe objective values decrease and stay in the stated sublevel set. Summing the inequality and using its lower bound $f_{\inf }$ yieldswhich proves the limit. Every cluster point is a stationary point by continuity of the gradient. If the initial sublevel set is compact, cluster points exist. This global convergence result guarantees stationarity from arbitrary initial points under these assumptions; it does not, for a general nonconvex objective, guarantee convergence of the whole iterate sequence or a global minimum.

For any vectors $a,b$,Thus, among directions with $\Vert d{\Vert }_{\infty }\le 1$, $g^{T}d\ge -\Vert g{\Vert }_1$. Equality is achieved byFor $g\ne 0$ these minimizing directions have infinity norm one. The strongest decrease per unit infinity-norm step is $-\Vert g{\Vert }_1$, illustrating the dual norm pairing between the infinity norm and the one-norm.

To match the unnormalized convention in part (a), minimize $g^{T}s+\frac{1}{2}\Vert s{\Vert }_{\infty }^2$. At fixed $t=\Vert s{\Vert }_{\infty }$, its minimum is $-t\Vert g{\Vert }_1+\frac{1}{2}{t}^2$, attained at $t=\Vert g{\Vert }_1$. One conventional choice is therefore $\boxed{s=-\Vert g{\Vert }_1\mathrm{sgn}(g)}$, with zero entries where $g_j=0$. Its ray agrees with the unit direction just computed.

A local minimizer of a differentiable function on ${\mathbb{R}}^N$ necessarily satisfies $\boxed{\nabla f(x_{\ast })=0}$. A sufficient condition for a strict local minimum is $\boxed{\nabla f(x_{\ast })=0,{\nabla }^{2}f(x_{\ast })\text{ positive definite}}$. Indeed, the second-order Taylor expansion has a strictly positive quadratic term that dominates its $o(\Vert x-x_{\ast }{\Vert }^2)$ remainder near $x_{\ast }$.

For Newton's method, solve $H_n{s}_n=-g_n$ with $H_n={\nabla }^{2}f(x_n)$, $g_n=\nabla f(x_n)$, and set $x_{n+1}=x_n+s_n$. A positive-definite Hessian makes this a descent direction; general Hessians may need modification or a separate line search for a globally useful method.

The sequence is q-quadratically convergent if there is $C<\infty$ such that $\Vert x_{n+1}-x_{\ast }\Vert \le C\Vert x_n-x_{\ast }{\Vert }^2$ eventually. Sufficient local hypotheses are $\nabla f(x_{\ast })=0$, a nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, a Lipschitz continuous Hessian near $x_{\ast }$, and $x_0$ sufficiently close. For convergence to a local minimum take $H_{\ast }$ positive definite. Near $x_{\ast }$, inverse Hessians are uniformly bounded, and integration along the error segment givesA Hessian Lipschitz constant $L_H$ yields $\Vert x_{n+1}-x_{\ast }\Vert \le \frac{1}{2}{L}_H\Vert H_n^{-1}\Vert \Vert x_n-x_{\ast }{\Vert }^2$. Choosing a sufficiently small invariant neighborhood proves quadratic convergence. Continuous second derivatives alone do not guarantee this quadratic rate; the Lipschitz hypothesis supplies the needed remainder bound.

A quasi-Newton method replaces the Hessian in the Newton system by an efficiently updated approximation $B_n$:The matrices must be nonsingular for the step to exist. Symmetry reflects the true Hessian, and positive definiteness makes every nonzero step a descent direction, since $\nabla f(x_n{)}^T{s}_n=-s_n^T{B}_n{s}_n<0$. Secant updates often enforce the Quasi-Newton secant equation $B_{n+1}{s}_n=\nabla f(x_{n+1})-\nabla f(x_n)$.

Q-superlinear convergence means $\Vert x_{n+1}-x_{\ast }\Vert /\Vert x_n-x_{\ast }\Vert \to 0$, unless the sequence terminates exactly. A sufficient Dennis-Moré condition isassuming $x_n\to x_{\ast }$, $\nabla f(x_{\ast })=0$, continuous Hessian near $x_{\ast }$ and nonsingular $H_{\ast }$. Only accuracy on the actual step direction is required; full matrix convergence $B_n\to H_{\ast }$ is sufficient but stronger.

To prove the assertion, continuity of the Hessian along the short segment from $x_n$ to $x_{n+1}$ givesNonsingularity of $H_{\ast }$ and $\nabla f(x_{\ast }+e)=H_{\ast }e+o(\Vert e\Vert )$ give a constant $C$ with $\Vert e\Vert \le C\Vert \nabla f(x_{\ast }+e)\Vert$ near zero. Writing $e_n=x_n-x_{\ast }$, we obtainThus $\Vert e_{n+1}\Vert /\Vert e_n\Vert \le {\epsilon }_n/(1-{\epsilon }_n)\to 0$. This proves sufficiency. It is a local rate result for an already convergent sequence, not a claim that arbitrary unmodified quasi-Newton iterations converge from every starting point.

Put $J(x)=DR(x)$, with one residual gradient per row. The chain rule givesDifferentiating each product givesThe approximation $B_n=J(x_n{)}^{T}J(x_n)$ defines the Gauss-Newton method. It is symmetric, and full column rank gives $v^T{B}_{n}v=\Vert J(x_n)v{\Vert }_2^2>0$ for $v\ne 0$, so the step is well-defined.

If $x_n\to x_{\ast }$, $R(x_{\ast })=0$ and $J(x_{\ast })$ has full column rank, then $\nabla f(x_{\ast })=0$ and $H_{\ast }={\nabla }^{2}f(x_{\ast })=J(x_{\ast }{)}^{T}J(x_{\ast })$ is positive definite. Continuity of $J$ gives $B_n\to H_{\ast }$. ThereforeThe Dennis-Moré condition applies, proving $\boxed{x_n\to x_{\ast }\text{ q-superlinearly}}$, or finite termination. The zero-residual hypothesis is what makes the discarded second-derivative term vanish at the limit.

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.