Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems

Zhou Wei; Michel Théra; Jen-Chih Yao

doi:10.5802/ojmo.13

Zhou Wei ^1,²; Michel Théra ³; Jen-Chih Yao ⁴

¹ College of Mathematics and Information Science, Hebei University, Baoding 071002, China
² Department of Mathematics, Yunnan University, Kunming 650091, China
³ XLIM UMR-CNRS 7252, Université de Limoges, Limoges, France Federation University Australia, Ballarat
⁴ Research Center for Interneural Computing, China Medical University Hospital China Medical University, Taichung 40402, Taiwan

Open Journal of Mathematical Optimization, Volume 3 (2022), article no. 2, 17 p.

Abstract

In this paper, we mainly study error bounds for a single convex inequality and semi-infinite convex constraint systems, and give characterizations of stability of error bounds via directional derivatives. For a single convex inequality, it is proved that the stability of local error bounds under small perturbations is essentially equivalent to the non-zero minimum of the directional derivative at a reference point over the unit sphere, and the stability of global error bounds is proved to be equivalent to the strictly positive infimum of the directional derivatives, at all points in the boundary of the solution set, over the unit sphere as well as some mild constraint qualification. When these results are applied to semi-infinite convex constraint systems, characterizations of stability of local and global error bounds under small perturbations are also provided. In particular such stability of error bounds is proved to only require that all component functions in semi-infinite convex constraint systems have the same linear perturbation. Our work demonstrates that verifying the stability of error bounds for convex inequality constraint systems is, to some degree, equivalent to solving convex minimization problems (defined by directional derivatives) over the unit sphere.

Received: 2021-07-02
Revised: 2022-01-21
Accepted: 2022-02-22
Published online: 2022-03-03

DOI: 10.5802/ojmo.13

Keywords: Local and global error bounds, Stability, Convex inequality, Semi-infinite convex constraint systems, Directional derivative

Author's affiliations:

