R-algorithm for Solving Quadratic Programming Problems

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.