A Unified Analysis of Hoffman’s Bound via Fenchel Duality
Authors:
- James V. BurkeJBJames V. Burke
- Paul TsengPTPaul Tseng
- 1 May 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 6 (2) , 265-282
Abstract
In 1952, Hoffman showed that the distance from any point to the solution set of a linear system is bounded above by a constant times the norm of the residual. Subsequently, this bound has been studied extensively and has found many practical uses. In this paper, we consider an extension of Hoffman’s bound to a partially infinite-dimensional setting in which the norm defining the distance is replaced by a positively homogeneous convex function and the linear system is replaced by a convex inclusion of the form $Ax - a \in K$, where A is a continuous linear operator from some normed linear space into $\mathbf{R}^m ,a$ is an element of the range space of A, and K is a nonempty closed convex cone in $\mathbf{R}^m $. When specialized to the finite-dimensional case, we unify and extend many existing results on Hoffman’s bound. Our analysis is based on the use of Fenchel duality to express the distance as the supremum of a certain concave function over a bounded subset of the polar of K. Much of our analysis also extends to the case where K is a nonempty closed convex set, not only a convex cone.
Keywords
This publication has 32 references indexed in Scilit:
- A note of Lipschitz constants for solutions of linear inequalities and equationsLinear Algebra and its Applications, 1996
- Approximations to Solutions to Systems of Linear InequalitiesSIAM Journal on Matrix Analysis and Applications, 1995
- Sharp Lipschitz Constants for Basic Optimal Solutions and Basic Feasible Solutions of Linear ProgramsSIAM Journal on Control and Optimization, 1994
- The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear programLinear Algebra and its Applications, 1993
- The distance to a polyhedronLinear Algebra and its Applications, 1992
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth MinimizationSIAM Journal on Control and Optimization, 1992
- On approximate solutions of infinite systems of linear inequalitiesLinear Algebra and its Applications, 1989
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity ProblemsSIAM Journal on Control and Optimization, 1987
- An Application of Error Bounds for Convex Programming in a Linear SpaceSIAM Journal on Control, 1975
- Bounds for error in the solution set of a perturbed linear programLinear Algebra and its Applications, 1973