Characterizations of Stability of Error Bounds for Convex Inequality Constraint Systems

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

doi:10.5802/ojmo.13

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

¹ 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, Tome 3 (2022), article no. 2, 17 p.

Résumé

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.

Reçu le : 2021-07-02
Révisé le : 2022-01-21
Accepté le : 2022-02-22
Publié le : 2022-03-03

DOI : 10.5802/ojmo.13

Mots clés : Local and global error bounds, Stability, Convex inequality, Semi-infinite convex constraint systems, Directional derivative

Affiliations des auteurs :

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

@article{OJMO_2022__3__A2_0,
     author = {Wei, Zhou and Th\'era, Michel and Yao, Jen-Chih},
     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 = {http://www.numdam.org/articles/10.5802/ojmo.13/}
}

TY  - JOUR
AU  - Wei, Zhou
AU  - Théra, Michel
AU  - Yao, Jen-Chih
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  - http://www.numdam.org/articles/10.5802/ojmo.13/
DO  - 10.5802/ojmo.13
LA  - en
ID  - OJMO_2022__3__A2_0
ER  -

%0 Journal Article
%A Wei, Zhou
%A Théra, Michel
%A Yao, Jen-Chih
%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 http://www.numdam.org/articles/10.5802/ojmo.13/
%R 10.5802/ojmo.13
%G en
%F OJMO_2022__3__A2_0

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

Bibliographie
Cité par

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

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

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

[5] Azé, Dominique; Corvellec, Jean-Noël 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] Azé, Dominique; Corvellec, Jean-Noël 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] Bauschke, Heinz H.; Borwein, Jonathan M. On projection algorithms for solving convex feasibility problems, SIAM Rev., Volume 38 (1996) no. 3, pp. 367-426 | DOI | MR | Zbl

[8] Beck, Amir; Teboulle, Marc 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] Bednarczuk, Ewa M.; Kruger, Alexander Y. 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] Burke, James V.; Deng, Sien Weak sharp minima revisited. I. Basic theory, Control Cybern., Volume 31 (2002) no. 3, pp. 439-469 | MR | Zbl

[11] Burke, James V.; Deng, Sien 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] Cánovas, María J.; Kruger, Alexander Y.; López, Marco A.; Parra, Juan; Théra, Michel Calmness modulus of linear semi-infinite programs, SIAM J. Optim., Volume 24 (2014) no. 1, pp. 29-48 | DOI | MR | Zbl

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

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

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

[16] Deng, Sien 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] Dontchev, Asen L.; Lewis, Adrian S.; Rockafellar, Ralph T. The radius of metric regularity, Trans. Am. Math. Soc., Volume 355 (2003) no. 2, pp. 493-517 | DOI | MR | Zbl

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

[19] Gfrerer, Helmut 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] Güler, Osman Augmented Lagrangian algorithms for linear programming, J. Optim. Theory Appl., Volume 75 (1992) no. 3, pp. 445-478 | DOI | MR

[21] Hesse, Robert; Luke, D. Russell 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] Hoffman, A. J. On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards, Volume 49 (1952), pp. 263-265 | DOI | MR

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

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

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

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

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

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

[29] Jourani, Abderrahim 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] Klatte, Diethard; Li, Wu Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program., Volume 84 (1999) no. 1, pp. 137-160 | DOI | MR | Zbl

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

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

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

[34] Kruger, Alexander Y.; López, Marco A.; Yang, Xiaoqi; Zhu, Jiangxing 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] Kruger, Alexander Y.; Ngai, Huynh Van; Théra, Michel 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] Lewis, Adrian S.; Pang, Jong-Shi 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] Luke, D. Russell; Nguyen, H. Thao; Tam, Matthew K. Implicit error bounds for Picard iterations on Hilbert spaces, Vietnam J. Math., Volume 46 (2018) no. 2, pp. 243-258 | DOI | MR | Zbl

[38] Luo, Zhi-Quan; Tseng, Paul 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] Luo, Zhi-Quan; Tseng, Paul 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] Mangasarian, Olvi L. A condition number for differentiable convex inequalities, Math. Oper. Res., Volume 10 (1985), pp. 175-179 | DOI | MR | Zbl

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

[42] Ngai, Huynh Van; Kruger, Alexander Y.; Théra, Michel 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] Ngai, Huynh Van; Théra, Michel 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] Pang, Jong-Shi Error bounds in mathematical programming, Math. Program., Volume 79 (1997) no. 1-3, pp. 299-332 | DOI | MR | Zbl

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

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

[47] Robinson, Stephen M. 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] Robinson, Stephen M. 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] Robinson, Stephen M. A characterization of stability in linear programming, Oper. Res., Volume 25 (1977), pp. 435-447 | DOI | MR | Zbl

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

[51] Tseng, Paul; Bertsekas, Dimitri P. 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] Wu, Zili; Ye, Jane J. On error bounds for lower semicontinuous functions, Math. Program., Volume 92 (2002) no. 2, pp. 301-314 | MR | Zbl

[53] Zheng, Xi Yin; Ng, Kung Fu 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] Zheng, Xi Yin; Ng, Kung Fu 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] Zheng, Xi Yin; Ng, Kung Fu 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] Zheng, Xi Yin; Wei, Zhou 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

Cité par Sources :