Л.Д. Попов. Об одном приеме повышения гладкости внешних штрафных функций в линейном и выпуклом программировании ... С. 88-101

УДК 519.658.4

MSC: 47N05, 37N25, 37N40

DOI: 10.21538/0134-4889-2021-27-4-88-101

Данное исследование выполнено в Уральском математическом центре при финансовой поддержке Министерства науки и высшего образования Российской Федерации (номер проекта 075-02-2021-1383).

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

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

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

1.   Еремин И. И. Метод штрафов в выпуклом программировании // Докл. АН СССР. 1967. Т. 173, № 4. С. 748–751.

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

3.   Зангвилл У. И. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973. 312 с.

4.   Полак Э. Численые методы оптимизации. М.: Мир, 1974. 376 с.

5.   Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978. 351 с.

6.   Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.

7.   Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 509 с.

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

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

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

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

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

13.   Попов Л. Д. Комбинированные штрафы и обобщенные решения несобственных задач линейного и выпуклого программирования 1-го рода // Тр. Ин-та математики и механики УрО РАН. 2010. T. 16, № 3. C. 217–226.

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

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

Поступила 19.05.2021

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

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

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

Ссылка на статью: Л.Д. Попов. Об одном приеме повышения гладкости внешних штрафных функций в линейном и выпуклом программировании // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 4. С. 88-101

English

L.D. Popov. On one method of increasing the smoothness of external penalty functions in linear and convex programming

We propose original constructions of external penalty functions in linear and convex programming, which asymptotically reduce constrained optimization problems to unconstrained ones with increased smoothness. The latter admit an effective solution by second-order methods and, at the same time, do not require the knowledge of an interior feasible point of the original problem to start the process. Moreover, the proposed approach is applicable to improper linear and convex programs (problems with contradictory constraint systems), for which they can generate some generalized (compromise) solutions. Convergence theorems and the data of numerical experiments are presented.

Keywords: linear programming, improper (ill-posed) problems, generalized solutions, penalty functions, Newton method

Received May 19, 2021

Revised July 20, 2021

Accepted July 26, 2021

Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2021-1383).

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. On one method of increasing the smoothness of external penalty functions in linear and convex programming, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 4, pp. 88–101.

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