2023, issue 2, p. 46-54
Received 18.07.2023; Revised 24.07.2023; Accepted 25.07.2023
Published 28.07.2023; First Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.5
Previous | FULL TEXT (in Ukrainian) | Next
Computational Experiments for the r(𝛂)-Algorithm with an Accelerated Implementation of Space Dilation
Anton Suprun
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.
In the article, a modification of the r(α)-algorithm with adaptive line search which implements accelerated space dilation operation is considered. In classical r(α)-algorithm with adaptive line search, space is dilated along the difference of the two successive subgradients. In its modified variant, space is dilated along the direction which is determined by the largest absolute value components of the vector of difference of the two successive subgradients. The number of such components varies at each iteration of the algorithm and depends on a control parameter. Thus, at each iteration only corresponding subspace of a smaller dimension is dilated and the number of multiplication operations used for this decreases from 2n2 + 3n to 2nm + 2m + n, where n is the dimension of the space, m is the number of non-zero components of the space dilation direction.
Description of the modified r(α)-algorithm with adaptive line search which implements accelerated space dilation operation is given. Results of the numerical experiments of minimization of the two classes of convex piecewise linear functions and quadratic strongly convex functions are presented. To solve the problems C++ implementations of the classical r(α)-algorithm with an adaptive line search ralgb5a and its modified version with accelerated space dilation ralgb5at were used. Obtained results show that for minimization of the piecewise linear functions compared with the classical r(α)-algorithm its modified version requires approximately the same number of iterations to converge but uses a significantly smaller number of multiplication operations. For minimization of the quadratic strongly convex functions modified r(α)-algorithm requires a smaller number of iterations to converge and as a result has a smaller execution time.
Therefore, it is concluded that the variants of the r-algorithm that implements accelerated space dilation operation along directions which approximate the difference of the two successive subgradients may be quite promising since for some classes of functions they might better take into account the shape of the function’s ravines and with appropriate software implementation have a smaller execution time.
Keywords: space dilation operator, r(α)-algorithm, piecewise linear function.
Cite as: Suprun A. Computational Experiments for the r(𝛂)-Algorithm with an Accelerated Implementation of Space Dilation. Cybernetics and Computer Technologies. 2023. 2. P. 46–54. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.2.5
References
1. Shor N.Z. Minimization methods for nondifferentiable functions and their applications. Kiev: Naukova dumka, 1979. 200 p. (in Russian)
2. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
3. 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
4. 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
5. Stetsyuk P.I., Zhmud O.O. On the accelerated realization of the space dilation operator. Issues of applied mathematics and mathematical modeling. Abstracts of reports of the XVIII international scientific and practical conference "Mathematical and software support of intelligent systems (MPZIS-2020)", Dnipro, November 18–20, 2020. Dnipro: DNU, 2020.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next