Л.Д. Попов. Барьеры и симметричная регуляризация функции Лагранжа при анализе несобственных задач линейного программирования ... С. 138-155

УДК 519.658.4

MSC: 90C05, 90C51, 90C53

DOI: 10.21538/0134-4889-2023-29-3-138-155

Полный текст статьи (Full text)

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

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

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

1.   Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // Докл. АН СССР. 1981. Т. 256, № 2. С. 272–276.

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

3.   Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.

4.   Морозов В.А. О псевдорешениях // Журн. вычисл. математики и мат. физики. 1969. Т. 9, № 6. С. 1387–1391.

5.   Кочиков И.В., Матвиенко А.Н., Ягола А.Г. Обобщенный принцип невязки для решения несовместных уравнений // Журн. вычисл. математики и мат. физики. 1984. Т. 24, № 7. С. 1087–1090.

6.   Исследования по несобственным задачам оптимизации: cб. науч. статей / УрО АН СССР. Свердловск, 1988. 78 с.

7.   Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования: cб. науч. статей / УНЦ АН СССР. Свердловск, 1985. 136 с.

8.   Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 1986. Т. 26, № 3. С. 439–448.

9.   Нерегулярная двойственность в математическом программировании: cб. науч. статей / УНЦ АН СССР. Свердловск, 1990. 78 с.

10.   Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. Екатеринбург, 2008. T. 14, № 2. C. 115–128.

11.   Попов Л.Д. Поиск обобщенных решений несобственных задач линейного и выпуклого программирования с помощью барьерных функций // Изв. Иркут. гос. ун-та. Сер. Математика. 2011. Т. 4, № 2. C. 134–146.

12.   Еремин И.И., Попов Л.Д. Внутренние штрафные функции и двойственность в линейном программировании // Тр. Ин-та математики и механики УрО РАН. 2012. Т. 18, № 3. C. 83–89.

13.   Попов Л.Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. Вып. 3. C. 3–11.

14.   Фиакко А., Мак–Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.

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

16.   Рокафеллар Р.Т. Выпуклый анализ. М.: Мир, 1973. – 472 с.

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

Поступила 26.01.2023

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

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

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

Ссылка на статью: Л.Д. Попов. Барьеры и симметричная регуляризация функции Лагранжа при анализе несобственных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 138-155

English

L.D. Popov. Barriers and symmetric regularization of the Lagrange function in the analysis of improper linear programming problems

In this paper, the author continues his research on the modification and adaptation of classical methods of the central path in order to apply them to the analysis of improper problems of linear programming. In the new constructions presented in the paper, in contrast to those developed earlier, it becomes possible to apply second-order optimization methods. Moreover, there is no need to specify in advance the type of impropriety of the problem being solved. Convergence theorems for the constructed methods are given, a meaningful interpretation of the obtained generalized solution is provided, and the results of numerical experiments are presented.

Keywords: linear programming, improper problems, generalized solutions, barrier function method, regularization

Received January 26, 2023

Revised June 9, 2023

Accepted June 13, 2023

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

Cite this article as: L.D. Popov. Barriers and symmetric regularization of the Lagrange function in the analysis of improper linear programming problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 138–155.

[References -> on the "English" button bottom right]