One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square

Pasechnyuk D.A., Stonyakin F.S.
 pdf (3822K)  / List of references

In the article we have obtained some estimates of the rate of convergence for the recently proposed by Yu. E.Nesterov method of minimization of a convex Lipschitz-continuous function of two variables on a square with a fixed side. The idea of the method is to divide the square into smaller parts and gradually remove them so that in the remaining sufficiently small part. The method consists in solving auxiliary problems of one-dimensional minimization along the separating segments and does not imply the calculation of the exact value of the gradient of the objective functional. The main result of the paper is proved in the class of smooth convex functions having a Lipschitz-continuous gradient. Moreover, it is noted that the property of Lipschitzcontinuity for gradient is sufficient to require not on the whole square, but only on some segments. It is shown that the method can work in the presence of errors in solving auxiliary one-dimensional problems, as well as in calculating the direction of gradients. Also we describe the situation when it is possible to neglect or reduce the time spent on solving auxiliary one-dimensional problems. For some examples, experiments have demonstrated that the method can work effectively on some classes of non-smooth functions. In this case, an example of a simple non-smooth function is constructed, for which, if the subgradient is chosen incorrectly, even if the auxiliary one-dimensional problem is exactly solved, the convergence property of the method may not hold. Experiments have shown that the method under consideration can achieve the desired accuracy of solving the problem in less time than the other methods (gradient descent and ellipsoid method) considered. Partially, it is noted that with an increase in the accuracy of the desired solution, the operating time for the Yu. E. Nesterov’s method can grow slower than the time of the ellipsoid method.

Keywords: minimization problem, convex functional, Lipshitz-continuous functional, Lipshitz-continuous gradient, non-smooth functional, subgradient, gradient method, ellipsoid method, rate of convergence
Citation in English: Pasechnyuk D.A., Stonyakin F.S. One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square // Computer Research and Modeling, 2019, vol. 11, no. 3, pp. 379-395
Citation in English: Pasechnyuk D.A., Stonyakin F.S. One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square // Computer Research and Modeling, 2019, vol. 11, no. 3, pp. 379-395
DOI: 10.20537/2076-7633-2019-11-3-379-395
URL: http://crm-en.ics.org.ru/journal/article/2798/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.
Views (last year): 34.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science