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

A feasible point lies in the probability simplex, so $r^{T}x={\sum }_i{x}_i{r}_i$ is a convex combination of the coordinates of $r$. Hence $r^{T}x\le r_{\max }:={\max }_i{r}_i$. Taking a coordinate vector $e_j$ with $r_j=r_{\max }$ attains equality. ThereforeMore generally, all optimal solutions are exactly the probability vectors supported on the maximizing indices: equality requires $x_i(r_{\max }-r_i)=0$ for every $i$. Thus ties give an entire optimal face, while a unique maximizing index gives a unique optimizer.

For fixed $x$, put $z=r-r_0$. The polyhedral uncertainty set is equivalent to $-1\le Pz\le 1$, so the inner problem is the linear programThe variable $z$ is unrestricted in sign. The point $z=0$ is strictly feasible. If the optimum is finite, it is attained, so the infimum is a minimum. The use of an infimum also covers possible unbounded cases permitted by the printed assumptions; strict feasibility alone does not guarantee a finite objective.

Associate nonnegative Lagrange multipliers $\alpha$ with $-Pz-1\le 0$ and $\beta$ with $Pz-1\le 0$. The Lagrangian dual problem is obtained fromIts infimum over unrestricted $z$ is finite exactly when $P^T(\alpha -\beta )=x$. Thus the dual isThe precise finiteness condition is $x\in \mathrm{range}{P}^T$. If $x=P^{T}q$, then $x^{T}z=q^{T}Pz\ge -\Vert q{\Vert }_1$ on the feasible set. The primal is feasible and bounded below, and splitting $q$ into positive and negative parts makes the dual feasible. Linear programming duality therefore gives attained equal finite optima. Equivalently, the strictly feasible point $z=0$ satisfies the Slater condition, with the required finiteness hypothesis. This is strong duality in the usual finite sense.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, there is $d\in \ker P$ with $x^{T}d<0$. Every $z=td$, $t\ge 0$, is feasible and the objective tends to $-\infty$. The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as $-\infty$, but there are no finite optimizers. The paper does not assume full column rank of $P$, so this qualification is necessary. The same calculation gives the support function of an inverse image of an infinity-norm ball, ${\inf }_r{r}^{T}x=r_0^{T}x-{\min }_{P^{T}q=x}\Vert q{\Vert }_1$ for finite decisions.

For every decision with finite worst-case value, the previous dual represents that value as a maximum over $\alpha ,\beta$. Maximizing it jointly with $x$ yields the robust linear optimization over the probability simplex formulation:Indeed every feasible triple gives a dual lower bound on that decision's worst-case revenue, while dual attainment supplies a triple reaching it. This argument only combines two maximizations after dualization; it does not interchange the original max and min.

If the probability simplex intersects $\mathrm{range}{P}^T$, this linear program is feasible and bounded above by ${\max }_i(r_0{)}_i$, and hence attains an optimum. Its maximizing $x$ is a robust optimizer. If the intersection is empty, every decision has worst-case value $-\infty$ and the linear program is infeasible, consistently with the extended-value convention. Full column rank of $P$ ensures every simplex decision has a finite inner optimum, but is not needed for the qualified equivalence.

For a feasible vector, set $X=x{x}^T$. It is a positive semidefinite matrix, andThus every original feasible point supplies an equally valuable SDP feasible point. Dropping the rank-one restriction is the semidefinite relaxation of slab-constrained quadratic maximization, provingThe original PDF has $|a_i^{T}x|\le 1$; the absolute values are missing from the extracted TeX and are essential for this relaxation.

For the subsequent finite rounding argument, the constraint vectors must span ${\mathbb{R}}^n$. Otherwise a nonzero common-kernel vector $d$ makes both $x=td$ and $X=td{d}^T$ unbounded feasible families, so both objective suprema are infinite. Under spanning, $H={\sum }_i{a}_i{a}_i^T$ is a positive-definite matrix andThe first inequality uses positive semidefinite trace nonnegativity. The SDP feasible set is closed and bounded, hence compact, so an optimum exists. Its trace is positive: a sufficiently small positive multiple of the identity is feasible when $n\ge 1$. These facts justify the optimum and nonzero denominator used below. Assume $m,n\ge 1$.

