Authors

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.