caa a22 4500 475769333 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000501xx s 000 0 eng 10.1007/s101070050001 doi (NATIONALLICENCE)springer-10.1007/s101070050001 Computing approximate solutions for convex conic systems of constraints [Elektronische Daten] [J. Peña, J. Renegar] Abstract. : We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to 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 forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.¶The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Springer-Verlag Berlin Heidelberg, 2000 Mathematics Subject Classification (1991): 49M50, 65F35, 90C25, 90C51, 90C60 nationallicence Peña J. Graduate School of Industrial Administration, Carnegie Mellon University¶e-mail: jfp@andrew.cmu.edu, US aut Renegar J. School of Operations Research and Industrial Engineering, Cornell University¶e-mail: renegar@orie.cornell.edu, US aut https://doi.org/10.1007/s101070050001 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070050001 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Peña J. Graduate School of Industrial Administration, Carnegie Mellon University¶e-mail: jfp@andrew.cmu.edu, US aut NATIONALLICENCE 700 1- Renegar J. School of Operations Research and Industrial Engineering, Cornell University¶e-mail: renegar@orie.cornell.edu, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer