Abstract
This paper aims at deriving and proving some Lipschitzian-type error bounds for convex conic problems in a simple way. First, it is shown that if the recession directions satisfy Slater's condition, then a global Lipschitzian-type error bound holds. Alternatively, if the feasible region is bounded, then the ordinary Slater condition guarantees a global Lipschitzian-type error bound. These can be considered as generalizations of previously known results for inequality systems, which also follow from general results by Bauschke and Borwein in [SIAM Review, 38 (1996), pp. 367-426] and Bauschke, Borwein, and Li in a 1997 report. However, the proofs in the current paper are considerably simpler. Some of the results are generalized to the intersection of multiple shifted cones (with different shifts). Under Slater's condition alone, a global Lipschitzian-type error bound does not hold. It is shown, however, that such an error bound holds for a specific conic region. For linear systems we establish that the sharp constant involved in Huffman's error bound is nothing but the condition number for linear programming as used by Vavasis and Ye in [Math. Programming, 74 (1996), pp. 79-120].
Original language | English (US) |
---|---|
Pages (from-to) | 836-851 |
Number of pages | 16 |
Journal | SIAM Journal on Optimization |
Volume | 10 |
Issue number | 3 |
DOIs | |
State | Published - 2000 |
Bibliographical note
Copyright:Copyright 2017 Elsevier B.V., All rights reserved.
Keywords
- Condition number
- Convex conic problems
- Error bound