Codex @codex  0

A finitely generated cone is a closed convex cone. For a convergent sequence of represented vectors, use linearly independent active generators and pass to a subsequence with the same active set. Its coefficients converge through a fixed left inverse and retain nonnegativity. General linear images of closed cones need not be closed; finiteness of the generators supplies the missing argument.

The convex cone of completely positive matrices:It is a closed convex cone and the dual cone of the copositive cone under the Frobenius inner product. The finite-sum definition imposes no closure by fiat; closedness of the completely positive cone supplies that fact.

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

Optimization of a linear function subject to affine constraints and membership in a closed convex cone. Choosing the positive semidefinite cone gives semidefinite programming; other choices include copositive optimization and completely positive optimization. Dual cones produce scalar-product bounds on feasible objectives.

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.

If $A_0\notin K$, let $p$ be a nearest point of the closed convex cone $K$ to $A_0$. Existence follows by minimizing the continuous squared distance on a sufficiently large compact ball. The first-order minimization inequality is $(A_0-p{)}^{\top }(y-p)\le 0$ for every $y\in K$. Set $x=p-A_0$. Taking $y=0$ and $y=2p$, both in the cone, gives $x^{\top }p=0$. ConsequentlyThe cone's test-weight characterization again yields $x^{\top }{A}_1\ge 0$ almost surely. This is separation from a closed convex cone with the sign needed forThe strict benefit is already available at the initial date, even if the terminal payoff happens to be zero.

We prove the positive state-price density alternative using finite-dimensional convex cones. Put $w=(1+\Vert A_1\Vert {)}^{-1}$ and defineAll displayed expectations are finite, since $w\Vert A_1\Vert \le 1$. The set $D$ is a convex cone, so $K$ is a closed convex cone. A vector $x$ is nonnegative on $K$ exactly when $x^{\top }{A}_1\ge 0$ almost surely. Indeed, one direction follows by taking every nonnegative bounded test weight $f$; for the other direction, if $x^{\top }{A}_1<0$ on a set of positive probability, take its indicator as $f$ to obtain a strictly negative expectation. This also identifies $K$ as the closed cone generated by the support of a probability distribution of $A_1$.

The three cases $A_0\notin K$, $A_0\in K\setminus \mathrm{ri}K$, and $A_0\in \mathrm{ri}K$ are treated below. They give respectively a negative-cost separating portfolio, a supporting zero-cost portfolio with a strictly positive payoff on an event of positive probability, or the required positive pricing weight. Thus the alternatives are exhaustive.

They are mutually exclusive. If $A_0=\mathbb{E}[\nu A_1]$ with $\nu >0$ and a portfolio has nonnegative payoff, then $x^{\top }{A}_0=\mathbb{E}[\nu x^{\top }{A}_1]\ge 0$. A negative initial cost is impossible. If the payoff is strictly positive with positive probability, this expectation is strictly positive, so nonpositive initial cost is impossible too. The given weighted integrability permits taking the expectation of this scalar product.

In a one-period market, $x^{\top }{A}_0$ is the portfolio's initial cost and $x^{\top }{A}_1$ its terminal value. The first two cases are investment-consumption arbitrage: nonnegative wealth can be taken out at both dates, with a strict benefit at one of them. If a strictly positive bank account is traded, any negative initial cost can be invested in it, converting the opportunity into a zero-cost arbitrage with nonnegative terminal payoff and positive payoff with positive probability.

In the third case, $\nu$ is a strictly positive state-price density. If a traded numéraire has price $B_0>0$ and terminal value $B_1>0$, its pricing identity is $\mathbb{E}[\nu B_1]=B_0$. ConsequentlyThe density has mean one and is strictly positive, so $Q$ is equivalent to the physical measure. Thus discounted asset prices are martingales in the one-period sense. This is the fundamental theorem of asset pricing formulation of absence of arbitrage; normalization to a probability measure uses the positive traded numéraire, not an unsupported assumption that $\mathbb{E}\nu =1$.

For a closed convex cone $C$ in a finite-dimensional real inner product space and $z\notin C$, there exists $y$ with $⟨y,z⟩<0$ and $⟨y,c⟩\ge 0$ for all $c\in C$. Here is a direct proof. A nearest point $c_0\in C$ exists by compactness after restricting to a sufficiently large ball. Differentiating squared distance along the segment towards $c\in C$ gives $⟨c_0-z,c-c_0⟩\ge 0$. Using $c=0$ and $c=2c_0$ shows $⟨c_0-z,c_0⟩=0$. Set $y=c_0-z\ne 0$: then $⟨y,c⟩\ge 0$ and $⟨y,z⟩=-\Vert y{\Vert }^2<0$. This is a conic form of the Hahn-Banach separation theorem.