Ellipsoid method

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.

History

The ellipsoid method has a long history. As an iterative method, a preliminary version was introduced by Naum Z. Shor. In 1972, an approximation algorithm for real convex minimization was studied by Arkadi Nemirovski and David B. Yudin (Judin). As an algorithm for solving linear programming problems with rational data, the ellipsoid algorithm was studied by Leonid Khachiyan; Khachiyan's achievement was to prove the polynomial-time solvability of linear programs.

This was a notable step from a theoretical perspective: The standard algorithm for solving linear problems at the time was the simplex algorithm, which has a run time that typically is linear in the size of the problem, but for which examples exist for which it is exponential in the size of the problem. As such, having an algorithm that is guaranteed to be polynomial for all cases was a theoretical breakthrough.

Khachiyan's work showed, for the first time, that there can be algorithms for solving linear programs whose runtime can be proven to be polynomial. In practice, however, the algorithm is fairly slow and of little practical interest, though it provided inspiration for later work that turned out to be of much greater practical use. Specifically, Karmarkar's algorithm, an interior-point method, is much faster than the ellipsoid method in practice. Karmarkar's algorithm is also faster in the worst case.

The ellipsoidal algorithm allows complexity theorists to achieve (worst-case) bounds that depend on the dimension of the problem and on the size of the data, but not on the number of rows, so it remained important in combinatorial optimization theory for many years. Only in the 21st century have interior-point algorithms with similar complexity properties appeared.

Description

A convex minimization problem consists of the following ingredients. A convex function f_0(x): \mathbb{R}^n \to \mathbb{R} to be minimized over the vector x (containing n variables); Convex inequality constraints of the form f_i(x) \leqslant 0 , where the functions f_i are convex; these constraints define a convex set Q . Linear equality constraints of the form h_i(x) = 0 .

We are also given an initial ellipsoid \mathcal{E}^{(0)} \subset \mathbb{R}^n defined as \mathcal{E}^{(0)} = \left \{z \in \mathbb{R}^n \ : \ (z - x_0)^T P_{(0)}^{-1} (z-x_0) \leqslant 1 \right \} containing a minimizer x^* , where P_{(0)} \succ 0 and x_0 is the center of \mathcal{E} . Finally, we require the existence of a separation oracle for the convex set Q .

