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

For a vector in the nonnegative orthant, the PDF's matrix gives the quadratic formThus it is a copositive matrix. On the other hand, with $u=(1,-1{)}^T$,so it is not a positive semidefinite matrix. Equivalently, the eigenvalues are $3$ and $-1$, with eigenvectors $(1,1{)}^T$ and $(1,-1{)}^T$.

The local TeX has corrupted the matrix entries. The PDF has diagonal entries one and off-diagonal entries two. The all-twos matrix in the TeX would instead have quadratic form $2(x_1+x_2{)}^2$ and would be a positive semidefinite matrix; it cannot demonstrate the requested distinction.

For $x$ in the nonnegative orthant, the positive semidefinite matrix $P$ satisfies $x^{T}Px\ge 0$. The nonnegative matrix $N$ satisfiessince every summand is nonnegative. Adding these inequalities provesConsequently $A=P+N$ is a copositive matrix. The symmetry of $N$ follows from that of $A$ and $P$; entrywise nonnegativity alone need not imply positive semidefiniteness.

This gives the inclusion of the positive-semidefinite-plus-nonnegative cone in the copositive cone. It is only a sufficient construction; the argument does not claim that every copositive matrix has this decomposition in arbitrary dimension.

For each fixed $x$ in the nonnegative orthant, the map $A\mapsto x^{T}Ax$ is a continuous linear function on the vector space of real symmetric matrices. Thusis an intersection of closed half-spaces, using the Frobenius inner product $⟨A,B{⟩}_F=\mathrm{tr}(AB)$ on this space. Arbitrary intersections of closed sets are closed, so $K$ is closed.

If $A,B\in K$ and $s,t\ge 0$, then $x^T(sA+tB)x=s{x}^{T}Ax+t{x}^{T}Bx\ge 0$ for every $x\ge 0$. Therefore $sA+tB\in K$, including the zero matrix when $s=t=0$. HenceThe copositive cone is defined in the real space of symmetric matrices; symmetry is needed later to recover every matrix entry from these quadratic forms.

A pointed cone has no nonzero line through the origin: equivalently $K\cap (-K)=\{0\}$. If $A\in K\cap (-K)$, its quadratic form vanishes on the nonnegative orthant. Testing the coordinate vectors gives $A_{ii}=0$. Testing $e_i+e_j$ then givesSince $A$ is a symmetric matrix, every entry is zero. Thus $\boxed{K\cap (-K)=\{0\}}$.

The identity matrix gives an interior point. For a symmetric perturbation $E$ with operator norm $\Vert E{\Vert }_2<1$, the Cauchy-Schwarz inequality givesThis open norm ball around $I$ lies even in the positive semidefinite cone, hence in $K$. Consequently $\boxed{I\in \mathrm{int}K}$ and the interior is nonempty.

More generally, the interior of the copositive cone consists exactly of strictly copositive matrices. Positivity on the compact nonnegative unit sphere has a positive minimum and persists under small perturbations; a zero there is destroyed by an arbitrarily small negative multiple of $I$.

For a convex cone $D$ in an inner product space, use the nonnegative-pairing conventionHere the pairing is the Frobenius inner product on real symmetric matrices. Let $C_0$ be the conic hull of the nonnegative rank-one matrices $x{x}^T$, and let $C=\overline{C_0}$. For $A\in K$, $⟨A,x{x}^T{⟩}_F=x^{T}Ax\ge 0$. This extends to conic combinations, and by continuity to their limits. Hence $C\subseteq K^{\ast }$.

For the converse, if $B\notin C$, separation from a closed convex cone supplies a symmetric $H$ withIn particular $x^{T}Hx\ge 0$ for every $x\ge 0$, so $H\in K$. The negative pairing then excludes $B$ from $K^{\ast }$. ThereforeThe same generator test gives $C^{\ast }=K$. This is the duality of copositive and completely positive cones; the next argument removes the closure.

The real vector space of symmetric matrices has dimension $N=n(n+1)/2$. By the conic Carathéodory theorem, every member of $C_0$ is a conic combination of at most $N$ generators. Absorb each nonnegative coefficient into its vector through $\lambda x{x}^T=(\sqrt{\lambda }x)(\sqrt{\lambda }x{)}^T$.

If $B_{\ell }\in C_0$ converges to $B$, write, padding with zero vectors if necessary,The matrix trace satisfiesThe left side is bounded because $B_{\ell }$ converges. Thus the finite tuple $(x_{\ell 1},\dots ,x_{\ell N})$ is bounded. The Bolzano-Weierstrass theorem gives a subsequence on which every vector converges, say $x_{\ell j}\to x_j\ge 0$. Continuity of the outer product now gives $B={\sum }_{j=1}^N{x}_j{x}_j^T\in C_0$. HenceThis proves closedness of the completely positive cone. The uniform bound on the number of factors and the matrix trace bound are both essential: an arbitrary conic hull of a closed generating set need not be closed.

