Abstract

We investigate near equality and almost convexity of extended real valued functions defined on finite-dimensional Euclidean spaces. The main result states that an almost convex function (respectively, its domain, lower level set) is nearly equal to (respectively, the domain, lower level set of) its closure, convex hull and closed convex hull. It is proved that almost convexity of an extended real valued function is equivalent to near equality of itself and another almost convex function. Moreover, it is shown that the operations given by sum, scalar multiple, pointwise supremum, epi-sum and epi-multiple of almost convex functions preserve almost convexity, the formulation of the subdifferential of sum and scalar multiple of almost convex functions on the relative interior of their domain is analogous to that of convex functions under suitable additional assumptions and the proximal average of almost convex functions enjoys analogous properties of lower semi-continuous and convex functions. The epi-sum of almost convex functions is proved to be convex under additional assumptions and the Moreau envelope of an almost convex function is shown to be convex and continuously differentiable with the gradient given by the one related to its closure. Applications to almost convex optimization problems are provided, in particular, under suitable assumptions, the solution set is proved to be nearly convex and the solution sets of two almost convex optimization problems are shown to be nearly equal if the related objective functions are nearly equal. Another application shows that the classical Hoffman's error bound holds for almost convex inequalities under a generalized Slater condition. Several examples are given to illustrate these results.

Author information

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

Jun Li

School of Mathematics and Information, China West Normal University, 637009 Nanchong, Sichuan, P. R. China

junli@cwnu.edu.cn

Giandomenico Mastroeni

Department of Computer Science, University of Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy

gmastroeni@di.unipi.it

Keywords

  • Near equality
  • almost convexity
  • near convexity
  • proximal average
  • optimization
  • error bounds

Mathematics Subject Classification

26B25, 52A20, 90C26