Given a point x\in \mathbb{R}^n , the oracle should return one of two answers: "The point x is in Q ", or - "The point x is not in Q , and moreover, here is a hyperplane that separates x from Q ", that is, a vector c such that c\cdot x for all y\in Q . The output of the ellipsoid method is either: Any point in the polytope Q (i.e., any feasible point), or - A proof that Q is empty. 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 (i.e. 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.

Unconstrained minimization

At the k-th iteration of the algorithm, we have a point x^{(k)} at the center of an ellipsoid \mathcal{E}^{(k)} = \left \{x \in \mathbb{R}^n \ : \ \left (x-x^{(k)} \right )^T P_{(k)}^{-1} \left (x-x^{(k)} \right ) \leqslant 1 \right \}. We query the cutting-plane oracle to obtain a vector g^{(k+1)} \in \mathbb{R}^n such that g^{(k+1)T} \left (x^* - x^{(k)} \right ) \leqslant 0. We therefore conclude that x^* \in \mathcal{E}^{(k)} \cap \left \{z \ : \ g^{(k+1)T} \left (z - x^{(k)} \right ) \leqslant 0 \right \}.

We set \mathcal{E}^{(k+1)} to be the ellipsoid of minimal volume containing the half-ellipsoid described above and compute x^{(k+1)} . The update is given by \begin{align} x^{(k+1)} &= x^{(k)} - \frac{1}{n+1} P_{(k)} \tilde{g}^{(k+1)} \\ P_{(k+1)} &= \frac{n^2}{n^2-1} \left(P_{(k)} - \frac{2}{n+1} P_{(k)} \tilde{g}^{(k+1)} \tilde{g}^{(k+1)T} P_{(k)} \right ) \end{align} where \tilde{g}^{(k+1)} = \left (\frac{1}{\sqrt{g^{(k+1)T} P_{(k)} g^{(k+1)}}} \right )g^{(k+1)}.

The stopping criterion is given by the property that \sqrt{g^{(k)T}P_{(k)}g^{(k)}} \leqslant \epsilon \quad \Rightarrow \quad f (x^{(k)} ) - f \left(x^* \right ) \leqslant \epsilon.

Inequality-constrained minimization

At the k-th iteration of the algorithm for constrained minimization, we have a point x^{(k)} at the center of an ellipsoid \mathcal{E}^{(k)} as before. We also must maintain a list of values f_{\rm{best}}^{(k)} recording the smallest objective value of feasible iterates so far.

Depending on whether or not the point x^{(k)} is feasible, we perform one of two tasks: If x^{(k)} is feasible, perform essentially the same update as in the unconstrained case, by choosing a subgradient g_0 that satisfies g_0^T (x^*-x^{(k)} ) + f_0 (x^{(k)} ) - f_{\rm{best}}^{(k)} \leqslant 0 If x^{(k)} is infeasible and violates the j-th constraint, update the ellipsoid with a feasibility cut. Our feasibility cut may be a subgradient g_j of f_j which must satisfy g_j^T (z-x^{(k)} ) + f_j (x^{(k)} )\leqslant 0 for all feasible z.

Under these assumptions, the ellipsoid method is "R-polynomial". This means that there exists a polynomial Poly such that, for every problem-instance p and every approximation-ratio ε>0, the method finds a solution x satisfying : f(x) - \min_G f \leq \varepsilon\cdot [\max_G f - \min_G f] , using at most the following number of arithmetic operations on real numbers: Poly(Size(p))\cdot \ln\left(\frac{V(p)}{\epsilon}\right) where V(p) is a data-dependent quantity.

Intuitively, it means that the number of operations required for each additional digit of accuracy is polynomial in Size(p). In the case of the ellipsoid method, we have: V(p) = \left[\frac{Vol(\text{initial ellipsoid})}{Vol(G)}\right]^{1/n} \leq\left[\frac{Vol(\text{initial ellipsoid})}{MinVol(p)}\right]^{1/n} . The ellipsoid method requires at most 2(n-1)n\cdot \ln\left(\frac{V(p)}{\epsilon}\right) steps, and each step requires Poly(Size(p)) arithmetic operations. Step 1: reducing optimization to search.

The theorem of linear programming duality says that we can reduce the above minimization problem to the search problem: find x,y s.t. Ax ≤ b ; A T y = c ; y ≤ 0 ; c T x=b T y. The first problem is solvable iff the second problem is solvable; in case the problem is solvable, the x-components of the solution to the second problem are an optimal solution to the first problem. Therefore, from now on, we can assume that we need to solve the following problem: find z ≥ 0 s.t. Rz ≤ r.

Multiplying all rational coefficients by the common denominator, we can assume that all coefficients are integers. Step 2: reducing search to feasibility-check. The problem find z ≥ 0 s.t. Rz ≤ r can be reduced to the binary decision problem: "is there a z ≥ 0 such that Rz ≤ r?". This can be done as follows. If the answer to the decision problem is "no", then the answer to the search problem is "None", and we are done.

Otherwise, take the first inequality constraint R 1 z ≤ r 1 ; replace it with an equality R 1 z = r 1 ; and apply the decision problem again. If the answer is "yes", we keep the equality; if the answer is "no", it means that the inequality is redundant, and we can remove it. Then we proceed to the next inequality constraint. For each constraint, we either convert it to equality or remove it. Finally, we have only equality constraints, which can be solved by any method for solving a system of linear equations.

Step 3: the decision problem can be reduced to a different optimization problem. Define the residual function f(z) := max[(Rz) 1 -r 1 , (Rz) 2 -r 2 , (Rz) 3 -r 3 ,...]. Clearly, f(z)≤0 iff Rz ≤ r. Therefore, to solve the decision problem, it is sufficient to solve the minimization problem: min z f(z). The function f is convex (it is a maximum of linear functions). Denote the minimum value by f*. Then the answer to the decision problem is "yes" iff f*≤0.

Step 4: In the optimization problem min z f(z), we can assume that z is in a box of side-length 2 L , where L is the bit length of the problem data. Thus, we have a bounded convex program, that can be solved up to any accuracy ε by the ellipsoid method, in time polynomial in L. Step 5: It can be proved that, if f*>0, then f*>2 -poly(L) , for some polynomial. Therefore, we can pick the accuracy ε=2 -poly(L) . Then, the ε-approximate solution found by the ellipsoid method will be positive, iff f*>0, iff the decision problem is unsolvable.

The number of steps is N := \lceil 5n \log(1/\epsilon) + 5n^2 \log(2R)\rceil , the number of required accuracy digits is p := 8N, and the required accuracy of the separation oracle is d := 2 −p . In the deep-cut ellipsoid method, the cuts remove more than half of the ellipsoid in each step. This makes it faster to discover that K is empty. However, when K is nonempty, there are examples in which the central-cut method finds a feasible point faster. The use of deep cuts does not change the order of magnitude of the run-time.

In the shallow-cut ellipsoid method, the cuts remove less than half of the ellipsoid in each step. This variant is not very useful in practice, but it has theoretical importance: it allows to prove results that cannot be derived from other variants. The input is a rational number ε>0, a convex body K given by a shallow separation oracle, and a number R such that S(0,R) contains K.

The output is a positive definite matrix A and a point a such that one of the following holds: (a) The ellipsoid E(A,a) has been declared "tough" by the oracle, or - (b) K is contained in E(A,a) and the volume of E(A,a) is at most ε. The number of steps is N := \lceil 5n(n+1)^2 \log(1/\epsilon) + 5n^2(n+1)^2 \log(2R) + \log(n+1)\rceil , and the number of required accuracy digits is p := 8N.

Notes

Further reading

Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.) V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37. V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45. George B. Dantzig and Mukund N. Thapa. 1997.

Linear programming 1: Introduction. Springer-Verlag. George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag. L. Lovász: An Algorithmic Theory of Numbers, Graphs, and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986 Kattta G. Murty, Linear Programming, Wiley, 1983. M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999. Christos H.

Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover. Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998,

External links

EE364b, a Stanford course homepage

Text derived from https://en.wikipedia.org/w/index.php?oldid=1339374437 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.