On strata of degenerate polyhedral cones I : Condition and distance to strata
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 23-28 |
Journal / Publication | European Journal of Operational Research |
Volume | 198 |
Issue number | 1 |
Publication status | Published - 1 Oct 2009 |
Link(s)
Abstract
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.
Research Area(s)
- Condition numbers, Degeneracy, Polyhedral conic systems
Citation Format(s)
On strata of degenerate polyhedral cones I: Condition and distance to strata. / Cheung, Dennis; Cucker, Felipe; Peña, Javier.
In: European Journal of Operational Research, Vol. 198, No. 1, 01.10.2009, p. 23-28.
In: European Journal of Operational Research, Vol. 198, No. 1, 01.10.2009, p. 23-28.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review