References

  1. A. Aleman: On some generalizations of convex sets and convex functions, Anal. Numér. Théor. Approx. 14(1) (1985) 1–6.Google Scholar
  2. 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
  3. H. H. Bauschke, R. Goebel, Y. Lucet, X. F. Wang: The proximal average: basic theory, SIAM J. Optim. 19(2) (2008) 766–785.https://doi.org/10.1137/070687542Google Scholar
  4. H. H. Bauschke, Y. Lucet, M. Trienis: How to transform one convex function continuously into another, SIAM Rev. 50(1) (2008) 115–132.https://doi.org/10.1137/060664513Google Scholar
  5. H. H. Bauschke, E. Matoušková, S. Reich: Projection and proximal point methods: convergence results and counterexamples, Nonlinear Anal. 56(5) (2004) 715–738.https://doi.org/10.1016/j.na.2003.10.010Google Scholar
  6. H. H. Bauschke, S. M. Moffat, X. F. Wang: Near equality, near convexity, sums of maximally monotone operators, and averages of firmly nonexpansive mappings, Math. Program. Ser. B 139(1-2) (2013) 55–70.https://doi.org/10.1007/s10107-013-0659-7Google Scholar
  7. J. M. Borwein, A. S. Lewis: Partially finite convex programming. I: Quasi-relative interiors and duality theory, Math. Program. Ser. B 57(1) (1992) 15–48.https://doi.org/10.1007/BF01581072Google Scholar
  8. R. I. Boţ, S. M. Grad, G. Wanka: Fenchel’s duality theorem for nearly convex functions, J. Optim. Theory Appl. 132(3) (2007) 509–515.https://doi.org/10.1007/s10957-007-9234-9Google Scholar
  9. R. I. Boţ, S. M. Grad, G. Wanka: Duality in Vector Optimization, Springer, Berlin et al. (2009).https://doi.org/10.1007/978-3-642-02886-1Google Scholar
  10. R. I. Boţ, G. Kassay, G. Wanka: Strong duality for generalized convex optimization problems, J. Optim. Theory Appl. 127(1) (2005) 45–70.https://doi.org/10.1007/s10957-005-6392-5Google Scholar
  11. R. I. Boţ, G. Kassay, G. Wanka: Duality for almost convex optimization problems via the perturbation approach, J. Global Optim. 42(3) (2008) 385–399.https://doi.org/10.1007/s10898-008-9300-3Google Scholar
  12. W. W. Breckner, G. Kassay: A systematization of convexity concepts for sets and functions, J. Convex Analysis 4(1) (1997) 109–127.https://doi.org/10.68381/jca04005Google Scholar
  13. H. Brezis, A. Haraux: Image d’une somme d’opérateurs monotones et applications, Israel J. Math. 23(2) (1976) 165–186.https://doi.org/10.1007/BF02756796Google Scholar
  14. J. V. Burke, S. Deng: Weak sharp minima revisited. II: Application to linear regularity and errors bounds, Math. Program. Ser. B 104(2-3) (2005) 235–261.https://doi.org/10.1007/s10107-005-0615-2Google Scholar
  15. J. V. Burke, M. C. Ferris: Weak sharp minima in mathematical programming, SIAM J. Control Optim. 31(5) (1993) 1340–1359.https://doi.org/10.1137/0331063Google Scholar
  16. Ş. Cobzaş, I. Muntean: Duality relations and characterizations of best approximation for p-convex sets, Anal. Numér. Théor. Approx. 16(2) (1987) 95–108.Google Scholar
  17. F. Flores-Bazán, A. Jourani, G. Mastroeni: On the convexity of the value function for a class of nonconvex variational problems: existence and optimality conditions, SIAM J. Control Optim. 52(6) (2014) 3673–3693.https://doi.org/10.1137/14096877XGoogle Scholar
  18. J. B. G. Frenk, G. Kassay: Lagrangian duality and cone convexlike functions, J. Optim. Theory Appl. 134(1) (2007) 207–222.https://doi.org/10.1007/s10957-007-9221-1Google Scholar
  19. J. W. Green, W. Gustin: Quasiconvex sets, Canadian J. Math. 2 (1950) 489–507.https://doi.org/10.4153/CJM-1950-046-xGoogle Scholar
  20. R. Henrion, J. V. Outrata: Calmness of constraint systems with applications, Math. Program. Ser. B 104(2-3) (2005) 437–464.https://doi.org/10.1007/s10107-005-0623-2Google Scholar
  21. J. B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, Springer, Berlin et al. (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  22. A. J. Hoffman: On approximate solutions of systems of linear inequalities, J. Research Nat. Bur. Standards 49 (1952) 263–265.https://doi.org/10.6028/jres.049.027Google Scholar
  23. V. Jeyakumar, J. Gwinner: Inequality systems and optimization, J. Math. Anal. Appl. 159(1) (1991) 51–71.https://doi.org/10.1016/0022-247X(91)90221-KGoogle Scholar
  24. D. Klatte, W. Li: Asymptotic constraint qualifications and global errors for convex inequalities, Math. Program. Ser. A 84(1) (1999) 137–160.https://doi.org/10.1007/s10107980002aGoogle Scholar
  25. A. S. Lewis, J. S. Pang: Error bounds for convex inequality systems, in: Generalized Convexity, Generalized Monotonicity, J. P. Crouzeix et al. (eds.), Kluwer Academic Publishers, Dordrecht et al. (1998) 75–110.https://doi.org/10.1007/978-1-4613-3341-8_3Google Scholar
  26. W. Li: Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities, SIAM J. Optim. 7(4) (1997) 966–978.https://doi.org/10.1137/S1052623495287927Google Scholar
  27. Z. Q. Luo, J. S. Pang: Error bounds for analytic systems and their applications, Math. Program. Ser. A 67(1) (1994) 1–28.https://doi.org/10.1007/BF01582210Google Scholar
  28. G. J. Minty: On the maximal domain of a “monotone” function, Michigan Math. J. 8 (1961) 135–137.https://doi.org/10.1307/mmj/1028998564Google Scholar
  29. J. J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  30. K. F. Ng, X. Y. Zheng: Error bounds for lower semicontinuous functions in normal spaces, SIAM J. Optim. 12(1) (2001) 1–17.https://doi.org/10.1137/S1052623499358884Google Scholar
  31. J. S. Pang: Error bounds in mathematical programming, Math. Program. Ser. A 79(1-3) (1997) 299–332.https://doi.org/10.1007/BF02614322Google Scholar
  32. A. W. Roberts, D. E. Varberg: Convex Functions, Academic Press, New York et al. (1973).Google Scholar
  33. S. M. Robinson: An application of error bounds for convex programming in a linear space, SIAM J. Control 13(2) (1975) 271–273.https://doi.org/10.1137/0313015Google Scholar
  34. R. T. Rockafellar: Duality and stability in extremum problems involving convex functions, Pacific J. Math. 21 (1967) 167–187.https://doi.org/10.2140/pjm.1967.21.167Google Scholar
  35. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  36. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  37. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin et al. (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  38. A. M. Rubinov: Abstract Convexity and Global Optimization, Kluwer Academic Publishers, Dordrecht et al. (2000).https://doi.org/10.1007/978-1-4757-3200-9Google Scholar
  39. Z. L. Wu, J. J. Ye: On error bounds for semicontinuous functions, Math. Program. Ser. A 92(2) (2002) 301–314.https://doi.org/10.1007/s101070100278Google Scholar
  40. C. Zãlinescu: Convex Analysis in General Vector Spaces, World Scientific, River Edge (2002).https://doi.org/10.1142/5021Google Scholar

Suggested citation

J. Li, G. Mastroeni. “Near Equality And Almost Convexity Of Functions With Applications To Optimization And Error Bounds.” Journal of Convex Analysis 26 (2019), No. 3, 785–822. https://doi.org/10.68381/jca26043

Download BibTeXPublished by Heldermann Verlag.

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