TY - JOUR
T1 - On strata of degenerate polyhedral cones I
T2 - Condition and distance to strata
AU - Cheung, Dennis
AU - Cucker, Felipe
AU - Peña, Javier
PY - 2009/10/1
Y1 - 2009/10/1
N2 - Systems Ay ≥ 0 with a degenerate cone of solutions are considered ill-posed since finite-precision algorithms are not expected to find points in the cone of solutions. Consequently, common condition numbers for these systems, such as C (A) [J. Renegar. Some perturbation theory for linear programming, Mathematical Programming 65 (1994) 73-91] and C (A) [D. Cheung, F. Cucker, A new condition number for linear programming, Mathematical Programming 91 (2001) 163-174], which are based on the notion of distance to the nearest ill-posed problem, become infinite on such ill-posed instances. In this paper, we extend these two condition numbers to versions over(C, -) (A) and over(C, -) (A) which are always finite. Both condition numbers can be expressed in terms of a distance to a change in the geometry of the cone of solutions. The main result shows that for both of them, the distance corresponds to a notion of best conditioned solution for a canonical complementarity problem associated to the system Ay ≥ 0. © 2008 Elsevier B.V. All rights reserved.
AB - Systems Ay ≥ 0 with a degenerate cone of solutions are considered ill-posed since finite-precision algorithms are not expected to find points in the cone of solutions. Consequently, common condition numbers for these systems, such as C (A) [J. Renegar. Some perturbation theory for linear programming, Mathematical Programming 65 (1994) 73-91] and C (A) [D. Cheung, F. Cucker, A new condition number for linear programming, Mathematical Programming 91 (2001) 163-174], which are based on the notion of distance to the nearest ill-posed problem, become infinite on such ill-posed instances. In this paper, we extend these two condition numbers to versions over(C, -) (A) and over(C, -) (A) which are always finite. Both condition numbers can be expressed in terms of a distance to a change in the geometry of the cone of solutions. The main result shows that for both of them, the distance corresponds to a notion of best conditioned solution for a canonical complementarity problem associated to the system Ay ≥ 0. © 2008 Elsevier B.V. All rights reserved.
KW - Condition numbers
KW - Degeneracy
KW - Polyhedral conic systems
UR - http://www.scopus.com/inward/record.url?scp=62749116591&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-62749116591&origin=recordpage
U2 - 10.1016/j.ejor.2008.07.012
DO - 10.1016/j.ejor.2008.07.012
M3 - 21_Publication in refereed journal
VL - 198
SP - 23
EP - 28
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -