pith. sign in

arxiv: 2307.01034 · v2 · pith:GEUMJZAEnew · submitted 2023-07-03 · 🧮 math.OC

Hoffman constant of the argmin mapping in linear optimization

J. Camacho , M.J. C\'anovas , H. Gfrerer , J. Parra This is my paper

Pith reviewed 2026-05-24 07:35 UTC · model grok-4.3

classification 🧮 math.OC
keywords Hoffman constantargmin mappinglinear optimizationcalmness moduluspiecewise convex mappingstabilityright-hand side perturbation
0
0 comments X

The pith

The argmin mapping of a linear program has an exact point-based formula for its Hoffman constant under right-hand side perturbations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper derives the first exact formula for the Hoffman constant of the argmin mapping in linear optimization, which serves as the sharp Lipschitz constant on the mapping's domain. The derivation relies on introducing well-connected piecewise convex mappings and establishing that for these mappings the global Hoffman constant equals the supremum of local calmness moduli. A reader focused on stability in optimization would gain a precise, pointwise computable measure where previously only upper estimates were available.

Core claim

The paper provides a point-based expression for the Hoffman constant of the argmin mapping, understood as the sharp Lipschitz constant restricted to its domain. This expression is obtained in the parametric setting of right-hand side perturbations by showing that well-connected piecewise convex mappings satisfy an equality between the global Hoffman constant and the supremum of calmness moduli, with additional notes on directional stability of optimal solutions.

What carries the argument

Well-connected piecewise convex mapping, which equates the global Hoffman constant to the supremum of local calmness moduli and thereby yields the exact point-based formula.

If this is right

  • The Hoffman constant becomes computable from local point data rather than requiring global analysis.
  • Upper estimates from prior literature can be replaced by exact values for this class of mappings.
  • Directional stability properties of optimal solutions follow directly from the same local moduli.
  • The formula applies specifically to right-hand side perturbations of the constraint system in linear programs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equality between global and local constants may extend to other parametric optimization problems that admit a piecewise convex structure.
  • Numerical procedures could be designed to evaluate the point-based expression by sampling local calmness moduli at finitely many points.
  • The framework suggests a route to exact constants in nearby problems such as quadratic programming under similar perturbation models.

Load-bearing premise

The argmin mapping belongs to the class of well-connected piecewise convex mappings so that the global Hoffman constant equals the supremum of local calmness moduli.

What would settle it

A concrete linear program and right-hand side perturbation sequence where the distance from the perturbed argmin set to the original set exceeds the value predicted by the point-based Hoffman constant formula.

read the original abstract

The main goal of this paper is to provide a point-based expression for the Hoffman constant of the argmin mapping in linear optimization, understood as the sharp Lipschitz constant restricted to its domain. The work is mainly developed in the parametric context of right-hand side perturbations of the constraint system. To the authors' knowledge, this is the first exact formula for this constant, although we can find in the literature different upper estimates. The paper tackles this objective from a broader perspective, which introduces new tools of their own interest, such as the concept of well-connected piecewise convex mapping. We isolate the nice behavior of such mappings to derive a crucial equality between the Hoffman constant (which is a global stability measure) and the supremum of calmness moduli (of local nature). The paper also includes some specifics about directional stability of optimal solutions and finishes with some conclusions and notes about further research.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper derives a point-based expression for the Hoffman constant of the argmin mapping in linear optimization (under right-hand side perturbations), claimed to be the first exact formula. It introduces the class of well-connected piecewise convex mappings, proves that the argmin mapping belongs to this class, and uses this to establish equality between the global Hoffman constant and the supremum of local calmness moduli. The work also addresses directional stability of optimal solutions.

Significance. If the central derivation holds, the result is significant because it replaces existing upper estimates with an exact expression for a sharp global Lipschitz constant of the argmin mapping. The new mapping class and the global-local equality it enables may be of independent interest in variational analysis and stability theory for optimization problems. Credit is due for the explicit construction of the point-based formula and the isolation of the relevant mapping properties.

minor comments (3)
  1. The definition and properties of well-connected piecewise convex mappings (introduced to obtain the key equality) should be stated with explicit verification that the argmin mapping satisfies all required conditions; this would strengthen readability of the central argument.
  2. Notation for the Hoffman constant, calmness moduli, and the domain restriction should be made uniform across sections to avoid ambiguity when the equality is invoked.
  3. The discussion of directional stability would benefit from a brief comparison table or example contrasting the new formula with prior upper bounds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript, including the recognition of the significance of the exact point-based formula for the Hoffman constant and the introduction of well-connected piecewise convex mappings. The recommendation for minor revision is noted. However, the report lists no specific major comments under the MAJOR COMMENTS section, so there are no individual points requiring point-by-point rebuttal or revision at this stage. We remain available to address any additional minor suggestions or clarifications that may arise.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation introduces the class of well-connected piecewise convex mappings as a new tool, then proves membership of the argmin mapping in this class to obtain the equality between the global Hoffman constant and the supremum of local calmness moduli. This is presented as a direct consequence of the class properties rather than a self-referential definition, fitted input renamed as prediction, or load-bearing self-citation. The point-based formula follows from the established membership and the isolated behavior of the class, making the chain self-contained without reduction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

The central claim rests on the newly introduced concept of well-connected piecewise convex mappings and the equality it induces between global and local stability measures; no free parameters or external data fitting are mentioned.

invented entities (1)
  • well-connected piecewise convex mapping no independent evidence
    purpose: To isolate behavior that equates the global Hoffman constant with the supremum of local calmness moduli
    Introduced in the paper as a new tool to derive the exact formula

