New characterizations of Hoffman constants for systems of linear constraints

2019/05/07 by Pena, Javier, Vera, Juan, Zuluaga, Luis · 5 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1905.02894

Abstract

We give a characterization of the Hoffman constant of a system of linear constraints in \Rⁿ \em relative to a \em reference polyhedron R⊆\Rⁿ. The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case R = \Rⁿ, we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose R⊆ ℝⁿ is a reference polyhedron, A∈ \R^{m× n}, and A(R):=\Ax: x∈ R\. We characterize the sharpest constant H(A|R) such that for all b ∈ A(R) + \R^m₊ and u∈ R \dist(u, P_A(b)∩ R) ≤ H(A|R) ⋅ ‖(Au-b)₊‖, where P_A(b) = \x∈ \Rⁿ: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.

Cited by

• Linear Convergence and Error Bounds for Optimization Without Strong Convexity
• Desirable Effort Fairness and Optimality Trade-offs in Strategic Learning
• Lipschitzianity of expected value under decision-dependent uncertainty with moving support
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
• Lipschitz upper semicontinuity of linear inequality systems under full perturbations

Related

• An algorithm to compute the Hoffman constant of a system of linear constraints
• Duality of Hoffman constants
• An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
• From calmness to Hoffman constants for linear semi-infinite inequality systems
• Hoffman constant of the argmin mapping in linear optimization