Dual interior point algorithms

V. I. Zorkaltsev

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2011), pp. 33-53.

Résumé

For a linear programming problem stated in the canonical form we consider the dual problem and describe a class of interior point algorithms which generate monotonically improving approximations to its solution. We theoretically substantiate the optimization process in the admissible domain under the assumption that the dual problem is non-degenerate. In addition, we describe subsets of algorithms that lead to relative interior points of optimal solutions. These algorithms have linear and superlinear convergence rates. Moreover, we obtain a special subset of algorithms which generate iterative sequences of approximations to a solution of the direct problem, whose convergence rate exceeds that of the sequences of monotonically improving approximations to a solution of the dual problem.

Détail

Keywords: linear programming, dual interior point algorithms, relative interior.

Bibliographie

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

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

[3] Dikin I. I., Zorkaltsev V. I., Iterativnoe reshenie zadach matematicheskogo programmirovaniya: algoritmy metoda vnutrennikh tochek, Nauka, Novosibirsk, 1980 | MR | Zbl

[4] Evtushenko Yu. G., Zhadan V. G., “Relaksatsionnyi metod resheniya zadach nelineinogo programmirovaniya”, Zhurn. vychisl. matem. i matem. fiz., 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 | Zbl

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

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

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

[9] Zorkaltsev V. I., “Klass algoritmov vnutrennikh tochek”, Zhurn. vychisl. matem. i matem. fiziki, 49:12 (2009), 2114–2130 | MR

[10] Zorkaltsev V. I., Otnositelno vnutrennyaya tochka optimalnykh reshenii, Komi filial AN SSSR, Syktyvkar, 1984

[11] Zorkaltsev V. I., Metod otnositelno vnutrennikh tochek, Komi filial AN SSSR, Syktyvkar, 1986

[12] Adler I., Rende M. G., Veiga G., “An implementation of Karmarkar's algorithm for linear programming”, Math. Program. Ser. A, 44:3 (1989), 297–335 | DOI | MR | Zbl

[13] Monma C. L., Morton A. J., Computational experience with a dual affine variant of Karmarkar's method for linear programming, Manuscript, Bell Communication Research, Morristown, NJ, 1987

[14] Chernikov S. N., Lineinye neravenstva, Fizmatlit, M., 1968

[15] Eremin I. I., Teoriya lineinoi optimizatsii, IMM UrO RAN, Ekaterinburg, 1999

[16] Broyden C. G., “On theorems of the alternative”, Optimization methods and software, 16 (2001), 101–111 | DOI | MR | Zbl

[17] Zorkaltsev V. I., Kiseleva M. A., Sistemy lineinykh neravenstv, IGU, Irkutsk, 2007

[18] Rokafellar R., Vypuklyi analiz, Mir, M., 1973

[19] Zorkaltsev V. I., Metod naimenshikh kvadratov: geometricheskie svoistva, alternativnye podkhody, prilozheniya, Nauka, Novosibirsk, 1995 | MR

[20] Zorkaltsev V. I., Metody prognozirovaniya i analiza effektivnosti funktsionirovaniya sistemy toplivosnabzheniya, Nauka, M., 1988

[21] Sadov S. L., “Issledovanie effektivnosti algoritmov metoda vnutrennikh tochek”, Voprosy teorii i praktiki sozdaniya regionalnykh avtomatizirovannykh sistem, Komi NTs UrO AN SSSR, Syktyvkar, 1988

[22] Zorkaltsev V. I., “Proektivnye algoritmy optimizatsii, ispolzuyuschie mnozhiteli predyduschei iteratsii”, Zhurn. vychisl. matematiki i matem. fiz., 34:7 (1994), 1095–1103 | MR