Continuous Optimisation HT26, Overview of results and methods

For the unconstrained problem $\min _ {x \in \mathbb R^n} f(x)$ with $f \in \mathcal C^1$, every local minimiser is stationary:

The converse is false — stationary points also include maximisers and saddles — so this is only a first filter, sharpened by the second-order conditions below (and made sufficient in the convex case).

If $\nabla f(x)^\top s < 0$ then $s$ is a genuine descent direction: $f(x + \alpha s) < f(x)$ for all sufficiently small $\alpha > 0$. This is the workhorse behind every linesearch method and the contradiction step of the optimality proofs.

If $x^\ast$ is a local minimiser of $f \in \mathcal C^2$ then, in addition to stationarity, the Hessian is positive semidefinite:

PSD (not PD) is the most we can conclude — e.g. $f(x)=x^3$ at $0$ satisfies it vacuously yet has no minimiser.

If $\nabla f(x^\ast) = 0$ and $\nabla^2 f(x^\ast) \succ 0$ then $x^\ast$ is a strict local minimiser. The PD requirement is sufficient but not necessary ($f(x)=x^4$ at $0$ is a strict minimiser with $f''(0)=0$).

For $q(x) = g^\top x + \tfrac12 x^\top H x$ with $H$ symmetric, $\nabla q = Hx + g$ and $\nabla^2 q = H$, so stationary points solve the linear system $Hx + g = 0$. When $H$ is nonsingular the unique stationary point is $x^\ast = -H^{-1}g$, classified by the definiteness of $H$ (PD $\to$ min, ND $\to$ max, indefinite $\to$ saddle). This is the prototype for local behaviour near any critical point, since $f$ is locally quadratic there.

A function $f$ on a convex domain is convex if the chord lies on or above the graph; for $f \in \mathcal C^1$ this is equivalent to the tangent lying on or below the graph, and for $f \in \mathcal C^2$ to $\nabla^2 f(x) \succeq 0$ everywhere:

Convexity collapses the optimality hierarchy: every stationary point and every local minimiser is automatically a global minimiser.

At a constrained minimiser of $\min f(x)$ s.t. $c _ E(x)=0,\ c _ I(x)\ge 0$, the KKT system (stationarity of the Lagrangian, primal/dual feasibility, complementary slackness) holds provided a constraint qualification makes the linearised feasible directions $\mathcal F(x^\ast)$ coincide with the tangent cone $T _ \Omega(x^\ast)$. The course proves only the equality-only case (the general inequality case via Farkas is non-carded and a pending to-do).

If every constraint is affine, $c(x) = Ax - b$, then a local minimiser is a KKT point with no constraint qualification required — affineness makes the first-order linearisation of the constraints exact, so the CQ is automatic.

For a convex program ($f$ convex, each $c _ i$ ($i\in I$) concave, $c _ E$ affine) the feasible set $\Omega$ is convex and any KKT point is a global minimiser — for convex problems the first-order KKT conditions are both necessary and sufficient.

At a constrained local minimiser that is a KKT point with multipliers $(y^\ast,\lambda^\ast)$, the Lagrangian Hessian is PSD on the critical cone:

It is the Lagrangian Hessian, not $\nabla^2 f$, because curvature of the constraints matters (the two-circles example: same linear $f$, min vs max distinguished only by $\nabla^2 _ {xx}\mathcal L$). The full proof is non-examinable (Lecture 11 handout).

If $(x^\ast,y^\ast,\lambda^\ast)$ satisfies KKT and $s^\top \nabla^2 _ {xx}\mathcal L\, s > 0$ for every nonzero $s$ in the critical cone, then $x^\ast$ is a constrained local minimiser. This is the constrained analogue of the unconstrained PD-Hessian sufficient condition.

A QP is $\min c^\top x + \tfrac12 x^\top H x$ s.t. $Ax = b,\ \tilde A x \ge \tilde b$; it is convex iff $H \succeq 0$, and its KKT system is linear-plus-complementarity. For a strictly convex QP with only inequality constraints the primal and dual optimal values coincide (strong duality).

If $\nabla f$ is $L$-Lipschitz and $s^k$ is a descent direction, the Armijo condition holds for every step in an explicit interval:

This explicit interval is what makes the backtracking stepsize bound (Lemma 3) and hence global convergence quantitative.

The bArmijo linesearch terminates in finitely many steps and the accepted stepsize is bounded below:

A short or absent lower bound here would break the telescoping global-convergence argument.

With $f \in \mathcal C^1$ bounded below, $\nabla f$ Lipschitz, and descent directions $s^k$, the bArmijo GLM satisfies: either $\nabla f(x^l)=0$ for some $l$, or

The $\min$ form is exactly why $s^k$ must stay bounded away from orthogonality to $-\nabla f$ (the $\cos\theta _ k \ge \delta$ requirement) for genuine $\ \vert \nabla f\ \vert \to 0$.

