Received 17.12.2022; Revised 19.12.2022; Accepted 20.12.2022

Published 29.12.2022; First Online 28.02.2023

https://doi.org/10.34229/2707-451X.22.4.4

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

MSC 46N10, 65K05, 90C25, 15A04

On Subgradient Methods with Polyak’s Step and Space Transformation

Viktor Stovba ^* ,   Oleksandr Zhmud

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Minimization of ravine convex functions, both smooth and non-smooth, arises in many problems of planning, control, stability analysis of dynamic systems, artificial intelligence, and machine learning. Therefore, the development of new and improvement of existing methods is an important task, taking into account the fact that more and more frequently the functions to be minimized depend on a large number of variables.

Special attention should be paid to the methods using the operation of linear transformation of space, which allow to improve the properties of the objective function and significantly accelerate its minimization. Known methods of this type, in particular, ellipsoid methods and r-algorithms, require recalculation of the transformation matrix at each iteration. Therefore, the development of methods with a one-time transformation of space, which have a lower cost of iteration, is definitely an urgent task.

The purpose of the article is to review modifications of subgradient method with Polyak’s step that use a scalar parameter m³1 and one-time space transformation operation. Supplement the justification of the convergence and convergence rate of the modifications described. Give recommendations regarding determination of parameter m and space transformation matrix B.

Results. Subgradient method with Polyak’s step in transformed space and parameter m>1 is an effective method for minimizing smooth and non-smooth convex functions that have a ravine structure. Determination of an appropriate value of the parameter m³1 and space transformation matrix B allows to significantly accelerate this method and use it for minimization functions that depend on a large number of variables.

Conclusions. The development of fast methods for minimization of non-smooth convex functions of many variables with a ravine structure makes it possible to effectively solve modern problems of artificial intelligence, in particular, the problems of machine learning, image recognition, big data analysis, etc.

 

Keywords: subgradient method, space transformation, ravine functions.

 

Cite as: Stovba V., Zhmud O. On Subgradient Methods with Polyak’s Step and Space Transformation. Cybernetics and Computer Technologies. 2022. 4. P. 45–55. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.4.4

 

References

           1.     Agmon S. The relaxation method for linear inequalities. Canad. J. Math. 1954. No. 6. P. 382−392. https://doi.org/10.4153/CJM-1954-037-2

           2.     Motzkin T., Schoenberg I. The relaxation method for linear inequalities. Canad. J. Math. 1954. No. 6. P. 393−404. https://doi.org/10.4153/CJM-1954-038-x

           3.     Polyak B.T. Introduction to optimizaton. М.: Nauka. 1983. 384 p. (in Russian)

           4.     Polyak B.T. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics. 1969. 9 (3). P. 14–29. https://doi.org/10.1016/0041-5553(69)90061-5

           5.     Eremin I.I. Generalization of the Agmon-Motzkin relaxation method. UMN. 1965. 20 (122). P. 183–187. (in Russian)

           6.     Bregman L.M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. ZVM and MF. 1967. 7 (3). P. 200–217. (in Russian) https://doi.org/10.1016/0041-5553(67)90040-7

           7.     Stetsyuk P.I. r-Algorithms and Ellipsoids. Cybernetics and Systems Analysis. 1996. No. 1. P. 113–134. (in Russian) https://doi.org/10.1007/BF02366587

           8.     Stetsyuk P.I. Orthogonalizing linear operators in convex programming. І. Cybernetics and Systems Analysis. 1997. No. 3. P. 97–119. (in Russian) https://doi.org/10.1007/BF02733072

           9.     Stetsyuk P.I. Orthogonalizing linear operators in convex programming. ІІ. Cybernetics and Systems Analysis. 1997. No. 5. P. 111–124. (in Russian) https://doi.org/10.1007/BF02667194

       10.     Gershovich V.I., Shor N.Z. Method of ellipsoids, its generalizations and applications. Cybernetics. 1982. No. 5. P. 61–69. (in Russian) https://doi.org/10.1007/BF01068741

       11.     Stetsyuk P.I. Amsg2p method for ravine convex functions. Informacionnyj byulleten' Associacii matematicheskogo programmirovaniya. 2011. No. 12. P. 57–58. (in Russian)

       12.     Stovba V.O. Subgradient method with Polyak’s step in transformed space : Diss. for a Doctor of Philosophy Degree : 113 Apllied Mathematics / V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, 2020. 184 p. (in Ukrainian)

       13.     Stetsyuk P.І. Assceleration of Polyak’s subgradient method. Teoria optymal’nyh rishen’. 2012. No. 11. P. 151–60. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/85030

       14.     Stetsyuk P.І., Stovba V.O., Zhmud O.O. On convergence rate of subgradient methods with Polyak’s step. Nauk. visnyk of Uzhhorod University. Ser. of math. and inform. 2019. 1 (34). P. 94–101. (in Ukrainian) https://doi.org/10.24144/2616-7700.2019.1(34).94-101

       15.     Sergienko I.V., Stetsyuk P.I. On N.Z. Shor’s three scientific ideas. Cybernetics and Systems Analysis. 2012. No. 1. P. 4–22. (in Russian) https://doi.org/10.1007/s10559-012-9387-x

       16.     Stetsyuk P., Stovba V., Chernousova Z. Subgradient method with Polyak’s step in transformed space. Optimization and Applications (OPTIMA 2018). 2018. Vol. 974. P. 49–63. https://doi.org/10.1007/978-3-030-10934-9_4

       17.     Shor N.Z. Cut-off method with space extension in convex programming problems. Cybernetics. 1977. No. 1. P. 94–95. (in Russian) https://doi.org/10.1007/BF01071394

       18.     Shor N.Z., Zhurbenko N.G. A minimization method using the operator of extension of the space in the direction of the difference of two successive gradients. Cybernetics. 1971. No. 3. P. 51–59. (in Russian) https://doi.org/10.1007/BF01070454

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next