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.

Revised:

Accepted:

Published online:

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

Author's affiliations:

^{1, 2}; Michel Théra

^{3}; Jen-Chih Yao

^{4}

@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}, 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 TI - Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems JO - Open Journal of Mathematical Optimization PY - 2022 DA - 2022/// VL - 3 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.13/ UR - https://doi.org/10.5802/ojmo.13 DO - 10.5802/ojmo.13 LA - en ID - OJMO_2022__3__A2_0 ER -

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/

[1] Strongly regular points of mappings, Fixed Point Theory Algorithms Sci. Eng., Volume 2021 (2021), 14 | Article

[2] Global regularity theorems, Math. Oper. Res., Volume 13 (1988) no. 2, pp. 243-253 | Zbl: 0655.90059

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

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

[5] On the sensitivity analysis of Hoffman constants for systems of linear inequalities, SIAM J. Optim., Volume 12 (2002) no. 4, pp. 913-927

[6] Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM, Control Optim. Calc. Var., Volume 10 (2004), pp. 409-425

[7] On projection algorithms for solving convex feasibility problems, SIAM Rev., Volume 38 (1996) no. 3, pp. 367-426

[8] Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems, Optim. Methods Softw., Volume 18 (2003) no. 4, pp. 377-394

[9] Error bounds for vector-valued functions: necessary and sufficient conditions, Nonlinear Anal., Theory Methods Appl., Volume 75 (2012) no. 3, pp. 1124-1140

[10] Weak sharp minima revisited. I. Basic theory, Control Cybern., Volume 31 (2002) no. 3, pp. 439-469

[11] Weak sharp minima revisited. II. Application to linear regularity and error bounds, Math. Program., Volume 104 (2005) no. 2-3, pp. 235-261

[12] Calmness modulus of linear semi-infinite programs, SIAM J. Optim., Volume 24 (2014) no. 1, pp. 29-48

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

[14] Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program., Volume 114 (2008) no. 2, pp. 291-319

[15] Error bounds revisited (2020) (https://arxiv.org/abs/2012.03941v1)

[16] 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

[17] The radius of metric regularity, Trans. Am. Math. Soc., Volume 355 (2003) no. 2, pp. 493-517

[18] Error bounds: necessary and sufficient conditions, Set-Valued Var. Anal., Volume 18 (2010) no. 2, pp. 121-149

[19] 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

[20] Augmented Lagrangian algorithms for linear programming, J. Optim. Theory Appl., Volume 75 (1992) no. 3, pp. 445-478

[21] Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., Volume 23 (2013) no. 4, pp. 2397-2419

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

[23] On first- and second-order conditions for error bounds, SIAM J. Optim., Volume 14 (2004) no. 4, pp. 1057-1073

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

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

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

[27] Variational analysis of regular mappings. Theory and applications, Springer Monographs in Mathematics, Springer, 2017

[28] On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Program., Volume 47 (1990) no. 1, pp. 37-51

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

[30] Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program., Volume 84 (1999) no. 1, pp. 137-160

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

[32] Error bounds and metric subregularity, Optimization, Volume 64 (2015) no. 1, pp. 49-79

[33] Perturbation of error bounds, Math. Program., Volume 168 (2018) no. 1-2, pp. 533-554

[34] 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

[35] Stability of error bounds for convex constraint systems in Banach spaces, SIAM J. Optim., Volume 20 (2010) no. 6, pp. 3280-3296

[36] 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

[37] Implicit error bounds for Picard iterations on Hilbert spaces, Vietnam J. Math., Volume 46 (2018) no. 2, pp. 243-258

[38] 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

[39] Perturbation analysis of a condition number for linear systems, SIAM J. Matrix Anal. Appl., Volume 15 (1994) no. 2, pp. 636-660

[40] A condition number for differentiable convex inequalities, Math. Oper. Res., Volume 10 (1985), pp. 175-179

[41] Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optim., Volume 12 (2001) no. 1, pp. 1-17

[42] Stability of error bounds for semi-infinite convex constraint systems, SIAM J. Optim., Volume 20 (2080) no. 4, pp. 2080-2096 | Zbl: 1202.49024

[43] Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Program., Volume 116 (2009) no. 1-2, pp. 397-427

[44] Error bounds in mathematical programming, Math. Program., Volume 79 (1997) no. 1-3, pp. 299-332

[45] Calculus without derivatives, Graduate Texts in Mathematics, 266, Springer, 2013

[46] Convex functions, Monotone Operators and Differentiability, Lecture Notes in Mathematics, 1364, Springer, 1993

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

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

[49] A characterization of stability in linear programming, Oper. Res., Volume 25 (1977), pp. 435-447

[50] Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, 1970

[51] On the convergence of the exponential multiplier method for convex programming, Math. Program., Volume 60 (1993) no. 1, pp. 1-19

[52] On error bounds for lower semicontinuous functions, Math. Program., Volume 92 (2002) no. 2, pp. 301-314

[53] 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

[54] Metric subregularity and calmness for nonconvex generalized equations in Banach spaces, SIAM J. Optim., Volume 20 (2010) no. 5, pp. 2119-2136

[55] Metric subregularity for proximal generalized equations in Hilbert spaces, Nonlinear Anal., Theory Methods Appl., Volume 75 (2012) no. 3, pp. 1686-1699

[56] 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

*Cited by Sources: *