Containing and shrinking ellipsoids in the path-following algorithm |
| |
Authors: | Yinyu Ye Michael J Todd |
| |
Institution: | (1) Department of Management Sciences, The Univeristy of Iowa, Iowa City, IA, USA;(2) Department of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, USA |
| |
Abstract: | We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio
, in comparison to 2– (1) in Karmarkar's algorithm and 2– (1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.Research supported by The U.S. Army Research Office through The Mathematical Sciences Institute of Cornell University when the author was visiting at Cornell.Research supported in part by National Science Foundation Grant ECS-8602534 and Office of Naval Research Contract N00014-87-K-0212. |
| |
Keywords: | Linear programming convex quadratic programming path-following algorithm Karmarkar's algorithm ellipsoid method |
本文献已被 SpringerLink 等数据库收录! |
|