Л.Д. Попов. Методы внутренних точек, адаптированные к несобственным задачам линейного программирования ... C. 208-216

УДК 519.658.4

MSC: 90C05, 90C46

DOI: 10.21538/0134-4889-2018-24-4-208-216

Работа выполнена при поддержке РФФИ (проект 16-07-00266).

Для задач линейного программирования рассматриваются схемы формирования некоторого обобщенного центрального пути, возникающие при одновременном использовании внутренних и внешних штрафных слагаемых в традиционной функции Лагранжа и порождаемых ею минимаксных задачах. Новые схемы обладают тем преимуществом, что не требуют априорного знания допустимых внутренних точек в прямой или двойственной задаче. Более того, будучи примененными к задачам с несовместными ограничениями, они автоматически приводят к некоторым их обобщенным решениям, имеющим важное прикладное содержание. Приводятся описание алгоритмов, их обоснование и результаты численных экспериментов.

Ключевые слова:  линейное программирование, двойственность, методы штрафных функций, методы регуляризации, несобственные задачи, центральный путь

СПИСОК ЛИТЕРАТУРЫ

1.   Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. Chichester: John Wiley & Sons Ltd, 1997. 484 p.

2.   Eremin I.I. Theory of linear optimization. Inverse and ill-posed problems series. Utrecht; Boston; Koln; Tokyo: VSP, 2002. 248 p.

3.   Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.

4.   Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979. 285 с.

5.   Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981. 400 с.

6.   Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.

7.   Popov L.D. Use of barrier functions for optimal correction of improper problems of linear programming of the 1st kind // Automation and Remote Control. 2012. Vol. 73, № 3. P. 417–424. doi: 10.1134/S0005117912030010

8.   Popov L. D. Dual approach to the application of barrier functions for the optimal correction of improper linear programming problems of the first kind // Proc. Steklov Inst. Math. 2015. Vol. 288, suppl. 1. P. 173–179. doi: 10.1134/S0081543815020170

Поступила 24.08.2018

После доработки 08.11.2018

Принята к публикации 12.11.2018

Попов Леонид Денисович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
профессор кафедры ВКТ
Уральский федеральный университет,
г. Екатеринбург
e-mail: popld@imm.uran.ru

English

L.D. Popov. Interior point methods adapted to infeasible linear programs

For linear programs, we consider schemes for the formation of a generalized central path, which arise under the simultaneous use of interior and exterior penalty terms in the traditional Lagrange function and the minimax problems generated by it. The advantage of the new schemes is that they do not require the a priori knowledge of feasible interior points in the primal or dual problem. Moreover, when applied to problems with inconsistent constraints, the schemes automatically lead to some of their generalized solutions, which have important applied content. Descriptions of the algorithms, their justification, and results of numerical experiments are presented.

Keywords: linear programming, duality, penalty function methods, regularization methods, infeasible problems, central path

Received August 24, 2018

Revised November 08, 2018

Accepted November 12, 2018

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 16-07-00266).

Leonid Denisovich Popov, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: popld@imm.uran.ru