2022, issue 3, p. 98-112
Received 16.09.2022; Revised 29.09.2022; Accepted 15.11.2022
Published 29.11.2022; First Online 10.12.2022
https://doi.org/10.34229/2707-451X.22.3.10
Previous | FULL TEXT (in Ukrainian) | Next
GNU Octave and Python Implementation of Shor's r-Algorithm with Adaptive Step Control
Petro Stetsyuk 1 *
, Aleksandr Pylypovskyi 2
, Olha Khomiak 1
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Kyiv Academic University, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
r-algorithms, or subgradient methods with dilation of space in the direction of the difference of two sequential subgradients, were proposed by N.Z.Shor in 1970 in his doctoral thesis. Respective software implementations proved to be competitive with the most effective methods for smooth ill-conditioned problems, both in terms of reliability and calculation time and accuracy of results.
The article is devoted to the description of two software implementations of Shor's r-algorithm modification with a constant coefficient of space dilation and adaptive step control. The first program is implemented using the GNU Octave, and the second program is implemented using Python.
Material of the paper is presented in three sections. In the first section, we describe a modification of the r-algorithm with a constant coefficient of space dilation in the direction of the difference of two sequential subgradients and an adaptive method for step size adjustment in the direction of the antisubgradient in the transformed space of variables. The software implementation of this modification is presented in the form of octave-function ralgb5a, which allows to find either approximation of the minimum point of a convex function, or approximation of the maximum point of the concave function. The code of the ralgb5a function is given with a brief description of its input and output parameters.
The second section describes test experiments to investigate efficiency of the octave-function ralgb5a to maximizing the piecewise linear concave function, which is obtained using the method of non-smooth penalty functions for the linear programming problem. Another example represents minimization of the piecewise linear convex function, which corresponds to the method of least modules. Results of these computational experiments for test problems with 200, 500, 1000, 1500 and 2000 variables are presented to demonstrate the effective operation of the octave-function ralgb5a.
The third section describes the python function ralgb5a and provides its code with a description of the input and output parameters. It is show, how the ralgb5a function can be accelerated by setting two parameters. The results of computational experiments to solve the test problem using the method of least modules for 5,000 variables and 10,000 observations are presented.
Keywords: r-algorithm, linear programming problem, nonsmooth penalty function, least modulus method, GNU Octave, python.
Cite as: Stetsyuk P., Pylypovskyi A., Khomiak O. GNU Octave and Python Implementation of Shor's r-Algorithm with Adaptive Step Control. Cybernetics and Computer Technologies. 2022. 3. P. 98–112. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.3.10
References
1. Shor N. Z. Methods of minimization of nondifferentiable functions and their applications. Authors Abstracts of Ph.D. Theses. Kyiv. 1970. 44 p. (in Russian)
2. 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. Cybern. Syst. Anal. 1971. 7 (3). P. 450–459. https://doi.org/10.1007/BF01070454
3. Shor N.Z. Minimization methods for nondifferentiable functions and their applications. Kiev: Naukova dumka, 1979. 200 p. (in Russian)
4. Shor N.Z., Stetsenko S. I. Quadratic Extremum Problems and Nondifferentiable Optimisztion. Kiev: Naukova dumka, 1989. 208 p. (in Russian)
5. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
6. Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd. 2008. 568 p.
7. Stetsyuk P.I. Theory and Software Implementations of Shor’s r-Algorithms. Cybern. Syst. Anal. 2017. 53. P. 692–703. https://doi.org/10.1007/s10559-017-9971-1
8. Stetsyuk P.I. Subgradient methods ralgb5 and ralgb4 for minimization of ravine-like convex functions. Computational technologies. 2017. 22 (2). P. 127–149. (in Russian) http://www.ict.nsc.ru/jct/getfile.php?id=1782
9. Stetsyuk P.I. Computer program "Octave program ralgb5a: r(α)-algorithm with adaptive step". Svidotstvo pro rejestratsiju avtorskogo prava na tvir 85010. Ukraine. Ministerstvo ekonomichnogo rozvytku I torgivli. Derzhavnyi department intelektualnoji vlasnosti. Data reiestratsii 29.01.2019. (in Ukrainian)
10. Stetsyuk P.I., Stetsyuk М.G., Bragin D.А., Мolodyk N.А. Use of the Shor’s r-Algorithm in Linear Robust Optimization Problems. Cybernetics and Computer Technologies. 2021. No. 1. P. 29–42. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.1.3
11. Huber Peter J. Robust statistics. New York: John Wiley & Sons, Inc., 1981. 308 p. https://doi.org/10.1002/0471725250
12. Lyn C. Thomas, David B. Edelman, Jonathan N. Crook. Credit Scoring and its Applications. SIAM Monographs on Mathematical Modeling and Computation. Philadelphia, 2002. 243 p. https://doi.org/10.1137/1.9780898718317
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next