On Subgradient Methods with Polyak’s Step and Space Transformation

Abstract

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