Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 339 / 1

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.