Characterizations of stability of error bounds for convex inequality constraint systems. (English) Zbl 1497.90206
Summary: 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.
MSC:
| 90C34 | Semi-infinite programming |
| 90C25 | Convex programming |
| 90C31 | Sensitivity, stability, parametric optimization |
Keywords:
local and global error bounds; stability; convex inequality; semi-infinite convex constraint systems; directional derivativeReferences:
| [1] | Abbasi, Malek; Théra, Michel, Strongly regular points of mappings, Fixed Point Theory Algorithms Sci. Eng., 2021 (2021) · Zbl 07525618 · doi:10.1186/s13663-021-00699-z |
| [2] | Auslender, A. A.; Crouzeix, Jean-Pierre, Global regularity theorems, Math. Oper. Res., 13, 2, 243-253 (1988) · Zbl 0655.90059 |
| [3] | Azé, Dominique, A survey on error bounds for lower semicontinuous functions, ESAIM, Proc., 13, 1-17 (2003) · Zbl 1037.49009 |
| [4] | Azé, Dominique, A unified theory for metric regularity of multifunctions, J. Convex Anal., 13, 2, 225-252 (2006) · Zbl 1101.49013 |
| [5] | Azé, Dominique; Corvellec, Jean-Noël, On the sensitivity analysis of Hoffman constants for systems of linear inequalities, SIAM J. Optim., 12, 4, 913-927 (2002) · Zbl 1014.65046 |
| [6] | Azé, Dominique; Corvellec, Jean-Noël, Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM, Control Optim. Calc. Var., 10, 409-425 (2004) · Zbl 1085.49019 |
| [7] | Bauschke, Heinz H.; Borwein, Jonathan M., On projection algorithms for solving convex feasibility problems, SIAM Rev., 38, 3, 367-426 (1996) · Zbl 0865.47039 |
| [8] | Beck, Amir; Teboulle, Marc, Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems, Optim. Methods Softw., 18, 4, 377-394 (2003) · Zbl 1060.90060 |
| [9] | Bednarczuk, Ewa M.; Kruger, Alexander Y., Error bounds for vector-valued functions: necessary and sufficient conditions, Nonlinear Anal., Theory Methods Appl., 75, 3, 1124-1140 (2012) · Zbl 1236.49032 |
| [10] | Burke, James V.; Deng, Sien, Weak sharp minima revisited. I. Basic theory, Control Cybern., 31, 3, 439-469 (2002) · Zbl 1105.90356 |
| [11] | Burke, James V.; Deng, Sien, Weak sharp minima revisited. II. Application to linear regularity and error bounds, Math. Program., 104, 2-3, 235-261 (2005) · Zbl 1124.90349 |
| [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., 24, 1, 29-48 (2014) · Zbl 1374.90391 |
| [13] | Combettes, Patrick L., Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optim., 35, 3, 311-330 (1997) · Zbl 0872.90069 |
| [14] | Corvellec, Jean-Noël; Motreanu, Viorica V., Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program., 114, 2, 291-319 (2008) · Zbl 1190.90206 |
| [15] | Cuong, Nguyen Duy; Kruger, Alexander Y., Error bounds revisited (2020) · Zbl 1489.49010 |
| [16] | Deng, Sien, Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems, Math. Program., 83, 2, 263-276 (1998) · Zbl 0920.90116 |
| [17] | Dontchev, Asen L.; Lewis, Adrian S.; Rockafellar, Ralph T., The radius of metric regularity, Trans. Am. Math. Soc., 355, 2, 493-517 (2003) · Zbl 1042.49026 |
| [18] | Fabian, Marian J.; Henrion, René; Kruger, Alexander Y.; Outrata, Jiří V., Error bounds: necessary and sufficient conditions, Set-Valued Var. Anal., 18, 2, 121-149 (2010) · Zbl 1192.49018 |
| [19] | Gfrerer, Helmut, First order and second order characterizations of metric subregularity and calmness of constraint set mappings, SIAM J. Optim., 21, 4, 1439-1474 (2011) · Zbl 1254.90246 |
| [20] | Güler, Osman, Augmented Lagrangian algorithms for linear programming, J. Optim. Theory Appl., 75, 3, 445-478 (1992) · Zbl 0797.90061 |
| [21] | Hesse, Robert; Luke, D. Russell, Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., 23, 4, 2397-2419 (2013) · Zbl 1288.65094 |
| [22] | Hoffman, A. J., On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards, 49, 263-265 (1952) |
| [23] | Huang, L. R.; Ng, Kung Fu, On first- and second-order conditions for error bounds, SIAM J. Optim., 14, 4, 1057-1073 (2004) · Zbl 1073.90048 |
| [24] | Ioffe, Alexander D., Theory of Extremal Problems, 6 (1979), North-Holland · Zbl 0427.58008 |
| [25] | Ioffe, Alexander D., Metric regularity – a survey. I: Theory, J. Aust. Math. Soc., 101, 2, 188-243 (2016) · Zbl 1369.49001 |
| [26] | Ioffe, Alexander D., Metric regularity – a survey. II: Applications, J. Aust. Math. Soc., 101, 3, 376-417 (2016) · Zbl 1369.49002 |
| [27] | Ioffe, Alexander D., Variational analysis of regular mappings. Theory and applications (2017), Springer · Zbl 1381.49001 |
| [28] | Iusem, Alfredo N.; De Pierro, Alvaro R., On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Program., 47, 1, 37-51 (1990) · Zbl 0712.90054 |
| [29] | Jourani, Abderrahim, Hoffman’s error bound, local controllability, and sensitivity analysis, SIAM J. Control Optimization, 38, 3, 947-970 (2000) · Zbl 0945.46023 |
| [30] | Klatte, Diethard; Li, Wu, Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program., 84, 1, 137-160 (1999) · Zbl 1050.90557 |
| [31] | Kruger, Alexander Y., Error bounds and Hölder metric subregularity, Set-Valued Var. Anal., 23, 4, 705-736 (2015) · Zbl 1330.49012 |
| [32] | Kruger, Alexander Y., Error bounds and metric subregularity, Optimization, 64, 1, 49-79 (2015) · Zbl 1311.49043 |
| [33] | Kruger, Alexander Y.; López, Marco A.; Théra, Michel, Perturbation of error bounds, Math. Program., 168, 1-2, 533-554 (2018) · Zbl 1391.49051 |
| [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., 27, 4, 995-1023 (2019) · Zbl 1430.49014 |
| [35] | Kruger, Alexander Y.; Ngai, Huynh Van; Théra, Michel, Stability of error bounds for convex constraint systems in Banach spaces, SIAM J. Optim., 20, 6, 3280-3296 (2010) · Zbl 1208.49030 |
| [36] | Lewis, Adrian S.; Pang, Jong-Shi, Generalized Convexity, Generalized Monotonicity: Recent Results (Luming, 1996), 27, Error bounds for convex inequality systems, 75-100 (1996), Kluwer Academic Publishers |
| [37] | Luke, D. Russell; Nguyen, H. Thao; Tam, Matthew K., Implicit error bounds for Picard iterations on Hilbert spaces, Vietnam J. Math., 46, 2, 243-258 (2018) · Zbl 1391.49025 |
| [38] | Luo, Zhi-Quan; Tseng, Paul, On a global error bound for a class of monotone affine variational inequality problems, Oper. Res. Lett., 11, 3, 159-165 (1992) · Zbl 0777.49009 |
| [39] | Luo, Zhi-Quan; Tseng, Paul, Perturbation analysis of a condition number for linear systems, SIAM J. Matrix Anal. Appl., 15, 2, 636-660 (1994) · Zbl 0799.65063 |
| [40] | Mangasarian, Olvi L., A condition number for differentiable convex inequalities, Math. Oper. Res., 10, 175-179 (1985) · Zbl 0565.90059 |
| [41] | Ng, Kung Fu; Zheng, Xi Yin, Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optim., 12, 1, 1-17 (2001) · Zbl 1040.90041 |
| [42] | Ngai, Huynh Van; Kruger, Alexander Y.; Théra, Michel, Stability of error bounds for semi-infinite convex constraint systems, SIAM J. Optim., 20, 4, 2080-2096 (2080) · Zbl 1202.49024 |
| [43] | Ngai, Huynh Van; Théra, Michel, Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Program., 116, 1-2, 397-427 (2009) · Zbl 1215.49028 |
| [44] | Pang, Jong-Shi, Error bounds in mathematical programming, Math. Program., 79, 1-3, 299-332 (1997) · Zbl 0887.90165 |
| [45] | Penot, Jean-Paul, Calculus without derivatives, 266 (2013), Springer · Zbl 1264.49014 |
| [46] | Phelps, Robert R., Convex functions, Monotone Operators and Differentiability, 1364 (1993), Springer · Zbl 0921.46039 |
| [47] | Robinson, Stephen M., Bounds for error in the solution set of a perturbed linear program, Linear Algebra Appl., 6, 69-81 (1973) · Zbl 0283.90028 |
| [48] | Robinson, Stephen M., An application of error bounds for convex programming in a linear space, SIAM J. Control, 13, 271-273 (1975) · Zbl 0297.90072 |
| [49] | Robinson, Stephen M., A characterization of stability in linear programming, Oper. Res., 25, 435-447 (1977) · Zbl 0373.90045 |
| [50] | Rockafellar, Ralph T., Convex Analysis, 28 (1970), Princeton University Press · Zbl 0193.18401 |
| [51] | Tseng, Paul; Bertsekas, Dimitri P., On the convergence of the exponential multiplier method for convex programming, Math. Program., 60, 1, 1-19 (1993) · Zbl 0783.90101 |
| [52] | Wu, Zili; Ye, Jane J., On error bounds for lower semicontinuous functions, Math. Program., 92, 2, 301-314 (2002) · Zbl 1041.90053 |
| [53] | Zheng, Xi Yin; Ng, Kung Fu, Perturbation analysis of error bounds for systems of conic linear inequalities in Banach spaces, SIAM J. Optim., 15, 4, 1026-1041 (2005) · Zbl 1114.90134 |
| [54] | Zheng, Xi Yin; Ng, Kung Fu, Metric subregularity and calmness for nonconvex generalized equations in Banach spaces, SIAM J. Optim., 20, 5, 2119-2136 (2010) · Zbl 1229.90220 |
| [55] | Zheng, Xi Yin; Ng, Kung Fu, Metric subregularity for proximal generalized equations in Hilbert spaces, Nonlinear Anal., Theory Methods Appl., 75, 3, 1686-1699 (2012) · Zbl 1254.90248 |
| [56] | Zheng, Xi Yin; Wei, Zhou, Perturbation analysis of error bounds for quasi-subsmooth inequalities and semi-infinite constraint systems, SIAM J. Optim., 22, 1, 41-65 (2012) · Zbl 1250.49019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
