Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 (C12.1, DMAC 2488, DMSU 2488)

Original solutions to all six questions and all thirteen printed terminal parts of the Numerical Linear Algebra and Continuous Optimisation paper sat on 9 June 2009. Source: released Mathematics papers, Part C 2007 11.pdf.

A real square orthogonal matrix satisfies $Q^{T}Q=Q{Q}^T=I$, so it preserves the Euclidean norm. The columns of $Z_h$ are orthonormal, hence $\Vert Z_{h}v{\Vert }_2=\Vert v{\Vert }_2$. The induced matrix norm therefore givesFor the left truncation, $\Vert Q_{\ell }^{T}A{\Vert }_2\le \Vert A{\Vert }_2$, and equality is guaranteed for arbitrary $A$ only when $\boxed{\ell =m}$. Indeed, if $\ell <m$, take $A=q_{\ell +1}{e}_1^T$, where $q_{\ell +1}$ is an omitted column of $Q$. Then $\Vert A{\Vert }_2=1$ but $Q_{\ell }^{T}A=0$. Merely taking $\ell \ge n$ does not guarantee preservation for an arbitrary $A$.

A full QR decomposition of a real $m\times n$ matrix is $A=QR$, with $Q$ orthogonal and $R$ upper trapezoidal; for a square matrix, $R$ is upper triangular. Fix the following sign convention for a Givens rotation: it is the identity except for its $(i,k)$ blockThe block transpose times the block is $I_2$ because $c^2+s^2=1$, proving orthogonality. Writing $r=\sqrt{x_i^2+x_k^2}$, the choice $\boxed{c=x_i/r,s=x_k/r}$ gives $(Jx{)}_k=0$ and $(Jx{)}_i=r$. To zero the other coordinate take $\boxed{c=x_k/r,s=-x_i/r}$, giving $(Jx{)}_i=0$. If $r=0$, both entries are already zero and the identity suffices.

For a tridiagonal matrix, successively rotate adjacent row pairs $(1,2),(2,3),\dots ,(n-1,n)$, each time zeroing the current entry $(k+1,k)$. Earlier columns remain triangular because both affected rows are already zero there. The result $R=J_{n-1}\cdots J_{1}A$ is upper triangular, so $Q=J_1^T\cdots J_{n-1}^T$ gives its QR decomposition. Only $n-1$ rotations are required; the resulting $R$ has at most two superdiagonals.

For a full square matrix, process columns $j=1,\dots ,n-1$. Within column $j$, for $i=n,n-1,\dots ,j+1$, rotate rows $(i-1,i)$ to eliminate the current $(i,j)$ entry. Previously cleared columns stay clear. With $J_1,\dots ,J_s$ in application order, $s=n(n-1)/2$, one has $\boxed{R=J_s\cdots J_{1}A,Q=J_1^T\cdots J_s^T}$. This is QR decomposition by Givens rotations.

The Gauss-Seidel method updates coordinates successively using the newest available entries:It is well-defined for every initial vector exactly when every $a_{ii}\ne 0$, equivalently when the triangular matrix $D+L$ is invertible. Nonsingularity of $A$ alone does not ensure this. The matrix form isIf the iterates converge to $z$, passing to the limit gives $(D+L)z=b-Uz$, hence $Az=b$. Nonsingularity identifies $z$ as the unique solution $x$.

Now assume $A$ is a symmetric positive-definite matrix. Testing with the coordinate vector gives $a_{ii}=e_i^{T}A{e}_i>0$, so $D$ is positive definite. The form $⟨v,w{⟩}_A=v^{T}Aw$ is an inner product: bilinearity and symmetry are immediate and positivity is the hypothesis. Its Cauchy-Schwarz inequality givesproving the triangle inequality; definiteness and absolute homogeneity are immediate. Thus $\Vert v{\Vert }_A=\sqrt{v^{T}Av}$ is the energy norm.

Subtract the iteration from the exact equation to obtain $(D+L)e_{k+1}=-L^T{e}_k$. HenceUsing the preceding iteration also gives $(D+L)e_k=-L^T{e}_{k-1}$ and therefore $A{e}_k=L^T(e_k-e_{k-1})$ for $k\ge 1$, as required.

Put $d=e_k-e_{k+1}$. Expanding the two quadratic forms and using the first identity gives the exact Gauss-Seidel energy decrease identity:Here $2d^{T}Ld=d^T(L+L^T)d$. If $d=0$, then $A{e}_k=0$, so $e_k=0$. Otherwise $d^{T}Dd>0$. Thus $\boxed{\Vert e_k{\Vert }_A>\Vert e_{k+1}{\Vert }_A}$ unless the exact solution has already been reached.

The Krylov subspace is $\boxed{K_k(A,r)=\mathrm{span}\{r,Ar,\dots ,A^{k-1}r\}}$. If $y-z=q(A)r$ for a polynomial $q$ of degree at most $k-1$, thenso $\mathrm{deg}p\le k$ and $p(0)=1$. Conversely, this residual identity impliesThus the converse holds whenever $A$ is invertible. More precisely, for fixed $A,r,k$ it holds for every such $y$ exactly when $\ker A\subseteq K_k(A,r)$: the identity determines $y-z$ only up to an arbitrary nullspace vector. Without this qualification the singular-matrix converse is false, for example when $A=0$, $r=e_1$ and $y-z=e_2$.

Assume $r\ne 0$ and exact arithmetic for the Lanczos algorithm. At step $j$ putprovided $w\ne 0$. The initial coefficient of $v_0=0$ is immaterial. Inductively suppose $v_1,\dots ,v_j$ are orthonormal. Then $v_j^{T}w=0$ by the choice of ${\delta }_j$. For $j>1$, symmetry and the preceding recurrence give $v_{j-1}^{T}A{v}_j={\gamma }_j$, so $v_{j-1}^{T}w=0$. If $i\le j-2$, the recurrence gives $A{v}_i\in \mathrm{span}(v_1,\dots ,v_{i+1})$, and therefore $v_i^{T}A{v}_j=(A{v}_i{)}^T{v}_j=0$. Hence $w$ is perpendicular to every preceding basis vector. Its normalization supplies the next orthonormal vector.

Every new $v_{j+1}$ belongs to $K_{j+1}(A,r)$. The $j+1$ orthonormal vectors are independent, whereas that Krylov subspace has dimension at most $j+1$; they therefore form its basis. Continuing the recurrence one more step givesIn particular $T_k=V_k^{T}A{V}_k$. If the next residual is zero, the last term is zero and the span is an invariant subspace; no undefined normalized vector is needed. If $v_1$ is an eigenvector, $A{v}_1={\delta }_1{v}_1$, so ${\gamma }_2=0$ immediately. The algorithm terminates with the exact one-dimensional invariant subspace, rather than generating further vectors. If $r=0$, the initial residual has already vanished and the normalization defining $v_1$ is unnecessary.

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.