2021, issue 1, p. 29-42
Received 12.03.2021; Revised 19.03.2021; Accepted 25.03.2021
Published 30.03.2021; First Online 03.04.2021
https://doi.org/10.34229/2707-451X.21.1.3
Previous | Full text (in Ukrainian) | Next
Use of the Shor’s r-Algorithm in Linear Robust Optimization Problems
P.I.
Stetsyuk 1 * 
,
М.G. Stetsyuk 1, D.А. Bragin 2, N.А. Мolodyk 2
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
The paper is devoted to the description of a new approach to the construction of algorithms for solving linear programming problems (LP-problems), in which the number of constraints is much greater than the number of variables. It is based on the use of a modification of the r-algorithm to solve the problem of minimizing a nonsmooth function, which is equivalent to LP problem. The advantages of the approach are demonstrated on the linear robust optimization problem and the robust parameters estimation problem using the least moduli method. The developed octave programs are designed to solve LP problems with a very large number of constraints, for which the use of standard software from linear programming is either impossible or impractical, because it requires significant computing resources.
The material of the paper is presented in three sections. In the first section for the problem of minimizing a convex function we describe a modification of the r-algorithm with a constant coefficient of space dilation in the direction of the difference of two successive 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 or 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.
In the second section, a method for solving the LP problem is presented using a nonsmooth penalty function in the form of maximum function and the construction of an auxiliary problem of unconstrained minimization of a convex piecewise linear function. The choice of the finite penalty coefficient ensures equivalence between the LP-problem and the auxiliary problem, and the latter is solved using the ralgb5a program. The results of computational experiments in GNU Octave for solving test LP-problems with the number of constraints from two hundred thousand to fifty million and the number of variables from ten to fifty are presented.
The third section presents least moduli method that is robust to abnormal observations or "outliers". The method uses the problem of unconstrained minimization of a convex piecewise linear function, and is solved using the ralgb5a program. The results of computational experiments in GNU Octave for solving test problems with a large number of observations (from two hundred thousand to five million) and a small number of unknown parameters (from ten to one hundred) are presented. They demonstrate the superiority of the developed programs over well-known linear programming software such as the GLPK package.
Keywords: robust optimization, linear programming problem, nonsmooth penalty function, r-algorithm, least modulus method, GNU Octave.
Cite as: 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. 1. P. 29–42. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.1.3
References
1. Ben-Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009. 576 p. https://doi.org/10.1515/9781400831050
2. Goryashko, A.P., Nemirovski, A.S. Robust energy cost optimization of water distribution system with uncertain demand. Autom Remote Control. 2014. 75. P. 1754–1769. https://doi.org/10.1134/S000511791410004X
3. Alekseeva I.V., Perevozniuk T.I. Application of robust optimization for a linear model of operation of a small enterprise. Mathematics in Modern Technical University. 2018. 1. P. 61–73. (in Ukrainian) https://doi.org/10.20535/mmtu-2018.1-061
4. Shor N.Z. Minimization methods for nondifferentiable functions and their applications. Kiev: Naukova dumka. 1979. 200 p. (in Russian)
5. 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
6. 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)
7. 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
8. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London, 1998. 412 p.
9. Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd, 2008. 568 p.
10. GNU Linear Programming Kit (GLPK). http://www.gnu.org/software/glpk/glpk.html (accessed 12.03.2021)
11. Huber Peter J. Robust statistics. New York: John Wiley & Sons, Inc., 1981. 308 p. https://doi.org/10.1002/0471725250
12. Stetsyuk P.I., Kolesnik Yu.S., Leibovich M.M. On the robustness of the least modulus method. Kompiuternaia matematika. 2002. P. 114–123. (in Russian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next