Let $U=\{x\ge 0:\Vert x{\Vert }_2=1\}$. This set is nonempty and compact for $n\ge 1$, and the quadratic form is continuous. Its minimum $\alpha$ is therefore attained.

For every nonzero $y$ in the nonnegative orthant, normalizing $y$ givesThe zero vector imposes no further condition. It follows that $Q-\lambda I$ is a copositive matrix exactly when $\lambda \le \alpha$. Thus the feasible scalar set is $(-\infty ,\alpha ]$, andBoth optima are attained. This copositive reformulation of an orthant Rayleigh minimum follows directly from homogeneity; it does not require invoking a duality theorem for the original nonconvex constraint.

The restriction to $x\ge 0$ matters. For the matrix in part (a), this minimum is $1$ whereas the unrestricted smallest eigenvalue is $-1$.

For $X$ in the dual cone $C$, copositivity of $Q-\lambda I$ gives $⟨X,Q-\lambda I{⟩}_F\ge 0$. An upper-bounding Lagrangian for the maximization is thereforeIts supremum over unrestricted $\lambda$ is finite precisely when $\mathrm{tr}X=1$. Minimizing that upper bound gives the conic programThis is completely positive optimization, not simply semidefinite programming: $C$ is the completely positive cone.

There is also a direct equality certificate. Every feasible $X={\sum }_j{u}_j{u}_j^T$, $u_j\ge 0$, has ${\sum }_j\Vert u_j{\Vert }_2^2=1$. Its objective is a weighted average of the nonnegative-sphere Rayleigh quotients, hence is at least $\alpha$. For a minimizing unit vector $x_{\ast }$ from part (g), $X_{\ast }=x_{\ast }{x}_{\ast }^T$ is feasible and has objective $\alpha$. Thus $\boxed{X_{\ast }=x_{\ast }{x}_{\ast }^T}$ attains the dual and both values agree, without relying on unverified regularity assumptions.

Split the sign vector as $x=(p^T,q^T{)}^T$. Multiplication of the two off-diagonal blocks givesbecause the two terms are the same real scalar. The map $(p,q)\mapsto x$ is a bijection between the feasible sign choices. ThereforeThis is the symmetric lifting of bipartite binary quadratic optimization to binary quadratic optimization. The factor $1/2$ is necessary: otherwise the two blocks would double the objective. No positive semidefiniteness of $A$ is assumed; generally its off-diagonal structure makes its quadratic form indefinite.

Every feasible sign vector gives the rank-one matrix $X=x{x}^T$. It is a positive semidefinite matrix, since $u^{T}Xu=(u^{T}x{)}^2\ge 0$, and $X_{ii}=x_i^2=1$. The matrix trace identity givesThus all original feasible objectives appear among the relaxed ones, provingThe semidefinite relaxation of binary quadratic optimization drops the rank-one requirement and keeps the elliptope constraints.

An optimal relaxed matrix exists. The feasible set is nonempty, since it contains $I$, and closed. Its two-by-two principal minors give $|X_{ij}{|}^2\le X_{ii}{X}_{jj}=1$, so it is bounded and therefore compact. The linear objective attains its maximum. Also $\mathrm{tr}(AI)=0$ and hence $p_{\mathrm{SDP}}^{\ast }\ge 0$, including the zero-objective case.

Write a test vector as $(u,v)$ and put $s={\sum }_i{u}_i$, $t={\sum }_j{v}_j$. Its quadratic form against the block-constant matrix isSince $a\ge |b|$, both $a$ and $a-|b|$ are nonnegative, andEquivalently it isTherefore the bipartite block-constant positive semidefinite matrix satisfies $\boxed{\left(\begin{array}{cc}a{J}_{n,n}& b{J}_{n,m}\\ b{J}_{m,n}& a{J}_{m,m}\end{array}\right)⪰0}$.

For positive block sizes, the condition is also necessary: choose $s=t$ and $s=-t$ to obtain $a+b\ge 0$ and $a-b\ge 0$. Equality is allowed, and vectors whose sums vanish in both blocks lie in the kernel. Positive semidefiniteness, rather than positive definiteness, is the conclusion.

