Variable metric relaxation methods. II: The ellipsoid method
[For part I see Tech. Rep. SOL 81-16, Systems Optimization Laboratory, Oper. Res. Dept., Stanford Univ. (1981).] The deepest, or least shallow, cut ellipsoid method is a polynomial (time and space) method which finds an ellipsoid, representable by polynomial space integers, such that the maximal ellipsoidal distance relaxation method using this fixed ellipsoid is polynomial; this is equivalent to finding a linear transformation such that the maximal distance relaxation method of \textit{S. Agmon} [Can. J. Math. 6, 382-392 (1954; Zbl 0055.350)] and \textit{T. Motzkin} and \textit{I. J. Schoenberg} [ibid. 6, 393-404 (1954; Zbl 0055.350)] in this transformed space is polynomial. If perfect arithmetic is used, then the sequence of ellipsoids generated by the method converges to a set of ellipsoids, which share some of the properties of the classical Hessian at an optimum point of a function; and thus the ellipsoid method is quite analogous to a variable metric quasi-Newton method.
- A Bound on Solutions of Linear Integer Equalities and Inequalities
- Convergence of a cyclic ellipsoid algorithm for systems of linear equalities
- Feature Article—The Ellipsoid Method: A Survey
- scientific article; zbMATH DE number 3868523 (Why is no real title available?)
- scientific article; zbMATH DE number 3516928 (Why is no real title available?)
- scientific article; zbMATH DE number 3588394 (Why is no real title available?)
- scientific article; zbMATH DE number 3229353 (Why is no real title available?)
- scientific article; zbMATH DE number 3385445 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
- On the non-polynomiality of the relaxation method for systems of linear inequalities
- On the relationship between the Hausdorff distance and matrix distances of ellipsoids
- The ellipsoid method and its consequences in combinatorial optimization
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Solving Systems of Linear Inequalities
- Theorie der konvexen Körper
- Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
- Über die affine Exzentrizität konvexer Körper
- A deep cut ellipsoid algorithm for convex programming: Theory and applications
- The generalized ellipsoid method and its implementation
- scientific article; zbMATH DE number 3950214 (Why is no real title available?)
- scientific article; zbMATH DE number 3980933 (Why is no real title available?)
- scientific article; zbMATH DE number 566419 (Why is no real title available?)
- Goffin's algorithm for zonotopes
- On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data
- Non-standard approaches to integer programming
This page was built for publication: Variable metric relaxation methods. II: The ellipsoid method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683896)