1. One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square
- Author
-
Dmitry Arkad'evich Pasechnyuk and Fedor Sergeevich Stonyakin
- Subjects
minimization problem ,convex functional ,Lipshitz-continuous functional ,Lipshitz-continuous gradient ,non-smooth functional ,subgradient ,gradient method ,ellipsoid method ,rate of convergence ,Applied mathematics. Quantitative methods ,T57-57.97 ,Mathematics ,QA1-939 - Abstract
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. Nesterovs method can grow slower than the time of the ellipsoid method. more...
- Published
- 2019
- Full Text
- View/download PDF