New characterizations of Hoffman constants for systems of linear constraints

• 成果类型: Article
• 署名作者: Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
• 署名单位: Carnegie Mellon University; Tilburg University; Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01473-6
• 发表日期: 2021
• 页码: 79-109
• 关键词: error-bounds; convex-optimization; 1st-order methods; Complexity theory; ill-posedness; distance; inequalities; continuity; geometry

摘要

We give a characterization of the Hoffman constant of a system of linear constraints in Rn relative to a reference polyhedron R. Rn. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = Rn, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose R. Rn is a reference polyhedron, A. Rmxn, and A( R) := {Ax : x. R}. We characterize the sharpest constant H( A| R) such that for all b. A( R) + Rm + and u R dist(u, PA(b) n R) = H( A|R) center dot ( Au - b)+ parallel to, where PA(b) = {x. Rn : Ax = b}. Our characterization is stated in terms of the largest of a canonical collection of easily computable Hoffman constants. Our characterization in turn suggests new algorithmic procedures to compute Hoffman constants.