Abstract

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.

Author information

Contact details are reproduced from the original publication and may be historical.

Zhou Wei

Hebei Key Laboratory of Machine Learning and Computational Intelligence, College of Mathematics and Information Science, Hebei University, Baoding, China

weizhou@hbu.edu.cn

Michel Théra

XLIM UMR – CNRS 7252, Université de Limoges, France and: Federation University, Ballarat, Australia

michel.thera@unilim.fr

Jen-Chih Yao

Dept. of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan

yaojc@math.nsysu.edu.tw

Keywords

  • Error bound
  • composite-convex inequality
  • Bouligand tangent cone
  • lower Hadamard directional derivative
  • Hausdorff-Pompeiu excess

Mathematics Subject Classification

90C31, 90C25, 49J52, 46B20

References

  1. M. Abassi, M. Théra: Strongly regular points of mappings, Fixed Point Theory Algorithms Sci. Eng. (2021), art. no. 14.https://doi.org/10.1186/s13663-021-00699-zGoogle Scholar
  2. M. Abassi, M. Théra: About error bounds in metrizable topological vector spaces, Set-Valued Var. Analysis 30 (2022) 1291–1311.https://doi.org/10.1007/s11228-022-00643-2Google Scholar
  3. D. Aussel, A. Daniillids, L. Thibault: Subsmooth sets: Functional characterizations and related concepts, Trans. Amer. Math. Soc. 357 (2005) 1275–1301.https://doi.org/10.1090/S0002-9947-04-03718-3Google Scholar
  4. A. Auslender, J. P. Crouzeix: Global regularity theorems, Math. Oper. Res. 13/2 (1988) 243–253.https://doi.org/10.1287/moor.13.2.243Google Scholar
  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.https://doi.org/10.1051/cocv:2004013Google Scholar
  6. H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Rev. 38/3 (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  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.https://doi.org/10.1080/10556780310001604977Google Scholar
  8. E. M. Bednarczuk, A. Y. Kruger: Error bounds for vector-valued functions: Necessary and sufficient conditions, Nonlinear Analysis 75/3 (2012) 1124–1140.https://doi.org/10.1016/j.na.2011.05.098Google Scholar
  9. J. V. Burke, S. Deng: Weak sharp minima revisited. I: Basic theory, Control Cyber. 31/3 (2002) 439–469.Google Scholar
  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.https://doi.org/10.1007/s10107-005-0615-2Google Scholar
  11. P. L. Combettes: Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optimization 35/3 (1997) 311–330.https://doi.org/10.1007/BF02683333Google Scholar
  12. J.-N. Corvellec, V. V. Motreanu: Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program. 114/2 (2008) 291–319.https://doi.org/10.1007/s10107-007-0102-zGoogle Scholar
  13. N. D. Cuong, A. Y. Kruger: Error bounds revisited, Optimization 71/4 (2022) 1021–1053.https://doi.org/10.1080/02331934.2022.2032695Google Scholar
  14. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings, Springer, Berlin (2009).https://doi.org/10.1007/978-0-387-87821-8Google Scholar
  15. A. L. Dontchev: Lectures on Variational Analysis, Applied Mathematical Sciences 205, Springer, Cham (2021).https://doi.org/10.1007/978-3-030-79911-3Google Scholar
  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.https://doi.org/10.1007/s11228-010-0133-0Google Scholar
  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.https://doi.org/10.1137/100813415Google Scholar
  18. O. Güler: Augmented Lagrangian algorithms for linear programming, J. Optimization Theory Appl. 75/3 (1992) 445–478.https://doi.org/10.1007/BF00940486Google Scholar
  19. R. Hesse, D. R. Luke: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optimization 23/4 (2013) 2397–2419.https://doi.org/10.1137/120902653Google Scholar
  20. A. J. Hoffman: On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards 49 (1952) 263–265.https://doi.org/10.6028/jres.049.027Google Scholar
  21. A. D. Ioffe: Regular points of Lipschitz functions, Trans. Amer. Math. Soc. 251 (1979) 61–69.https://doi.org/10.1090/S0002-9947-1979-0531969-6Google Scholar
  22. A. D. Ioffe: Metric regularity-a survey. I: Theory, J. Aust. Math. Soc. 101/2 (2016) 188–243.https://doi.org/10.1017/S1446788715000701Google Scholar
  23. A. D. Ioffe: Metric regularity-a survey. II: Applications, J. Aust. Math. Soc. 101/3 (2016) 376–417.https://doi.org/10.1017/S1446788715000695Google Scholar
  24. A. D. Ioffe: Variational Analysis of Regular Mappings. Theory and Applications, Springer Monographs in Mathematics, Springer, Cham (2017).https://doi.org/10.1007/978-3-319-64277-2Google Scholar
  25. A. Jourani: Hoffman’s error bound, local controllability, and sensitivity analysis, SIAM J. Control Optimization 38/3 (2000) 947–970.https://doi.org/10.1137/S0363012998339216Google Scholar
  26. A. N. Iusem, A. R. De Pierro: On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Program. 47 (1990) 37–51.https://doi.org/10.1007/BF01580851Google Scholar
  27. G. Jameson: Ordered Linear Spaces, Springer, Berlin (1970).https://doi.org/10.1007/BFb0059130Google Scholar
  28. D. Klatte, W. Li: Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Program. 84/1 (1999) 137–160.https://doi.org/10.1007/s10107980002aGoogle Scholar
  29. A. Y. Kruger, M. A. López, M. A. Théra: Perturbation of error bounds, Math. Program. 168 (2018) 533–554.https://doi.org/10.1007/s10107-017-1129-4Google Scholar
  30. 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.https://doi.org/10.1137/100782206Google Scholar
  31. S. Łojasiewicz: Sur le problème de la division, Studia Math. 18 (1959) 87–136.https://doi.org/10.4064/sm-18-1-87-136Google Scholar
  32. A. S. Lewis, J. S. Pang: Error bounds for convex inequality systems, in: Generalized 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.https://doi.org/10.1007/978-1-4613-3341-8_3Google Scholar
  33. 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.https://doi.org/10.1016/0167-6377(92)90080-MGoogle Scholar
  34. Z.-Q. Luo, P. Tseng: Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res. 46 (1993) 157–178.https://doi.org/10.1007/BF02096261Google Scholar
  35. W. Li: Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities, SIAM J. Optimization 7 (1997) 966–978.https://doi.org/10.1137/S1052623495287927Google Scholar
  36. B. S. Mordukhovich: Complete characterization of openness, metric regularity, and Lipschitzian properties of set-valued mappings, Trans. Amer. Math. Soc. 340 (1993) 1–35.https://doi.org/10.1090/S0002-9947-1993-1156300-4Google Scholar
  37. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation I, Springer, Berlin (2006).https://doi.org/10.1007/3-540-31247-1Google Scholar
  38. K. F. Ng, X. Y. Zheng: Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optimization 12/1 (2001) 1–17.https://doi.org/10.1137/S1052623499358884Google Scholar
  39. 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.https://doi.org/10.1137/090767819Google Scholar
  40. 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.https://doi.org/10.1023/B:SVAN.0000023396.58424.98Google Scholar
  41. H. V. Ngai, M. Théra: Error bounds in metric spaces and applications to the perturbation stability of metric regularity, SIAM J. Optimization 19/1 (2008) 1–20.https://doi.org/10.1137/060675721Google Scholar
  42. 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.https://doi.org/10.1007/s10107-007-0121-9Google Scholar
  43. H. V. Ngai, N. H. Tron, N. V. Vu, M. Théra: Variational analysis of paraconvex multifunctions, J. Optim. Theory Appl. 193 (2022) 180–218.https://doi.org/10.1007/s10957-022-02021-2Google Scholar
  44. J. S. Pang: Error bounds in mathematical programming, Math. Program. 79/1-3 (1997) 299–332.https://doi.org/10.1007/BF02614322Google Scholar
  45. 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.https://doi.org/10.1090/conm/514/10110Google Scholar
  46. J.-P. Penot: Calculus Without Derivatives, Graduate Texts in Mathematics 266, Springer, New York (2013).https://doi.org/10.1007/978-1-4614-4538-8Google Scholar
  47. R. R. Phelps: Convex Functions, Monotone Operators and Differentiability, Lecture Notes in Mathematics 1364, Springer, New York (1989).https://doi.org/10.1007/978-3-662-21569-2Google Scholar
  48. H. Rådström: An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. 3 (1952) 165–169.https://doi.org/10.1090/S0002-9939-1952-0045938-2Google Scholar
  49. S. M. Robinson: Bounds for error in the solution set of a perturbed linear program, Linear Algebra Appl. 6 (1973) 69–81.https://doi.org/10.1016/0024-3795(73)90007-4Google Scholar
  50. S. M. Robinson: A characterization of stability in linear programming, Oper. Res. 25 (1977) 435–447.https://doi.org/10.1287/opre.25.3.435Google Scholar
  51. A. Shapiro: Existence and differentiability of metric projections in Hilbert spaces, SIAM J. Optimization 4 (1994) 130–141.https://doi.org/10.1137/0804006Google Scholar
  52. A. Shapiro, F. Al-Khayyal: First order conditions for isolated locally optimal solutions, J. Optim. Theory Appl. 77 (1993) 189–196.https://doi.org/10.1007/BF00940785Google Scholar
  53. 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.https://doi.org/10.1137/18M1192615Google Scholar
  54. L. Thibault: Unilateral Variational Analysis in Banach Spaces, World Scientific, Singapore (2023).https://doi.org/10.1142/12797Google Scholar
  55. P. Tseng, D. P. Bertsekas: On the convergence of the exponential multiplier method for convex programming, Math. Program. 60/1 (1993) 1–19.https://doi.org/10.1007/BF01580598Google Scholar
  56. Z. Wei, C. Tammer, J.-C. Yao: Characterizations for strong Abadie constraint qualification and applications to calmness, J. Optimization Theory Appl. 189 (2021) 1–18.https://doi.org/10.1007/s10957-020-01808-5Google Scholar
  57. Z. Wei, J.-C. Yao: On constraint qualifications of a nonconvex inequality, Optimization Letters 12 (2018) 1117–1139.https://doi.org/10.1007/s11590-017-1172-3Google Scholar
  58. Z. Wei, J.-C. Yao: On applications of the calmness moduli for multifunctions to error bounds, Optimization 71/12 (2022) 3647–3668.https://doi.org/10.1080/02331934.2021.1906873Google Scholar
  59. Z. Wei, J.-C. Yao, X. Y. Zheng: Strong Abadie CQ, ACQ, calmness and linear regularity, Math. Program. 145 (2014) 97–131.https://doi.org/10.1007/s10107-013-0641-4Google Scholar
  60. 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 Optimization Methods and Their Applications, Irkutsk (2001) 272–284.Google Scholar
  61. X. Y. Zheng, K. F. Ng: Metric regularity and constraint qualifications for convex inequalities on Banach spaces, SIAM J. Optimization 14 (2004) 757–772.https://doi.org/10.1137/S1052623403423102Google Scholar

Suggested citation

Z. Wei, M. Théra, J.-C. Yao. “Primal Characterizations of Error Bounds for Composite-Convex Inequalities.” Journal of Convex Analysis 30 (2023), No. 4, 1329–1350. https://doi.org/10.68381/jca30060

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press.