Global error bounds for convex conic problems

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 languageEnglish (US)
Pages (from-to)836-851
Number of pages16
JournalSIAM Journal on Optimization
Volume10
Issue number3
DOIs
StatePublished - 2000

Bibliographical note

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

  • Condition number
  • Convex conic problems
  • Error bound

Fingerprint Dive into the research topics of 'Global error bounds for convex conic problems'. Together they form a unique fingerprint.

Cite this