Ellipsoid method

Ellipsoid method

The ellipsoid method is an algorithm for solving convex optimization problems. It was introduced by Naum Z. Shor, Arkady Nemirovsky, and David B. Yudin in 1972, and used by Leonid Khachiyan to prove the polynomial-time solvability of linear programs. At the time, the ellipsoid method was the only algorithm for solving linear programs whose runtime was provably polynomial. However, the interior-point method and variants of the simplex algorithm are much faster than the ellipsoid method, in both theory and practice. The algorithm works by enclosing the minimizer of a convex function in a sequence of ellipsoids whose volume decreases at each iteration.

Description

A convex optimization problem consists of a convex function f_0(x): mathbb{R}^n o mathbb{R} to be minimized over the variable x, convex inequality constraints of the form f_i(x) leq 0, where the functions f_i are convex, and 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) leq 1 ight }

containing the minimizer x^*, where P succ 0 and x_0 is the center of mathcal{E}. Finally, we require the existence of a cutting-plane oracle for the function f . One example of a cutting-plane is given by the subgradient g of f .

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 : x^T P_{(k)}^{-1} x leq 1 ight }. We query the cutting-plane oracle to obtain a vector g^{(k+1)} in mathbb{R}^n such that g^{(k+1)T} (x^* - x^{(k)} ) leq 0. We therefore conclude that

:x^* in mathcal{E}^{(k)} cap {z: g^{(k+1)T} (z - x^{(k)} ) leq 0 }.

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

:x^{(k+1)} = x^{(k)} - frac{1}{n+1} P_{(k)} ilde{g}^{(k+1)}:P_{(k+1)} = frac{n^2}{n^2-1} left(P_{(k)} - frac{2}{n+1} P_{(k)} ilde{g}^{(k+1)} ilde{g}^{(k+1)T} P_{(k)} ight )

where ilde{g}^{(k+1)} = (1/sqrt{g^{(k+1)T} P g^{(k+1))g^{(k+1)}. The stopping criterion is given by the property that

sqrt{g^{(k)T}P_{(k)}g^{(k) leq epsilon Rightarrow f(x^{(k)}) - f(x^*) leq 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_{ m{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_{ m{best^{(k)} leq 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)})leq 0

for all feasible z .

Application to Linear Programming

Performance

The ellipsoid method is rarely used in practice due to poor practical performance and is used almost exclusively as an educational tool to prove the polynomial complexity of linear programs.

External links

* [http://www.stanford.edu/class/ee364/ EE364] and [http://www.stanford.edu/class/ee364b/ EE364b] , a Stanford course homepage


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Ellipsoid — This article is about the shape. For the type of theatrical spotlight, see ellipsoidal reflector spotlight. For the surface that approximates the figure of the Earth, see reference ellipsoid. triaxial redirects here. For the electrical cable, see …   Wikipedia

  • Newton's method — In numerical analysis, Newton s method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real valued function. The… …   Wikipedia

  • Iterative method — In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination… …   Wikipedia

  • Newton's method in optimization — A comparison of gradient descent (green) and Newton s method (red) for minimizing a function (with small step sizes). Newton s method uses curvature information to take a more direct route. In mathematics, Newton s method is an iterative method… …   Wikipedia

  • Nelder–Mead method — Nelder–Mead simplex search over the Rosenbrock banana function (above) and Himmelblau s function (below) See simplex algorithm for Dantzig s algorithm for the problem of linear opti …   Wikipedia

  • Nonlinear conjugate gradient method — In numerical optimization, the nonlinear conjugate gradient method generalizes the conjugate gradient method to nonlinear optimization. For a quadratic function : The minimum of f is obtained when the gradient is 0: . Whereas linear conjugate… …   Wikipedia

  • Cutting-plane method — In mathematical optimization, the cutting plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to… …   Wikipedia

  • Interior point method — Interior point methods (also referred to as barrier methods) are a certain class of algorithms to solve linear and nonlinear convex optimization problems. These algorithms have been inspired by Karmarkar s algorithm, developed by Narendra… …   Wikipedia

  • Poinsot's ellipsoid — In classical mechanics, Poinsot s construction is a geometrical method for visualizing the torque free motion of a rotating rigid body, that is, the motion of a rigid body on which no external forces are acting. This motion has four constants:… …   Wikipedia

  • Bestanschließendes Ellipsoid — Als bestanschließendes Ellipsoid wird ein aus geodätischen Messungen abgeleitetes Referenzellipsoid bezeichnet, das sich der regionalen Erdkrümmung eines Staatsgebietes oder eines Kontinents am besten anschmiegt. Die Parameter dieses regionalen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”