Error bounds for inequality systems defining convex sets
- PDF / 342,146 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 231 Views
Series B
Error bounds for inequality systems defining convex sets Joydeep Dutta1 · Juan Enrique Martínez-Legaz2,3 Received: 29 October 2019 / Accepted: 25 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract The main goal in this paper is to devise an approach to explicitly calculate the constant in the Hoffman’s error bound for (not necessarily convex) inequality systems defining convex sets. We give a constructive proof of the Hoffman’s error bound and show that we can use our method to calculate the constant at least in simple cases. Mathematics Subject Classification 90C25 (Primary) · 49K10 (Secondary)
1 Introduction and preliminaries It is well known that an iterative algorithm used to solve optimization problems in general will not give us an exact solution even if there is one. Thus, when the algorithm stops and returns us a point, it is important to know how far that point is from the actual solution set of the problem. The feasibility of the given problem becomes also a fundamental issue when we use, for example, the penalty function method. Thus, for an optimization problem it is also worthwhile to estimate the distance from a point to the feasible set. We basically seek an upper bound to this distance, which will be called an error bound associated with a convex feasible set defined by not necessarily convex
Dedicated to Prof. Marco A. López on the occasion of his 70th birthday. Juan Enrique Martínez-Legaz acknowledges financial support from the Spanish Ministry of Science, Innovation and Universities, through Grant PGC2018-097960-B-C21 and the Severo Ochoa Program for Centers of Excellence in R&D (CEX2019-000915-S). He is affiliated with MOVE (Markets, Organizations and Votes in Economics).
B
Juan Enrique Martínez-Legaz [email protected]
1
Department of Economic Sciences, Indian Institute of Technology Kanpur, Kanpur 208016, India
2
Departament d’Economia i d’Història Econòmica, Universitat Autònoma de Barcelona, Bellaterra, Spain
3
BGSMath, Barcelona, Spain
123
J. Dutta, J. E. Martínez-Legaz
inequality constraints. There has been a good amount of research on error bounds and their stability; see, for example, [11,19,22,25]. A fundamental reference is [16], which unifies several approaches into a coherent framework and also provides, to the best of our knowledge, the weakest known condition so far for the existence of error bounds. For a recent survey including the latest developments, we refer to [9]. Let us consider the issue of finding an error bound for a convex inequality system, which defines the convex set (1) S := x ∈ Rn : f (x) ≤ 0 , where f = ( f 1 , . . . , f m ) : Rn → Rm is a convex function, that is, each component function f i is convex and the inequality in (1) is in the componentwise sense. An error bound for the system of inequalities describing the set S is an inequality of the form d(x, S) ≤ K f (x)+
∀x ∈ Rn ,
(2)
where K ≥ 0 is a constant independent of x and, for y ∈ R, we
Data Loading...
