Error bounds of lower semi-continuous convex-along-rays functions

Document Type : Research Paper

Authors

1 Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran

2 Department of Mathematics and Mahani Mathematical Research Center, Shahid Bahonar University of Kerman, Iran

Abstract

In this paper, we study Lipschitz global error bounds for lower semi-continuous convex-along-rays (l.s.c. CAR) functions. We find a condition that ensures the existence of a global error bound for a CAR function. Moreover, we find a condition under which an l.s.c. CAR function does not have a Lipschitz global error bound. Finally, we survey Lipschitz's global error bounds of an l.s.c. (in particular, an l.s.c. CAR) function from the perspective of abstract convexity.

Keywords

[1] J.P. Aubin and H. Frankowska, Set-valued Analysis, Birkhauser, Boston, 1990.
[2] D. Aze, J.N. Corvellec, Characterization of error bound for lower semi-continuous functions on metric spaces, ESAIM: Control Optim. Calc. Variations 10 (2004), 409–425.
[3] H.H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, 2010.
[4] M. Chao and C. Cheng, Linear and non-linear error bound for lower semi-continuous functions, Optim. Lett. 8 (2014), 1301–1312.
[5] F.H. Clark, Optimization and non-smooth Analysis, Wiley, New York, 1983.
[6] S. Deng, Computable error bounds for convex inequality systems in reflexive Banach spaces, SIAMJ. Optim. 7 (1997), 274–279.
[7] S. Deng, Global error bound for convex inequality systems in Banach spaces, SIAM J. Control Optim. 36 (1998), no. 4, 1240–1249.
[8] M.J. Fabian, R. Henrion, A.Y. Kruger and J.V. Outrata, Error bounds necessary and sufficient conditions Setvalued Anal 18 (2010), 121–149.
[9] O. Guler, A. Hoffman and U. Rothblum, Approximations to solutions to systems of linear inequalities, SIAM J. Matrix Anal. Appl. 16 (1995), no. 2, 688–696.
[10] A.J. Hoffman, On approximate solutions of system of linear inequalities, J. Res. Nat. Bureau Standards 49 (1952), 263–265.
[11] H. Hu, Characterizations of local and global error bounds for convex inequalities in Banach spaces, SIAMJ. Optim. 20 (2010), 3280–3296.
[12] D. Klatte, Lipschitz stability and Hoffman error bounds for convex inequality systems, Proc. Conf. on Parametric Optimization and Related Topics IV, Enschede, 1995.
[13] D. Klatte and G. Thiere, Error bounds for solutions of linear equations and inequalities, Z. Oper. Res. 41 (1995), no. 2, 191–214.
[14] F.N. Kung and Z. Rui, Linear regularity and ϕ-regularity of non-convex sets, J. Math. Anal. Appl. 328 (2007), no. 1, 257–280.
[15] H.A. Lethi, H.V. Ngai and T. Phamdinh, Exact penalty and error bounds in DC programming, J. Glob. Optim. 52 (2012), 509–535.
[16] A.S. Lewis and J.S. Pang, Error bounds for convex inequality systems, Crouzeix. J.-P. Martinez-Legaz. J-E. Volle. M. Eds, Generalized convexity. Generalized monotonicity, 1998, pp. 75–110.
[17] G. Li, Global error bounds for piecewise convex polynomials, Math Program. Ser.A 137 (2011), 37–64.
[18] W. Li, Abadie constraint qualifications, metric regularity and error bounds for differentiable convex inequalities, SIAM J. Optim. 7 (1997), no. 4, 966–978.
[19] W. Li, Error bounds for piecewise convex quadratic programs and applications, SIAM J. Control Optim. 33 (1995), no. 5, 1510–1529.
[20] C. Lin and P. Wang, Iteration complexity of feasible descent methods for convex optimization, J. Machine Learn. Res. 15 (2014), no. 1, 1523–1548.
[21] X.D. Luo and Z.Q. Luo, Extensions of Hoffman error bound to polynomial systems, SIAM J. Optim. 4 (1994), 383–392.
[22] K.F. Ng and X.Y. Zheng, Error bounds for lower semi-continuous functions in normed spaces, SIAM. J. Optim. 12 (2002), no. 1, 1–17.
[23] J. Pena, J. Vera and L.F. Zuluaga, An algorithm to compute the Hoffman constant of a system of linear constraints, arXiv preprint arXiv:1804.08418, 2018-arxiv.org
[24] J.P. Penot, Error bounds, calmness and their applications in non-smooth Analysis, Contemp. Math. 514 (2010), 225–247.
[25] A. Rubinov, Abstract convexity and global optimization, Kluwer, 2000,
[26] Z. Wu and J.J.Ye, On error bounds for lower semi-continuous functions, Math. Program. 92 (2002), no. 2, 301–314.
[27] Z. Wu and J.J. Ye, Sufficient conditions for error bounds, SIAM. Optim. 12 (2002), no. 2, 421–435.
Volume 14, Issue 10
October 2023
Pages 139-153
  • Receive Date: 04 June 2022
  • Revise Date: 12 January 2023
  • Accept Date: 05 February 2023