In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets, generating a sequence of ellipsoids whose volume uniformly decreases at every step while continuing to enclose a minimizer of the function. When specialized to solving feasible linear optimization problems with rational data, it becomes an algorithm that finds an optimal solution in a number of steps polynomial in the size of the input.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.