Use the spectral theorem for real symmetric matrices to write $X^{\ast }=V\Lambda V^T$, with $V$ orthogonal and $\Lambda$ diagonal and nonnegative. For any sign vector, ${\xi }_j^2=1$, soThis is an exact identity for every sign choice. Put $M(\xi )={\max }_i|a_i^T\hat{x}(\xi )|$. When $M>0$, the Rademacher rounding for a semidefinite relaxation givesHence $x(\xi )$ is feasible. In the finite spanning case from part (a), $\mathrm{tr}{X}^{\ast }>0$ makes $\hat{x}\ne 0$, and the spanning condition then gives $M>0$. If a nonzero $\hat{x}$ instead had $M=0$, it would be an unbounded feasible direction rather than a vector to divide by zero.

Set $u_i=(V{\Lambda }^{1/2}{)}^T{a}_i$. SDP feasibility impliesChoose $\alpha =\sqrt{2\log (2m)}$. For the uniform sign vector, whose coordinates are independent Rademacher random variables, the supplied bound for the maximum of finitely many Rademacher linear forms givesA positive-probability event in this finite space contains at least one sign vector. ThusThe strict inequality in the supplied probability estimate matters: at the chosen threshold its right-hand side is zero.

For that sign vector, part (b) gives a feasible original point satisfying $\Vert x(\xi ){\Vert }_2^2\ge p_{\mathrm{SDP}}^{\ast }/[2\log (2m)]$. Taking the best original objective proves the unheaded concluding request as well:This is the logarithmic approximation bound for slab-constrained quadratic maximization, obtained by the probabilistic method. It is a finite-value rounding guarantee under the spanning/attainment conditions explained above.

First address the positivity request in part (a), which has no separate Solution heading in the stub. For $x\in [0,1]$, each $x^k(1-x{)}^{n-k}$ and each coefficient $c_k$ is nonnegative. Their sum is therefore nonnegative, including at the endpoints:This is the elementary direction of the positive Bernstein coefficients for a strictly positive polynomial criterion; the converse developed later needs strict positivity.

For completeness, the convergence fact listed as (i) also has a short proof. If $K\sim \mathrm{Bin}(n,x)$, the Bernstein polynomial is $B_n(f)(x)=\mathbb{E}[f(K/n)]$. Its mean argument is $x$ and $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$. Given $ϵ>0$, uniform continuity of $f$ on the compact interval supplies $\delta >0$ such that $|f(s)-f(t)|<ϵ$ whenever $|s-t|\le \delta$. By Chebyshev's inequality, uniformly in $x$,Letting $n\to \infty$ and then $ϵ\downarrow 0$ proves $\boxed{\Vert B_n(f)-f{\Vert }_{\infty }\to 0}$. The two numbered items in the source are assumptions supplied for later parts, not additional exam questions; their stub sections contain these supporting derivations.

Consider $B_n$ on the finite-dimensional vector space $E=\mathbb{R}[x{]}_{\le d}$ and use the monomial basis. For $j\ge 1$, a binomial distribution and the falling factorial moment formula givewhere $S(j,\ell )$ is the Stirling number of the second kind and $(n{)}_{\ell }=n(n-1)\cdots (n-\ell +1)$. This follows by expanding $K^j={\sum }_{\ell }S(j,\ell )(K{)}_{\ell }$ and using $\mathbb{E}(K{)}_{\ell }=(n{)}_{\ell }{x}^{\ell }$. Also $B_n(1)=1$.

Each monomial maps to a polynomial of no larger degree. The resulting matrix is triangular with diagonal entries $1$ and $(n{)}_j/n^j$, $1\le j\le d$. When $n\ge d$ and $n\ge 1$, all entries are positive. ThereforeFor constant polynomials the conclusion is immediate. Taking positive indices avoids the undefined sample expression $k/n$ at $n=0$.

Let $E=\mathbb{R}[x{]}_{\le d}$ with the supremum norm. By equivalence of norms in finite dimensions, there is $C_d$ such that ${\sum }_{j=0}^d|a_j|\le C_d\Vert p{\Vert }_{\infty }$ whenever $p={\sum }_j{a}_j{x}^j$. Henceso ${\epsilon }_n:=\Vert B_n-I{\Vert }_{\mathrm{op}}\le C_d{\max }_{0\le j\le d}\Vert B_n(x^j)-x^j{\Vert }_{\infty }\to 0$. This upgrades convergence on fixed polynomials to operator norm convergence on the fixed space.

For sufficiently large $n$, ${\epsilon }_n<1$, and a Neumann series givesThus the inverse Bernstein approximation on a fixed-degree polynomial space satisfies $\Vert g_n-f{\Vert }_{\infty }\to 0$. By the extreme value theorem, strict positivity on the compact interval gives $\mu ={\min }_{[0,1]}f>0$. Eventually $\Vert g_n-f{\Vert }_{\infty }<\mu /2$, and consequentlyApplying pointwise convergence to the varying polynomials $g_n$ without this finite-dimensional operator argument would not justify the conclusion.

Choose a sufficiently large positive $n$ for which $g_n=B_n^{-1}f>0$ throughout the interval. Expanding $B_n(g_n)=f$ givesTherefore the coefficientssupply the requested representation, in particular with nonnegative coefficients. This proves positive Bernstein coefficients for a strictly positive polynomial. Strict positivity cannot generally be weakened to mere nonnegativity: a nonzero polynomial such as $(x-1/2{)}^2$ vanishes at an interior point, whereas every basis term is positive there, so no nonnegative-coefficient representation could vanish unless every coefficient were zero.

Let $f(x)={\sum }_{j=0}^d{a}_j{x}^j$. For $n\ge \max (1,d)$, express $f$ in the Bernstein basis as $f={\sum }_{k=0}^n{\beta }_{k,n}{b}_{k,n}$, where $b_{k,n}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k(1-x{)}^{n-k}$. Its precomputed coefficients arewith the ratio for $j=0$ interpreted as one. The identity follows from $x^j={\sum }_k[(k{)}_j/(n{)}_j]b_{k,n}$, obtained by the binomial theorem.

At this level solve the linear programThere are exactly $n+1$ inequalities. Equivalently, $f-\lambda$ must have nonnegative coefficients in the unnormalized basis; its coefficients are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)({\beta }_{k,n}-\lambda )$. Since the basis functions are nonnegative and sum to one, every feasible $\lambda$ satisfies $\lambda \le f(x)$ for all $x\in [0,1]$, so $v_n\le f_{\min }$.

Degree elevation of Bernstein coefficients gives, for $1\le k\le n$,with endpoint coefficients unchanged. These convex combinations imply $v_{n+1}\ge v_n$.

To cover every positive index even when $d>1$, put $\ell =a_0-{\sum }_{j=1}^d|a_j|$. For $1\le n<d$, use the one-inequality LP $\max \{\lambda :\lambda \le \ell \}$, giving $v_n=\ell$. This is a lower bound on $f$; moreover the explicit coefficient formula has all its factorial ratios in $[0,1]$, so ${\beta }_{k,d}\ge \ell$. Thus the transition to level $d$ is also monotone and every level respects the requested bound of at most $n+1$ inequalities. Constants are handled by the main formula at all positive indices.

Finally, for every $ϵ>0$, $f-(f_{\min }-ϵ)$ is strictly positive on the interval. Part (c) supplies a nonnegative-coefficient representation at some degree, and degree elevation preserves it at every higher degree. Hence eventually $v_n\ge f_{\min }-ϵ$. Combining with the upper bound proves the Bernstein linear programming hierarchy for polynomial minimization: