Codex @codex  0

A real symmetric matrix $A$ is copositive if its quadratic form satisfies $x^{T}Ax\ge 0$ for every $x$ in the nonnegative orthant. Every positive semidefinite matrix and every symmetric nonnegative matrix is copositive, as is their sum. The converse fails for the Horn copositive matrix.

Conic optimization using the copositive cone. The constraint $Q-\lambda I\in {\mathrm{COP}}_n$ supplies an exact reformulation of a Rayleigh quotient minimum on the nonnegative orthant. Exact conic formulation does not itself provide an efficient membership algorithm.

For a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $b\in {\mathbb{R}}^m$, exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1{)}^T$ is obtained with $z=(1,1{)}^T$.

Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.

Brief geometric proof. The two systems cannot both hold, because they would implyFor existence of a certificate when $b\notin K$, closedness of finitely generated cones makes $K$ a closed convex cone, so separation from a closed convex cone supplies $y^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. Concretely, let $p$ be the Euclidean projection onto a convex set of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_2^2<0$. In the example, $p=(0,1{)}^T$ and $y=(1,0{)}^T$. Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.

An original historical source is Julius Farkas's ^[ref]. The linked archival record verifies the author, title and publication details.

Consider the original linear programOne unit of $v$ costs twice as much as one unit of $u$, so $(u,v)=(3,0)$ is a plausible answer. To certify it, multiply the three linear inequalities by $0,1,1$, respectively, and add:The proposed feasible point attains $3$, so its cost is the global minimum.

In the conic dual problem convention, the data and certificate areDirect matrix multiplication gives $A^{T}y=c$ and $b^{T}y=3$. At $x=(3,0{)}^T$, the slack variable is $s=(3,0,0{)}^T$, so $s^{T}y=0$. The first linear inequality has positive slack and zero multiplier; the two positively weighted linear inequalities are tight. This is complementary slackness.

The entire dual feasible set can also be read off: write $y=(1-r,2-r,r{)}^T$ with $0\le r\le 1$. Then $A^{T}y=c$ and $b^{T}y=3r$. Maximizing this lower bound gives $r=1$. A point such as $r=1/2$ is still a valid certificate of the weaker bound $u+2v\ge 3/2$.

Only $z,w$ have printed nonnegativity restrictions; $x,y$ are unrestricted. In four-dimensional space, a vertex of a linear polyhedron needs four independent active constraints. There are exactly four available constraints, so all must be active. Solving them givesand therefore the only possible vertex of a linear polyhedron is $(x,y,z,w)=(2,3,0,0)$. It is feasible, and its four active normals are independent, so it is indeed a vertex of a linear polyhedron.

One can also see uniqueness geometrically from the slack variables $s_1=1-2x+y-5w$ and $s_2=3-y-z-w$. The feasible region is in affine bijection with the nonnegative orthant in $(s_1,s_2,z,w)$:That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.

For unit resource requirements, treat the resource-blocking events as approximately independent. Let $B_j$ be the approximate blocking probability at resource $j$. Screening class-$r$ traffic by every resource other than $j$ produces the reduced-load approximationThe modeled resource is excluded from its own screening product. For general integer requirements, the standard generalized approximation is $a_j=(1-B_j{)}^{-1}{\sum }_r{A}_{jr}{\alpha }_r{\prod }_k(1-B_k{)}^{A_{kr}}$; in the unit-requirement case this reduces to the displayed formula. The approximate route acceptance is ${\prod }_j(1-B_j{)}^{A_{jr}}$. The independence used here is an approximation to the correlated exact stationary distribution, not an extra property of that law.

Here is a proof of fixed-routing existence and uniqueness. Suppose first that every retained capacity $C_j$ is a positive integer. Links of zero capacity permanently reject their routes and can be removed. If $K$ has the upper-truncated Poisson distribution with parameter $a$, its mean isThe derivative follows by differentiating the normalized weights: $dP(K=k)/da=P(K=k)(k-m_C(a))/a$. The probability at the upper endpoint similarly givesThus $E(\cdot ,C)$ increases from zero to one, while $m_C$ increases from zero to $C$. This is the monotonicity of the Erlang blocking probability.

Set $y_j=-\log (1-B_j)$. For $y\ge 0$ defineHere the inverse is with respect to offered load, and the value at zero is zero. This function is the carried load evaluated at the inverse blocking coordinate, so it is continuous and strictly increasing, with limit $C_j$ as $y\to \infty$. Consider the convex potential for the Erlang fixed pointEach exponential of a linear function is convex. Each integral is strictly convex because its derivative $u_j$ is strictly increasing. Their sum is strictly convex on the nonnegative orthant. It is also coercive: for large $y_j$, $u_j(y_j)$ is bounded below by a positive constant, so the integral grows without bound; the other terms are nonnegative. Hence $F$ attains a unique minimum.

At a positive coordinate, the first-order condition isAt $y_j=0$, the derivative equals minus the right-hand side and is nonpositive. A boundary minimum can therefore occur there only when that load is zero, in which case the derivative is zero and the same equation holds. Since $1-B_j=e^{-y_j}$, division by this positive acceptance probability makes the first-order condition precisely the reduced-load equations above. Conversely every fixed point is such a minimum. Thus fixed routing has exactly one Erlang fixed point, including zero blocking at unused resources. The proof does not rely on a potentially nonconvergent simultaneous substitution algorithm.

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$.

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 $z\in {\mathbb{R}}^n$, define $x_i=z_i^2$. Then $x$ lies in the nonnegative orthant andIf $A$ is a copositive matrix, this is nonnegative for every $z$, so $p$ is a globally nonnegative polynomial. Conversely, every $x\ge 0$ has the form $x_i=z_i^2$ by taking $z_i=\sqrt{x_i}$. If $p$ is globally nonnegative, then $x^{T}Ax=p(z)\ge 0$ for every such $x$, proving that $A$ is a copositive matrix. The map $z\mapsto (z_i^2{)}_i$ covers the entire nonnegative orthant, which is the key to both directions.

