Primal characterizations of error bounds for composite-convex inequalities. (English) Zbl 1522.90220
Summary: This paper is devoted to primal conditions of error bounds for a general function. In terms of Bouligand tangent cones, lower Hadamard directional derivatives and the Hausdorff-Pompeiu excess of subsets, we provide several necessary and/or sufficient conditions for error bounds with mild assumptions. Then we use these primal results to characterize error bounds for composite-convex functions (i.e. the composition of a convex function with a continuously differentiable mapping). It is proved that the primal characterization of error bounds can be established via Bouligand tangent cones, directional derivatives and the Hausdorff-Pompeiu excess if the mapping is metrically regular at the given point. The accurate estimate on the error bound modulus is also obtained.
MSC:
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C25 | Convex programming |
| 49J52 | Nonsmooth analysis |
| 46B20 | Geometry and structure of normed linear spaces |
Keywords:
error bound; composite-convex inequality; Bouligand tangent cone; lower Hadamard directional derivative; Hausdorff-Pompeiu excessReferences:
| [1] | M. Abassi, M. Théra: Strongly regular points of mappings, Fixed Point Theory Al-gorithms Sci. Eng. (2021), art. no. 14. · Zbl 07525618 |
| [2] | M. Abassi, M. Théra: About error bounds in metrizable topological vector spaces, Set-Valued Var. Analysis 30 (2022) 1291-1311. · Zbl 1514.46052 |
| [3] | D. Aussel, A. Daniillids, L. Thibault: Subsmooth sets: Functional characterizations and related concepts, Trans. Amer. Math. Soc. 357 (2005) 1275-1301. · Zbl 1094.49016 |
| [4] | A. Auslender, J. P. Crouzeix: Global regularity theorems, Math. Oper. Res. 13/2 (1988) 243-253. · Zbl 0655.90059 |
| [5] | D. Azé, J.-N. Corvellec: Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM Control Optim. Calc. Var. 10 (2004) 409-425. · Zbl 1085.49019 |
| [6] | H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Rev. 38/3 (1996) 367-426. · Zbl 0865.47039 |
| [7] | A. Beck, M. Teboulle: Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems, Optim. Methods Software 18/4 (2003) 377-394. · Zbl 1060.90060 |
| [8] | E. M. Bednarczuk, A. Y. Kruger: Error bounds for vector-valued functions: Necessary and sufficient conditions, Nonlinear Analysis 75/3 (2012) 1124-1140. · Zbl 1236.49032 |
| [9] | J. V. Burke, S. Deng: Weak sharp minima revisited. I: Basic theory, Control Cyber. 31/3 (2002) 439-469. · Zbl 1105.90356 |
| [10] | J. V. Burke, S. Deng: Weak sharp minima revisited. II: Application to linear regularity and error bounds, Math. Program., 104/2-3 (2005) 235-261. · Zbl 1124.90349 |
| [11] | P. L. Combettes: Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optimization 35/3 (1997) 311-330. · Zbl 0872.90069 |
| [12] | J.-N. Corvellec, V. V. Motreanu: Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program. 114/2 (2008) 291-319. · Zbl 1190.90206 |
| [13] | N. D. Cuong, A. Y. Kruger: Error bounds revisited, Optimization 71/4 (2022) 1021-1053. · Zbl 1489.49010 |
| [14] | A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings, Springer, Berlin (2009). · Zbl 1178.26001 |
| [15] | A. L. Dontchev: Lectures on Variational Analysis, Applied Mathematical Sciences 205, Springer, Cham (2021). · Zbl 1490.49002 |
| [16] | M. J. Fabian, R. Henrion, A. Y. Kruger, J. V. Outrata: Error bounds: Necessary and sufficient conditions, Set-Valued Var. Analysis 18/2 (2010) 121-149. · Zbl 1192.49018 |
| [17] | H. Gfrerer: First order and second order characterizations of metric subregularity and calmness of constrant set mapping, SIAM J. Optim. 21/4 (2011) 1439-1474. · Zbl 1254.90246 |
| [18] | O. Güler: Augmented Lagrangian algorithms for linear programming, J. Optimization Theory Appl. 75/3 (1992) 445-478. · Zbl 0797.90061 |
| [19] | R. Hesse, D. R. Luke: Nonconvex notions of regularity and convergence of fundamen-tal algorithms for feasibility problems, SIAM J. Optimization 23/4 (2013) 2397-2419. · Zbl 1288.65094 |
| [20] | A. J. Hoffman: On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards 49 (1952) 263-265. |
| [21] | A. D. Ioffe: Regular points of Lipschitz functions, Trans. Amer. Math. Soc. 251 (1979) 61-69. · Zbl 0427.58008 |
| [22] | Z. Wei, M. Théra, J. -C. Yao / Primal Characterizations of Error Bounds ... 1349 |
| [23] | A. D. Ioffe: Metric regularity-a survey. I: Theory, J. Aust. Math. Soc. 101/2 (2016) 188-243. · Zbl 1369.49001 |
| [24] | A. D. Ioffe: Metric regularity-a survey. II: Applications, J. Aust. Math. Soc. 101/3 (2016) 376-417. · Zbl 1369.49002 |
| [25] | A. D. Ioffe: Variational Analysis of Regular Mappings. Theory and Applications, Springer Monographs in Mathematics, Springer, Cham (2017). · Zbl 1381.49001 |
| [26] | A. Jourani: Hoffman’s error bound, local controllability, and sensitivity analysis, SIAM J. Control Optimization 38/3 (2000) 947-970. · Zbl 0945.46023 |
| [27] | A. N. Iusem, A. R. De Pierro: On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Program. 47 (1990) 37-51. · Zbl 0712.90054 |
| [28] | G. Jameson: Ordered Linear Spaces, Springer, Berlin (1970). · Zbl 0196.13401 |
| [29] | D. Klatte, W. Li: Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program. 84/1 (1999) 137-160. · Zbl 1050.90557 |
| [30] | A. Y. Kruger, M. A. López, M. A. Théra: Perturbation of error bounds, Math. Pro-gram. 168 (2018) 533-554. · Zbl 1391.49051 |
| [31] | A. Y. Kruger, H. V. Ngai, M. Théra: Stability of error bounds for convex constraint systems in Banach spaces, SIAM J. Optimization 20/6 (2010) 3280-3296. · Zbl 1208.49030 |
| [32] | S. Łojasiewicz: Sur le problème de la division, Studia Math. 18 (1959) 87-136. · Zbl 0115.10203 |
| [33] | A. S. Lewis, J. S. Pang: Error bounds for convex inequality systems, in: General-ized Convexity, Generalized Monotonicity: Recent Results, Proc. Fifth Symp. on Generalized Convexity, Luminy 1996, J.-P. Crouzeix et al. (eds.), Kluwer Academic Publishers, Dordrecht (1997) 75-110. · Zbl 0953.90048 |
| [34] | Z.-Q. Luo, P. Tseng: On a global error bound for a class of monotone affine variational inequality problems, Oper. Res. Letters 11/3 (1992) 159-165. · Zbl 0777.49009 |
| [35] | Z.-Q. Luo, P. Tseng: Error bounds and convergence analysis of feasible descent meth-ods: a general approach, Ann. Oper. Res. 46 (1993) 157-178. · Zbl 0793.90076 |
| [36] | W. Li: Abadie’s constraint qualification, metric regularity, and error bounds for dif-ferentiable convex inequalities, SIAM J. Optimization 7 (1997) 966-978. · Zbl 0891.90132 |
| [37] | B. S. Mordukhovich: Complete characterization of openness, metric regularity, and Lipschitzian properties of set-valued mappings, Trans. Amer. Math. Soc. 340 (1993) 1-35. · Zbl 0791.49018 |
| [38] | B. S. Mordukhovich: Variational Analysis and Generalized Differentiation I, Springer, Berlin (2006). |
| [39] | K. F. Ng, X. Y. Zheng: Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optimization 12/1 (2001) 1-17. · Zbl 1040.90041 |
| [40] | H. V. Ngai, A. Y. Kruger, M. Théra: Stability of error bounds for semi-infinite convex constraint systems, SIAM J. Optimization 20 (2010) 2080-2096. · Zbl 1202.49024 |
| [41] | H. V. Ngai, M. Théra: Error bounds and implicit multifunction theorem in smooth Banach spaces and applications to optimization, Set-Valued Analysis 12/1-2 (2004) 195-223. · Zbl 1058.49017 |
| [42] | H. V. Ngai, M. Théra: Error bounds in metric spaces and applications to the pertur-bation stability of metric regularity, SIAM J. Optimization 19/1 (2008) 1-20. · Zbl 1158.49020 |
| [43] | H. V. Ngai, M. Théra: Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Program. 116/1-2 (2009) 397-427. · Zbl 1215.49028 |
| [44] | Z. Wei, M. Théra, J. -C. Yao / Primal Characterizations of Error Bounds ... |
| [45] | H. V. Ngai, N. H. Tron, N. V. Vu, M. Théra: Variational analysis of paraconvex mul-tifunctions, J. Optim. Theory Appl. 193 (2022) 180-218. · Zbl 1532.90142 |
| [46] | J. S. Pang: Error bounds in mathematical programming, Math. Program. 79/1-3 (1997) 299-332. · Zbl 0887.90165 |
| [47] | J.-P. Penot: Error bounds, calmness and their applications in nonsmooth analysis, in: Nonlinear Analysis and Optimization. II: Optimization, Contemporary Mathematics 514, American Mathematical Society, Providence (2010) 225-247. · Zbl 1222.49022 |
| [48] | J.-P. Penot: Calculus Without Derivatives, Graduate Texts in Mathematics 266, Springer, New York (2013). · Zbl 1264.49014 |
| [49] | R. R. Phelps: Convex Functions, Monotone Operators and Differentiability, Lecture Notes in Mathematics 1364, Springer, New York (1989). · Zbl 0658.46035 |
| [50] | H. Rådström: An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. 3 (1952) 165-169. · Zbl 0046.33304 |
| [51] | S. M. Robinson: Bounds for error in the solution set of a perturbed linear program, Linear Algebra Appl. 6 (1973) 69-81. · Zbl 0283.90028 |
| [52] | S. M. Robinson: A characterization of stability in linear programming, Oper. Res. 25 (1977) 435-447. · Zbl 0373.90045 |
| [53] | A. Shapiro: Existence and differentiability of metric projections in Hilbert spaces, SIAM J. Optimization 4 (1994) 130-141. · Zbl 0793.41021 |
| [54] | A. Shapiro, F. Al-Khayyal: First order conditions for isolated locally optimal solu-tions, J. Optim. Theory Appl. 77 (1993) 189-196. · Zbl 0792.90074 |
| [55] | Z. Shen, J.-C. Yao, X. Y. Zheng: Calmness and the Abadie CQ for multifunctions and linear regularity for a collection of closed sets, SIAM J. Optim. 29/3 (2019) 2291-2319. · Zbl 1422.90059 |
| [56] | L. Thibault: Unilateral Variational Analysis in Banach Spaces, World Scientific, Singapore (2023). · Zbl 1536.49002 |
| [57] | P. Tseng, D. P. Bertsekas: On the convergence of the exponential multiplier method for convex programming, Math. Program. 60/1 (1993) 1-19. · Zbl 0783.90101 |
| [58] | Z. Wei, C. Tammer, J.-C. Yao: Characterizations for strong Abadie constraint qual-ification and applications to calmness, J. Optimization Theory Appl. 189 (2021) 1-18. · Zbl 1470.90085 |
| [59] | Z. Wei, J.-C. Yao: On constraint qualifications of a nonconvex inequality, Optimiza-tion Letters 12 (2018) 1117-1139. · Zbl 1407.90343 |
| [60] | Z. Wei, J.-C. Yao: On applications of the calmness moduli for multifunctions to error bounds, Optimization 71/12 (2022) 3647-3668. · Zbl 1506.90252 |
| [61] | Z. Wei, J.-C. Yao, X. Y. Zheng: Strong Abadie CQ, ACQ, calmness and linear regu-larity, Math. Program. 145 (2014) 97-131. · Zbl 1302.90156 |
| [62] | C. Zălinescu: Weak sharp minima, well-behaving functions and global error bounds for convex inequalities in Banach spaces, in: Proc. 12th Baikal Int. Conf. on Opti-mization Methods and Their Applications, Irkutsk (2001) 272-284. |
| [63] | X. Y. Zheng, K. F. Ng: Metric regularity and constraint qualifications for convex in-equalities on Banach spaces, SIAM J. Optimization 14 (2004) 757-772. · Zbl 1079.90103 |
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.
