Ellipsoid method

From Glossary

Jump to: navigation, search

This algorithm seeks to solve LaTeX: Ax \le b by iterations that begin with LaTeX: x=0 and LaTeX: Q=\mbox{diag}(2^{-L}), where LaTeX: L is a measure of the smallest datum that can be represented -- i.e., LaTeX: x is a solution if, and only if, it satisfies LaTeX: Ax \le b + 2^{-L}. If the current iterate, LaTeX: x, does not satisfy this, a new pair LaTeX: (x', Q') is defined by choosing one of the violated inequalities, say LaTeX: A_{i,*}x > b_i. Then, let LaTeX: v = A_{i,*}^T, and apply the following rules:

  1. LaTeX:  x' = \frac{1} {(n+1)\sqrt{v'Qv}} \; (x - Qv)
  2. LaTeX:  Q' = \frac{n^2}{(n^2 - 1)(n+1) (v^T Q v)} \; (Q - 2 v v^T)
Now LaTeX: E(x',Q') defines an ellipsoid centered at LaTeX: x', and it contains all the feasible points in LaTeX: E(x,Q). After at most LaTeX: O(n^2 L) iterations, the algorithm terminates with a solution, or with the fact that no solution exists.

By treating the objective as a constraint, say LaTeX: c^T x \le c^Tx^* - e and/or LaTeX: c^T x \ge c^Tx^* + e, the ellipsoid method can be used to solve a linear program. Its significance is that it was the first algorithm for linear programming shown to have polynomial time complexity.


Views
Personal tools