An algorithm to compute the Hoffman constant of a system of linear constraints
arXiv:1804.08418
Abstract
We propose a combinatorial algorithm to compute the Hoffman constant of a system of linear equations and inequalities. The algorithm is based on a characterization of the Hoffman constant as the largest of a finite canonical collection of easy-to-compute Hoffman constants. Our algorithm and characterization extend to the more general context where some of the constraints are easy to satisfy as in the case of box constraints. We highlight some natural connections between our characterizations of the Hoffman constant and Renegar's distance to ill-posedness for systems of linear constraints.
arXiv comment28 pages, 1 figure
References in corpus (6)
- On the Global Linear Convergence of Frank-Wolfe Optimization Variants
- A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
- Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins
- Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques
- The condition of a function relative to a polytope
- A stroll in the jungle of error bounds