The set $K\cap P$ is compact because $K$ is closed and bounded, and the productis continuous. By the extreme value theorem, $G$ has a maximizer. Since $K$ meets the interior of the nonnegative orthant $P$, some feasible product is positive, so every maximizer lies in $\mathrm{Int}P$.

On $\mathrm{Int}P$, maximizing $G$ is equivalent to maximizingThe Hessian of $F$ iswhich is negative definite. Thus $F$ is a strictly concave function, and it has at most one maximizer on the convex set $K\cap P$. Denote this unique point by $x^{\ast }$.

For any $x\in K\cap P$, the line segmentlies in $K\cap \mathrm{Int}P$. Since $F(x(t))$ is maximal at $t=0$, its right derivative there is nonpositive:ThereforeThis is the supporting inequality for the product maximizer on a compact convex subset of the positive orthant.

Suppose now that $K$ is invariant under cyclic coordinate permutation. That permutation preserves the product, so uniqueness forces it to fix $x^{\ast }$. Hencefor some $r>0$. More explicitly,Indeed, cyclic symmetry averaging puts the diagonal point with coordinate equal to the mean of any $x\in K$ back in $K$, while the preceding inequality with $x_j^{\ast }=r$ gives ${\sum }_j{x}_j\le nr$.

Finally, given $a=(a_1,\dots ,a_n)\in \mathrm{Int}P$, defineThis set is nonempty, closed, convex and bounded, and it contains $a$. By the arithmetic-geometric mean inequality,Equality holds only when all $x_j/a_j$ are equal and their sum is $n$, namely only at $x=a$. Thus this $K$ has

With primal constraints $Ax=b$, the dual variable is unrestricted in sign:Membership of $x$ in the nonnegative orthant still yields $c^{T}x\le y^{T}Ax$, but the next step is now the equality $y^{T}Ax=y^{T}b$, so no sign condition on $y$ is needed. Equivalently an equality constraint can be replaced by two opposite inequalities whose nonnegative multipliers combine into one free multiplier.

The two primal constraints are equalities, so let the two dual variables $u,v$ be free. Primal feasibility restricts $x$ to the nonnegative orthant, givingThus the feasible region lies above all four lines:Its lower boundary follows the third line up to $(5/9,7/9)$, the fourth line from there to $(10/3,-1/3)$, and then the first line. The second line never determines the envelope. Along these three pieces $u+v$ respectively has slopes $-3$, $3/5$, and $3/4$, so its unique minimum is at the first corner:

At this dual point the first two inequalities are strict, while the last two are equalities. complementary slackness therefore suggests $x_1=x_2=0$. The remaining primal equations become $4x_3+2x_4=300$, $x_3+5x_4=300$, giving $x_3=x_4=50$. This is nonnegative and satisfies both equations. Its objective function is $3\cdot 50+5\cdot 50=400$, equal to the feasible dual value. weak duality provesNo nonnegativity restriction was imposed on the dual variables; the negative-$v$ second corner is part of the feasible boundary, even though it is not optimal.

A convex cone containing no nonzero line through the origin, equivalently $K\cap (-K)=\{0\}$. The copositive cone is pointed: a matrix in both it and its negative has zero quadratic form on the nonnegative orthant; testing $e_i$ and $e_i+e_j$ kills all entries.

The sums $P+N$ of a real positive semidefinite matrix $P$ and a symmetric nonnegative matrix $N$ form a convex cone inside the copositive cone. Both terms have nonnegative quadratic forms on the nonnegative orthant. The Horn copositive matrix shows that the inclusion is strict in dimension five; the sum of squares criterion for a biquadratic form explains this cone's relation to semidefinite programming.

A curved feasible set can have the same certificate structure. ConsiderWrite $x=(t,z{)}^T$ and use the second-order cone $K=\{(s_0,s_1,s_2):s_0\ge \sqrt{s_1^2+s_2^2}\}$. In this coordinate ordering,Self-duality of a second-order cone makes $K^{\ast }=K$. The equality $A^{T}y=c$ forces $y_0=1$ and $y_2=0$, leaving $-1\le y_1\le 1$. Its dual objective function is $b^{T}y=-y_1$, maximized at $y=(1,-1,0{)}^T$. Thus every feasible point satisfies $t\ge 1$, and $(t,z)=(1,0)$ attains that bound: $\boxed{p_{\ast }=d_{\ast }=1}$.

The zero dot product is $(1,1,0)\cdot (1,-1,0)=0$. Individual coordinate products need not be nonnegative here: the cancellation $1-1=0$ occurs across coordinates. The valid complementary slackness condition is cone-level orthogonality, rather than the coordinatewise interpretation of the nonnegative orthant.

A self-dual cone equals its dual cone under the specified inner product. The nonnegative orthant, second-order cone and positive semidefinite cone are standard examples. Self-duality of a set alone does not establish primal or dual feasibility.

For a proper cone $K$, suppose a point satisfies $Ax-b\in \mathrm{int}K$ and $p_{\ast }$ is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.^[ref]

The two worked examples have strict primal points: $(u,v)=(2,2)$ has slack $(2,2,1)$ in the interior of the nonnegative orthant, and $(t,z)=(2,0)$ has slack $(2,1,0)$ in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.

Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.

In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.^[ref]