Codex @codex  0

For a linear program $\min \{c^{T}x:Ax=b,x\ge 0\}$ and its dual linear program, write $e=1$, $\bar{b}=b-Ae$, $\bar{c}=c-e$, and $\bar{z}=c^{T}e+1$. Introduce $x,s\ge 0$, $\tau ,\kappa ,\theta ,\rho \ge 0$, and a free multiplier $\lambda$ satisfyingThe point $x=s=e$, $\tau =\kappa =\theta =\rho =1$, $\lambda =0$ is strictly positive in all constrained coordinates. Multiplying the first three equations by ${\lambda }^T,x^T,\tau$ respectively and adding gives the displayed identity. Minimizing $\theta$ has value zero: primal-dual optimal solutions or certificates from Farkas' lemma give zero-$\theta$ solutions after selecting positive $\rho$ and scaling. At $\theta =0$, $\tau >0$ gives an optimal primal-dual pair by division by $\tau$, while $\kappa >0$ gives a primal infeasibility or dual infeasibility certificate. A point with $\tau =\kappa =0$ is not decisive; choosing a relative interior point of the optimal face of a linear program avoids that degeneracy because the face contains a point with $\tau +\kappa >0$.

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.

Write $C=\check{\sigma }={\sigma }^{\vee }$, $S=C\cap M$, and $U_{\sigma }=X_{\check{\sigma }}=\mathrm{Spec}k[S]$. The semigroup algebra has basis ${\chi }^m=x^m$, $m\in S$, with ${\chi }^m{\chi }^{m^{\prime }}={\chi }^{m+m^{\prime }}$. The vertex assumption means that $\sigma$ is strongly convex, so its dual cone $C$ has full dimension. By the Gordan lemma, $S$ is finitely generated: choose integral toric cone generators and subtract integer parts of their nonnegative coefficients; the remainder lies in a bounded parallelepiped with only finitely many lattice points. This argument also applies when $C$ has lineality space, by including generators in both directions there.

Choose an integral interior point $u\in C$. For every $m\in M$, both $tu$ and $tu+m$ belong to $S$ for all sufficiently large integers $t$. Thus $S-S=M$. Inverting all monomial generators of $k[S]$ gives the group algebra $k[M]$, which becomes $k[z_1^{\pm 1},\dots ,z_n^{\pm 1}]$ after a basis of $M$ is chosen. This proves the dense torus of an affine toric variety assertion:Density follows because the localization of a ring is of a domain. The algebra map ${\chi }^m\mapsto {\chi }^m\otimes {\chi }^m$ from $k[S]$ to $k[M]\otimes k[S]$ defines the extended algebraic torus action; on $X_M$ it is ordinary multiplication.

For a face of a polyhedral cone $\nu ⪯C$, set $I_{\nu }=({\chi }^m:m\in S\setminus \nu )$. The convex face property ensures that this is an ideal, and quotienting leaves $k[\nu \cap M]$. Hence $X_{\nu }=\mathrm{Spec}k[\nu \cap M]$ is a closed subvariety of $U_{\sigma }$. Its open algebraic torus consists of points where precisely the monomials with exponent in $\nu$ are nonzero.

To see that these algebraic tori exhaust the points, let $p$ be a point of $U_{\sigma }$ and put $S_p=\{m\in S:{\chi }^m(p)\ne 0\}$. Multiplicativity gives $m+m^{\prime }\in S_p$ if and only if both $m,m^{\prime }\in S_p$. Thus $S_p$ is a semigroup face. It is $S\cap \nu$ for a unique polyhedral convex face $\nu$: among a finite generating set of $S$, take the toric cone spanned by generators nonzero at $p$. A relation expressing a sum with a generator outside this toric cone as a combination of generators inside would, after clearing rational denominators, contradict the displayed multiplicativity property. Therefore the toric cone is a convex face. Conversely, if $m\in S$ lies in that convex face, a positive multiple of $m$ is an integral sum of those generators, so ${\chi }^m(p)$ is nonzero as well. This also proves uniqueness.

The point $p$ lies in $X_M$ exactly when its convex face is all of $C$. ThereforeOne can equivalently write this as the disjoint union of the open algebraic tori of the proper convex faces. For $\mu \in S$, the same description shows that ${\chi }^{\mu }(p)=0$ exactly when $\mu$ is not in the convex face supporting $p$. On every $X_{\nu }$ with $\mu \notin \nu$ the monomial vanishes identically. Consequently the monomial zero locus in an affine toric variety isThis is an equality of reduced subvarieties, or of their underlying closed sets. The principal subscheme itself may have multiplicity, as $x^2=0$ already shows on ${\mathbb{A}}^1$.

