Far Eastern Mathematical Journal

To content of the issue

On the Step Choice in Projection Algorithms for Large-Scale Linear Programming Problems

A. S. Velichko

2012, issue 2, P. 160–170

Abstract

In order to solve large-scale linear programming problems the group of algorithms with projection of a point onto the set is considered. Special method for selecting the initial approximation and the step-size parameters is given to reduce computational time. Comparative analysis of the rates of convergence and running time of the algorithm with various step parameters is done for the special large-scale test problem with randomly generated data.

Keywords: constrained optimization, linear programming, large-scale problem, numerical method, projection algorithm

Download the article (PDF-file)

References

[1] I. I. Eremin, “O nekotorykh iteratsionnykh metodakh v vypuklom programmirovanii”, Ekonomika i matematicheskie metody, 2:6 (1966), 870–886. [2] I. I. Eremin, V. L. Mazurov, Nestatsionarnye protsessy matematicheskogo programmirovaniia, Nauka, M., 1979. [3] I. I. Eremin, “Metody feierovskikh priblizhenii v vypuklom programmirovanii”, Matematicheskie zametki, 3:2 (1968), 217–234. [4] L. M. Bregman, “Relaksatsionnyi metod nakhozhdeniia obshchei tochki vypuklykh mnozhestv i ego primenenie dlia zadach vypuklogo programmirovaniia”, Zhurn. vychisl. matem. i matem. fiziki, 7:3 (1967), 620–631. [5] L. G. Gurin, B. T. Poliak, E. V. Raik, “Metody proektsii dlia otyskaniia obshchei tochki vypuklykh mnozhestv”, Zhurn. vychisl. matem. i matem. fiziki, 7:6 (1967), 1211–1228. [6] E. G. Gol'shtein, E. G. Tret'iakov, Modifitsirovannye funktsii Lagranzha. Teoriia i metody optimizatsii, Nauka, M., 1989. [7] H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems”, SIAM Review, 38:3 (1996), 367–426. [8] Y. Censor, W. Chen, P. L. Combettes, R. Davidi, G. T. Herman, “On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints”, Computational Optimization and Applications, 2012, no. 3, 1065–1088. [9] E. A. Berdnikova, I. I. Eremin, L. D. Popov, “Raspredelennye feierovskie protsessy dlia sistem lineinykh neravenstv i zadach lineinogo programmirovaniia”, Avtomatika i telemekhanika, 2004, № 2, 16–32. [10] I. I. Eremin, L. D. Popov, “Feierovskie protsessy v teorii i praktike: obzor poslednikh rezul'tatov”, Izvestiia VUZov. Matematika, 2009, № 1, 44–65. [11] E. A. Nurminskii, “Ispol'zovanie dopolnitel'nykh malykh vozdeistvii v feierovskikh modeliakh iterativnykh algoritmov”, Zhurn. vychisl. matem. i matem. fiziki, 48:12 (2008), 2121–2128. [12] E. A. Nurminskii, “Feierovskie protsessy c malymi vozmushcheniiami”, Doklady AN, 422:5 (2008), 601–605. [13] C. Michelot, “A finite algorithm for finding the projection of a point onto the canonical simplex of Rn”, Journal of Optimization Theory and Applications, 50:1 (1986), 195–200. [14] E. A. Nurminskii, “Proektsiia na vneshne zadannye poliedry”, Zhurn. vychisl. matem. i matem. fiziki, 48:3 (2008), 387–396. [15] B. T. Poliak, Vvedenie v optimizatsiiu, Nauka, M., 1983. [16] Iu. E. Nesterov, Vvedenie v vypukluiu optimizatsiiu, MTsNMO, M., 2010. [17] I. I. Eremin, “Obobshchenie relaksatsionnogo metoda Motskina – Agmona”, Uspekhi matem. nauk, 20:2 (1965), 183–187. [18] B. T. Poliak, “Minimizatsiia negladkikh funktsionalov”, Zhurn. vychisl. matem. i matem. fiziki, 9:3 (1969), 509–521. [19] N. Z. Shor, “O skorosti skhodimosti metoda obobshchennogo gradientnogo spuska s rastiazheniem prostranstva”, Kibernetika, 1970, № 2, 80–85. [20] A. S. Velichko, “Reshenie zadach optimizatsii metodom posledovatel'nykh proektsii s razlichnymi sposobami vybora nachal'nogo priblizheniia i shagovykh mnozhitelei”, sv. o gos. reg. prog. dlia EVM Ross. Fed. 2011614018 ot 24.05.11; zaiavl. 06.04.11; opubl. 20.09.2011., RU OBPBT, 3, 319 s. [21] E. D. Dolan, J. J. More, “Benchmarking optimization software with perfomance profiles”, Mathematical programming, 91:2 (2002), 201–213.

To content of the issue