Computing approximate solutions for convex conic systems of constraints

Citation
J. Pena et J. Renegar, Computing approximate solutions for convex conic systems of constraints, MATH PROGR, 87(3), 2000, pp. 351-383
Citations number
13
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
87
Issue
3
Year of publication
2000
Pages
351 - 383
Database
ISI
SICI code
0025-5610(200005)87:3<351:CASFCC>2.0.ZU;2-D
Abstract
We propose a way to reformulate a conic system of constraints as an optimiz ation problem. When an appropriate interior-point method (ipm) is applied t o the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forwar d-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of d istance to ill-posedness of the original conic system. The condition numbers of the lineal equations encountered when applying; an ipm influence the computational cost at each iteration. We show that For t he reformulation, the condition numbers of the linear equations are uniform ly bounded both when computing reasonably-accurate backward-approximate sol utions to arbitrary conic systems and when computing forward-approximate so lutions to well-conditioned conic systems.