Ellipsoid method
Description

A convex minimization problem consists of the following ingredients.

We are also given an initial ellipsoid E (0) ⊂ R n {\displaystyle {\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}} defined as

containing a minimizer x ∗ {\displaystyle x^{*}}, where P (0) ≻ 0 {\displaystyle P_{(0)}\succ 0} and x 0 {\displaystyle x_{0}} is the center of E {\displaystyle {\mathcal {E}}}.

Finally, we require the existence of a separation oracle for the convex set Q {\displaystyle Q}. Given a point x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}}, the oracle should return one of two answers:

The output of the ellipsoid method is either:

Inequality-constrained minimization of a function that is zero everywhere corresponds to the problem of simply identifying any feasible point. It turns out that any linear programming problem can be reduced to a linear feasibility problem (e.g. minimize the zero function subject to some linear inequality and equality constraints). One way to do this is by combining the primal and dual linear programs together into one program, and adding the additional (linear) constraint that the value of the primal solution is no worse than the value of the dual solution. Another way is to treat the objective of the linear program as an additional constraint, and use binary search to find the optimum value.
detectable_content:postscript