Geodesic
Interior point algorithms in linear optimization
Sibirskij žurnal industrialʹnoj matematiki, Tome 21 (2018) no. 1, pp. 11-20.

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

This is a survey of the results concerning the development and study of the interior point algorithms. Some families of the direct and dual algorithms are considered. These algorithms entering the domain of feasible solutions take into account the objective function, which makes it possible to obtain the first feasible solution close to the optimal solution. The main results on the theoretical justification of algorithms are given. Recommendations are proposed concerning the advantages of individual variants of algorithms on the basis of the obtained theoretical results, available experimental studies, and experience of using algorithms in the models of energy engineering. Some numerically efficient version of the polynomial optimization algorithm in the cone of the central path is also presented.
Keywords: interior point method, relative interior, central path, linear programming. 
@article{SJIM_2018_21_1_a1,
     author = {V. I. Zorkaltsev and I. V. Mokryi},
     title = {Interior point algorithms in linear optimization},
     journal = {Sibirskij \v{z}urnal industrialʹnoj matematiki},
     pages = {11--20},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJIM_2018_21_1_a1/}
}
TY  - JOUR
AU  - V. I. Zorkaltsev
AU  - I. V. Mokryi
TI  - Interior point algorithms in linear optimization
JO  - Sibirskij žurnal industrialʹnoj matematiki
PY  - 2018
SP  - 11
EP  - 20
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJIM_2018_21_1_a1/
LA  - ru
ID  - SJIM_2018_21_1_a1
ER  - 
%0 Journal Article
%A V. I. Zorkaltsev
%A I. V. Mokryi
%T Interior point algorithms in linear optimization
%J Sibirskij žurnal industrialʹnoj matematiki
%D 2018
%P 11-20
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJIM_2018_21_1_a1/
%G ru
%F SJIM_2018_21_1_a1
V. I. Zorkaltsev; I. V. Mokryi. Interior point algorithms in linear optimization. Sibirskij žurnal industrialʹnoj matematiki, Tome 21 (2018) no. 1, pp. 11-20. http://geodesic.mathdoc.fr/item/SJIM_2018_21_1_a1/

[1] Dikin I. I., Zorkaltsev V. I., Iterativnoe reshenie zadach matematicheskogo programmirovaniya (algoritmy metoda vnutrennikh tochek), Nauka, Novosibirsk, 1980 | MR

[2] Dikin I. I., “Iterativnoe reshenie zadachi lineinogo i kvadratichnogo programmirovaniya”, Dokl. AN SSSR, 174:4 (1967), 747–748 | MR | Zbl

[3] Antsyz S. M., Dikin I. I., “Ob odnom chislennom metode resheniya zadachi lineinogo programmirovaniya i nekotorykh ee obobschenii”, Upravlyaemye sistemy, 3, 1969, 54–56

[4] Evtushenko Yu. G., “Relaksatsionnyi metod resheniya zadachi nelineinogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 17:4 (1977), 890–904 | MR | Zbl

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

[6] Zorkaltsev V. I., “Ob odnom klasse algoritmov vnutrennikh tochek”, Zhurn. vychisl. matematiki i mat. fiziki, 49:12 (2009), 2114–2130 | MR

[7] Zorkal'tsev V. I., “Substantiation of interior point algorithms”, Comput. Math. Math. Phys., 39:2 (1999), 198–211 | MR | Zbl

[8] Zorkaltsev V. I., Otnositelno vnutrennyaya tochka optimalnykh reshenii, izd. Komi fil. AN SSSR, Syktyvkar, 1984

[9] Monteiro R. D. C., Tsuchiya T., Wang Y., “A simplified global convergence proof of the affine scaling algorithm”, Ann. Oper. Res., 47 (1993), 443–482 | DOI | MR

[10] Vanderbey R. J., Mecheton M. S., Freedman B. A., “Modification of Karmarkar's linear programming algorithm”, Algorithmica, 1 (1986), 395–407 | DOI | MR

[11] Barnes E. R., “A variation on Karmarkar's algorithm for solving linear problems”, Math. Programming, 36 (1986), 174–182 | DOI | MR

[12] Wei Zi Luan, “An interior point method for linear programming”, J. Comput. Math., 5:4 (1987), 342–351 | MR

[13] Zorkaltsev V. I., Metod otnositelno vnutrennikh tochek, izd. Komi fil. AN SSSR, Syktyvkar, 1986

[14] Zorkal'tsev V. I., “Dual interior point algorithms”, Rus. Math. 2011, 55:4, 26–43 | MR

[15] Monma C. L., Morton A. J., Computational Experience with a Dual Affino Variant of Karmarkar's Method for Linear Programming, Manuscript, Bell Communication Research, Morristown, 1987 | MR

[16] Kojima M., Mizuno S., Yoshise A., “A polynomial-time algorithm for a class of linear complementarity problems”, Math. Programming, 44 (1989), 1–26 | DOI | MR

[17] Monteiro R., Adler I., “Interior path following primal-dual algorithms: linear programming. P. I”, Math. Programming, 44 (1989), 27–41 | DOI | MR

[18] Zorkaltsev V. I., Nechaeva M. S., Optimizatsiya v konuse tsentralnogo puti, izd. SEI SO RAN, Irkutsk, 1995

[19] Zorkal'tsev V. I., “Optimization algorithms in the cone of central path”, Comput. Math. Math. Phys., 40:2 (2000), 304–312 | MR | Zbl

[20] Dikin I. I., Metod vnutrennikh tochek v lineinom i nelineinom programmirovanii, KRASAND, M., 2010

[21] Zhadan V. G., Metody optimizatsii. Ch. 2. Chislennye algoritmy, Ucheb. posobie, izd. MFTI, M., 2015

[22] Karmarkar N. K., “A new polynomial-time algorithm for linear programming”, Combinatorica, 4 (1984), 373–395 | DOI | MR