2023, issue 3, p. 16-22
Received 18.09.2023; Revised 25.09.2023; Accepted 26.09.2023
Published 29.09.2023; First Online 19.10.2023
https://doi.org/10.34229/2707-451X.23.3.2
On Shor's r-Algorithm for Problems with Constraints
Vladimir Norkin 1, 2
, Anton Kozyriev 2
*
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv,
2 National Technical University of Ukraine "Ihor Sikorsky Kyiv Polytechnic Institute", Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Nonsmooth optimization problems arise in a wide range of applications, including engineering, finance, and deep learning, where activation functions often have discontinuous derivatives, such as ReLU. Conventional optimization algorithms developed primarily for smooth problems face difficulties when applied to nonsmooth contexts due to discontinuities and other associated irregularities. Possible approaches to overcome these problems include smoothing of functions and applying non-smooth optimization techniques. In particular, Shor's r-algorithm (Shor, Zhurbenko (1971), Shor (1979)) with space stretching in the direction of the difference of two subsequent subgradients is a competitive non-smooth optimization method (Bagirov et al. (2014)). However, the original r-algorithm is designed to minimize unconstrained convex functions.
The goal of the work. The standard technique for applying this algorithm to problems with constraints consists in the use of exact non-smooth penalty functions (Eremin (1967), Zangwill (1967)). At the same time, it is necessary to correctly choose (quite large) the penalty coefficient of the penalty functions. Norkin (2020, 2022), Galvan et al. (2021) propose the so-called projective exact penalty functions method, which theoretically does not require choice of the penalty coefficient. The purpose of the present work is to study an applicability of the new exact projective non-smooth penalty functions method for solving conditional problems of non-smooth optimization by Shor's r-algorithm.
The results. In this paper, the original optimization problem with convex constraints is first transformed into an unconstrained problem by the projective penalty function method, and then the r-algorithm is used to solve the transformed problem. The results of testing this approach on problems with linear constraints using a program implemented in Matlab are presented. The results of the present study show that the standard method of non-smooth penalties combined with Shor's r-algorithm is fast, due to the use of the provided program to calculate the subgradients, but it requires the correct selection of the penalty parameter. The projective penalty method is slow because in this study it uses finite differences to calculate the gradients, but it is quite stable with respect to the choice of the penalty parameter. Further research will be aimed at investigating the differential properties of the projection mapping and reducing the time of computing subgradients for account of parallel calculations.
Keywords: Subgradient descent, constrained optimization, r-algorithm, exact projective penalty.
Cite as: Norkin V., Kozyriev A. On Shor's r-Algorithm for Problems with Constraints. Cybernetics and Computer Technologies. 2023. 3. P. 16–22. https://doi.org/10.34229/2707-451X.23.3.2
References
1. Mikhalevich V.S., Gupal A.M., Norkin V.I. Methods of Nonconvex Optimization. Moscow. Nauka. 1987. (in Russian)
2. Mayne D.Q., Polak E. Nondifferential optimization via adaptive smoothing. Journal of Optimization Theory and Applications. 1984. 43 (4). P. 601–613. https://doi.org/10.1007/BF00935008
3. Nesterov Y., Spokoiny V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics. 2015. 17. P. 527–566. https://doi.org/10.1007/s10208-015-9296-2
4. Shor N.Z. Minimization Methods for Non-Differentiable Functions. Kiev. Naukova Dumka. 1979. 200 p. (In Russian)
5. Bagirov A., Karmitsa N., Mäkelä M. M. Introduction to Nonsmooth Optimization. Springer. 2014. https://doi.org/10.1007/978-3-319-08114-4
6. Eremin I.I. The penalty method in convex programming. Soviet Math. Dokl. 1966. 8. P. 459–462.
7. Eremin I.I. The penalty method in convex programming. Cybernetics. 1967. 3 (4). P. 53–56. https://doi.org/10.1007/BF01071708
8. Zangwill W. Non-linear programming via penalty junctions. Management Science. 1967. 13. P. 344–358. https://doi.org/10.1287/mnsc.13.5.344
9. Norkin V.I. A stochastic smoothing method for nonsmooth global optimization. Cybernetics and Computer technologies. 2020. 1. P. 5–14. https://doi.org/10.34229/2707-451X.20.1.1
10. Norkin V.I . A new projective exact penalty function for a general constrained optimization. Dopovidi Nac.akademii nauk Ukrainy. 2022. 5. P. 23–29. https://doi.org/10.15407/dopovidi2022.04.023
11. Galvan G., Sciandrone M., Eucidi S. A parameter-free unconstrained reformulation for nonsmooth problems with convex constraints. 2021. CompuL. Optim. Appl. 80. P. 33–53. https://doi.org/10.1007/s10589-021-00296-1
12. 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). P. 450–459. https://doi.org/10.1007/BF01070454
13. Stetsyuk P.I. Theory and Software Implementations of Shor’s r-Algorithms. Cybern Syst Anal. 2017. 53 (5). P. 692–703. https://doi.org/10.1007/s10559-017-9971-1
14. Stetsyuk P.I. Subgradient methods ralgb5 and ralgb4 for minimizing ravine convex functions. Computational technologists (ICT SB RAS). 2017. 22 (2). P. 127–149.
15. Norkin V.I. The projective exact penalty method for general constrained optimization. Preprint. V.M. Glushkov Institute of Cybernetics, Kyiv, 2022. https://optimization-online.org/?p=20458
16. Rockafellar R.T., Wets R.J-B. Variational Analysis. Springer. 1998. 734 p. https://doi.org/10.1007/978-3-642-02431-3
17. Kappel F., Kuntsevich A.V. An implementation of Shor’s r-algorithm. Comput. Optim. and Appl. 2000. 15 (2). P. 193–205. https://doi.org/10.1023/A:1008739111712
18. Davis T.A., Sigmon K. MATLAB® Primer. Eighth Edition. CHAPMAN & HALL/CRC. 2010. 214 p.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)