For each coefficient index $k\ge 0$, let $H_k$ have constant diagonal blocks $f_{k}J$ and cross blocks $g_{k}J$. The preceding block-constant argument gives $H_k⪰0$. Define the Hadamard powers $X^{\circ k}$, withThis is the constant entrywise power, including at zero entries; it is not the identity matrix. Repeated use of the Schur product theorem shows $X^{\circ k}⪰0$ for every $k\ge 0$.

Applying the Schur product theorem again makes every summand $H_k\circ X^{\circ k}$ positive semidefinite. The partial sums are positive semidefinite, and their entrywise limit is exactly $Y$. In finite dimension this is a matrix-norm limit; the positive semidefinite cone is closed. ConsequentlyEndpoint convergence follows from the stated expansions on the full interval: $f_k\ge 0$ and $\sum f_k=f(1)<\infty$, while $\sum |g_k|\le \sum f_k$. Thus the expansions converge absolutely at every matrix entry. This is coefficient-dominated entrywise positivity.

The coefficient condition must include index zero. We interpret the PDF's $\mathbb{N}$ accordingly. If it means only positive integers and no condition is imposed on $f_0,g_0$, the assertion is false: take $n=m=1$, $X=0$, $f=-1$ and $g=0$. All positive-index inequalities hold, but $Y=-I_2$.

Put $t=\log (1+\sqrt{2})=\mathrm{arsinh}(1)$, so $c_K=2t/\pi$. The power series coefficients of the hyperbolic sine preprocessing areThus $f_j=|g_j|$ for every $j\ge 0$, and the series converge on the full interval. Applying coefficient-dominated entrywise positivity gives $Y⪰0$.

Every diagonal entry belongs to one of the diagonal blocks and equals $f(X_{ii})=f(1)=\sinh t$. Because $e^t=1+\sqrt{2}$ and $e^{-t}=\sqrt{2}-1$, this is $(e^t-e^{-t})/2=1$. ThereforeThe matrix lies in the elliptope and admits a Gram matrix representation by unit vectors. This preprocessing is the Krivine rounding scheme; the equality of absolute coefficients is what preserves positive semidefiniteness even though the cross-block sine coefficients alternate in sign.

The Gram matrix representation and $Y_{ii}=1$ give $\Vert v_i{\Vert }_2=1$. For a standard Gaussian random vector $Z$, each $⟨v_i,Z⟩$ is a standard normal scalar, so the zero event has probability zero. Choose either sign convention at zero; the resulting vector is almost surely a feasible sign vector. Consequently $y^{T}Ay\le v^{\ast }$ almost surely.

The Gaussian sign-correlation identity givesThe last equality uses symmetry of the real matrices. HenceThe inverse sine is applied entrywise, not through spectral matrix functional calculus.

For completeness, the correlation coefficient identity has a geometric proof. If the angle between two unit vectors is $\theta$, the isotropic Gaussian random vector direction in their two-dimensional span gives opposite signs on angular sectors with probability $\theta /\pi$. Thus the sign product has expectation $1-2\theta /\pi =(2/\pi )\arcsin (\cos \theta )$. Parallel and antiparallel pairs give the endpoint values $1$ and $-1$ directly. This is Gaussian hyperplane rounding, and needs no independence between the rounded coordinates.

The Krivine rounding constant has $t=c_K\pi /2=\log (1+\sqrt{2})<\pi /2$. Since $|X_{ij}|\le 1$, the principal real inverse sine satisfieson every cross-block entry. The matrix $A$ has zero diagonal blocks, so those cross blocks are the only contributors to its Frobenius inner product with $\arcsin [Y]$. Explicitly,No analogous identity is needed for the diagonal blocks involving $\sinh$.

Combining with the preceding expectation formula and optimality of $X$ gives the bipartite sign rounding boundAt least one feasible rounded outcome attains at least this expectation. This is an expectation-based approximation guarantee for the specific bipartite sign problem; no claim is made that $c_K$ is the largest possible constant. The inequalities remain valid when the optimal objective is zero.

On the unit circle, $z^{-1}=\overline{z}$, soThus the trigonometric polynomial is nonnegative, with a zero at $z=-1$, andEquivalently, writing $z=e^{i\theta }$ gives $p(z)=2+2\cos \theta =4{\cos }^2(\theta /2)$. The factor has polynomial degree one as required. Multiplication of $q$ by any constant of modulus one leaves the factorization unchanged; uniqueness of $q$ is not claimed.

This is the simplest instance of the Fejér–Riesz theorem, where nonnegativity of a trigonometric polynomial on the unit circle admits a polynomial modulus-square factorization.