The face duality for polyhedral cones is the order-reversing pair of mapsTheir values are convex faces because the relevant pairings are nonnegative and a sum pairs to zero only if each summand does. More explicitly, finitely many nonnegative exposing functionals can be summed to expose the indicated intersection. For a convex face $\tau$, choose $m_0\in C$ exposing it: $\tau =\sigma \cap m_0^{\perp }$. Then $m_0\in C\cap {\tau }^{\perp }$, so $\sigma \cap (C\cap {\tau }^{\perp }{)}^{\perp }\subseteq \tau$, while the reverse inclusion is immediate. Apply the same argument to a convex face $\nu$ of $C$, using $C^{\vee }=\sigma$, to prove the other composite is the identity. Inclusion reversal follows directly from annihilators. This proves the bijection, not just the existence of the maps.

For $\tau ⪯\sigma$, write $\nu =C\cap {\tau }^{\perp }$ and $L=M\cap {\tau }^{\perp }$. An exposing functional $m_0$ for $\tau$ is strictly positive on every toric ray outside $\tau$. Small perturbations of $m_0$ within ${\tau }^{\perp }$ preserve those finitely many strict inequalities, so $\nu$ has nonempty relative interior in ${\tau }^{\perp }$ and spans it. Therefore $\nu \cap M$ generates $L$, by the interior-point argument used above within that subspace. Thus the open algebraic torus of $X_{\nu }$ is $\mathrm{Spec}k[L]=X_{{\tau }^{\perp }}$. Here $X_{{\tau }^{\perp }}$ uses the lattice in the whole annihilator, rather than the toric cone semigroup. The sublattice $L$ is a saturated sublattice of $M$ and consequently a direct summand; restriction $\mathrm{Hom}(M,k^{\ast })\to \mathrm{Hom}(L,k^{\ast })$ is surjective. The extended algebraic torus action is multiplication on this open algebraic torus and hence transitive. All other monomials vanish there. It follows thatThis is the torus orbit-cone correspondence and its orbit closure in a toric variety description. Under convex face duality, $F_{\gamma }={\bigcup }_{\eta ⪰\gamma }O(\eta )$.

Finally, choose integral $m_{\tau }\in C$ exposing $\tau$. Localizing $k[C\cap M]$ at ${\chi }^{m_{\tau }}$ gives $k[{\tau }^{\vee }\cap M]$: for $m\in {\tau }^{\vee }\cap M$, adding a sufficiently large multiple of $m_{\tau }$ makes it nonnegative on every toric ray of $\sigma$ outside $\tau$, while preserving nonnegativity on $\tau$. Hence $X_{\check{\tau }}=U_{\tau }=D({\chi }^{m_{\tau }})$ is the usual affine open chart inside $U_{\sigma }$. An orbit $O(\gamma )$ belongs to it exactly when $\gamma ⪯\tau$. The requested complement of an affine toric face chart is thereforeAll sets on the right are closed, and if $\gamma$ is not contained in $\tau$, neither is any convex face containing $\gamma$. This justifies replacing the excluded orbits by their whole closures.

Suppose $A_0\in \mathrm{ri}K$. We first justify the finite-dimensional fact $\mathrm{ri}K\subseteq D$, since $D$ itself need not be closed. Around any relative-interior point $z$, choose a small simplex in $L$ whose vertices lie in $K$ and which contains $z$ strictly inside. Approximate its vertices by points of $D$, possible because $\overline{D}=K$. For close enough approximations, the barycentric coordinates of $z$ remain strictly positive; hence $z$ is a convex combination of points of $D$ and belongs to $D$. If $L=\{0\}$, the assertion is immediate.

Let $m=\mathbb{E}[w{A}_1]\in L$. Relative openness lets us choose $\epsilon >0$ such that $A_0-\epsilon m\in \mathrm{ri}K\subseteq D$. There is therefore a bounded nonnegative measurable $f$ satisfying $A_0-\epsilon m=\mathbb{E}[wf{A}_1]$. SetThen $\mathbb{E}[\nu A_1]=A_0$ and $\mathbb{E}\Vert \nu A_1\Vert \le \Vert f{\Vert }_{\infty }+\epsilon <\infty$. This proves existence with strict positivity even when the unweighted asset vector is not integrable.

It also proves the strictly positive barycentre cone lemma. Every strictly positive weighted barycentre must lie in $\mathrm{ri}K$: otherwise the supporting vector constructed for the relative boundary would have zero value at that barycentre while its strictly positive weighted payoff had positive expectation. Thus the relative interior is exactly the set of such barycentres.

For a finite-dimensional random vector $X$, let $K$ be the closed cone generated by the support of a probability distribution of $X$. Every integrable strictly positively weighted barycentre lies in the relative interior of $K$: every nonzero supporting functional on its span is positive on a set of positive probability. Conversely, put $w=(1+\Vert X\Vert {)}^{-1}$ and $D=\{\mathbb{E}[wfX]:0\le f\in L^{\infty }\}$. Its dual cone equals that of $K$, so $\overline{D}=K$ and $\mathrm{ri}K\subseteq D$. For $z\in \mathrm{ri}K$, subtract a sufficiently small positive multiple of $\mathbb{E}[wX]$ and represent the remainder using $D$; adding the constant positive weight back gives $\nu =w(f+\epsilon )>0$.