Geodesic
Quadratic approximation of penalty functions for solving large-scale linear programs
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 2, pp. 206-221 
L. D. Popov. Quadratic approximation of penalty functions for solving large-scale linear programs. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 2, pp. 206-221. http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_2_a4/
@article{ZVMMF_2007_47_2_a4,
     author = {L. D. Popov},
     title = {Quadratic approximation of penalty functions for solving large-scale linear programs},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {206--221},
     year = {2007},
     volume = {47},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_2_a4/}
}
TY  - JOUR
AU  - L. D. Popov
TI  - Quadratic approximation of penalty functions for solving large-scale linear programs
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2007
SP  - 206
EP  - 221
VL  - 47
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_2_a4/
LA  - ru
ID  - ZVMMF_2007_47_2_a4
ER  - 
%0 Journal Article
%A L. D. Popov
%T Quadratic approximation of penalty functions for solving large-scale linear programs
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2007
%P 206-221
%V 47
%N 2
%U http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_2_a4/
%G ru
%F ZVMMF_2007_47_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

Using the least squares, modified Lagrangian function, and some other methods as examples, the capabilities of the new optimization technique based on the quadratic approximation of penalty functions that has been recently proposed by O. Mangasarian for a special class of linear programming problems are demonstrated. The application of this technique makes it possible to use unified matrix operations and standard linear algebra packages (including parallel ones) for solving large-scale problems with sparse strongly structured constraint matrices. With this technique, the computational schemes of some well-known algorithms can take an unexpected form.

[1] Eremin I. I., Theory of linear optimization. Inverse and ill-posed problems series, VSP, Boston etc., 2002 | MR

[2] Eremin I. I., Mazurov Vl. D., Nestatsionarnye protsessy matematicheskogo programmirovaniya, Nauka, M., 1979 | MR

[3] Evtushenko Yu. G., Metody resheniya ekstremalnykh zadach i ikh primenenie v sistemakh optimizatsii, Nauka, M., 1982 | MR | Zbl

[4] Vasilev F. P., Chislennye metody resheniya ekstremalnykh zadach, Fizmatgiz, M., 1988 | MR

[5] Vasilev F. P., Ivanitskii A. Yu., Lineinoe programmirovanie, Faktorial, M., 2003 | MR

[6] Antipin A. C., Metody nelineinogo programmirovaniya, osnovannye na pryamoi i dvoistvennoi modifikatsii funktsii Lagranzha, preprint, VNIISI, M., 1979

[7] Lebedev V. Yu., “Priblizhennyi algoritm resheniya zadachi lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 14:4 (1974), 1052–1058 | Zbl

[8] Razumikhin B. C., “Metod kasatelnykh dlya stokhasticheskikh i dinamicheskikh zadach optimizatsii”, Avtomatika i telemekhan., 1977, no. 1, 5–15 | Zbl

[9] Polyak B. T., Tretyakov N. V., “Ob odnom iteratsionnom metode lineinogo programmirovaniya i ego ekonomicheskoi interpretatsii”, Ekonomika i matem. metody, 8:5 (1972), 740–751

[10] Mangasarian O. L., “A finite Newton method for classification”, Optimizat. Meth. Software, 17 (2002), 913–930 | DOI | MR

[11] Kanzow C., Qi H., Qi L., “On the minimum norm solution of linear program”, J. Optimizat. Theory and Appl., 116 (2003), 333–345 | DOI | MR | Zbl

[12] Golikov A. I., Evtushenko Yu. G., Mollaverdi H., “Primenenie metoda Nyutona k resheniyu zadach lineinogo programmirovaniya bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 44:9 (2004), 1564–1573 | MR | Zbl

[13] Golub Dzh., Van Doun Ch., Matrichnye vychisleniya, Mir, M., 1999

[14] Ortega Dzh., Vvedenie v parallelnye i vektornye metody resheniya lineinykh sistem, Mir, M., 1991 | MR

[15] Gondzio J., Sarkissian R., “Parallel interior-point solver for structured linear programs”, Math. Program. Ser. A, 96 (2003), 561–584 | DOI | MR | Zbl