Симметричная двойственность в выпуклой оптимизации и модели потокораспределения

• Автор: Медвежонков, Дмитрий Сергеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Иркутск
• Количество страниц: 135 с. : ил.

Содержание
Введение

Глава 1. Обзор по теории симметричной двойственности, моделям

потокораспределения и алгоритмам внутренних точек

§1.1. Основы симметричной двойственности задач оптимизации § 1.2. Модели потокораспределения и задачи оптимизации

§1.3. Метод внутренних точек как способ расчета моделей 2

§1.4. Выводы по главе

Глава 2. Симметричная двойственность в задачах выпуклой оптимизации с ограничениями-неравенствами
§2.1. Двойственность задач оптимизации со строго выпуклой дифференцируемой целевой функцией -

§2.2. Обсуждение свойств двойственных задач оптимизации

Глава 3. Реализация и исследование вариантов алгоритмов внутренних точек

§3.1. Прямые алгоритмы внутренних точек
§3.2. Двойственные алгоритмы внутренних точек
§3.3. Численные эксперименты на задачах потокораспределения 60 §3.4. Расчеты на задачах проекции точки на политоп
Глава 4. Нелинейные модели потокораспределения в экономике и
энергетике
§4.1. Модель гидравлической системы с автоматическими регуляторами расхода -
§4.2. Нелинейная транспортная модель (экономическая интерпретация; варианты потокораспределения и тарифообразования) 89 §4.3. Нелинейная модель оценки возможностей ЕСГ или ЕСН в
чрезвычайных ситуациях
Заключение
Список литературы
Приложение. Справка о внедрении

Введение
Актуальность проблемы
Математическое моделирование и методы оптимизации важны при поиске системных связей и закономерностей функционирования сложных систем, для повышения эффективности управления в технических, экономических, социальных системах. Современная теория оптимизации во многих случаях служит методической основой для выбора наилучших экономических и технических решений, средством математического моделирования, инструментом вычислительной математики. Весомый вклад в развитие теории и методов оптимизации внесли: А. Таккер, JI.B. Канторович, Дж. Данциг, X. Кун, Г. Зойтендейк, Е.Г. Гольштейн, И.И. Еремин,
В.П. Булатов, Б.Т. Поляк, Ф.П. Васильев, Н.З. Шор, Б.Н. Пшеничный, В.Ф. Демьянов, Ю.Г. Евтушенко, У. Зангвилл и многие другие. [7, 13, 14, 24, 33, 42, 109, 128, 136, 139, 142, 144, 145, 154, 157, 167, 174, 180].
Одним из важнейших разделов теории оптимизации является теория двойственности [7, 13, 39, 67, 112, 158, 184, 188]. Двойственные задачи оптимизации применяются для доказательства оптимальности полученного решения, для анализа его устойчивости к варьированию исходных данных, для содержательной интерпретации математических моделей, теоретического обоснования и разработки новых алгоритмов решения задач математического программирования.
Вид двойственной задачи оптимизации зависит от вида исходной задачи и правил формирования двойственной задачи. Случай, когда двойственная задача оптимизации к двойственной задаче совпадает с исходной, в математическом программировании называют симметричной двойственностью. Симметричная двойственность имеет место для задач линейного программирования. Двойственные задачи нелинейного программирования не обладают в общем случае свойством симметричной двойственности, хотя для некоторых типов задач нелинейной оптимизации симметричная двойствен-

ность имеет место. Например, в работах У. Дорна [152], Дж. Денниса [16], а также С.И. Зуховицкого, Л.И. Авдеевой [65] формулируются симметричные двойственные задачи квадратичного программирования. Симметричная двойственность задач оптимизации с целевой функцией, выпуклой по одному векторному аргументу и вогнутой по другому, исследовалась в работах Г. Данцига, Е. Эйзенберга, Р. Коттла [150], М. Базара, Дж. Гуди [134], Г. Дэви [151], Б. Монда, Т. Вейра [169, 170] и др.
Основное внимание в диссертации уделяется симметричной двойственности на важном во многих приложениях подклассе задач минимизации сепарабельной дифференцируемой строго выпуклой функции при линейных ограничениях в виде равенств и неравенств на значения отдельных переменных. Теоретической основой для симметричной двойственности на этом классе задач служит теория альтернативных систем линейных неравенств [10, 40, 116, 125, 146, 147] и преобразование Лежандра-Фенхеля [80, 111, 127, 153, 176], известное из выпуклого анализа. Указанный подкласс задач исследовался ранее в работах научного руководителя, причём рассматривались только ограничения-равенства и односторонние ограничения-неравенства на переменные [28, 31, 50-53]. Теоремы, доказываемые в диссертации, развивают существующие исследования на случай задач оптимизации с двусторонними ограничениями-неравенствами на отдельные переменные.
В качестве объекта приложения симметричных двойственных задач оптимизации в диссертации рассматриваются модели потокораспределе-ния. Рассматриваемые модели можно разбить на два класса, различающиеся содержательной интерпретацией: гидравлические цепи и нелинейные транспортные модели (обобщающие линейные транспортные задачи).
В начале XX века в работах М.М. Андрияшева, В.Г. Лобачева, X. Кросса [3, 79, 148] были предложены первые методы расчета гидравлических сетей. С середины 60-х годов XX в. начала формироваться (в рамках системных научных исследований) теория гидравлических цепей, обобщаю-

F(x) + srx-> min (12)
Ах = b, (13)
IA j-s •— m Ч ь (14)
XJ-XJ’ j&JH’ (15)
Xj < Xj < Xj, j e JLH. (16)
Будем называть задачу (12)—(16) исходной задачей оптимизации
Теорема 1. Для существования решения задачи (12)—(16) достаточно непротиворечивости ограничений (13)—(16). Если у данной задачи имеется оптимальное решение, то оно единственно.
Доказательство. Введем обозначения: P](xJ) = FJ(xJ) + s]xJ и
Р(х) = F(x) + sTx. Обозначим р - производную функции Pj для j&J. Для функции Р(х) рассмотрим совокупность множеств Лебега, зависящих от вещественного параметара а:
R" : Р(х) < а}.
Из условия Fj е Z , j е J следует, что функции Pj (Xj) - строго выпуклы, а также lim р (х ) = -оо, lim р (х ) = +go при j е J . Следовательно,
XJ ->-00 —>+00 * '
lim Р(х') = +00 и lim Р (х ) =+оо при / е J . Отсюда вытекает, что
X ->-00 J J х —>+00 J J
inf Pix) > -оо. Если а < inf Р(х), то множество Лебега Ха, очевидно, пусто.
Покажем, что для любого вещественного а множество Лебега Ха ограничено, то есть для всякого а е R существует число М е R такое, что ||х|| < М для всех х е Ха, где И - векторная норма (любая, поскольку в конечномерном пространстве все нормы эквивалентны).
Обозначим РЬ~' (у j) - обратную функцию к функции Ру {х]), определенную при таких хj, что f} {х}) + s} < 0, a PR ' ) - обратную функцию