pith-pipeline@v0.9.0 · 5686 in / 1258 out tokens · 21985 ms · 2026-05-24T07:35:32.163453+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    AZ ´E, J.-N

    D. AZ ´E, J.-N. COR VELLEC, On the sensitivity Analysis of Hoffman constants for systems of linear inequalities , SIAM J. Optim. 12 (2002), pp. 913-927. 19

    work page 2002

  2. [2]

    CAMACHO, M

    J. CAMACHO, M. J. C ´ANOV AS, J. PARRA, From calmness to Hoff- man constants for linear semi-infinite inequality systems , SIAM J, Op- tim. 32 (2022), pp. 2859-2878

    work page 2022

  3. [3]

    CAMACHO, M

    J. CAMACHO, M. J. C ´ANOV AS, J. PARRA, Lipschitz up- per semicontinuity in linear optimization via local direc- tional convexity , Optimization, published online 06 Apr 2022, DOI:10.1080/02331934.2022.2057851

    work page doi:10.1080/02331934.2022.2057851 2022

  4. [4]

    M. J. C ´ANOV AS, R. HENRION, M. A. L ´OPEZ, J. PARRA, Outer limit for subdifferentials and calmness moduli in linear and nonlinear programming, J. Optim. Theory Appl. 169 (2016), pp. 925-952

    work page 2016

  5. [5]

    M. J. C ´ANOV AS, M. A. L´OPEZ, J. PARRA, F. J. TOLEDO, Calmness of the feasible set mapping for linear inequality systems , Set-Valued Var. Anal. 22 (2014), pp. 375–389

    work page 2014

  6. [6]

    A. L. DONTCHEV, R. T. ROCKAFELLAR, Implicit Functions and Solution Mappings: A View from Variational Analysis , Springer, New York, 2009

    work page 2009

  7. [7]

    GISBERT, M.J

    M.J. GISBERT, M.J. CANOV AS, J. PARRA, F.J. TOLEDO, Calm- ness of the optimal value in linear programming . SIAM J. Optim. 28 (2018), pp. 2201 - 2221

    work page 2018

  8. [8]

    M. A. GOBERNA, M. A. L ´OPEZ, Linear Semi-Infinite Optimization , John Wiley & Sons, Chichester (UK), 1998

    work page 1998

  9. [9]

    HOFFMAN, On approximate solutions of systems of linear in- equalities

    A.J. HOFFMAN, On approximate solutions of systems of linear in- equalities. J. Res. Natl. Bur. Stand. 49 (1952), pp. 263–265

    work page 1952

  10. [10]

    HU, Characterizations of the strong basic constraint qualificat ions

    H. HU, Characterizations of the strong basic constraint qualificat ions. Math Oper Res. 30 (2005), pp. 956-965

    work page 2005

  11. [11]

    KLATTE, B

    D. KLATTE, B. KUMMER, Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications , Nonconvex Optim. Appl. 60, Kluwer Academic, Dordrecht, The Netherlands, 200 2

    work page

  12. [12]

    KLATTE, G

    D. KLATTE, G. THIERE, Error bounds for solutions of linear equa- tions and inequalities Z. Oper. Res. 41 (1995), pp. 191-214

    work page 1995

  13. [13]

    LI, Sharp Lipschitz constants for basic optimal solutions and ba sic feasible solutions of linear programs

    W. LI, Sharp Lipschitz constants for basic optimal solutions and ba sic feasible solutions of linear programs. SIAM J. Control Optim. 32 (1994), pp. 140–153. 20

    work page 1994

  14. [14]

    TSENG, Error bounds and convergence analysis of feasible descent methods: a general approach

    Z, LUO, P. TSENG, Error bounds and convergence analysis of feasible descent methods: a general approach . Ann. Oper. Res. 46(1), 157–178 (1993)

    work page 1993

  15. [15]

    B. S. MORDUKHOVICH, Variational Analysis and Generalized Dif- ferentiation, I: Basic Theory , Springer, Berlin, 2006

    work page 2006

  16. [16]

    NECOARA, Y

    I. NECOARA, Y. NESTEROV, F. GLINEAUR, Linear convergence of first order methods for non-strongly convex optimization. Math. Pro- gram. 175, 69–107 (2019)

    work page 2019

  17. [17]

    PE ˜NA, D

    J. PE ˜NA, D. RODR ´IGUEZ, Polytope conditioning and linear conver- gence of the Frank–Wolfe algorithm. Math. Oper. Res. 44, 1–18 (2019)

    work page 2019

  18. [18]

    PE ˜NA, J.C

    J. PE ˜NA, J.C. VERA, L.F. ZULUAGA, New characterizations of Hoff- man constants for systems of linear constraints , Math. Program. 187 (2021), pp. 79–109

    work page 2021

  19. [19]

    R. T. ROCKAFELLAR, R. J-B. WETS, Variational Analysis , Springer, Berlin, 1998

    work page 1998

  20. [20]

    Z ˘ALINESCU, Sharp estimates for Hoffman ’s constant for systems of linear inequalities and equalities , SIAM J

    C. Z ˘ALINESCU, Sharp estimates for Hoffman ’s constant for systems of linear inequalities and equalities , SIAM J. Optim. 14 (2003), pp. 517-533

    work page 2003

  21. [21]

    Z. ZHOU, A. SO, A unified approach to error bounds for structured convex optimization problems . Math. Program. 165(2), 689–728 (2017) 21

    work page 2017