Duality of Hoffman constants

2023/12/15 by Pena, Javier F., Vera, Juan C., Zuluaga, Luis F.
#90C05 #90C25 #90C57 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2312.09858

Abstract

Suppose A∈ ℝ^{m× n}, and R⊆ ℝⁿ and S⊆ ℝ^m are \em reference polyhedral cones with dual cones R^*⊆ ℝⁿ, S^*⊆ ℝ^m. We show that a suitable Slater condition implies a \em duality inequality between the Hoffman constants of the feasibility problems Ax-b ∈ S
x ∈ R and c-A\transp y ∈ R^*
y ∈ S^*. As an interesting application, we show a striking identity between the Hoffman constants of \em box-constrained feasibility problems with a similar primal-dual format, but where one of the reference sets is a box and the other is a linear subspace. We also establish a surprising identity between Hoffman constants of box-constrained feasibility problems and the chi condition measures for weighted least-squares problems.

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
• A weak constraint qualification for conic programs and a problem on duality gap
• A geometry in the set of solutions to ill-posed linear problems with box constraints: Applications to probabilities on discrete sets