Since $p$ is real on the unit circle,Multiply the difference by $z^d$. It is an ordinary polynomial of polynomial degree at most $2d$ vanishing at every point of the unit circle. A nonzero polynomial has only finitely many roots of a polynomial, so all its coefficients vanish. This proves the conjugate symmetry of trigonometric polynomial coefficients:For arbitrary nonzero complex $z$, coefficient substitution now gives preciselyEquivalently $p(1/\overline{z})=\overline{p(z)}$. The complex conjugation on the right applies to the whole value, including the coefficients; it cannot simply be discarded away from the circle.

The PDF additionally assumes $p_d\ne 0$. Then $p_{-d}=\overline{p_d}\ne 0$, so the ensuing polynomial $P=z^{d}p$ has polynomial degree exactly $2d$ and nonzero constant term. These clauses and this subpart are absent from the damaged TeX, but present in the PDF.

For $z\ne 0$, the coefficient symmetry yieldsThus $P$ equals its reversed-conjugate polynomial. If $\zeta \ne 0$ is a root of a polynomial, with $P(\zeta )=0$, this identity gives $P(1/\overline{\zeta })=0$, provingThe reciprocal-conjugate root pairing also preserves the multiplicity of a root: reversal and complex conjugation take each factor associated with $\zeta$ to the corresponding factor associated with $1/\overline{\zeta }$, with the same exponent.

Since $P(0)=p_{-d}\ne 0$, no zero root of a polynomial occurs, so the reciprocal operation is always defined on the roots of a polynomial. Roots off the unit circle are paired on opposite sides of it; roots of a polynomial on the unit circle are fixed by this operation. Pairing alone does not force even multiplicity at those fixed roots of a polynomial; that extra fact uses nonnegativity.

Pair the off-circle roots of a polynomial using reciprocal-conjugate root pairing, and split each unit-circle root of a polynomial's even multiplicity equally between the two members of a pair. The fundamental theorem of algebra and the leading coefficient $p_d$ give $P(z)=p_d{\prod }_{i=1}^d(z-{\zeta }_i)(z-1/\overline{{\zeta }_i})$. None of the selected ${\zeta }_i$ is zero.

On the unit circle, the identityturns $P(z)/z^d$ intoAt a point of the unit circle outside the finite set of roots of a polynomial, the product is positive and $p(z)$ is nonzero and nonnegative. Its ratio to the product is therefore real and strictly positive. This proves $c>0$, even though the algebraic expression initially permits a complex constant. ConsequentlyThis proves the Fejér–Riesz theorem for a nonzero trigonometric polynomial of actual order $d$. A positive constant has a constant square-root factor, and the identically zero trigonometric polynomial has $q=0$; if $p_d=0$ for a specified upper order $d$, reduce to the actual order first.

Although the PDF permits assuming even multiplicity, there is a short proof of even multiplicity of unit-circle roots of a nonnegative trigonometric polynomial. The real analytic function $p(e^{i\theta })\ge 0$ cannot have a zero of odd order. Near $\zeta =e^{i{\theta }_0}$, $e^{i\theta }-\zeta$ has a simple zero, and the nonzero factor $e^{-id\theta }$ leaves the zero order of $P(e^{i\theta })$ unchanged. Hence the multiplicity of a root must be even.

Collect the factor's coefficients in the column vector $q=(q_0,\dots ,q_d{)}^T$ and setThis is a Hermitian matrix and a positive semidefinite matrix, because for every complex vector $x$,On the unit circle, expanding the modulus square givesUniqueness of the finite Laurent polynomial coefficients, proved as in part (b)(i), therefore givesThis is the rank-one spectral-factor Gram matrix. The matrix $M$ has matrix rank one when $q\ne 0$ and zero when $q=0$. The orientation $i-j=k$ is the PDF's convention: using $\overline{q_i}{q}_j$ instead would generally interchange $p_k$ and $p_{-k}$.

For $z$ on the unit circle, use the conjugated monomial vectorThen the prescribed diagonal sums givePositive semidefiniteness provesThis is the Gram matrix representation of a trigonometric polynomial. The Hermitian condition also implies $p_{-k}=\overline{p_k}$, so its values on the unit circle are real. The conjugated monomial vector is required by the source's $i-j=k$ convention; the unconjugated vector would represent $p(z^{-1})$ instead.

In particular $p_0=\mathrm{tr}M\ge 0$. If this matrix trace is zero, all nonnegative eigenvalues vanish and $M=0$, so $p=0$. A general feasible Gram matrix need not have matrix rank one; the Fejér–Riesz theorem ensures a rank-one representative exists whenever the nonnegative trigonometric polynomial is nonzero.