phone +7 (3412) 91 60 92

Archive of Issues

Russia Nizhni Novgorod
Section Mathematics
Title Application of extreme sub- and epiarguments, convex and concave envelopes to search for global extrema
Author(-s) Galkin O.E.a, Galkina S.Yu.a
Affiliations National Research University Higher School of Economics, Nizhni Novgoroda
Abstract For real-valued functions $f$, defined on subsets of real linear spaces, the notions of extreme subarguments, extreme epiarguments, natural convex $\check{f}$ and natural concave $\hat{f}$ envelopes are introduced. It is shown that for any strictly convex function $g$, any point of the global maximum of the function $f+g$ is an extreme subargument for the function $f$. A similar result is obtained for functions of the form $f/v + g$. Based on these results, a method is proposed, that facilitates the search for global extrema of functions in some cases. It is proved that under certain conditions the functions $f/v+g$ and $\hat{f}/v+g$ have the same global maximum and the same points of the global maximum. Necessary and sufficient conditions for the naturalness of the convex envelope of function are given. A sufficient condition for the invariance of values of the concave envelope $\hat{f}$ during narrowing the domain of $f$ is established. Extreme sub- and epiarguments for continuous nowhere differentiable Gray-Takagi function $K(x)$ of Kobayashi on the segment $[0;1]$ are found. Moreover, the global extrema of the function $K(x)/\cos{x}$ and the global maximum of the function $K(x)-\sqrt{x(1-x)}$ on $[0;1]$ are calculated. The article is provided with examples and graphic illustrations.
Keywords nondifferentiable optimization, extreme subarguments (subabscissae) and epiarguments (epiabscissae) of function, natural convex and concave envelopes of function, Gray Takagi function of Kobayashi
UDC 517.518.244, 519.6
MSC 26A27, 26A30, 26B25, 49M30, 90C26
DOI 10.20537/vm190402
Received 16 September 2019
Language Russian
Citation Galkin O.E., Galkina S.Yu. Application of extreme sub- and epiarguments, convex and concave envelopes to search for global extrema, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2019, vol. 29, issue 4, pp. 483-500.
  1. Dem'yanov V.F., Malozemov V.N. Introduction to minimax, New York: Dover, 1990. Original Russian text published in Dem'yanov V.F., Malozemov V.N. Vvedenie v minimaks, Moscow: Nauka, 1972.
  2. Sukhorukova N., Ugon J. Chebyshev approximation by linear combinations of fixed knot polynomial splines with weighting functions, Journal of Optimization Theory and Applications, 2016, vol. 171, no. 2, pp. 536-549.
  3. Kobayashi Z. Digital sum problems for the Gray code representation of natural numbers, Interdisciplinary Information Sciences, 2002, vol. 8, no. 2, pp. 167-175.
  4. Chen L.H.Y., Hwang H.-K., Zacharovas V. Distribution of the sum-of-digits function of random integers: A survey, Probability Surveys, 2014, vol. 11, pp. 177-236.
  5. Galkin O.E., Galkina S.Yu. Global extrema of the Gray Takagi function of Kobayashi and binary digital sums, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2017, vol. 27, issue 1, pp. 17-25 (in Russian).
  6. Dem'yanov V.F., Vasil'ev L.V. Nondifferentiable optimization, New York: Springer, 1985. Original Russian text published in Dem'yanov V.F., Vasil'ev L.V. Nedifferentsiruemaya optimizatsiya, Moscow: Nauka, 1981.
  7. Rockafellar R.T. Convex analysis, Princeton: Princeton Univ. Press, 1970. Translated under the title Vypuklyi analiz, Moscow: Mir, 1973.
  8. Ioffe A.D., Tihomirov V.M. Theory of extremal problems, Amsterdam: Elsevier Science, 1979. Original Russian text published in Ioffe A.D., Tikhomirov V.M. Teoriya ekstremal'nykh zadach, Moscow: Nauka, 1974.
  9. Polovinkin E.S., Balashov M.V. Elementy vypuklogo i sil'no vypuklogo analiza (Elements of convex and strongly convex analysis), Moscow: Fizmatlit, 2007.
  10. Elhedhli S., Goffin J.-L., Vial J.-P. Nondifferentiable optimization, Encyclopedia of optimization, Boston, MA: Springer, 2009, pp. 2584-2590.
  11. Bagirov A., Karmitsa N., Mäkelä M.M. Introduction to nonsmooth optimization. Theory, practice and software, Springer, 2014.
  12. Ovcharova N., Gwinner J. A study of regularization techniques of nondifferentiable optimization in view of application to hemivariational inequalities, Journal of Optimization Theory and Applications, 2014, vol. 162, no. 3, pp. 754-778.
  13. Kolosnitsyn A.V. Computational efficiency of the simplex embedding method in convex nondifferentiable optimization, Computational Mathematics and Mathematical Physics, 2018, vol. 58, no. 2, pp. 215-222.
  14. Mishura Y., Schied A. On (signed) Takagi-Landsberg functions: $p$th variation, maximum, and modulus of continuity,Journal of Optimization Theory and Applications, 2019, vol. 473, no. 1, pp. 258-272.
  15. Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsional'nogo analiza (Elements of the theory of functions and functional analysis), Moscow: Nauka, 1976.
  16. Schwartz L. Analyse mathématique. I, Hermann, 1967. Translated under the title Analiz. Tom 1, Moscow: Mir, 1972.
  17. Allaart P.C., Kawamura K. The Takagi function: a survey, Real Analysis Exchange, 2011, vol. 37, no. 1, pp. 1-54.
  18. Preparata F., Shamos M. Computational geometry. An introduction, New York: Springer, 1985.
    Translated under the title Vychislitel'naya geometriya. Vvedenie, Moscow: Mir, 1989.
Full text
<< Previous article
Next article >>