A survey on error bounds for lower semicontinuous functions

We survey ancient and recent results on global error bounds for the distance to a sublevel set of a lower semicontinuous function defined on a complete metric space. We emphasize the case of a recent characterization of this property which appeared in [CITE]. We also review the convex case and show how the known result on sufficient condition for a global error bound can be derived from the quoted characterization.

Related papers:

title: On approximate solutions of systems of linear inequalities
abstract: (briefly, ), one arrives at a vector JC that "almost" satisfies (1). It is almost obvious geometrically that, if (1) is consistent, one can infer that there is a solution x0 of (1) "close" to x. The purpose of this report is to justify and formulate precisely this assertion. We shall use fairly general definitions of functions that measure the size of vectors, since it may be possible to obtain better estimates of the constant c (whose important role is described in the statement of the theorem) for some measuring functions than for others. We shall make a few remarks on the estimation of c after completing the proof of the main theorem.

title: Stability Theory for Systems of Inequalities, Part II: Differentiable Nonlinear Systems
abstract: This paper develops a condition for stability of the solution set of a system of nonlinear inequalities over a closed convex set in a Banach space, when the functions defining the inequalities are ...

title: A Condition Number for Differentiable Convex Inequalities
abstract: For a system of differentiable convex inequalities, a new bound is given for the absolute error in an infeasible point in terms of the absolute residual. By using this bound a condition number is defined for the system of inequalities which gives a bound for the relative error in an infeasible point in terms of the relative residual.

title: Global Regularity Theorems
abstract: For a system of nondifferentiable convex inequalities and linear equalities, the best bound is given for the quotient of the distance of an infeasible point and the norm of the residual vector. Applications to stability theory are then obtained.

title: Asymptotic constraint qualifications and global error bounds for convex inequalities
abstract: In this paper we study various asymptotic constraint qualifications for the existence of global error bounds for approximate solutions of convex inequalities. Many known conditions that ensure the existence of such a global error bound are shown to be equivalent to one of the following three conditions: (i) the bounded excess condition, (ii) Slater condition together with the asymptotic constraint qualification defined by Auslender and Crouzeix , and (iii) positivity of normal directional derivatives of the maximum of the constraint functions introduced by Lewis and Pang .

title: Computable Error Bounds For Convex Inequality Systems In Reflexive Banach Spaces
abstract: In 1952, A. J. Hoffman proved a fundamental result of an error bound on the distance from any point to the solution set of a linear system in $\hbox{{\bbb R}}^n$. In SIAM J. Control, 13 (1975), pp. 271--273, Robinson extended Hoffman's theorem to any system of convex inequalities in a normed linear space which satisfies the Slater constraint qualification and has a bounded solution set. This paper studies any system of convex inequalities in a reflexive Banach space which has an unbounded solution set. It is shown that Hoffman's error bound holds for such a system when a related convex system, which defines the recession cone of the solution set for the system, satisfies the Slater constraint qualification.

title: Global Error Bounds for Convex Inequality Systems in Banach Spaces
abstract: We study conditions under which a global error bound in terms of a natural residual exists for a convex inequality system. Specifically, we obtain an error bound result, which unifies many existing results assuming a Slater condition. We also derive two characterizations for a convex inequality system to possess a global error bound; one is in terms of metric regularity, and the other is in terms of an associated convex inequality system. As a consequence, we show that in \font\bbbabstract=msbm10 at 8pt% $\mbox{\bbbabstract R}^n$ a global error bound holds for such a system under the assumption of the zero vector in the relative interior of the domain of an associated conjugate function along with metric regularity at every point of the feasible set defined by the system. Finally, we discuss some applications of these results to convex programs.

title: Metric regularity and subdifferential calculus
abstract: The theory of metric regularity is an extension of two classical results: the Lyusternik tangent space theorem and the Graves surjection theorem. Developments in non-smooth analysis in the 1980s and 1990s paved the way for a number of far-reaching extensions of these results. It was also well understood that the phenomena behind the results are of metric origin, not connected with any linear structure. At the same time it became clear that some basic hypotheses of the subdifferential calculus are closely connected with the metric regularity of certain set-valued maps. The survey is devoted to the metric theory of metric regularity and its connection with subdifferential calculus in Banach spaces.

title: Error Bounds for Lower Semicontinuous Functions in Normed Spaces
abstract: Without the convexity or analyticity assumption, we study error bounds for an inequality system defined by a general lower semicontinuous function and establish sufficient/necessary conditions on the existence of error bounds in infinite dimensional normed spaces. Some characterizations for a convex inequality system to possess an error bound in a reflexive Banach space are also given. As applications, in dealing with the Hoffman error bound result in normed spaces, we give a computable Lipschitz bound constant, which is better than previous Lipschitz bound constants in some examples; we also consider error bounds for quadratic functions on Rn.

title: On error bounds for lower semicontinuous functions
abstract: We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f.

title: First-Order and Second-Order Conditions for Error Bounds
abstract: For a lower semicontinuous function f on a Banach space X, we study the existence of a positive scalar $\mu$ such that the distance function dS associated with the solution set S of $f(x)\leq 0$ satisfies \[  \] for each point x in a neighborhood of some point x0 in X with $f(x)<\epsilon$ for some $0<\epsilon \leq +\infty.$ We give several sufficient conditions for this in terms of an abstract subdifferential and the Dini derivatives of f. In a Hilbert space we further present some second-order conditions. We also establish the corresponding results for a system of inequalities, equalities, and an abstract constraint set.

