Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems |
| |
Authors: | Y Nesterov MJ Todd Y Ye |
| |
Institution: | (1) CORE, Catholic University of Louvain, Louvain-Neuve, Belgium, e-mail: nesterov@core.ucl.ac.be. Research supported in part by the Russian Fund for Fundamental Research through grant N96-01-00293, BE;(2) School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853, e-mail: miketodd@cs.cornell.edu. Research supported in part by NSF through grant DMS-9505155 and ONR through grant N00014-96-1-0050, US;(3) Department of Management Science, The University of Iowa, Iowa City, IA 52242, e-mail: yyye@dollar.biz.uiowa.edu. Research supported in part by NSF Grants DDM-9207347 and DMI-9522507, US |
| |
Abstract: | ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρf is a feasibility measure.
We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility
(primal or dual) can be detected in O(ln) iterations, where ρ· is a primal or dual infeasibility measure.
Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998 |
| |
Keywords: | : convex programming – infeasibility detection – homogeneous self-dual model – primal-dual interior-point algorithms – infeasible-start methods |
本文献已被 SpringerLink 等数据库收录! |
|