Steepest descent ($s^k=-\nabla f(x^k)$) with (b)Armijo and the Theorem 4 hypotheses gives $\nabla f(x^l)=0$ for some $l$ or $\ \vert \nabla f(x^k)\ \vert \to 0$. It is a one-line corollary of Theorem 4 with $\cos\theta _ k\equiv 1$.

Near a PD-Hessian minimiser, SD converges only linearly, with rate governed by the Hessian conditioning:

Ill-conditioning ($\kappa \gg 1$) pushes $\rho _ {\mathrm{SD}} \to 1$ (Rosenbrock: $\kappa\approx 258$, $\rho _ {\mathrm{SD}}\approx 0.992$), the core weakness of SD.

With $\nabla^2 f(x^\ast)$ nonsingular, $\nabla^2 f$ locally Lipschitz, and $x^{k _ 0}$ close enough to $x^\ast$, pure Newton is well-defined and converges quadratically:

The “close enough” neighbourhood depends on unknown problem constants, which is why pure Newton is wrapped in a globalisation in practice.

With $\beta < \tfrac12$ and $\alpha _ {(0)}=1$, backtracking-Armijo eventually accepts $\alpha^k=1$, so globalised Newton recovers the pure-Newton quadratic rate near $x^\ast$. The mechanism is the “half-decrease” identity $f(x^k+s^k)=f(x^k)+\tfrac12\nabla f(x^k)^\top s^k+o(\ \vert s^k\ \vert ^2)$.

If the Hessian eigenvalues at the iterates are positive and uniformly bounded below away from zero, then bArmijo-Newton gives $\nabla f(x^l)=0$ for some $l$ or $\ \vert \nabla f(x^k)\ \vert \to 0$. (Strong convexity is a clean sufficient set of hypotheses.) Positivity makes the Newton step descent; the uniform lower bound controls $\ \vert s^k\ \vert $.

The Theorem 9 conclusion holds for any $s^k$ solving $B^k s^k = -\nabla f(x^k)$ when the eigenvalues of $B^k$ are uniformly bounded above and below away from zero (so the proof is structurally identical with $B^k$ in place of $\nabla^2 f$). This is the umbrella result covering quasi-Newton and modified-Newton globalisation.

Newton’s iterates commute with any nonsingular linear change of variables $y=Ax$: $s _ y = A s _ x$, hence $y+\alpha s _ y = A(x+\alpha s _ x)$. This is the structural reason Newton is immune to the conditioning problems that cripple steepest descent.

When $\nabla^2 f(x^k)$ is not PD the Newton direction need not be descent; solve $(\nabla^2 f(x^k)+M^k)s^k=-\nabla f(x^k)$ with $M^k$ chosen to make the matrix sufficiently PD (zero when already PD). Three standard recipes: spectral, smallest-eigenvalue shift, modified Cholesky.

BFGS preserves positive-definiteness under the curvature condition $(\delta^k)^\top\gamma^k>0$ (enforced by Wolfe, not by Armijo alone), converges Q-superlinearly locally, and terminates in $n$ steps on a strictly convex quadratic with exact linesearch. SR1 is rank-1 and does not preserve PD.

For $\min \tfrac12\ \vert r(x)\ \vert ^2$, Gauss-Newton uses $\widetilde{\nabla^2}f=J^\top J$. It converges globally under a uniformly full-rank Jacobian and Lipschitz $\nabla f$ (to a stationary point of $f$, not necessarily $r=0$); locally it is quadratic in the zero-residual case (reduces to Theorem 7) and only linear in the nonzero-residual case (rate $ \vert \lambda \vert $, $\lambda$ the top eigenvalue of $(J^\top J)^{-1}\sum _ j r _ j\nabla^2 r _ j$).

With $f \in \mathcal C^2$ bounded below, $\nabla f$ Lipschitz, and the Cauchy-decrease condition, the generic trust-region method gives $\nabla f(x^k)=0$ for some $k$ or $\liminf _ {k\to\infty}\ \vert \nabla f(x^k)\ \vert =0$ (only $\liminf$, not $\lim$). It rests on the Cauchy model-decrease lemma (Lemma 12) and the trust-region radius lower bound (Lemma 13).

The Theorem 14 conclusion still holds with an arbitrary symmetric model Hessian $B^k$ provided $\ \vert B^k\ \vert \le \kappa _ B$; the convergence constants merely weaken to $c/(L+\kappa _ B)$ (Sheet 3 Q B.4).

$s^\ast$ solves $\min _ {\ \vert s\ \vert \le\Delta} g^\top s+\tfrac12 s^\top H s$ iff there is $\lambda^\ast \ge 0$ with

and the solution is unique when $H+\lambda^\ast I \succ 0$. The secular equation $1/\ \vert s(\lambda)\ \vert - 1/\Delta = 0$ turns this into a 1-D rootfind; the hard case is when $g \perp$ the $\lambda _ {\min}$-eigenspace.