Zhou Wei ^{1, 2}; Michel Théra ³; Jen-Chih Yao ⁴

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{OJMO_2022__3__A2_0,
     author = {Zhou Wei and Michel Th\'era and Jen-Chih Yao},
     title = {Characterizations of {Stability} of {Error} {Bounds} for {Convex} {Inequality} {Constraint} {Systems}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {2},
     pages = {1--17},
     publisher = {Universit\'e de Montpellier},
     volume = {3},
     year = {2022},
     doi = {10.5802/ojmo.13},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.13/}
}

TY  - JOUR
AU  - Zhou Wei
AU  - Michel Théra
AU  - Jen-Chih Yao
TI  - Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems
JO  - Open Journal of Mathematical Optimization
PY  - 2022
SP  - 1
EP  - 17
VL  - 3
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.13/
DO  - 10.5802/ojmo.13
LA  - en
ID  - OJMO_2022__3__A2_0
ER  -

%0 Journal Article
%A Zhou Wei
%A Michel Théra
%A Jen-Chih Yao
%T Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems
%J Open Journal of Mathematical Optimization
%D 2022
%P 1-17
%V 3
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.13/
%R 10.5802/ojmo.13
%G en
%F OJMO_2022__3__A2_0

Zhou Wei; Michel Théra; Jen-Chih Yao. Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems. Open Journal of Mathematical Optimization, Volume 3 (2022), article  no. 2, 17 p. doi : 10.5802/ojmo.13. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.13/

References
Cited by

[1] Malek Abbasi; Michel Théra Strongly regular points of mappings, Fixed Point Theory Algorithms Sci. Eng., Volume 2021 (2021), 14 | DOI | MR | Zbl

[2] A. A. Auslender; Jean-Pierre Crouzeix Global regularity theorems, Math. Oper. Res., Volume 13 (1988) no. 2, pp. 243-253 | DOI | MR | Zbl

[3] Dominique Azé A survey on error bounds for lower semicontinuous functions, ESAIM, Proc., Volume 13 (2003), pp. 1-17 (Proceedings of 2003 MODE-SMAI Conference) | MR | Zbl

[4] Dominique Azé A unified theory for metric regularity of multifunctions, J. Convex Anal., Volume 13 (2006) no. 2, pp. 225-252 | MR | Zbl

[5] Dominique Azé; Jean-Noël Corvellec On the sensitivity analysis of Hoffman constants for systems of linear inequalities, SIAM J. Optim., Volume 12 (2002) no. 4, pp. 913-927 | MR

[6] Dominique Azé; Jean-Noël Corvellec Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM, Control Optim. Calc. Var., Volume 10 (2004), pp. 409-425 | Numdam | MR | Zbl

[7] Heinz H. Bauschke; Jonathan M. Borwein On projection algorithms for solving convex feasibility problems, SIAM Rev., Volume 38 (1996) no. 3, pp. 367-426 | DOI | MR | Zbl

[8] Amir Beck; Marc Teboulle Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems, Optim. Methods Softw., Volume 18 (2003) no. 4, pp. 377-394 | DOI | MR | Zbl

[9] Ewa M. Bednarczuk; Alexander Y. Kruger Error bounds for vector-valued functions: necessary and sufficient conditions, Nonlinear Anal., Theory Methods Appl., Volume 75 (2012) no. 3, pp. 1124-1140 | DOI | MR | Zbl

[10] James V. Burke; Sien Deng Weak sharp minima revisited. I. Basic theory, Control Cybern., Volume 31 (2002) no. 3, pp. 439-469 | MR | Zbl

[11] James V. Burke; Sien Deng Weak sharp minima revisited. II. Application to linear regularity and error bounds, Math. Program., Volume 104 (2005) no. 2-3, pp. 235-261 | DOI | MR | Zbl

[12] María J. Cánovas; Alexander Y. Kruger; Marco A. López; Juan Parra; Michel Théra Calmness modulus of linear semi-infinite programs, SIAM J. Optim., Volume 24 (2014) no. 1, pp. 29-48 | DOI | MR | Zbl

[13] Patrick L. Combettes Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optim., Volume 35 (1997) no. 3, pp. 311-330 | DOI | MR | Zbl

[14] Jean-Noël Corvellec; Viorica V. Motreanu Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program., Volume 114 (2008) no. 2, pp. 291-319 | DOI | MR | Zbl

[15] Nguyen Duy Cuong; Alexander Y. Kruger Error bounds revisited (2020) (https://arxiv.org/abs/2012.03941v1)

[16] Sien Deng Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems, Math. Program., Volume 83 (1998) no. 2, pp. 263-276 | DOI | MR | Zbl

[17] Asen L. Dontchev; Adrian S. Lewis; Ralph T. Rockafellar The radius of metric regularity, Trans. Am. Math. Soc., Volume 355 (2003) no. 2, pp. 493-517 | DOI | MR | Zbl

[18] Marian J. Fabian; René Henrion; Alexander Y. Kruger; Jiří V. Outrata Error bounds: necessary and sufficient conditions, Set-Valued Var. Anal., Volume 18 (2010) no. 2, pp. 121-149 | DOI | MR | Zbl

[19] Helmut Gfrerer First order and second order characterizations of metric subregularity and calmness of constraint set mappings, SIAM J. Optim., Volume 21 (2011) no. 4, pp. 1439-1474 | DOI | MR | Zbl

[20] Osman Güler Augmented Lagrangian algorithms for linear programming, J. Optim. Theory Appl., Volume 75 (1992) no. 3, pp. 445-478 | DOI | MR

[21] Robert Hesse; D. Russell Luke Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., Volume 23 (2013) no. 4, pp. 2397-2419 | DOI | MR | Zbl

[22] A. J. Hoffman On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards, Volume 49 (1952), pp. 263-265 | DOI | MR

[23] L. R. Huang; Kung Fu Ng On first- and second-order conditions for error bounds, SIAM J. Optim., Volume 14 (2004) no. 4, pp. 1057-1073 | DOI | MR

[24] Alexander D. Ioffe Theory of Extremal Problems, Studies in Mathematics and its Applications, 6, North-Holland, 1979

[25] Alexander D. Ioffe Metric regularity – a survey. I: Theory, J. Aust. Math. Soc., Volume 101 (2016) no. 2, pp. 188-243 | DOI | MR | Zbl

[26] Alexander D. Ioffe Metric regularity – a survey. II: Applications, J. Aust. Math. Soc., Volume 101 (2016) no. 3, pp. 376-417 | DOI | MR | Zbl

[27] Alexander D. Ioffe Variational analysis of regular mappings. Theory and applications, Springer Monographs in Mathematics, Springer, 2017 | DOI

[28] Alfredo N. Iusem; Alvaro R. De Pierro On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Program., Volume 47 (1990) no. 1, pp. 37-51 | DOI | MR | Zbl

[29] Abderrahim Jourani Hoffman’s error bound, local controllability, and sensitivity analysis, SIAM J. Control Optimization, Volume 38 (2000) no. 3, pp. 947-970 | DOI | MR | Zbl

[30] Diethard Klatte; Wu Li Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program., Volume 84 (1999) no. 1, pp. 137-160 | DOI | MR | Zbl

[31] Alexander Y. Kruger Error bounds and Hölder metric subregularity, Set-Valued Var. Anal., Volume 23 (2015) no. 4, pp. 705-736 | DOI | Zbl

[32] Alexander Y. Kruger Error bounds and metric subregularity, Optimization, Volume 64 (2015) no. 1, pp. 49-79 | DOI | MR | Zbl

[33] Alexander Y. Kruger; Marco A. López; Michel Théra Perturbation of error bounds, Math. Program., Volume 168 (2018) no. 1-2, pp. 533-554 | DOI | MR | Zbl

[34] Alexander Y. Kruger; Marco A. López; Xiaoqi Yang; Jiangxing Zhu Hölder error bounds and Hölder calmness with applications to convex semi-infinite optimization, Set-Valued Var. Anal., Volume 27 (2019) no. 4, pp. 995-1023 | DOI | Zbl

[35] Alexander Y. Kruger; Huynh Van Ngai; Michel Théra Stability of error bounds for convex constraint systems in Banach spaces, SIAM J. Optim., Volume 20 (2010) no. 6, pp. 3280-3296 | DOI | MR | Zbl

[36] Adrian S. Lewis; Jong-Shi Pang Error bounds for convex inequality systems, Generalized Convexity, Generalized Monotonicity: Recent Results (Luming, 1996) (Nonconvex Optimization and Its Applications), Volume 27, Kluwer Academic Publishers, 1996, pp. 75-100 | DOI | Zbl

[37] D. Russell Luke; H. Thao Nguyen; Matthew K. Tam Implicit error bounds for Picard iterations on Hilbert spaces, Vietnam J. Math., Volume 46 (2018) no. 2, pp. 243-258 | DOI | MR | Zbl

[38] Zhi-Quan Luo; Paul Tseng On a global error bound for a class of monotone affine variational inequality problems, Oper. Res. Lett., Volume 11 (1992) no. 3, pp. 159-165 | MR | Zbl

[39] Zhi-Quan Luo; Paul Tseng Perturbation analysis of a condition number for linear systems, SIAM J. Matrix Anal. Appl., Volume 15 (1994) no. 2, pp. 636-660 | MR | Zbl

[40] Olvi L. Mangasarian A condition number for differentiable convex inequalities, Math. Oper. Res., Volume 10 (1985), pp. 175-179 | DOI | MR | Zbl

[41] Kung Fu Ng; Xi Yin Zheng Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optim., Volume 12 (2001) no. 1, pp. 1-17 | MR | Zbl

[42] Huynh Van Ngai; Alexander Y. Kruger; Michel Théra Stability of error bounds for semi-infinite convex constraint systems, SIAM J. Optim., Volume 20 (2080) no. 4, pp. 2080-2096 | DOI | MR | Zbl

[43] Huynh Van Ngai; Michel Théra Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Program., Volume 116 (2009) no. 1-2, pp. 397-427 | DOI | MR | Zbl

[44] Jong-Shi Pang Error bounds in mathematical programming, Math. Program., Volume 79 (1997) no. 1-3, pp. 299-332 | DOI | MR | Zbl

[45] Jean-Paul Penot Calculus without derivatives, Graduate Texts in Mathematics, 266, Springer, 2013 | DOI

[46] Robert R. Phelps Convex functions, Monotone Operators and Differentiability, Lecture Notes in Mathematics, 1364, Springer, 1993 | MR

[47] Stephen M. Robinson Bounds for error in the solution set of a perturbed linear program, Linear Algebra Appl., Volume 6 (1973), pp. 69-81 | DOI | MR | Zbl

[48] Stephen M. Robinson An application of error bounds for convex programming in a linear space, SIAM J. Control, Volume 13 (1975), pp. 271-273 | DOI | MR | Zbl

[49] Stephen M. Robinson A characterization of stability in linear programming, Oper. Res., Volume 25 (1977), pp. 435-447 | DOI | MR | Zbl

[50] Ralph T. Rockafellar Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, 1970 | DOI

[51] Paul Tseng; Dimitri P. Bertsekas On the convergence of the exponential multiplier method for convex programming, Math. Program., Volume 60 (1993) no. 1, pp. 1-19 | DOI | MR | Zbl

[52] Zili Wu; Jane J. Ye On error bounds for lower semicontinuous functions, Math. Program., Volume 92 (2002) no. 2, pp. 301-314 | MR | Zbl

[53] Xi Yin Zheng; Kung Fu Ng Perturbation analysis of error bounds for systems of conic linear inequalities in Banach spaces, SIAM J. Optim., Volume 15 (2005) no. 4, pp. 1026-1041 | DOI | MR | Zbl

[54] Xi Yin Zheng; Kung Fu Ng Metric subregularity and calmness for nonconvex generalized equations in Banach spaces, SIAM J. Optim., Volume 20 (2010) no. 5, pp. 2119-2136 | DOI | MR | Zbl

[55] Xi Yin Zheng; Kung Fu Ng Metric subregularity for proximal generalized equations in Hilbert spaces, Nonlinear Anal., Theory Methods Appl., Volume 75 (2012) no. 3, pp. 1686-1699 | DOI | MR | Zbl

[56] Xi Yin Zheng; Zhou Wei Perturbation analysis of error bounds for quasi-subsmooth inequalities and semi-infinite constraint systems, SIAM J. Optim., Volume 22 (2012) no. 1, pp. 41-65 | DOI | MR | Zbl

Cited by Sources: