Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 339 (Topics in Convex Optimisation)

Each map $x\mapsto ⟨a_i,x⟩+b_i$ is an affine function. For $0\le t\le 1$, the pointwise maximum of convex functions satisfiesso $f$ is convex.

A vector $g$ is a subgradient of a convex function $f$ at $x$ whenfor every $y$. Choose any active index $j\in I(x):=\{i:f(x)=⟨a_i,x⟩+b_i\}$. Thenand hence $\boxed{a_j\in \partial f(x)}$. More generally, every convex combination of the active vectors is a subgradient, and in fact

Put $G={\max }_i\Vert a_i{\Vert }_2$. By the Cauchy-Schwarz inequality,Interchanging $x$ and $y$ proves the Lipschitz bound

The subgradient method chooses $g_k\in \partial f(x_k)$ and a step size $t_k>0$, then setsAssume, as the question's use of $\min f$ requires, that a minimizer $x_{\ast }$ exists, and write $R=\Vert x_0-x_{\ast }{\Vert }_2$. Since every subgradient here has Euclidean norm at most $G$, the standard best-iterate estimate isTaking a suitable constant step when the target accuracy is known, or a standard diminishing sequence, gives error at most $ϵ$ initerations, so the requested exponent is $p=2$.

Write $z_i(x)=⟨a_i,x⟩+b_i$. The log-sum-exp function is convex and composition with the affine functions $z_i$ preserves convexity, so $f_{\beta }$ is convex. Directly, its Hessian matrix will also be shown positive semidefinite in part d.

Let $M=f(x)={\max }_i{z}_i(x)$. Factoring $e^{\beta M}$ out of the sum givesAt least one term in the sum is $1$, while every term is at most $1$. Thereforeand henceThus $f_{\beta }$ is a uniform smooth maximum of the affine pieces of $f$.

Define the softmax weightsThey obey $p_i\ge 0$ and ${\sum }_i{p}_i=1$. The gradient is their weighted mean,Differentiating once more gives the covariance-form Hessian matrixFor every unit vector $u$,where $G={\max }_i\Vert a_i{\Vert }_2$. The Hessian is a covariance matrix, so it is positive semidefinite; the displayed upper bound also gives ${\nabla }^2{f}_{\beta }⪯\beta G^{2}I$ in the Loewner order. Consequently $f_{\beta }$ has a Lipschitz gradient with

Chooseso the smooth maximum error is at most $ϵ/2$ and the Lipschitz gradient constant isSuppose a minimizer of $f_{\beta }$ lies within distance $R$ of the starting point. The Nesterov accelerated gradient method can find $x$ such thatiniterations. If $x_{\ast }$ minimizes $f$, then the smoothing inequalities implyThis improves the nonsmooth subgradient method dependence from $O({ϵ}^{-2})$ to $O({ϵ}^{-1})$.

The first-order subgradient inequality for a differentiable convex function givesand, after interchanging $v$ and $w$,Adding and rearranging yieldsThus the gradient $F=\nabla f$ is a monotone operator.

If $T(w)=w$, the defining equation becomes $M(w)+F(w)=M(w)$, so $\boxed{F(w)=0}$.

A map is firmly nonexpansive in the $M$-inner product whenPut $p=T(v)$ and $q=T(w)$. The two implicit equations giveBecause $F$ is a monotone operator,Thereforewhich is precisely firm nonexpansiveness. In particular, the preconditioned proximal point algorithm map $T=(M+F{)}^{-1}M$ is nonexpansive in the norm induced by the positive-definite matrix $M$.

Use the sign conventionfor the Lagrangian function in constrained optimization. The Lagrangian dual problem iswhere $f^{\ast }$ is the convex conjugate. For this convex problem with affine equality constraints, the stationarity and feasibility parts of the Karush-Kuhn-Tucker conditions areThey say exactly that the displayed operator satisfiesThus its zeros are precisely the primal-dual optimal points, subject to the usual attainment assumptions.

For $u=(x,z)$ and $\tilde{u}=(y,s)$, the Euclidean inner product givesThe last two terms cancel by the defining property of the matrix transpose, and the first is nonnegative by part a. Hence $F$ is a monotone operator.

The assertion uses the positive parameters required for $M$ to be a preconditioner: assume $\alpha >0$ and $\beta >0$. For $x\in {\mathbb{R}}^n$ and $z\in {\mathbb{R}}^m$, complete the square:The matrix 2-norm bound $\Vert Ax{\Vert }_2\le \Vert A{\Vert }_2\Vert x{\Vert }_2$ shows thatfor $x\ne 0$ when $\alpha \beta >\Vert A{\Vert }_2^2$. If $x=0$ and $z\ne 0$, the square contributes $\beta \Vert z{\Vert }_2^2>0$. Thus $\boxed{M\text{ is positive definite}}$. Equivalently, the Schur complement of the lower-right block is $\alpha I-A^{T}A/\beta \succ 0$.

Taken literally without the positivity inherited from part b, the product condition alone is insufficient: $A=0$ and $\alpha =\beta =-1$ is a counterexample. Thus $\alpha ,\beta >0$ is a necessary implicit hypothesis.

Write $w_k=(x_k,z_k)$ and $w_{k+1}=(x_{k+1},z_{k+1})$. ExpandinggivesThe off-diagonal terms in the first equation cancel. By the optimality condition for the proximal operator,The second equation then becomes the explicit linear updateThus each step of this preconditioned proximal point algorithm uses only one evaluation of the proximal operator of ${\alpha }^{-1}f$, together with applications of the linear map $A$ and its transpose $A^T$.