2025, issue 4, p. 12-28
Received 11.08.2025; Revised 11.11.2025; Accepted 18.11.2025
Published 08.12.2025; First Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.2
Previous | FULL TEXT (in Ukrainian) | Next
R-algorithm for Solving Quadratic Programming Problems
Petro Stetsyuk *
, Nelia Tukalevska,
Olha Khomiak , Maria Stetsyuk
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.
Quadratic programming problems have a wide range of practical applications in various fields of science and engineering, particularly in financial modeling and pattern recognition, which underscores the relevance of studying methods for their efficient solution. In real–world applications, the parameters of such models are often imprecise or variable, which can significantly affect the quality of the obtained solutions. Robust approaches ensure the stability of solutions under uncertainty, enabling reliable decisions that remain feasible for all admissible realizations of the input data.
This paper presents the algorithm QPralg (Quadratic Programming by r–algorithm) and its implementation in Octave for solving convex quadratic minimization problems with two–sided linear constraints. The proposed method is based on nonsmooth penalty functions and utilizes the Octave program ralgb5a, which implements an r-algorithm with adaptive step size. This is a subgradient method with a constant space stretching coefficient in the direction of the difference between two successive subgradients and an adaptive step adjustment along the anti–subgradient direction in the transformed variable space.
The material of the paper is presented in four sections. Section 1 describes the r–algorithm with an adaptive step size adjustment mechanism and provides the Octave program ralgb5a that implements it. Section 2 introduces the nonsmooth penalty function method for convex programming problems, along with two theorems that justify the use of finite penalty coefficients. Section 3 describes the QPralg algorithm and its implementation in Octave. Section 4 presents the results of computational experiments for quadratic programming problems with two–sided constraints.
QPralg is particularly suited for problems with a small number of variables and a very large number of constraints (ranging from hundreds of thousands to several millions). For such problems, commercial solvers like Gurobi require several times more computational time on modern computers with 8 GB of RAM. The ability to handle a large number of constraints also enables the effective solution of robust quadratic and linear optimization problems across a wide range of realizations of the uncertainty vector.
Keywords: quadratic programming problem, robust optimization, nonsmooth penalty function, r–algorithm, GNU Octave.
Cite as: Stetsyuk P., Tukalevska N., Khomiak O., Stetsyuk M. R-algorithm for Solving Quadratic Programming Problems. Cybernetics and Computer Technologies. 2025. 4. P. 12–28. (in Ukrainian) https://doi.org/10.34229/2707-451X.25.4.2
References
1. Nocedal J., Wright S.J. Numerical optimization (Springer Series in Operations Research and Financial Engineering). Berlin: Springer, 2006.
2. Gertz E.M., Wright S.J. Object-oriented software for quadratic programming. ACM Transactions on Mathematical Software (TOMS). 2003. Vol. 29, No. 1. P. 58–81. https://doi.org/10.1145/641876.641880
3. Boggs P.T., Tolle J.W. Sequential quadratic programming, Acta Numerica. 1995. Vol. 4. P. 1–51. https://doi.org/10.1017/S0962492900002518
4. Ben–Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009. 576 p. https://doi.org/10.1515/9781400831050
5. Shor N.Z. Minimization methods for nondifferentiable functions and their applications. Kyiv: Nauk. dumka. 1979. 200 p. (in Russian)
6. Octave. http://www.octave.org (accessed: 09.11.2025)
7. Shor N.Z., Stetsenko S.I. Quadratic extremal problems and non-differentiable optimization. Kyiv: Nauk. dumka, 1989. 208 p. (in Russian)
8. Stetsyuk P.I., Fischer A. Shor’s r–algorithms and octave–function ralgb5a. In: International Conference “Modern Informatics: Problems, Achievements and Prospects for Development”, Ukraine, Kyiv, December 2017. V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine. 2017. P. 143–146. (in Russian)
9. 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. No. 3. P. 98–112. (in Ukrainian) https://doi.org/10.34229/2707–451X.22.3.10
10. Bertsekas D.P. Necessary and sufficient conditions for a penalty method to be exact. Math. Program. 1975. 9. P. 87–99. https://doi.org/10.1007/bf01681332
11. Pshenichnyi B.N. The Linearization Method. M.: Nauka, 1983 (in Russian)
12. Alekseeva І.V., Perevozniuk Т.І. Application of robust optimization for a linear model of operation of a small enterprise. Mathematics in Modern Technical University. 2018. Vol. 2018, No 1. P. 61–73. (in Ukrainian) https://doi.org/10.20535/mmtu–2018.1–061
13. Stetsyuk P., Fischer A., Pichugina O. A Penalty Approach to Linear Programs with Many Two–Sided Constraints. In: Pardalos P., Khachay M., Kazakov A. (eds) Mathematical Optimization Theory and Operations Research. MOTOR 2021. Lecture Notes in Computer Science. Vol 12755. Springer, Cham. 2021. P. 206–217. https://doi.org/10.1007/978–3–030–77876–7_14
14. 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
15. Stetsyuk P., Fischer A., Khomiak O. Maximum Penalty Function in Linear Programming. Physico–mathematical modelling and informational technologies. 2021. 33. P. 156–160. https://doi.org/10.15407/fmmit2021.33.156
16. Shary S.P. Non–traditional intervals and their use. Which ones really make sense? Numerical Analysis and Applications. 2023. 16 (2). P. 179–191. https://doi.org/10.1134/S1995423923020088
17. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/ (accessed: 06.08.2025).
18. NEOS Solver. https://neos–server.org/ (accessed: 06.08.2025)
19. Stetsyuk P.I., Nurminski E.A. Nonsmooth penalty and subgradient algorithms to solve the problem of projection onto a polytope. Cybern Syst Anal. 2010. 46. P. 51–55. https://doi.org/10.1007/s10559–010–9182–5
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next