|
Article information
2017 , Volume 22, ¹ 2, p.127-149
Stetsyuk P.I.
Subgradient methods ralgb5 and ralgb4 for minimization of ravine-like convex functions
We consider properties of the three computational forms of the 𝑟-algorithm proposed by N.Z. Shor for optimization of non-smooth functions that differ in the complexity of a single iteration. Discussed is a variant of the 𝑟-algorithm with adaptive stepsize control along the direction of the normalized antisubgradient in the transformed space of variables. The Octave functions ralgb5 and ralgb4 are described, which implement two computationally stable forms of the 𝑟-algorithms with adaptive stepsize control and a constant space dilation factor. The results of computational experiments for an essentially ravine-like piecewise quadratic function and a piecewise linear function related to solvability of interval linear tolerance problem are presented.
[full text]
Keywords: subgradient method, space dilation, r-algorithm, adaptive stepsize control, GNU Octave, Octave function, piecewise-quadratic function maxquad, interval linear tolerance problem
Author(s):
Stetsyuk Petr Ivanovich
Dr.
Position: Head of Departament
Office: V.M.Glushkov Institute of cybernetics of National Academy of Sciences of Ukraine
Address: 03680, Ukraine, Kiev, 40, acad. Glushkov avenue
Phone Office: (044) 526-21-68
E-mail: stetsyukp@gmail.com
References:
[1] Shor, N.Z. Metody minimizatsii nedifferentsiruemykh funktsiy i ikh primeneniya [Minimization Methods for Non-Differentiable Functions]. Kiev: Naukova dumka; 1979: 200. (In Russ.)
[2] Shor, N.Z. Nondifferentiable optimization and polynomial problems. Boston; Dordrecht; London: Kluwer Academic Publishers; 1998: 412.
[3] Shor, N.Z. Metody minimizatsii nedifferentsiruemykh funktsiy i ikh prilozheniya. Avtoref. dis. . . . dokt. fiz-mat. nauk [Minimization methods for non-differentiable functions and their applications]. Kiev; 1970: 44. ( In Russ.)
[4] Shor, N.Z., Zhurbenko, N.G. A minimization method using the operation of extension of the space in the direction of the difference of two successive gradients. Cybernetics and Systems Analysis. 1971; 7(3):450–459.
[5] GNU Octave. Available at: http://www.octave.org.
[6] Stetsyuk, P.I. Convergence of r-algorithms. Cybernetics and Systems Analysis. 1995; 31(6):935–937.
[7] Stetsyuk,P.I., Ivlichev,A.V., Ishchenko,A.A. On the convergence of rµ(α) –algorithm. Computer Mathematics. 2015; (1):142–152. (In Russ.)
[8] Shor, N.Z., Stetsenko S.I. Kvadratichnye ekstremal'nye zadachi i nedifferentsiruemaya optimizatsiya [Quadratic extremal problems and non-differentiable optimization]. Kiev: Naukova dumka; 1989: 208. (In Russ.)
[9] Zhurbenko N.G., Marchuk T.V. Algoritm minimizatsii negladkikh funktsionalov /r(α)- algoritm/ [Algorithm for minimization of nonsmooth functionals /r(α)-algorithm/]. AN USSR, RFAP; 1976: (22): ?????? (In Russ.)
[10] Shor, N.Z., Stetsyuk, P.I. Modified r-algorithm to find the global minimum of polynomial functions. Cybernetics and Systems Analysis. 1997; 33(4):482–497.
[11] Kappel, F., Kuntsevich, A.V. An implementation of Shor’s r-algorithm. Computational Optimization and Applications. 2000; 15(2):193–205.
[12] Stetsyuk, P.I., Likhovid, A.P., Chumakov, B.M., Vidil, A.Yu., Pilipovskiy, A.V. Matematicheskie i programmnye sredstva modelirovaniya i optimizatsii dinamicheskoy zagruzki moshchnostey energosistemy [Mathematical and software tools for modeling and optimization of dynamic loading of power system capacity]. Otchet o nauchno-issledovatel'skoy rabote ¹ gos. registratsii 0107U004963. Kiev: In-t kibernetiki im. V.M. Glushkova NAN Ukrainy; 2009: 136. (In Russ.) Available at: http://www.incyb.kiev.ua/file/d120-energy/Ot2009-2mb.pdf)
[13] Stetsyuk, P.I. Metody ellipsoidov i r-algoritmy [Ellipsoids methods and $r$-algorithms]. Kishineu: Evrika; 2014: 488. (In Russ.)
[14] tolsolvty - a program for investigation of solvability of the interval linear tolerance problem. Available at: http://www.nsc.ru/interval/Programing/SciCodes}
[15] Lemareshal, C., Mifflin, R. Nonsmooth optimization. Oxford: Pergamon Press; 1978: 186.
[16] Rzhevskiy, S.V. Monotonnye metody vypuklogo programmirovaniya [Monotonic methods of convex programmimg]. Kiev: Naukova dumka; 1993: 324. (In Russ.)
[17] Shary, S.P. Solving interval linear tolerance problem. Avtomatika i telemekhanika. 2004; (7):147–162. (In Russ.)
[18] Shary, S.P. Solving the linear interval tolerance problem. Mathematics and Computers in Simulation. 1995; (39):53–85.
Bibliography link:
Stetsyuk P.I. Subgradient methods ralgb5 and ralgb4 for minimization of ravine-like convex functions // Computational technologies. 2017. V. 22. ¹ 2. P. 127-149
|
