A path-following interior-point algorithm for linear and quadratic problems |
| |
Authors: | Stephen J. Wright |
| |
Affiliation: | (1) Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, 60439 Argonne, IL, USA |
| |
Abstract: | We describe an algorithm for the monotone linear complementarity problem (LCP) that converges from any positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementarity solution, the method converges subquadratically. We show that the algorithm and its convergence properties extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems.This research was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38. |
| |
Keywords: | Path-following interior-point methods linear complementarity problems Q-subquadratic convergence |
本文献已被 SpringerLink 等数据库收录! |
|