Abstract

This paper focuses on the stability of both local and global error bounds for a proper lower semicontinuous convex function defined on a Banach space. We first provide precise estimates of error bound moduli using directional derivatives. For a given proper lower semicontinuous convex function on a Banach space, we prove that the stability of local error bounds under small perturbations is equivalent to the directional derivative at a reference point having a non-zero minimum over the unit sphere. Additionally, the stability of global error bounds is shown to be equivalent to the infimum of the directional derivatives, at all points on the boundary of the solution set, being bounded away from zero over some neighborhood of the unit sphere.

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, P. R. China

weizhou@hbu.edu.cn

Jen-Chih Yao

(1) Research Center for Interneural Computing, China Medical University, Taichung, Taiwan
(2) Academy of Romanian Scientists, Bucharest, Romania
and: China Medical University Hospital, Taichung, Taiwan

yaojc@mail.cmu.edu.tw

Keywords

  • Stability
  • error bound
  • convex function
  • directional derivative
  • Hoffman's constant

Mathematics Subject Classification

90C31, 90C25, 49J52, 46B20

References

  1. M. Abbasi, M. Théra: Strongly regular points of mappings, Fixed Point Theory Algorithms Sci. Eng. 2021 (2021), art. no. 14, 13p.https://doi.org/10.1186/s13663-021-00699-zGoogle Scholar
  2. M. Abbasi, M. Théra: About error bounds in metrizable topological vector spaces, Set-Valued Var. Analysis 30/4 (2022) 1291–1311.https://doi.org/10.1007/s11228-022-00643-2Google Scholar
  3. 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
  4. D. Azé: A survey on error bounds for lower semicontinuous functions, ESAIM Proc. 13 (2003) 1–17.https://doi.org/10.1051/proc:2003004Google Scholar
  5. D. Azé: A unified theory for metric regularity of multifunctions, J. Convex Analysis 13/2 (2006) 225–252.https://doi.org/10.68381/jca13023Google Scholar
  6. D. Azé, J.-N. Corvellec: On the sensitivity analysis of Hoffman constants for systems of linear inequalities, SIAM J. Optim. 12/4 (2002) 913–927.https://doi.org/10.1137/S1052623400375853Google Scholar
  7. D. Azé, J.-N. Corvellec: Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM Control Optim. Calc. Var. 10/3 (2004) 409–425.https://doi.org/10.1051/cocv:2004013Google Scholar
  8. H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38/3 (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  9. A. Beck, M. Teboulle: Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems, Optim. Methods Softw. 18/4 (2003) 377-394.https://doi.org/10.1080/10556780310001604977Google Scholar
  10. 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
  11. J. V. Burke, S. Deng: Weak sharp minima revisited. I: Basic theory, Control Cybernetics 31/3 (2002) 439–469.Google Scholar
  12. J. V. Burke, S. Deng: Weak sharp minima revisited. II: Application to linear regularity and error bounds, Math. Programming Ser. B 104/2-3 (2005) 235–261.https://doi.org/10.1007/s10107-005-0615-2Google Scholar
  13. M. J. Cánovas, A. Y. Kruger, M. A. López, J. Parra, M. A. Théra: Calmness modulus of linear semi-infinite programs, SIAM J. Optim. 24/1 (2014) 29–48.https://doi.org/10.1137/130907008Google Scholar
  14. P. L. Combettes: Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optim. 35/3 (1997) 311–330.https://doi.org/10.1007/BF02683333Google Scholar
  15. J.-N. Corvellec, V. V. Motreanu: Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Programming Ser. A 114/2 (2008) 291–319.https://doi.org/10.1007/s10107-007-0102-zGoogle Scholar
  16. S. Deng: Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems, Math. Programming Ser. A 83/2 (1998) 263–276.https://doi.org/10.1007/BF02680562Google Scholar
  17. A. L. Dontchev, A. S. Lewis, R. T. Rockafellar: The radius of metric regularity, Trans. Amer. Math. Soc. 355/2 (2003) 493–517.https://doi.org/10.1090/S0002-9947-02-03088-XGoogle Scholar
  18. I. Ekeland: On the variational principle, J. Math. Analysis Appl. 47 (1974) 324–353.https://doi.org/10.1016/0022-247X(74)90025-0Google Scholar
  19. 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
  20. O. Güler: Augmented Lagrangian algorithms for linear programming, J. Optim. Theory Appl. 75/3 (1992) 445–470.https://doi.org/10.1007/BF00940486Google Scholar
  21. R. Hesse, D. R. Luke: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim. 23/4 (2013) 2397–2419.https://doi.org/10.1137/120902653Google Scholar
  22. 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
  23. 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
  24. 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
  25. 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
  26. A. D. Ioffe, V. M. Tihomirov: Theory of Extremal Problems, Studies in Mathematics and its Applications Vol. 6, North-Holland, Amsterdam (1979).Google Scholar
  27. A. N. Iusem, A. R. De Pierro: On the convergence properties of Hildreth’s quadratic programming algorithm, Math. Programming Ser. A 47/1 (1990) 37–51.https://doi.org/10.1007/BF01580851Google Scholar
  28. A. Jourani: Erratum to “Hoffman’s error bound, local controllability, and sensitivity analysis” (SIAM J. Control Optim. 38/3 (2000) 947–970, SIAM J. Control Optim. 39/5 (2000) 1650.https://doi.org/10.1137/S0363012998339216Google Scholar
  29. D. Klatte, W. Li: Asymptotic constraint qualifications and global error bounds for convex inequalities, Math. Programming Ser. A 84/1 (1999) 137–160.https://doi.org/10.1007/s10107980002aGoogle Scholar
  30. A. Y. Kruger: Error bounds and metric subregularity, Optimization 64/1 (2015) 49–79.https://doi.org/10.1080/02331934.2014.938074Google Scholar
  31. A. Y. Kruger, M. A. López, M. A. Théra: Perturbation of error bounds, Math. Programming Ser. B 168/1-2 (2018) 533–554.https://doi.org/10.1007/s10107-017-1129-4Google Scholar
  32. A. Y. Kruger, H. V. Ngai, M. Théra: Stability of error bounds for convex constraint systems in Banach spaces, SIAM J. Optim. 20/6 (2010) 3280–3296.https://doi.org/10.1137/100782206Google Scholar
  33. A. S. Lewis, J. S. Pang: Error bounds for convex inequality systems, in: Generalized Convexity, Generalized Monotonicity: Recent Results, J.-P. Crouzeix et al. (eds.), Nonconvex Optimization and its Applications Vol. 27, Kluwer Academic Publishers, Dordrecht (1998) 75-110.https://doi.org/10.1007/978-1-4613-3341-8_3Google Scholar
  34. D. R. Luke, N. H. Thao, M. K. Tam: Implicit error bounds for Picard iterations on Hilbert spaces, Vietnam J. Math. 46/2 (2018) 243–258.https://doi.org/10.1007/s10013-018-0279-xGoogle Scholar
  35. 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
  36. Z.-Q. Luo, P. Tseng: Perturbation analysis of a condition number for linear systems, SIAM J. Matrix Analysis Appl. 15/2 (1994) 636–660.https://doi.org/10.1137/S0895479892224768Google Scholar
  37. O. L. Mangasarian: A condition number for differentiable convex inequalities, Math. Oper. Res. 10/2 (1985) 175–179.https://doi.org/10.1287/moor.10.2.175Google Scholar
  38. B. Morduhovich: Variational Analysis and Generalized Differentiation I, A Series of Comprehensive Studies in Mathematics, Springer, Berlin (2006).Google Scholar
  39. B. Morduhovich: Variational Analysis and Generalized Differentiation II, A Series of Comprehensive Studies in Mathematics, Springer, Berlin (2006).Google Scholar
  40. K. F. Ng, X. Y. Zheng: Error bounds for lower semicontinuous functions in normed spaces, SIAM J. Optim. 12/1 (2001) 1–17.https://doi.org/10.1137/S1052623499358884Google Scholar
  41. H. V. Ngai, A. Y. Kruger, M. Théra: Stability of error bounds for semi-infinite convex constraint systems, SIAM J. Optim. 20/4 (2010) 2080–2096.https://doi.org/10.1137/090767819Google Scholar
  42. H. V. Ngai, M. Théra: Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Programming Ser. B 116/1-2 (2009) 397–427.https://doi.org/10.1007/s10107-007-0121-9Google Scholar
  43. J S. Pang: Error bounds in mathematical programming, Math. Programming Ser. B 79/1-3 (1997) 299–332.https://doi.org/10.1007/BF02614322Google Scholar
  44. J.-P. Penot: Calculus Without Derivatives, Graduate Texts in Mathematics Vol. 266, Springer, New York (2013).https://doi.org/10.1007/978-1-4614-4538-8Google Scholar
  45. R. R. Phelps: Convex Functions, Monotone Operators and Differentiability, 2nd ed., Lecture Notes in Mathematics Vol. 1364, Springer, Berlin (1993).Google Scholar
  46. 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
  47. S. M. Robinson: An application of error bounds for convex programming in a linear space, SIAM J. Control 13 (1975) 271–273.https://doi.org/10.1137/0313015Google Scholar
  48. S. M. Robinson: A characterization of stability in linear programming, Operations Res. 25/3 (1977) 435–447.https://doi.org/10.1287/opre.25.3.435Google Scholar
  49. T. R Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der mathematischen Wissenschaften Vol. 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  50. W. Schirotzek: Nonsmooth Analysis, Universitext, Springer, Berlin (2007).https://doi.org/10.1007/978-3-540-71333-3Google Scholar
  51. L. Thibault: Unilateral Variational Analysis in Banach Spaces. I: General Theory, World Scientific, Hackensack (2023).https://doi.org/10.1142/12797Google Scholar
  52. P. Tseng, D. P. Bertsekas: On the convergence of the exponential multiplier method for convex programming, Math. Programming Ser. A 60/1 (1993) 1–19.https://doi.org/10.1007/BF01580598Google Scholar
  53. Z. Wei, M. Théra, J.-C. Yao: Characterizations of stability of error bounds for convex inequality constraint systems, Open J. Math. Optim. 3 (2022), art. no. 2, 17p.https://doi.org/10.5802/ojmo.13Google Scholar
  54. Z. Wei, M. Théra, J.-C. Yao: Primal characterizations of error bounds for composite-convex inequalities, J. Convex Analysis 30/4 (2023) 1329–1350.https://doi.org/10.68381/jca30060Google Scholar
  55. Z. Wei, M. Théra, J.-C. Yao: Primal characterizations of stability of error bounds for semi-infinite convex constraint systems in Banach spaces, Optimization 73/12 (2024) 3725–3753.https://doi.org/10.1080/02331934.2024.2410266Google Scholar
  56. Z. Wu, J. J. Ye: On error bounds for lower semicontinuous functions, Math. Programming Ser. A 92/2 (2002) 301–314.https://doi.org/10.1007/s101070100278Google Scholar
  57. J.-C. Yao, X. Y. Zheng: Error bound and well-posedness with respect to an admissible function, Appl. Analysis 95/5 (2016) 1070–1087.https://doi.org/10.1080/00036811.2015.1051474Google Scholar

Suggested citation

Z. Wei, M. Théra, J.-C. Yao. “Perturbation Analysis of Error Bounds for Convex Functions on Banach Spaces.” Journal of Convex Analysis 32 (2025), No. 3, 883–900. https://doi.org/10.68381/jca32045

Download BibTeXPublished by Heldermann Verlag.

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