title: Conditioning and Upper-Lipschitz Inverse Subdifferentials in Nonsmooth Optimization Problems
abstract: In this paper, we study conditioning problems for convex and nonconvex functions defined on normed linear spaces. We extend the notion of upper Lipschitzness for multivalued functions introduced by Robinson, and show that this concept ensures local conditioning in the nonconvex case via an abstract subdifferential; in the convex case, we obtain complete characterizations of global conditioning in terms of an extension of the upper-Lipschitz property.

title: Error Bounds for Convex Inequality Systems
abstract: Using convex analysis, this paper gives a systematic and unified treatment for the existence of a globed error bound for a convex inequality system. We establish a necessary and sufficient condition for a closed convex set defined by a closed proper convex function to possess a globed error bound in terms of a natural residual. We derive many special cases of the main characterization, including the case where a Slater assumption is in place. Our results show clearly the essential conditions needed for convex inequality systems to satisfy global error bounds; they unify and extend a large number of existing results on global error bounds for such

title: On the Sensitivity Analysis of Hoffman Constants for Systems of Linear Inequalities
abstract: Relying on a general variational method developed by the authors and Lucchetti [] (the origin of which goes back to Ioffe [ (1979), pp. 61--69]), we give a formula for the best Hoffman constant $\sigma=\inf_{x\notin P_{A,b}}\frac{\|(Ax-b)^+\|_\infty}{d(x,P_{A,b})}$, where $P_{A,b}=\{x:Ax\le b\}$ is a nonempty polyhedron in ${\mathbb R}^n$. We also sharpen some results of Luo and Tseng [ (1994), pp. 636--659] by characterizing the continuity set of some Hoffman constants and by pointing out their locally Lipschitzian character. We apply these results to the study of the behavior of the solution set of a linear program $\inf_{Ax\le b}u^{\scriptscriptstyle T}x$ with respect to (A,b,u).

title: Characterizations of error bounds for lower semicontinuous functions on metric spaces
abstract: Refining the variational method introduced in Aze et al. [ (2002) 643-670], we give characterizations of the existence of so-called global and local error bounds, for lower semicontinuous functions defined on complete metric spaces. We thus provide a systematic and synthetic approach to the subject, emphasizing the special case of convex functions defined on arbitrary Banach spaces (refining the abstract part of Aze and Corvellec [ (2002) 913-927], and the characterization of the local metric regularity of closed-graph multifunctions between complete metric spaces.

title: Towards Metric Theory of Metric Regularity
abstract: It is shown that exact estimates for local metric regularity are obtained with the help of the slope introduced by De Giorgi-Marino-Tosques in 1980. Interrelation between the slope and subdifferentials are further analyzed.

title: Error bounds for infinite systems of convex inequalities without Slater’s condition
abstract: The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints. We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds of Hölder type, where the value of the residual of the constraints is raised to a certain power.¶We give sufficient conditions for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz case, we give five equivalent characterizations of the validity of a global error bound.¶We extend previous results in two directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do not assume that the Slater condition holds which has been required in almost all earlier papers.

title: On the variational principle
abstract: The variational principle states that if a differentiable functional F attains its minimum at some point zi, then F’(C) = 0; it has proved a valuable tool for studying partial differential equations. This paper shows that if a differentiable function F has a finite lower bound (although it need not attain it), then, for every E > 0, there exists some point u( where 11 F’(uJj* < l , i.e., its derivative can be made arbitrarily small. Applications are given to Plateau’s problem, to partial differential equations, to nonlinear eigenvalues, to geodesics on infinite-dimensional manifolds, and to control theory.

title: Weak sharp minima in mathematical programming
abstract: The notion of a sharp, or strongly unique, minimum is extended to include the possibility of a nonunique solution set. These minima will be called weak sharp minima. Conditions necessary for the solution set of a minimization problem to be a set of weak sharp minima are developed in both the unconstrained and constrained cases. These conditions are also shown to be sufficient under the appropriate convexity hypotheses. The existence of weak sharp minima is characterized in the cases of linear and quadratic convex programming and for the linear complementarity problem. In particular, a result of Mangasarian and Meyer is reproduced that shows that the solution set of a linear program is always a set of weak sharp minima whenever it is nonempty. Consequences for the convergence theory of algorithms are also examined, especially conditions yielding finite termination.

title: Asymptotic cones and functions in optimization and variational inequalities
abstract: Convex Analysis and Set Valued Maps: A Review.- Asymptotic Cones and Functions.- Existence and Stability in Optimization Problems.- Minimizing and Stationary Sequences.- Duality in Optimization Problems.- Maximal Monotone Maps and Variational Inequalities.

title: Error bounds for nondifferentiable convex inequalities under a strong Slater constraint qualification
abstract: A global error bound is given on the distance between an arbitrary point in then-dimensional real spaceRn and its projection on a nonempty convex set determined bym convex, possibly nondifferentiable, inequalities. The bound is in terms of a natural residual that measures the violations of the inequalities multiplied by a new simple condition constant that embodies a single strong Slater constraint qualification (CQ) which implies the ordinary Slater CQ. A very simple bound on the distance to the projection relative to the distance to a point satisfying the ordinary Slater CQ is given first and then used to derive the principal global error bound.

title: Well Behaved Asymptotical Convex Functions
abstract: In this paper, we introduce the class ℱ of proper closed convex functions for which satisfy the following property. “For all sequences {xn}, {cn} such that c n ∈ ∂ f ( x n ) and lim n → ∞ c n = 0 we have ” Characterizations and applications are then given.