Abstract

We analyse the C1,1C^{1,1} tight approximations of the finite maximum function defined by the upper compensated convex transform introduced in a previous paper of the second author [ Compensated convexity and its applications, Ann. Inst. H. Poincaré (C), Non Linear Analysis 25/4 (2008) 743–771]. We present the precise geometric structure, the tightness property, the sharp error estimates and the asymptotic properties of our approximation. We compare our method with the well-known "log-sum-exp" smooth approximation by showing that our approximation is geometrically much sharper than the "log-sum-exp" approximation. We apply our results to smooth approximations for functions defined by the maximum of finitely many smooth functions in Rn\mathbb{R}^n arising from finite and semi-infinite minimax optimization problems.

Author information

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

Ke Yin

Center for Mathematical Sciences, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

kyin@hust.edu.cn

Keywords

  • Maximum function
  • compensated convex transforms
  • tight smooth approximation
  • convex optimization
  • minimax problem

Mathematics Subject Classification

90C25, 90C30, 90C34, 90C47, 65K05, 65K10, 49M20, 49M37

References

  1. 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
  2. A. Beck, M. Teboulle: Smoothing and first order methods: A unified framework, SIAM J. Optimization 22/2 (2012) 557–580.https://doi.org/10.1137/100818327Google Scholar
  3. D. P. Bertsekas: Nondifferentiable optimization via approximation, Math. Programming Study 3 (1975) 1–25.https://doi.org/10.1007/BFb0120696Google Scholar
  4. P. Blanchard, D. J. Higham, N. J. Higham: Accurately computing the log-sum-exp and softmax functions, IMA J. Numer. Analysis 41/4 (2021) 2311–2330.https://doi.org/10.1093/imanum/draa038Google Scholar
  5. J. P. Boyle, R. L. Dykstra: A Method for Finding Projections onto the Intersection of Convex Sets in Hilbert Spaces, in: Advances in Order Restricted Statistical Inference, Lecture Notes in Statistics 37, Springer, New York (1986) 28–47.https://doi.org/10.1007/978-1-4613-9940-7_3Google Scholar
  6. D. Butnariu, Y. Censor, P. Gurfil, E. Hadar: On the behavior of subgradient projections methods for convex feasibility problems in Euclidean spaces, SIAM J. Optimization 19/2 (2008) 786–807.https://doi.org/10.1137/070689127Google Scholar
  7. Y. Censor, A. Lent: Cyclic subgradient projections, Math. Programming 24/1 (1982) 233–235.https://doi.org/10.1007/BF01585107Google Scholar
  8. C. Chen, O. L. Mangasarian: A class of smoothing functions for nonlinear and mixed complementarity problems, Comp. Optimization Appl. 5/2 (1996) 97–138.https://doi.org/10.1007/BF00249052Google Scholar
  9. X. Chen: Smoothing methods for nonsmooth, nonconvex minimization, Math. Programming 134/1 (2012) 71–99.https://doi.org/10.1007/s10107-012-0569-0Google Scholar
  10. 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
  11. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, MIT Press, Cambridge (2001).Google Scholar
  12. R. L. Dykstra: An algorithm for restricted least squares regression, J. Amer. Statist. Assoc. 78/384 (1983) 837–842.https://doi.org/10.1080/01621459.1983.10477029Google Scholar
  13. R. Escalante, M. Raydan: Alternating Projection Methods, Fundamentals of Algorithms 8, SIAM, Philadelphia (2011).https://doi.org/10.1137/9781611971941Google Scholar
  14. J.-B. Hiriart-Urruty, C. Lemaréchal: Fundamentals of Convex Analysis, Grundlehren, Springer, Berlin (2001).https://doi.org/10.1007/978-3-642-56468-0Google Scholar
  15. J. Hoschek, D. Lasser, L. L. Schumaker: Fundamentals of Computer Aided Geometric Design, A. K. Peters, Wellesley (1993).Google Scholar
  16. P. J. Huber: Robust estimation of a location parameter, in: Breakthroughs in Statistics. Volume 2, Springer Series in Statististics, Springer, New York (1992) 492–518.https://doi.org/10.1007/978-1-4612-4380-9_35Google Scholar
  17. B. Kirchheim, J. Kristensen: Differentiability of convex envelopes, C. Rend. Acad. Sci., Series I Math. 333/8 (2001) 725–728.https://doi.org/10.1016/S0764-4442(01)02117-6Google Scholar
  18. X.-S. Li, S.-C. Fang: On the entropic regularization method for solving min-max problems with applications, Math. Meth. Oper. Res. 46/1 (1997) 119–130.https://doi.org/10.1007/BF01199466Google Scholar
  19. M. López, G. Still: Semi-infinite programming, Eur. J. Oper. Res. 180/2 (2007) 491–518.https://doi.org/10.1016/j.ejor.2006.08.045Google Scholar
  20. Yu. Nesterov: Smooth minimization of non-smooth functions, Math. Programming 103/1 (2005) 127–152.https://doi.org/10.1007/s10107-004-0552-5Google Scholar
  21. Yu. Nesterov: Gradient methods for minimizing composite functions, Math. Programming 140/1 (2013) 125–161.https://doi.org/10.1007/s10107-012-0629-5Google Scholar
  22. E. Y. Pee, J. O. Royset: On solving large-scale finite minimax problems using exponential smoothing, J. Optimization Theory Appl. 148/2 (2011) 390–421.https://doi.org/10.1007/s10957-010-9759-1Google Scholar
  23. E. Polak, J. O. Royset, R. S. Womersley: Algorithms with adaptive smoothing for finite minimax problems, J. Optimization Theory Appl. 119/3 (2003) 459–484.https://doi.org/10.1023/B:JOTA.0000006685.60019.3eGoogle Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton Landmarks in Mathematics 28, Princeton University Press, Princeton (1970).Google Scholar
  25. J. O. Royset, E. Y. Pee: Rate of convergence analysis of discretization and smoothing algorithms for semiinfinite minimax problems, J. Optimization Theory Appl. 155/3 (2012) 855–882.https://doi.org/10.1007/s10957-012-0109-3Google Scholar
  26. S. Xu: Smoothing method for minimax problems, Comp. Optimization Appl. 20/3 (2001) 267–279.https://doi.org/10.1023/A:1011211101714Google Scholar
  27. H.-X. Yin: Error bounds of two smoothing approximations for semi-infinite minimax problems, Acta Math. Appl. Sinica, Engl. Ser. 25/4 (2009) 685–696.https://doi.org/10.1007/s10255-008-8828-9Google Scholar
  28. S. Žaković, B. Rustem: Semi-infinite programming and applications to minimax problems, Ann. Oper. Res. 124/1-4 (2003) 81–110.https://doi.org/10.1023/B:ANOR.0000004764.76984.30Google Scholar
  29. I. Zang: A smoothing-out technique for min-max optimization, Math. Programming 19/1 (1980) 61–77.https://doi.org/10.1007/BF01581628Google Scholar
  30. K. Zhang: Compensated convexity and its applications, Ann. Inst. H. Poincaré (C), Non Linear Analysis 25/4 (2008) 743–771.https://doi.org/10.1016/j.anihpc.2007.08.001Google Scholar
  31. K. Zhang: Convex analysis based smooth approximations of maximum functions and squared-distance functions, J. Nonlinear Convex Analysis 9 (2008) 379–406.Google Scholar
  32. K. Zhang, E. Crooks, A. Orlando: Compensated convexity, multiscale medial axis maps and sharp regularity of the squared-distance function, SIAM J. Math. Analysis 47/6 (2015) 4289–4331.https://doi.org/10.1137/140993223Google Scholar
  33. K. Zhang, E. Crooks, A. Orlando: Compensated convexity methods for approximations and interpolations of sampled functions in Euclidean spaces: Theoretical foundations, SIAM J. Math. Analysis 48/6 (2016) 4126–4154.https://doi.org/10.1137/15M1045673Google Scholar
  34. K. Zhang, E. Crooks, A. Orlando: Compensated convexity methods for approximations and interpolations of sampled functions in Euclidean spaces: Applications to contour lines, sparse data, and inpainting, SIAM J. Imaging Sciences 11/4 (2018) 2368–2428.https://doi.org/10.1137/17M116152XGoogle Scholar
  35. K. Zhang, A. Orlando, E. Crooks: Compensated convexity and Hausdorff stable geometric singularity extractions, Math. Models Meth. Appl. Sci. 25/4 (2015) 747–801.https://doi.org/10.1142/S0218202515500189Google Scholar
  36. K. Zhang, A. Orlando, E. Crooks: Compensated convexity and Hausdorff stable extraction of intersections for smooth manifolds, Math. Models Meth. Appl. Sci. 25/5 (2015) 839–873.https://doi.org/10.1142/S0218202515500207Google Scholar

Suggested citation

K. Yin, K. Zhang. “A Tight Smooth Approximation of the Maximum Function and its Applications.” Journal of Convex Analysis 29 (2022), No. 4, 1193–1224. https://doi.org/10.68381/jca29066

Download BibTeXPublished by Heldermann Verlag.

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