Том 25, номер 1, 2018 г., Стр. 75–97

УДК 519.8
Крылатов А. Ю.
Сведение задачи минимизации выпуклой сепарабельной функции с линейными ограничениями к задаче поиска неподвижной точки

Аннотация:
Статья посвящена исследованию специального вида задачи условной нелинейной оптимизации. Целевой функционал исследуемой задачи представлен выпуклой сепарабельной функцией, минимум которой ищется на множестве линейных ограничений в виде равенств. Доказано, что для данного типа оптимизационных задач может быть получен явный вид проектирующего оператора на базе обобщённой проектирующей матрицы. Проектирующий оператор позволяет представить исходную задачу в виде задачи поиска неподвижной точки. Явный вид задачи поиска неподвижной точки позволяет запустить процедуру простой итерации. Доказана сходимость полученного итерационного метода со скоростью геометрической прогрессии, а при дополнительных, достаточно естественных, условиях доказана квадратичная сходимость. Показано, что важным приложением разработанного метода является задача распределения потока в сети произвольной топологии с одной парой исток — сток.
Библиогр. 10.

Ключевые слова: условная нелинейная оптимизация, задача поиска неподвижной точки, обобщённая проектирующая матрица, распределение потока в сети.

DOI: 10.17377/daio.2018.25.560

Крылатов Александр Юрьевич ^1,2
1. Санкт-Петербургский гос. университет,
Университетская наб., 7/9, 199034 Санкт-Петербург, Россия
2. Институт проблем транспорта им. Н. С. Соломенко РАН,
12-я линия В. О., 13, 199178 Санкт-Петербург, Россия
е-mail: a.krylatov@spbu.ru, aykrylatov@yandex.ru

Статья поступила 26 декабря 2016 г.
Исправленный вариант — 8 августа 2017 г.

Литература

[1] Гантмахер Ф. Р. Теория матриц. М.: Наука, 1966. 576 с.

[2] Коннов И. В. Нелинейная оптимизация и вариационные неравенства. Казань: Изд-во Казан. ун-та, 2013. 508 с.

[3] Крылатов А. Ю. Распределение потока в сети как задача поиска неподвижной точки // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 63–87.

[4] Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 454 с.

[5] Beckmann M. J., McGuire C. B., Winsten C. B. Studies in the economics of transportation. New Haven, CT: Yale Univ. Press, 1956. 359 p.

[6] Bertsekas D. P. Nonlinear programming. Belmont, MA: Athena Scientific, 1999.

[7] Chen R.-J., Meyer R. R. Parallel optimization for traffic assignment // Math. Program. 1988. Vol. 42, No. 1-3. P. 327–345.

[8] Patriksson M. A unified description of iterative algorithms for traffic equilibria // Eur. J. Oper. Res. 1993. Vol. 71, No. 2. P. 154–176.

[9] Patriksson M. The traffic assignment problem: models and methods. Mineola, NY: Dover Publ., 2015. 240 p.

[10] Wardrop J. G. Some theoretical aspects of road traffic research // Proc. Inst. Civil Eng. 1952. Vol. 1, No. 3. P. 325–362.