For $\min f(x)$ s.t. $c(x)=0$ solved via $\Phi _ \sigma=f+\tfrac{1}{2\sigma}\ \vert c\ \vert ^2$ with $\sigma^k\to 0$ and approximate stationarity, if $x^k\to x^\ast$ with $\{\nabla c _ i(x^\ast)\}$ linearly independent (LICQ) then $x^\ast$ is a KKT point and the estimates $y^k=-c(x^k)/\sigma^k \to y^\ast$. LICQ is what makes the pseudo-inverse $J^+=(JJ^\top)^{-1}J$ well-defined; without $\sigma^k\to 0$ the limit need not be feasible.

For $\Phi=f-u^\top c+\tfrac{1}{2\sigma}\ \vert c\ \vert ^2$ with multiplier estimate $y^k=u^k-c(x^k)/\sigma^k$, under LICQ the multipliers converge and Lagrangian stationarity holds; the limit is a KKT point if either $\sigma^k\to 0$ (bounded $u^k$) or $u^k\to y^\ast$ (bounded $\sigma^k$). The second case is the distinctive advantage: KKT without driving $\sigma\to 0$, so the Hessian stays well-conditioned.

For $\min f(x)$ s.t. $c(x)\ge 0$, under strict complementarity, LICQ, and a second-order sufficient condition at $x^\ast$, there is a unique $\mathcal C^1$ central path $\mu\mapsto x(\mu)$ of barrier minimisers for small $\mu>0$, with $x(\mu)\to x^\ast$ as $\mu\to 0$. (Nonconvex problems can have one central path per local minimiser.)

Under LICQ, with $\mu^k\to 0$ and approximate stationarity of $f _ {\mu^k}$, the barrier iterates converge to a KKT point of (iCP) and the estimates $\lambda^k=\mu^k/c(x^k)\to\lambda^\ast$. The proof splits active/inactive indices: inactive multipliers vanish, active ones converge via the active-Jacobian pseudo-inverse.

Auxiliary theorems repeatedly used inside the convergence proofs above.

Iterate $x^{k+1}=x^k+\alpha^k s^k$ with a descent direction $s^k$ and a stepsize rule for $\alpha^k$. The rule must keep $\alpha^k$ neither too long (Armijo) nor too short (Wolfe / Goldstein curvature side); convergence is Theorem 4, resting on Lemmas 2-3.

GLM with $s^k=-\nabla f(x^k)$ — the direction that most decreases the linear model on a fixed-norm sphere. Globally convergent (Theorem 5) but only linearly local (Theorem 6), and scale-dependent.

GLM with $s^k$ solving $\nabla^2 f(x^k)s^k=-\nabla f(x^k)$ — minimiser of the second-order model. Quadratic local rate (Theorem 7), unit step under bArmijo (Theorem 8), global under bounded PD Hessian (Theorem 9), scale invariant; globalised by linesearch or trust region.

GLM with $s^k=-(B^k)^{-1}\nabla f(x^k)$ where $B^k$ approximates the Hessian via the secant equation $\gamma^k=B^{k+1}\delta^k$, updated cheaply ($O(n^2)$ via Sherman-Morrison-Woodbury). BFGS is the rank-2 PD-preserving update; SR1 is rank-1 and may be indefinite.

For $\min\tfrac12\ \vert r(x)\ \vert ^2$, approximate $\nabla^2 f\approx J^\top J$ and solve a linear least-squares subproblem $\min _ s\tfrac12\ \vert J(x^k)s+r(x^k)\ \vert ^2$ each step.

Minimise a local quadratic model inside $\ \vert s\ \vert \le\Delta _ k$; accept/reject by the actual-to-predicted ratio $\rho _ k$, adjusting $\Delta _ k$. Globally convergent (Theorem 14) via the Cauchy point; subproblem solved by the secular equation.

Minimise $\Phi _ \sigma=f+\tfrac{1}{2\sigma}\ \vert c\ \vert ^2$ for a decreasing $\sigma^k\to 0$. Converges to a KKT point under LICQ (Theorem 21) but the Hessian is $O(1/\sigma)$ ill-conditioned; an auxiliary-variable Newton system computes the step cleanly.

Minimise $\Phi=f-u^\top c+\tfrac{1}{2\sigma}\ \vert c\ \vert ^2$, updating the multiplier estimate $u$ and penalty $\sigma$. Converges to a KKT point (Theorem 22) and — unlike the pure penalty — can do so with $\sigma$ bounded, limiting ill-conditioning.

Replace $c(x)\ge 0$ by the log barrier $f _ \mu=f-\mu\sum\log c _ i$ and follow the central path as $\mu\to 0$ (Theorems 27-28). The basic primal method is ill-conditioned and has poor warm-starts; primal-dual methods fix this by making the multipliers explicit Newton variables (perturbed KKT $c _ i\lambda _ i=\mu$). For LP, IPMs are polynomial-time vs simplex’s exponential worst case.