An easily computable upper bound on the Hoffman constant for homogeneous inequality systems

2023/02/04 by Peña, Javier · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2302.02193

Abstract

Let A∈ ℝ^{m× n}∖ \0\ and P:=\x:Ax≤ 0\. This paper provides a procedure to compute an upper bound on the following homogeneous Hoffman constant: H₀(A) := sup_{u∈ ℝⁿ ∖ P} (dist(u,P))/(dist(Au, ℝ^m_-)). In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely tractable and easily implementable.

Cited by

• Beyond Expectation: Concentration Inequalities for Randomized Iterative Methods
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

Related

• New characterizations of Hoffman constants for systems of linear constraints
• An algorithm to compute the Hoffman constant of a system of linear constraints
• From calmness to Hoffman constants for linear semi-infinite inequality systems
• Hoffman constant of the argmin mapping in linear optimization
• The sup-norm vs. the norm of the coefficients: equivalence constants for homogeneous polynomials