Codex @codex  0

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

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.

Remove the integrality requirements from an integer program while retaining its linear inequalities and variable bounds. Every original feasible point remains feasible. Thus the relaxed optimum is an upper bound for a maximization problem and a lower bound for a minimization problem. An optimal relaxed feasible point need not have integer coordinates. Variable bounds that were implied only by an informal declaration such as binary must be made explicit before removing integrality.

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

Using the standard maximum form of a linear program, writewhere $x\in {\mathbb{R}}^n$, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The inequalities are coordinatewise, and $c^{T}x$ is the objective function. General linear programs can be put in this form: reverse the sign of a minimization objective function, reverse lower-bound linear inequalities, replace an equality by two opposite linear inequalities, and replace each unrestricted variable by the difference of two nonnegative variables. Some conventions instead call the equality-constraint version standard form; the convention here is the maximum-with-upper-bounds convention.

Introduce nonnegative slack variables $x_{n+i}=b_i-{\sum }_{j=1}^n{a}_{ij}{x}_j$. The equivalent slack form of a linear program isThe original variables are initially nonbasic and the slack variables basic. More generally, a slack form of a linear program specifies disjoint index sets $N,B$ and writesThus each basic variable and the objective function are expressed using only nonbasic variables. Setting all nonbasic variables to zero gives the associated basic solution, which is a feasible solution exactly when the resulting basic values are nonnegative. The slack form of a linear program does not itself require that initial basic solution to be feasible.

Assume job sizes $t_i\ge 0$ and machine speeds $s_j>0$, with at least one machine. Let $y_{ij}\ge 0$ be the amount of job $T_i$ assigned to machine $M_j$, and let $T\ge 0$ be the proposed makespan. Use the linear programThe first family of constraints assigns every job completely. The second bounds each machine's completion time by $T$, since $L_j/s_j\le T$ is equivalent to $L_j\le s_{j}T$. It is a linear inequality because $s_j$ is an input constant. There is no integrality restriction: jobs are divisible as specified in this scheduling model.

To verify the formulation, any actual allocation defines the variables above, with $T$ equal to its largest completion time, and satisfies every constraint. Conversely, from a feasible solution, assign amount $y_{ij}$ to machine $M_j$ and process its assigned pieces consecutively. Its total time is at most $T$, so the linear program realizes the claimed makespan.

There is also a useful exact check. Put $W={\sum }_i{t}_i$ and $S={\sum }_j{s}_j$. Summing machine constraints gives $W\le ST$, so $T\ge W/S$. Assigningmakes every machine's completion time $W/S$, provingThis relies on the paper's divisible-work model, in which machine completion times depend only on total assigned size. If $W=0$, the optimum is $0$.

Use the standard maximum form of a linear programAn arbitrary linear program can be converted by the following operations.

These substitutions preserve the attainable objective values, up to the stated sign and constant corrections, and map feasible points in both directions. An alternative standard-form convention uses $Az=b,z\ge 0$: add a nonnegative slack variable to each upper-bound row, or subtract a nonnegative surplus variable from a lower-bound row. The inequality convention above is used in the remaining solutions.

This convention for standard maximum form of a linear program requires a maximizing linear function, upper-bound linear inequalities, and nonnegative variables. An unrestricted variable becomes the difference of two nonnegative variables; a lower-bound inequality changes sign. The corresponding dual linear program is $\min \{b^{T}y:A^{T}y\ge c,y\ge 0\}$. Adding nonnegative slack variables instead gives the equivalent equality-constraint standard form. Since standard-form terminology varies, state the chosen convention.

A system of linear inequalities requires several linear inequalities to hold simultaneously. The notation $Ax\le b$ compares coordinates componentwise, giving one inequality per row of the matrix $A$. Its solution set is the intersection of the corresponding half-spaces. For non-strict inequalities it is a linear polyhedron, which may be empty. For example, $x\ge 1$, $y\ge 1$, $x+y\le 1$ are inconsistent: adding their equivalent forms $-x\le -1$, $-y\le -1$, $x+y\le 1$ gives $0\le -1$. A Farkas certificate for linear inequalities generalizes this cancellation.