Alternative systems

From Glossary

Jump to: navigation, search



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


Views
Personal tools