Example of graph.
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.
f0(x):ℝn→ℝ to be minimized over the vector fi are convex; these constraints define a convex set ℰ(0)⊂ℝn defined as- P(0)≻0 and Q.
The output of the ellipsoid method is either:
- Any point in the polytope x(k) at the center of an ellipsoid
- g(k+1)T(x∗−x(k))⩽0.
We therefore conclude that
- x(k+1). The update is given by
- g(k)TP(k)g(k)⩽ϵ⇒f(x(k))−f(x∗)⩽ϵ.
Inequality-constrained minimization
editAt the k-th iteration of the algorithm for constrained minimization, we have a point fbest(k) recording the smallest objective value of feasible iterates so far. Depending on whether or not the point g0 that satisfies
- gj of 0' of the volume G.
- Given Data(p) and a point x in R, one can compute using poly(Size(p)) arithmetic operations:
- A separation oracle for G (that is: either assert that x is in G, or return a hyperplane separating x from G).
- A first-order oracle for f (that is: compute the value of f(x) and a subgradient f'(x)).
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 :
V(p)=[Vol(initial ellipsoid)Vol(G)]1/n≤[Vol(initial ellipsoid)MinVol(p)]1/n.
The ellipsoid method requires at most 0, then f*>2, for some polynomial. Therefore, we can pick the accuracy ε=2. Then, the ε-approximate solution found by the ellipsoid method will be positive, iff f*>0, iff the decision problem is unsolvable.
Variants
editThe ellipsoid method has several variants, depending on what cuts exactly are used in each step.
Different cuts
editIn the central-cut ellipsoid method, the cuts are always through the center of the current ellipsoid. The input is a rational number ε>0, a convex body K given by a weak separation oracle, and a number R such that S(0,R) (the ball of radius R around the origin) contains K. The output is one of the following:
- (a) A vector at a distance of at most ε from K, or --
- (b) A positive definite matrix A and a point a such that the ellipsoid E(A,a) contains K, and the volume of E(A,a) is at most ε.
The number of steps is O(n2)ln1ϵ iterations, where each iteration consists of finding a separating hyperplane and finding a new circumscribed ellipsoid. Finding a circumscribed ellipsoid requires O(n3.5+δ) time for some small 0 "}}'>δ>0.
The relative efficiency of the methods depends on the time required for finding a separating hyperplane, which depends on the application: if the runtime is t>2.5 then the inscribed method is more efficient.
Related methods
edit- The center-of-gravity method is a conceptually simpler method, that requires fewer steps. However, each step is computationally expensive, as it requires to compute the center of gravity of the current feasible polytope.
- Interior point methods, too, allow solving convex optimization problems in polynomial time, but their practical performance is much better than the ellipsoid method.
Matoušek, Jiří; Gärtner, Bernd (2007). Understanding and using linear programming. Universitext. Berlin; New York: Springer. ISBN 978-3-540-30697-9.Notes
edit- 1 2 3 Berkovich, Yudin David; Semenovich, Nemirovsky Arkady. "Informational Complexity and Efficient Methods for the Solution of Convex Extremal Problems". Matekon. 13 (2): 22–45. ISSN 0025-1127.
- ↑
- Given Data(p) and a point x in R, one can compute using poly(Size(p)) arithmetic operations:
- gj of 0' of the volume G.
| View original on Wikipedia | Back | FazBrowse Home |