0x410 Linear Optimization


Definition (Standard form) The following form is the standard form of a linear programming problem. This form is computationally more convenient, in particular for simplex and interior-point methods

$$\min_x c^T x$$

$$s.t: Ax = b, x \geq 0$$

  • Inequality constraints can be reduced to these forms by introducing non-negative slack variables.
  • Unconstrainted variables can be represented as a diff of two non-negative numbers $x_i – x_j$.

The Geometry of Linear Programming

Definition (polyhedron) A polyhedron is a set that can be described in the following form where $A \in R^{m \times n}, b \in R^m$

$$\{ x \in R^n | Ax \geq b \}$$

A set of the form $\{ x \in R^n | Ax =b, x \geq 0\}$ is also a polyhedron and called polyhedron in standard form.

Definition (hyperspace, halfspace) Let $a \in R^n$ and $b \in R$

  • The set $\{ x \in R^n | a^T x = b \}$ is called a hyperplane
  • The set $\{ x in R^n | a^T x \geq b \}$ is called a halfspace

Definition (extreme point) Let $P$ be a polyhedron. A vector $x \in P$ is an extreme point if $x$ cannot be expressed by a convex combination of two other points in $P$


[1] Bertsimas, Dimitris, and John N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997.