 # Alternative systems

Two systems of inequalities and/or equations such that there exists a solution to one system, or there exists a solution to the other system, and there cannot exist a solution to both systems. Several alternative systems are widely used in mathematical programming, especially in the study of duality.

• Fourier (1826) $LaTeX: Ax \le a, \; Bx < b$ (not vacuous)
or $LaTeX: A^Ty + B^Tv = 0, \; y \ge 0, \; v \ge 0, \; a^Ty + b^T v < 0$
• Gordan (1873) $LaTeX: Ax > 0$
or $LaTeX: A^Ty = 0, \; y \ge 0, y \neq 0$
• Farkas (1902) $LaTeX: Ax = b, \; x \ge 0$
or $LaTeX: A^Ty \ge 0, \; b^Ty < 0$

A Variant is $LaTeX: Ax \le b$
or $LaTeX: A^Ty = 0, \; b^Ty < 0, \; y \ge 0$
• Fredholm (1903) $LaTeX: Ax = b$
or $LaTeX: A^Ty = 0, \; b^Ty > 0$
• Stiemke (1915) $LaTeX: Ax = 0, \; x > 0$
or $LaTeX: A^Ty \ge 0, \; A^T y \ne 0$
• Motzkin (1936) $LaTeX: Ax \le a, \; Bx < b, \; Cx = c$ ( $LaTeX: B$ not vacuous)
or $LaTeX: A^Ty + B^Tv + C^Tw = 0, \; y \ge 0, \; v \ge 0, \; v \neq 0, \; a^Ty + b^Tv +c^Tw \le 0$
• Ville (1938) $LaTeX: Ax > 0, \; x \ge 0$
or $LaTeX: A^Ty \le 0, \; y \ge 0, \; y \neq 0$
• Tucker (1956) $LaTeX: Ax \ge 0, \; Ax \neq 0, \; Bx \ge 0, \; Cx = 0$
or $LaTeX: A^Ty + B^Tv + C^Tw = 0, \; y > 0, \; v \ge 0$
• Gale (1960) $LaTeX: Ax \le b$
or $LaTeX: A^Ty = 0, \; b^Ty = -1, \; y \ge 0$

### Integer Systems

• Papadimitriou and Steiglitz (1982) Let $LaTeX: A$ be an $LaTeX: m \times n$ integer matrix, $LaTeX: a^* = \max_{(i,j)} |A_{i,j}|$, $LaTeX: M = (ma^*)^{m+1}$, and $LaTeX: b$ an integer $LaTeX: m$-vector. $LaTeX: Ax = 0, x \geq 0, \; x \neq 0, \; x \text{ integer-valued}$
or $LaTeX: A^Ty \geq 1, \; y \in \{ 0, \pm 1, \pm 2, \ldots, \pm M \}^m$.

### Convex Systems

For the following, $LaTeX: f$ is convex on $LaTeX: X$.

• Fan, Glicksburg and Hoffman (1957) $LaTeX: f(x) < 0$
or $LaTeX: y f(x) \geq 0$ for all $LaTeX: x \in X, \; y \geq 0, \; y \neq 0$.
(See NLP Myth 12 to avoid misconception.)