Skip to content

Jing Jian: Ellipsoid algorithm

by on February 21, 2012

My favorite algorithm is the ellipsoid algorithm in solving linear program-
ming problems. The algorithm uses the duality theorem to first transform a min-
imization/maximization linear programming problem into a problem of fi nding
a feasible solution for a linear system. Let P = {ax = b} be a system of linear
inequalities (x and b are vectors). Let the point set E = {(x-z)^T D^{-1} (x-z)} be
a generalized ellipsoid containing the polytope defi ned by P centered at point
z. The algorithm is as follows:
We start with E and test to see if z satis es P: if it does, the algorithm ter-
minates; if it does not, we find the hyperplane defi ned by the violated constraint
and nd ellipsoid that contains the half of E on the other side of the hyperplane.
We substitute the smaller ellipsoid for E and repeat the above procedure until
the ellipsoid’s center is a feasible point.
The algorithm terminates in O(n^6). The analysis of the algorithm bases on
upper bounding the size of the original ellipsoid and lower bounding the size of
the nal ellipsoid using the fact that our input is polynomial sized. Combined
with the fact that with each iteration of the loop the size of the ellipsoid shrinks
by a constant ratio.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: