«СИММЕТРИЧНАЯ ДВОЙСТВЕННОСТЬ В ВЫПУКЛОЙ ОПТИМИЗАЦИИ И МОДЕЛИ ПОТОКОРАСПРЕДЕЛЕНИЯ ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

Институт систем энергетики им. Л.А. Мелентьева СО РАН

На правах рукописи

МЕДВЕЖОНКОВ Дмитрий Сергеевич

СИММЕТРИЧНАЯ ДВОЙСТВЕННОСТЬ

В ВЫПУКЛОЙ ОПТИМИЗАЦИИ И МОДЕЛИ

ПОТОКОРАСПРЕДЕЛЕНИЯ

Специальность 05.13.01 – Системный анализ, управление и обработка информации (в технике, экологии и экономике)

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

д.т.н., проф. В.И. Зоркальцев Иркутск – Содержание Введение Глава 1. Обзор по теории симметричной двойственности, моделям потокораспределения и алгоритмам внутренних точек §1.1. Основы симметричной двойственности задач оптимизации – §1.2. Модели потокораспределения и задачи оптимизации §1.3. Метод внутренних точек как способ расчета моделей §1.4. Выводы по главе Глава 2. Симметричная двойственность в задачах выпуклой оптимизации с ограничениями-неравенствами §2.1. Двойственность задач оптимизации со строго выпуклой дифференцируемой целевой функцией – §2.2. Обсуждение свойств двойственных задач оптимизации Глава 3. Реализация и исследование вариантов алгоритмов внутренних точек §3.1. Прямые алгоритмы внутренних точек §3.2. Двойственные алгоритмы внутренних точек §3.3. Численные эксперименты на задачах потокораспределения §3.4. Расчеты на задачах проекции точки на политоп Глава 4. Нелинейные модели потокораспределения в экономике и энергетике §4.1. Модель гидравлической системы с автоматическими регуляторами расхода – §4.2. Нелинейная транспортная модель (экономическая интерпретация; варианты потокораспределения и тарифообразования) §4.3. Нелинейная модель оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях Заключение Список литературы Приложение. Справка о внедрении Введение Актуальность проблемы Математическое моделирование и методы оптимизации важны при поиске системных связей и закономерностей функционирования сложных систем, для повышения эффективности управления в технических, экономических, социальных системах. Современная теория оптимизации во многих случаях служит методической основой для выбора наилучших экономических и технических решений, средством математического моделирования, инструментом вычислительной математики. Весомый вклад в развитие теории и методов оптимизации внесли: А. Таккер, Л.В. Канторович, Дж. Данциг, Х. Кун, Г. Зойтендейк, Е.Г. Гольштейн, И.И. Еремин, В.П. Булатов, Б.Т. Поляк, Ф.П. Васильев, Н.З. Шор, Б.Н. Пшеничный, В.Ф.

Демьянов, Ю.Г. Евтушенко, У. Зангвилл и многие другие. [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 века в работах М.М. Андрияшева, В.Г. Лобачева, Х.

Кросса [3, 79, 148] были предложены первые методы расчета гидравлических сетей. С середины 60-х годов XX в. начала формироваться (в рамках системных научных исследований) теория гидравлических цепей, обобщающая методы моделирования и оптимизации трубопроводных систем. Вклад в ее развитие внесли В.Я. Хасилев, А.П. Меренков, М.Г. Сухарев, А.Г. Евдокимов, А.Д. Тевяшев, С.В. Сумароков, Е.В. Сеннова, Н.Н. Новицкий и др.

[20, 22, 73, 101, 102, 107, 114, 123, 132, 168, 185].

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

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

В качестве объекта приложения теории симметричной двойственности в диссертации рассматриваются также нелинейные транспортные модели, в которых затраты на перевозки по отдельным дугам задаются в виде нелинейных функций от объемов перевозок. Во многих случаях такие модели более адекватны действительности, чем традиционно рассматриваемые линейные транспортные модели [15, 68–71, 117–119, 122, 135, 155, 160, 162, 165, 166]. Нелинейные транспортные модели исследовались с конца 40-х гг. XX в работах Р.Д. Даффина, Г. Биркхофа, Д. Диаза, Д. Денниса, Миллара, Г.Д. Минти, В.Н. Лившица, Р. Рокафеллара, Д. Бертсекаса, Л.Д. Попова, Е.А. Нурминского и других [8, 16, 75–78, 108, 129, 138, 141, 143, 177]. Одним из важных аспектов нелинейных транспортных моделей, рассматриваемых в диссертации является выбор альтернативы формирования тарифов на перевозки – по предельным или по средним затратам.

В диссертации подробно рассматривается одно из конкретных приложений транспортных моделей для исследования проблем обеспечения энергетической безопасности страны и её регионов. В качестве развития линейной модели оценки производственных возможностей отраслевых систем энергетики в экстремальных ситуациях, используемой в ИСЭМ СО РАН, в диссертации предлагается рассмотреть нелинейную транспортную модель с двусторонними ограничениями-неравенствами. Нелинейная целевая функция более адекватно описывает риски от использования на отдельных транспортных ветвях режимов повышенной (относительно нормы) нагрузки. Для улучшения существующей методики ранжирования «узких мест» представляется целесообразным использовать факты симметричной двойственности.

Для расчета моделей потокораспределения могут применяться различные алгоритмы [137, 140, 159, 163, 175, 183, 187], в том числе из имеющегося большого разнообразия методов выпуклого программирования. В диссертационной работе акцент сделан на сравнительных экспериментальных исследованиях вариантов алгоритмов внутренних точек из особого класса, в которых ограничения-неравенства на переменные учитываются путем введения квадратичной штрафной функции (с итеративно меняющимися весами) в целевую функцию вспомогательной задачи поиска направления улучшения решения. Пионерами в разработке этих алгоритмов были в СССР в 60 – 70-х гг. XX века С.М. Анцыз, И.И. Дикин, Ю.Г. Евтушенко, В.Г. Жадан, В.И. Зоркальцев [17, 18, 23, 24]. В СО РАН эти алгоритмы использовались при реализации ряда моделей энергетики [19, 20, 44, 45, 49].

Повышенный интерес к алгоритмам внутренних точек во всем мире возник в 80-х годах прошлого века благодаря работам Л.Г. Хачияна, Д.Б.

Юдина, Н. Кармаркара, А.С. Немировского, Ю.Е. Нестерова над полиномиальными методами. Эти работы послужили импульсом для появления большого числа публикаций, посвященных теоретическим и экспериментальным исследованиям алгоритмов внутренних точек. Весомый вклад в развитие алгоритмов внутренних точек внесли зарубежные ученые: И. Адлер, Р. Вандербей, М. Коджима, Г. Мак-Кормик, Р. Монтейро, Ш. Мицуно, М. Тодд, Т. Тсучия, А. Фиакко и др. [120, 133, 164, 174, 182].

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

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

Можно выделить два подмножества алгоритмов внутренних точек рассматриваемого класса: прямые и двойственные алгоритмы. Симметричная двойственность имеет принципиальное значение для двойственных алгоритмов внутренних точек; без этого свойства их использование было бы невозможным. Частным случаем рассматриваемых алгоритмов является известные affine scaling method [133, 182] и dual affine scaling method для решения задач линейного программирования.

К настоящему времени получен ряд важных результатов в усовершенствовании и теоретическом обосновании алгоритмов внутренних точек, в том числе в работах [48, 58, 59]. В этих работах на задачах линейного программирования была доказана сходимость для семейства алгоритмов, различающихся правилами задания весовых коэффициентов. Имеет место недостаток экспериментальных исследований алгоритмов из этого семейства с различными способами задания весовых коэффициентов, особенно для задач выпуклой оптимизации. Одной из задач диссертации являются экспериментальные исследования с целью сопоставления прямых и двойственных алгоритмов, выявления их свойств, выбора наиболее эффективных вариантов реализации.

Цели исследований диссертации. Диссертация посвящена совершенствованию методов системного анализа сложных систем для повышения эффективности их функционирования. Исследования, представленные в диссертации, преследовали следующие три взаимосвязанные цели:

1) исследовать возможности развития и применения симметричной двойственности в оптимизации для задач выпуклого программирования с сепарабельной целевой функцией и линейными ограничениями – равенствами и неравенствами, в том числе двусторонними;

2) на базе теории симметричной двойственности исследовать свойства нелинейных моделей потокораспределения с ограничениями-неравенствами;

3) провести сравнительные экспериментальные исследования вариантов прямых и двойственных алгоритмов внутренних точек на моделях потокораспределения.

Объектом исследования являются задачи оптимизации с выпуклой целевой функцией и линейными ограничениями, алгоритмы внутренних точек, модели технических и экономических систем потокораспределения.

Предметом исследования является развитие теории симметричной двойственности, выявление новых свойств моделей потокораспределения и экспериментальные исследования алгоритмов внутренних точек.

Методы и инструменты исследования базируются на методологии математического моделирования, теории и методах оптимизации, выпуклом анализе, теории графов, линейной алгебре. Для реализации итерационных численных алгоритмов использованы языки программирования С и С++, также проведены расчеты в математических пакетах Maple и Matlab.

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

2) На основе теории симметричной двойственности получена содержательная интерпретация нелинейных моделей потокораспределения с двусторонними ограничениями на переменные. Разработана нелинейная модель оценки возможностей функционирования в чрезвычайных ситуациях Единых систем газо- или нефтеснабжения. Для этой модели даны рекомендации по использованию двойственных оценок при ранжировании «узких» мест сети.

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

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

Предложена новая нелинейная модель оценки возможностей Единой системы газоснабжения (ЕСГ) или Единой системы нефтеснабжения (ЕСН) в чрезвычайных ситуациях, являющаяся развитием существующей в ИСЭМ СО РАН линейной модели. Для предложенной модели даны рекомендации по использованию двойственных оценок для более детального ранжирования «узких» мест транспортной сети, что является новым в работах по исследованию живучести ЕСГ и ЕСН. Предложены новые интерпретации постановок нелинейных транспортных задач на базе теории симметричной двойственности.

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

Практическая значимость 1) Нелинейная модель оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях использована в исследованиях проблем энергетической безопасности, которые включают анализ последствий реализации возможных возмущений в системах энергетики, а также выявление слабых мест в системе топливо- и энергоснабжения потребителей. Полученные на основе теории симметричной двойственности оценки дают дополнительную информацию о потокораспределении, необходимую для более детального анализа живучести систем энергетики в чрезвычайных ситуациях.

2) Разработанный программный модуль, реализующий алгоритм внутренних точек для расчета нелинейной модели оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях, внедрен в программный комплекс «Нефть и газ России» (ИСЭМ СО РАН).

3) Распространение теории симметричной двойственности на класс задач оптимизации с ограничениями-неравенствами позволяет описывать с их помощью гидравлические системы с автоматическими регуляторами расхода. Для модели такой системы с учетом свойств разреженности матрицы инциденций выполнена программная реализация двойственного алгоритма внутренних точек, дающая выигрыш в скорости счета по сравнению с некоторыми коммерческими решателями.

4) Разработана программная среда EasyLink, позволяющая визуализировать процесс задания исходных данных модели потокораспределения.

5) Материалы диссертации используются в спецкурсе «Сетевые модели экономики и энергетики», читаемом студентам ИМЭИ ИГУ.

Соответствие диссертации паспорту научной специальности. В соответствии с паспортом специальности 05.13.01 в диссертации проведено развитие теории симметричной двойственности в оптимизации; выполнена формализация и постановка задач потокораспределения; усовершенствованы критерии оценки эффективности решения задач оптимизации для исследования энергетической безопасности; разработано специальное математическое и программное обеспечение для решения этих задач, а также для визуализации исходных данных (пп. 1–3, 5, 12 области исследований).

Достоверность научных результатов подтверждается строгими математическими доказательствами, а также проверкой исследуемых идей, моделей и алгоритмов на тестовых, модельных и прикладных задачах энергетики.

Апробация работы Исследования по теме диссертации выполнялись в рамках проектов РФФИ №05-01-00587a, №09-01-00306-а, РГНФ №06-02-00266а. Докладывались и обсуждались на 22 конференциях, из них: 5 международных и всероссийских. В том числе: на научно-теор. конференциях молодых ученых ИГУ (2006, 2007); на XXXVI–XXXXI конференциях научной молодежи ИСЭМ СО РАН (2006–2011); на Межвуз. конф. «Математика и проблемы ее преподав. в вузе» (2007, Иркутск, ИГПУ); на IX Школе-семинаре молодых ученых "Мат. моделир. и инф. технологии" (2007, Иркутск, Ангасолка, оз.

Байкал); на III и IV Всеросс. конф. «Проблемы оптимизации и экономические приложения» (2006, 2009, Омск, Омский филиал ИМ СО РАН); на Российской конф. "Дискретная оптимизация и исследование операций" (2007, Владивосток, ИМ СО РАН, ИАПУ ДВО РАН); на международной научно-практ.

конф. «Актуальные проблемы математики, информатики, механики и теории управления» (2009, Алматы, Казахстан); на II Междунар. школе-семинаре «Нелинейный анализ и экстремальные задачи» (2010, Иркутск, ИДСТУ СО РАН); Всеросс. научн. семинаре с междунар. участием «Математические модели и методы анализа и оптимальн. синтеза развивающ. трубопроводных и гидравлич. систем» (2010, Ялта, Украина); на XIV Всеросс. конф. «Мат. программир. и прилож.» (2011, ИММ УрО РАН, Екатеринбург); на РоссийскоМонгольской конф. мол. ученых по мат. моделир., вычисл.-инфор-мац. технологиям и управлению (2011, Ханх, Монголия); на XIV и XV Байкальской междунар. школе-семинаре «Методы оптимиз. и их приложения» (2008, Северобайк.; 2011, п. Листвянка, оз. Байкал).

Работа обсуждалась на семинарах в научных институтах: на совместном заседании секций «Специализир. системы энергетики» и «Прикл. математика и информатика» ИСЭМ СО РАН (2010, Иркутск); на совм. заседании семинаров «Мат. экономика» и «Модели экономич. систем с иерархией в управлении» ИМ СО РАН (2011, Новосибирск); на объединенном семинаре ИВМиМГ и кафедры выч. математики НГУ (2011, Новосибирск); на семинаре Отделения методов управления и исследования операций ИДСТУ СО РАН (2011, 2013, Иркутск).

Публикации Результаты опубликованы в 31 печатной работе [30, 32, 54–57, 60–64, 81–100]. Из этих работ 18 статей, в том числе: 5 статей в реферируемых журналах из списка ВАК [32, 56, 64, 92, 100], 1 статья [62] в зарубежном журнале. В числе публикаций 6 текстов докладов [55, 57, 63, 95, 98, 99] в материалах международных конференций.

Личный вклад автора. Все основные научные результаты, выносимые на защиту, получены автором самостоятельно и не нарушают авторских прав других лиц. Из совместных публикаций с В.И. Зоркальцевым, С.П. Епифановым, С.М. Пержабинским в диссертационную работу включены результаты, не затрагивающие интересы соавторов. А.В. Еделев осуществлял консультирование и помощь с внедрением нелинейной модели оценки возможностей ЕСГ или ЕСН.

Структура и объем работы. Диссертация изложена на 135 страницах и состоит из введения, четырех глав, заключения, списка литературы, который содержит 188 наименований, и приложения. В диссертации содержится 7 рисунков, 16 таблиц.

Глава 1. Обзор по теории симметричной двойственности, моделям потокораспределения и алгоритмам внутренних точек §1.1. Основы симметричной двойственности задач оптимизации Для широкого класса задач оптимизации применяются особые конструкции – двойственные задачи оптимизации, вид которых зависит от вида исходной задачи и правил формирования двойственной задачи. Случай, когда двойственная задача к двойственной совпадает с исходной назвают симметричной двойственностью. Подобный термин в используемом в диссертации смысле был введен в работе У. Дорна [152].

В диссертации сформулированы и доказаны теоремы, обосновывающие симметричную двойственность задач выпуклого программирования с линейными ограничениями, в том числе с двусторонними неравенствами на значения переменных. Эти теоремы развивают исследования, начатые в работах [28, 29, 31, 50–53]. Для доказательства теорем симметричной двойственности и исследования свойств задач оптимизации используются факты теории альтернативных систем линейных неравенств и свойства преобразования Лежандра-Фенхеля.

Теория альтернативных систем линейных неравенств Теоремы об альтернативных системах линейных неравенств лежат в основе теории математического программирования. На них базируется теория двойственности линейной оптимизации, которая, в свою очередь, является основой широкого класса задач нелинейной оптимизации. Эти теоремы имеют и другие важные приложения. В частности, они используются при идентификации несовместности системы линейных неравенств; для конструирования новых алгоритмов решения систем линейных и, на базе этого, нелинейных систем неравенств; для выявления избыточных ограничений в задачах оптимизации; для получения решений систем линейных неравенств с минимальным набором активных ограничений [116].

Теоремы об альтернативных системах линейных неравенств утверждают, что системе линейных неравенств можно поставить в соответствие (по некоторым правилам) альтернативную систему линейных неравенств.

Альтернативность состоит в том, что одна и только одна из этих двух систем будет иметь решение, а вторая обязательно будет иметь противоречивые условия. При этом имеет место симметрия систем: альтернативная к альтернативной системе совпадает с исходной системой.

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

Вклад в развитие теории альтернативных систем линейных неравенств внесли работы П. Гордана, Г. Минковского, Г. Фаркаша, Д. Гейла [10], С.Н. Черникова [125], И.И. Еремина [40], Н.Н. Астафьева [33], К.Г.

Бройдена [147, 146], А.И. Голикова, Ю.Г. Евтушенко [12], В.И. Зоркальцева [116] и других.

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

Одним из первых идею двойственности в задачах ЛП исследовал Л.В. Канторович. Развивая методы решения транспортной задачи, он еще в 1940 предложил метод разрешающих множителей, который можно рассматривать как идейную основу известного симплекс-метода, предложенного в 1947 г. Дж. Данцигом [15]. Развивая теорию и методы ЛП для решения задач экономики и производства, Л. В. Канторович ввел «двойственные оценки» ресурсов [71] (сам он называл их «объективно обусловленными оценками»), показывающие степень ценности этих ресурсов для общества. В своих работах Л.В. Канторович развил идею о том, что каждое оптимальное производственное и управленческое решение взаимосвязано с оптимальной системой цен, заданных двойственными оценками.

В работах И.И. Еремина исследовались постановки несобственных двойственных задач линейного программирования [34, 35], а также симметричных двойственных задач последовательного линейного программирования [36]. Перенос симметричной двойственности на ситуацию паретолексикографических задач оптимизации, в частности в предположениях несобственности, реализован в работах [37–39].

Идеи и факты теории симметричной двойственности ЛП используются в диссертации для построения симметричной двойственности задач оптимизации выпуклых функций при линейных ограничениях, в том числе двусторонних ограничениях-неравенствах на переменные.

Симметричная двойственность в нелинейном программировании Работа Дж. Денниса [16] посвящена обсуждению анологий между теорией электрических цепей и математическим программированием, в ней дана физическая интерпретация задач потокораспределения. В этой работе формулируются симметричные двойственные задачи квадратичного программирования с использованием преобразования Лежандра, обладающие свойством симметричной двойственности.

В книге С.И. Зуховицкого, Л.И. Авдеевой [65] излагаются методы и задачи линейного и выпуклого программирования, формулируются симметричные двойственные задачи линейного и квадратичного программирования с использованием преобразования Лежандра.

Симметричная двойственность для задач оптимизации вещественной функции f (x, y ), выпуклой по вектору переменных x и вогнутой по вектору переменных y формулируется в работах Г. Данцига, Е. Эйзенберга, и Р. Коттла [150], а также Б. Монда [169]. Обобщение результатов Г. Данцига и др. выполнено в работах М. Базараа и Дж. Гуди [134], а также Г. Дэви [151]. Б. Монд и Т. Вейр в статье [170] сформулировали постановки симметричных двойственных задач с псевдовыпуклой–псевдовогнутой целевой функцией.

В работах В.И. Зоркальцева [50–53] для задач оптимизации с целевыми функциями из специально введенного класса функций и линейными ограничениями были предложены формулировки двойственных задач, обладающие свойством симметричной двойственности. В работах [28, 29, 31, 51, 52] приводятся доказательства теорем симметричной двойственности для задач с ограничениями-равенствами, а также односторонними ограничениями-неравенствами.

Преобразование Лежандра-Фенхеля В теории оптимизации важную роль играют свойства выпуклости функций и множеств. Значительный прогресс в развтии методов оптимизации инициировала теория, получившая название «выпуклый анализ» (после работ В. Фенхеля [153] и Р. Рокафеллара [111]). В выпуклом анализе существенную роль играет преобразование Лежандра-Фенхеля.

Определение. Преобразованием Лежандра-Фенхеля выпуклой функции одного вещественного аргумента F : R R называется функция:

Отметим, что преобразование Лежандра-Фенхеля еще называют преобразованием Фенхеля [144], Лежандра-Юнга-Фенхеля [2, 80]. Функцию ( y ) также называют сопряженной с F (x) [109, 111, 127, 176].

В случае, когда вещественная функция F одного вещественного аргумента является строго выпуклой и дважды дифференцируемой, преобразование Лежандра-Фенхеля этой функции совпадает с классическим преобразованием Лежандра, задаваемым формулой:

где ( y ) – функция обратная к функции f (x), которая обозначает производную F (x).

Преобразование Лежандра получило своё название в честь французского математика Адриена-Мари Лежандра (1752–1833). Идея, которую хотел реализовать Лежандр, заключается в том, чтобы с помощью преобразования получить из исходной функции такую, что производные исходной и полученной функций были бы взаимно обратны.

Из определения следует, что для того, чтобы функция F (x) допускала преобразование Лежандра необходимо и достаточно, чтобы она была непрерывно дифференцируемой в области определения и чтобы её производная функция f (x) имела обратную. Последнее имеет место, если функция f (x) является взаимно однозначной (биекцией).

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

Свойства преобразования Лежандра-Фенхеля Приведем некоторые известные свойства преобразования ЛежандраФенхеля, которые будут использоваться в диссертации для доказательства теорем симметричной двойственности и для исследования свойств моделей потокораспределения.

1. Неравенство Фенхеля-Юнга [80, 111]. Для выпуклой функции F (x) и её преобразования Лежандра-Фенхеля ( y ) при любых x и y справедливо неравенство:

Это неравенство, в случае строго выпуклой дифференцируемой F (x), можно заменить парой условий [52]:

2. Функцию F : X R, X R называют полунепрерывной снизу, если для любого R множество Лебега X = {x X : F (x) } замкнуто.

Преобразование Лежандра-Фенхеля всегда является выпуклой полунепрерывной снизу функцией [111].

3. Результат применения преобразования Лежандра-Фенхеля к исходной функции дважды называется повторным преобразованием ЛежандраФенхеля. Его обозначают F ** (x).

Теорема Фенхеля-Моро [67, 80]. Для того, чтобы повторное преобразование Лежандра-Фенхеля F ** (x) было тождественно исходной функции F (x), необходимо и достаточно, чтобы F (x) была выпукла и полунепрерывна снизу.

Некоторые области применения преобразования Лежандра-Фенхеля Преобразование Лежандра и преобразование Лежандра-Фенхеля имеют ряд применений в математике:

1) в теории дифференциальных уравнений для более простого интегрирования некоторых классов дифференциальных уравнений [5, 74], 2) в дифференциальной геометрии к кривым и поверхностям для построения огибающих их семейств касательных [6, 21], 3) в вариационном исчислении для перехода от системы уравнений Эйлера – Лагранжа к системе уравнений Гамильтона [4, 2], 4) в математическом программировании для построения двойственных экстремальных формулировок задач [16, 29, 50–53, 65].

В физике преобразование Лежандра применяется:

1) в термодинамике для перехода между термодинамическими потенциалами [11, 82], 2) в классической механике для перехода от Лагранжевой механики к Гамильтоновой и обратно [4].

Во второй главе данной диссертации преобразование Лежандра-Фенхеля используется при построении двойственных задач оптимизации с выпуклыми сепарабельными целевыми функциями и линейными ограничениями равенствами и неравенствами. Преобразование Лежандра-Фенхеля помогает получить в явном виде целевую функцию двойственной задачи.

§1.2. Модели потокораспределения и задачи оптимизации Модели потокораспределения играют значительную роль при проектировании, построении сложных технических систем (в том числе транспортных системам) и оперативном управлении ими. Задачи и методы оптимизации служат инструментом для описания моделей потокораспределения. Развитие теории симметричной двойственности расширяет возможности описания и исследования таких систем. В данном параграфе выполнен обзор исследований различных авторов, посвященных изучению моделей потокораспределения.

Электрические и гидравлические цепи К одним из первых моделей потокораспределения можно отнести модели в виде систем уравнений, описывающие распространение тока в электрической цепи и распределения жидкости в гидравлической системе. Физические основы электрических цепей были заложены в работах Г. Ома, Г.

Кирхгофа, Д. Максвелла в XIX в. Первые методы расчета задач потокораспределения в гидравлической системе, основанные на решении системы нелинейных алгебраических уравнений, появились в 1930-х годах в работах М.М. Андрияшева [3], В.Г. Лобачева [79] и Х. Кросса [148].

Начиная с 1960-х годов в работах В.Я. Хасилева, А.П. Меренкова, М.Г. Сухарева были заложены основы теории гидравлических цепей [101], в которой рассматриваются модели и методы решения, связанные с произвольными трубопроводными и гидравлическими системами. Моделирование потокораспределения в трубопроводных системах основано на аналогах физических законов для электрических цепей. Поэтому при расчетах трубопроводных систем и электрических цепей используются общие методы их расчета. Значительную роль в развитии теории гидравлических цепей сыграли сотрудники Института систем энергетики им. Л.А. Мелентьева СО РАН (ранее СЭИ СО РАН).

Большой вклад в исследование гидравлических систем и разработку методов решения задач потокораспределения внесли: В.Я. Хасилев, А.П.

Меренков [101, 102, 123], С.В. Сумароков, М.Г. Сухарев, А.Г. Евдокимов, А.Д. Тевяшев [22], Б.Н. Пшеничный, Б.М. Каганович, Е.В. Сеннова, В.Г.

Сидлер [114], Н.Н. Новицкий [107], А.Г. Коваленко [73] и многие другие.

В работах С.П. Епифанова и В.И. Зоркальцева [28, 29, 50, 53] исследовались модели потокораспределения с линейными ограничениямиравенствами с помощью теории симметричной двойственности. Исходная задача оптимизации, используемая для описания модели потокораспределения гидравлической системы в [29], имеет вид:

Здесь переменные составляют вектор x R n ; задана матрица A размера m n и векторы b R m, c R n. Для j = 1,..., n задан набор функций F j Z, где Z – множество непрерывно дифференцируемых функций действительного аргумента, причем любая функция F j из Z удовлетворяет условиям:

Двойственная задача оптимизации в [29] имеет следующий вид:

Здесь переменные составляют векторы y R n, u R m. Для j = 1,..., n задан набор функций j из множества Z. Каждая функция j связана с функцией F j преобразованием Лежандра-Фенхеля. В [29] обосновывается симметричная двойственность задач (3)–(4) и (5)–(6).

В упомянутых работах не проводились исследования моделей потокораспределения на базе симметричных двойственных задач с двусторонними ограничениями-неравенствами на переменные. Подобные задачи важны, они позволяют описывать гидравлические системы с наличием автоматических регуляторов. Исследования подобных систем до настоящего времени велись на базе моделей, построенных с использованием систем уравнений и неравенств [20, 107, 114, 123].

Линейные и нелинейные модели потокораспределения Модели потокораспределения – достаточно универсальный класс моделей. С его помощью можно описать, кроме физических систем, также транспортные системы, возникающие в задачах экономики.

Первые постановки транспортных задач в экономике обычно связывают с работами А.Н. Толстого [117 – 119]. В [117] дается описание транспортной задачи, возникающей при планировании железнодорожных перевозок грузов между источниками и пунктами назначения. Там же предложено несколько подходов к решению, полученный в статье план перевозок действительно являлся оптимальным, однако строгих теорем и доказательств этого факта получено не было.

В 1941 г. Ф. Хичкоком была дана [162] оптимизационная постановка транспортной задачи, однако методы её решения не были предложены.

Серьезная попытка разработать математически обоснованные методы для широкого класса практических задач в экономике, в том числе транспортных, была сделана Л.В. Канторовичем в конце 1930-х годов. Транспортная задача рассматривалась им как оптимизационная. В работе [68] Канторовича с М. К. Гавуриным были в развернутой форме даны эффективные методы решения транспортной задачи.

Двойственные оценки получили различное толкование в работах самого Л.В. Канторовича [71] и западных ученых. Если в западной литературе наиболее популярны так называемые «теневые цены» на ресурсы, то Л.В.

Канторович использовал понятие «объективно обусловленных оценок».

За рубежом первыми сформулировали задачу о максимальном потоке Т.Харрис и Ф.Росс [160]. Интерес Харриса и Росса, в этой работе, засекреченной до 1999 года Министерством ВВС США, заключался в поиске мест с наименьшей пропускной способностью с целью наиболее эффективного поражения сети железнодорожного сообщения вероятного противника.

В [166] под редакцией Тьялинга Купманса опубликованы труды конференции, посвященной вопросам оптимального использования транспортных систем. В [166] Купманс приводит транспортную модель. В статье [143] Г. Биркгоф и Дж. Диаз впервые предлагают использовать релаксационные методы для решения выпуклых задач оптимизации на сетях.

Комбинаторные методы решения целочисленных задач о потоках в сетях рассмотрены в книге Форда и Фалкерсона [155]. Авторы делают упор на линейные постановки задач о потоке в сети и среди них лишь на те, для которых из предположения о исходных данных вытекает существование и целочисленного решения.

В книге Т. Рокафеллара [177], посвященной моделям потокораспределения и задачам монотропного программирования (так автор назвал задачи оптимизации с выпуклой сепарабельной целевой функцией и линейными ограничениями), приводится обширный обзор особенностей потоковых задач: как линейных, так и нелинейных. Также в книге рассматриваются алгоритмы решения задач потокораспределения с линейными, а также с выпуклыми возможно недифференцируемыми целевыми функциями. Изучаются вопросы двойственности задач оптимизации, и ставится задача транспортного равновесия.

Исследованием нелинейных транспортных задач в нашей стране занимался В.Н. Лившиц. В ряде публикаций [8, 75 – 78] им и группой соавторов были рассмотрены вопросы моделирования, развития магистральной транспортной сети, алгоритмы оптимального распределения потоков на сети, модели системного прогнозирования перевозок, вопросы эффективности капитальных вложений на транспорте, проблемы государственного регулирования естественных монополий, вопросы реформирование железнодорожного транспорта. Лившиц, однако, не рассматривал двойственные постановки нелинейных транспортных задач.

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

В [106, 110] описываются модели (на основе задач линейного программирования), которые позволяют оценить величины дефицита газа, возникшего у отдельных потребителей в случае возможной реализации крупномасштабного негативного возмущения в работе Единой системы газоснабжения (ЕСГ) или нефтеснабжения (ЕСН). В [113] исследуются вопросы определения и ранжирования «узких» места транспортной подсистемы, с целью выбора оптимального плана выхода из чрезвычайной ситуации. Газовый блок ПВК "Нефть и газ России", разработанный в ИСЭМ СО РАН [27], решает задачу нахождения максимального потока ресурса газовой сети при возможной минимизации стоимости этого потока. Для определения «узких» мест, ограничивающие возможности системы по удовлетворению потребителей требуемым ресурсом, а также ранжирования этих мест по значимости их влияния на работу системы, либо по приоритетности проведения мероприятий для рационального повышения производственных возможностей системы в [113] предлагается задача линейного программирования:

где v – величина суммарного дефицита ресурса у потребителей; d ij – ограничение на поток по дуге (i, j);. hij – приращение потока по дуге (i, j); qij – приращение потока по дуге (i, j) до d ij ; yij – приращение пропускной способности (i, j) свыше d ij ; Yij – ограничение на приращение пропускной способности по дуге (i, j) свыше d ij ; Cij – цена или удельные затраты на транспорт энергоресурса по дуге (i, j) в пределах d ij ; Aij – цена или удельные затраты на транспорт энергоресурса по приращению yij ; N + – подj множество "входящих" в узел j дуг; N – подмножество "выходящих" дуг из узла j; O – суммарный источник; S – суммарный сток; xij – значение потока по дуге (i, j), полученное при решении задачи нахождения максимального потока минимальной стоимости.

Задача (7)–(11) позвояет оценить каким образом и где необходимо увеличить пропускные способности дуг, чтобы получить искомый увеличенный поток с минимальными на это затратами. Для ранжирования «узких» мест используются величины yij, показывающие необходимость увеличения пропускной способности дуг свыше d ij.

Использование нелинейной целевой функции в (7) может повысить качество моделирования, поскольку нелинейная функция более реалистично описывает издержки, возникающие на практике в системах ЕСГ и ЕСН. Применение фактов двойственности в этой модели является одним из путей совершенствования методики решения проблемы ранжирования "узких" мест. Двойственные оценки позволяют выразить транспортные издержки и издержки от недопоставок в количественном выражении. Эту информацию можно использовать при проведении ранжирования.

Другие подходы к моделированию потокораспределения Транспортные модели могут быть представлены в виде систем равенств и неравенств. Например, такой системой являются условия оптимальности Куна-Таккера для линейной или нелинейной транспортной задачи. В книге [108] Л.Д. Попова содержится обзор линейных и нелинейных задач о дополнительности, а также их обобщений в виде вариационных неравенств. Вариационные неравенства являются, кроме того, обобщением для задач нелинейного программирования. Рассматриваемые в [108] постановки могут быть применены к задачам общего экономического равновесия, прогнозирования транспортных потоков и тарифов на грузоперевозки, в том числе к игровым постановкам транспортных задач.

В монографии [53] делается обзор равновесного программирования – подхода, обобщающего технику решения вариационных неравенств. В рамках этого направления равновесие определяется как неподвижная точка экстремального отображения. Обычная задача математического программирования представляет собой частный случай задачи равновесного программирования. Кроме того этот подход позволяет объединить в рамках одной теории биматричные игры, многокритериальную оптимизацию, а также равновесные модели математической экономики.

Публикации [126, 149, 158, 161, 172, 181, 186] посвящены постановкам транспортных задач в виде вариационных неравенств, исследованию условий существования, единственности и устойчивости транспортного равновесия. Статьи содержат информацию о соотношениях между различными видами равновесий и связях между задачами оптимизации и вариационными неравенствами.

§1.3. Метод внутренних точек как способ расчета моделей К эффективным и активно развиваемым методам решения задач оптимизации с ограничениями-неравенствами относятся алгоритмы методов внутренних точек. Первые алгоритмы метода внутренних точек появились в 1960-х. Алгоритмы этого класса, приближаются к оптимуму, находясь во внутренней части области допустимых по ограничениям неравенствам решений. В 1963 году А.В. Фиакко и Г.П. Мак-Кормик [120] описали метод внутренней точки для решения задачи нелинейного программирования с ограничениями-неравенствами. В 1967 г. И.И. Дикин [17] предложил алгоритм внутренних точек для решения задач линейного программирования, в основе которого лежит идея Л.В. Канторовича оценки методом наименьших квадратов множителей Лагранжа ограничений задачи при неоптимальном решении.

В работе [43] В.И. Зоркальцевым были предложены изменения вычислительного процесса алгоритма И.И. Дикина. Было предложено, в частности, при движении от точки текущего приближения вдоль направления улучшения не до границы эллипсоида, вписанного в допустимую область, как в методе внутренних точек Дикина, а на часть пути, определяемую коэффициентом (0,1), до границы допустимой области.

В 1984 г. Н. Кармакар публикует статью [164], в которой описывает алгоритм на основе метода внутренних точек для решения задач линейного программирования, в котором увеличение времени счета с ростом размера задачи полиномиально. Эта статья привлекла повышенное внимание во всём мире к алгоритмам внутренних точек.

Вариант метода внутренних точек, предложенный Зоркальцевым в [43], был переоткрыт в конце 1980-х в нескольких работах [133, 182] как модификация алгоритма Кармакара. За ним закрепилось название affine scaling method.

Алгоритмы внутренних точек данного типа активно развивались в России – в ВЦ АН СССР в работах академика Ю.Г. Евтушенко, ныне директора ВЦ РАН и доктора физико-математических наук В.Г. Жадана [23, 24, 41] и в СЭИ СО АН СССР (ныне ИСЭМ СО РАН), где эти алгоритмы использовались для проведения расчетов по нескольким моделям энергетики [18, 19, 20, 45, 49].

С середины 1980-х годов интерес к алгоритмам внутренних точек возрос во всем мире благодаря работам над полиномиальными методами Л.Г.

Хачияна, Н.З. Шора, Д.Б. Юдина, Н. Кармаркара, А.С. Немировского, Ю.Е. Нестерова [174]. Были опубликованы тысячи работ в разных странах. Определенный вклад в развитие алгоритмов внутренних точек внесли ученые: И. Адлер, Р. Вандербей, М. Коджима, Р. Монтейро, Ш. Мицуно, М. Тодд, Т. Тсучия и др.

К настоящему времени получен ряд важных результатов в усовершенствовании и теоретическом обосновании алгоритмов внутренних точек, в частности, в ИСЭМ СО РАН [48, 58, 59]. Выявлены подмножества алгоритмов, имеющих линейную и сверхлинейную скорости сходимости [47, 48].

Можно выделить два подмножества из рассматриваемого в диссертации класса алгоритмов внутренних точек: прямые и двойственные алгоритмы внутренних точек. Эти алгоритмы осуществляют монотонное улучшение решений исходной или двойственной задачи оптимизации внутри допустимой области по ограничениям-неравенствам соответствующей задачи. Частным случаем рассматриваемых алгоритмов внутренних точек являются affine scaling methods, разработанные для задач линейного программирования.

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

В работах В.И. Зоркальцева [44, 45, 58] обсуждаются правила задания весовых коэффициентов функций штрафа в алгоритмах внутренних точек, при которых можно доказать сходимость алгоритмов. В работах [9, 44, 45, 47, 121] проведены теоретические и экспериментальные исследования различных способов задания весовых коэффициентов в алгоритмах внутренних точек для задач линейного программирования.

Наиболее известными является квадратичными весовые коэффициенты. Алгоритм Дикина [17] использует данное правило задания весовых коэффициентов. Для них теоретически доказана возможность получения сверхлинейной скорости сходимости алгоритма [45, 58] при решении задач линейного программирования. Недостатком квадратичных весовых коэффициентов является то, что они очень чувствительны к неизбежным погрешностям в решении вспомогательной задачи.

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

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

§1.4. Выводы по главе Одним из важных разделов теории оптимизации является теория двойственности. Она имеет множество приложений. Задачи линейного программирования обладают свойством симметричной двойственности.

Задачи нелинейного программирования не всегда обладают свойством симметричной двойственности.

Для задач выпуклого программирования симметричную двойственность можно получить с использованием преобразования Лежандра-Фенхеля. В работах [16, 65] предложены постановки симметричных двойственных задач. В работах [28, 29, 31, 50–53] исследовалась симметричная двойственность задач оптимизации с сепарабельными дифференцируемыми строго выпуклыми целевыми функциями при ограничениях в виде равенств и односторонних неравенств для значений отдельных переменных. Естественным развитием этих исследований является формулировка и доказательство теорем симметричной двойственности для задач с двусторонними ограничениями-неравенствами.

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

Модели гидравлических и электрических цепей описывают распределение потоков (или токов) по дугам сети. В таких моделях двойственные оценки получают техническую интерпретацию (описывают давления или напряжения в узлах сети). В работах по теории гидравлических цепей системы с наличием автоматических регуляторов до настоящего времени исследовались на базе моделей, построенных с использованием систем уравнений и неравенств [20, 107, 114, 123]. В задачи диссертации входит исследование гидравлических систем с автоматическими регуляторами на базе симметричных двойственных задач с выпуклой сепарабельной целевой функцией и двусторонними ограничениями-неравенствами.

Транспортные модели в экономике (связанные с потокораспределением) [8, 68, 71, 76, 141, 143, 166, 177] зачастую сводятся к поиску минимума транспортных издержек при соблюдении ограничений на потоки. Некоторые постановки таких моделей исследованы в диссертации на базе теории симметричной двойственности. Важным с точки зрения моделирования здесь является содержательная экономическая интерпретация двойственных задач и двойственных оценок (с учетом различных постановок моделей). Эта интерпретация полезна, например, для оценки эффективности способов назначения тарифов и цен в транспортных системах.

Важным подклассом транспортных потоковых моделей экономики, являются модели анализа живучести и надежности отраслевых систем энергетики [106, 110, 113]. Эти модели позволяют определить производственные возможности отраслевых систем ТЭК (в частности, ЕСГ и ЕСН) и проранжировать «узкие» места при наличии разного рода возмущений в системе. Существующие модели (например, [113]) могут быть улучшены посредством введения нелинейных целевых функций. Двойственные оценки могут быть использованы при анализе и ранжировании «узких» мест для оценки эффективности ранжирования.

К классу эффективных численных методов для решения задач оптимизации с ограничениями-неравенствами относятся алгоритмы внутренних точек. В настоящее время существует большое число работ, посвященных исследованию этих алгоритмов (например, [17, 18, 41, 43, 133, 164, 174, 182]). В работах [9, 44, 45, 47, 58, 121] проведены теоретические и экспериментальные исследования различных способов задания весовых коэффициентов в алгоритмах внутренних точек для задач линейного программирования. Актуальной задачей, решаемой в диссертации, являются экспериментальные исследования вариантов алгоритмов внутренних точек для отдельных классов задач нелинейного программирования.

Глава 2. Симметричная двойственность в задачах выпуклой оптимизации с ограничениями-неравенствами В данной главе доказываются теоремы, обосновывающие симметричную двойственность задач оптимизации с сепарабельной строго выпуклой дифференцируемой целевой функцией и линейными ограничениями: равенствами и неравенствами. Здесь используется то же понятие симметричной двойственности, что и в [50–52, 152]. Обоснование теорем опирается на свойства преобразования Лежандра-Фенхеля [80, 111, 127, 144]. Формулируются теоремы о существовании и единственности решения исходной задачи, о связи между решениями двойственных задач оптимизации, об эквивалентных формах представления задач.

Доказательства теорем в первом параграфе являются развитием исследований, начатых в работах [28, 50–53]. Они обобщают упомянутые исследования на более широкий класс задач, поскольку здесь вводятся двусторонние ограничения-неравенства на значения переменных. Формулировка и обоснование условий оптимальности для двойственных задач с использованием кусочно-линейной функции-срезки (вместо использования билинейных условий дополняющей нежесткости) является развитием идей, предложенных научным руководителем в [52, 53].

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

§2.1. Двойственность задач оптимизации со строго выпуклой дифференцируемой целевой функцией Обозначим Z – множество дифференцируемых функций одного вещественного аргумента такое, что функция принадлежит Z тогда и только тогда, когда для функции и её производной справедливы следующие условия:

Примером функций, связанных преобразованием Лежандра-Фенхеля и принадлежащих множеству Z, могут служить функции, полученные в результате монотонно возрастающих строго выпуклых дифференцируемых преобразований двойственных норм. Из двойственных гельдеровских норм получаем, в качестве примера, такие функции:

Исходная задача оптимизации Пусть задана матрица A размера m n с элементами из R, и два множества индексов: I = {1,..., m} и J = {1,..., n}, где m и n – натуральные числа. Множество J разбито на четыре непересекающиеся подмножества:

J, J L, J H, J LH. Также заданы: вектор b R m, вектор s R n, числа x j, Пусть задан набор функций F j ( x j ), j J такой, что каждая из этих функций принадлежит множеству Z. Введем обозначение: F ( x) = Обозначим через f j производную функции Fj при j J.

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

Будем называть задачу (12)–(16) исходной задачей оптимизации Теорема 1. Для существования решения задачи (12)–(16) достаточно непротиворечивости ограничений (13)–(16). Если у данной задачи имеется оптимальное решение, то оно единственно.

P(x) F (x) + s T x. Обозначим p j – производную функции Pj для j J.

Для функции P(x) рассмотрим совокупность множеств Лебега, зависящих от вещественного параметара :

Из условия F j Z, j J следует, что функции Pj ( x j ) – строго выпуклы, а также lim p j ( x j ) =, lim p j ( x j ) = + при j J. Следовательно, inf P(x) >. Если < inf P(x), то множество Лебега X, очевидно, пусто.

Покажем, что для любого вещественного множество Лебега X ограничено, то есть для всякого R существует число M R такое, что x M для всех x X, где – векторная норма (любая, поскольку в конечномерном пространстве все нормы эквивалентны).

Обозначим PLj1 ( y j ) – обратную функцию к функции Pj ( x j ), определенную при таких x j, что f j ( x j ) + s j 0, а PR 1 ( y j ) – обратную функцию к функции Pj ( x j ), определенную при таких x j, что f j ( x j ) + s j 0.

Из условия F j Z, j J следует, что величины PLj1 ( ) и PR 1 ( ) определены и конечны при любом вещественном > inf P(x).

Искомое число M для любого вещественного равно x( ), где x( ) – вектор из R n с компонентами: x j ( ) = max{PLj1 ( ), PR 1 ( )}. Огj раниченность X доказана.

Если система ограничений (13)–(16) непротиворечива, то существует её решение ~. Непрерывность целевой функции P(x) и ограниченность множества Лебега X при = P (x ) и означает, что у задачи существует оптимальное решение. Строгая выпуклость P(x) и выпуклость множества допустимых по условиям (13)–(16) векторов означают, что оптимальное решение у задачи (12)–(16) может быть только единственным.

Теорема 1 доказана.

Рассмотрим систему уравнений и неравенств, переменные в которой – Система содержит условия (13)–(16), а также следующие условия:

Здесь символом ( ) + обозначена функция неотрицательной срезки веmax{0, }. Равенства (22), (23) являются личины в скобках, т.е.:

правилами вычисления величин l j, j J L J LH и hj, j J H J LH, их можно исключить из системы вместе с переменными l j и hj.

Теорема 2. Для того чтобы векторы x, y, u и скаляры l j, j J L J LH, h j, j J H J LH были решением системы (13)–(23) необходимо и достаточно, чтобы вектор x являлся оптимальным решением задачи (12)–(16), вектор u являлся вектором множителей Лагранжа ограничений (13), скаляры l j, h j являлись множителями Лагранжа ограничений (14)–(16), вектор y вычислялся по правилу (17). Если оптимальное решение задачи (12)–(16) существует, то векторы x и y единственны.

Доказательство. Уравнения (19)–(23) при выполнении (13)–(16) эквивалентны следующим условиям:

Докажем эквивалентность условий (21)–(23) и (26)–(30) для j J LH при выполнении (16). Пусть для j J LH выполнены (21)–(23), тогда условия (28) и (30) очевидно выполняются для этих j. Если AT u j < f j (x j ) + s j, то AT u j < f j (xj ) + s j (поскольку x j < x j и f j ( x j ) – строго возрастает), значит из (23) следует, что h j = 0. Отсюда h j ( x j x j ) = 0. Из (21) следует, что f j ( x j ) = f j ( x j ), значит x j = x j с учетом свойств f j ( x j ). Отсюда получаем для j J LH справедливость (27) и (с учетом (22)) справедливость условия (26). Если AT u j > f j (x j ) + s j, то AT u j > f j (x j ) + s j, значит из (22) следует, что x j = x j. Отсюда получаем для j J LH справедливость (29) и (с учетом (23)) справедливость условия (26). Если f j (x j ) AT u j s j f j (x j ), то из (22), (23) следует, что l j = 0, h j = 0. Из (21) следует, что f j (xj ) = ATu j s j, поэтому в этом случае также справедливы условия (26)–(30) для j J LH.

Пусть теперь, наоборот, для j J LH при справедливости (16) выполнены (26)–(30). Возможны три случая: 1) x j = x j, 2) x j = x j, 3) x j < x j < x j. Если x j = x j, тогда из (29) следует, что h j = 0. Тогда согласно (26), (28) справедливо l j = f j ( x j ) + s j [AT u] j, f j ( x j ) + s j [AT u] j 0. Значит выполнено (22), а с учетом справедливости неравенства f j ( x j ) f j ( x j ) выполнены и (21), (23) для j J LH. Если x j = x j, тогда из (27) следует, справедливости неравенства f j ( x j ) f j ( x j ) выполнены и (21), (22) для этом случае из (26) следует, что f j (xj ) = ATu j s j. Тогда с учетом свойств функции f j ( x j ) получаем f j ( x j ) < [AT u] j s j < f j ( x j ). При этом верны условия (21)–(23) для j J LH. Эквивалентность условий (21)–(23) и (26)–(30) для j J LH при выполнении (16) показана.

Эквивалентность условий (19), (22) и (24), (27), (28) для j J L при выполнении (14) и эквивалентность условий (20), (23) и (25), (29), (30) для j J H при выполнении (15) доказывается по аналогии с доказанным выше случаем эквивалентности (21)–(23) и (26)–(30) при j J LH.

Условия (13)–(16), (18), (24)–(30) являются условиями оптимальности Куна-Таккера для задачи (12)–(16), при этом они эквивалентны условиям (13)–(16), (18)–(23). В силу выпуклости целевой функции задачи (12)–(16) и линейности её ограничений условия оптимальности Куна-Таккера являются необходимыми и достаточными для того, чтобы вектор x, составляющий их решение, являлся оптимальным решением исходной задачи, а вектор u и скаляры l j, j J L J LH, h j, j J H J LH, составляющие их решение, являлись множителями Лагранжа ограничений исходной задачи.

Поскольку вектор x, являющийся оптимальным решением задачи (12)–(16), единственный, то и в решении системы (13)–(16), (18)–(23) этот вектор единственный. С учетом условия (17) и свойств функций f j ( x j ), j J вектор y единственный в решении системы (13)–(23).

Теорема 2 доказана.

Двойственная задача оптимизации Обратную функцию к функции f j ( x j ), j J обозначим j ( y j ). В силу свойств функции f j ( x j ), j J обратная функция j ( y j ) определена и при всех x j R, y j R, j J выполняются условия:

Пусть для всех j J функция j является преобразованием ЛежандраФенхеля функции F j Z. Из свойств преобразования Лежандра-Фенхеля и свойств функции F j следует, что j Z и что для положительных yj зации, переменные которой – векторы y R n, u R m и скаляры l j, Будем называть задачу (33)–(39) двойственной задачей оптимизации.

Теорема 3. Для того, чтобы векторы y, u и скаляры l j, j J L J LH и h j, j J H J LH, составляли оптимальное решение задачи (33)–(39), компоненты вектора x являлись множителями Лагранжа ограничений (34)–(37), необходимо и достаточно, чтобы вектор x являлся оптимальным решением задачи (12)–(16), компоненты вектора u являлись множиj J L J LH и h j, телями Лагранжа ограничений (13), скаляры l j, j J H J LH являлись множителями Лагранжа ограничений (14)–(16), а вектор y был связан с вектором x условиями (17).

Доказательство. Запишем условия оптимальности Куна-Таккера для задачи (33)–(39). В связи со строгой выпуклостью и дифференцируемостью целевой функции двойственной задачи, а также линейностью её ограничений эти условия будут необходимыми и достаточными для того, чтобы допустимое решение задачи (33)–(39) являлось оптимальным. В них войдут условия (34)–(39), а также:

Из (31) следует, что условие (40) равносильно условию (17). С учетом (17), условия (34)–(37) равносильны (18), (24)–(26). Условие (41) совпадаjL, ет с (13). Если исключить из условий (42), (43) переменные j J L J LH и jH, j J H J LH, то получим условия (14)–(16) и (27), (29).

Таким образом, условия (34)–(43) равносильны условиям (13)–(23), которые содержат условиями оптимальности Куна-Таккера для исходной задачи. Отсюда следует утверждение теоремы.

Теорема 3 доказана.

Замечание 1. (Условия существования решения двойственной задачи.) Двойственная задача всегда имеет допустимое решение. Например, очевидно получим допустимое решение.

Двойственная задача не имеет оптимального решения, только когда её целевая функция не ограничена снизу на области допустимых решений. А для этого, в связи со строгой выпуклостью (y ), необходимо и достаточно, чтобы была разрешима система линейных уравнений и неравенств относительно вектора u R m и скаляров lj, j J L J LH и h j, j J H J LH :

Действительно, для допустимого решения y, u, l j, j J L J LH, h j, j J H J LH задачи (33)–(39) векторы y, u + u и скаляры l j + lj, j J L J LH, h j + h j, j J H J LH будут также составлять допустимое решение при всяком вещественном 0. При возрастании целевая функция (33) будет неограниченно убывать, в соответствии с (50).

Согласно теории альтернативных систем линейных неравенств, система (44)–(50) имеет решение тогда и только тогда, когда не имеет решение система (13)–(16). Это подтверждает тот факт, что исходная и двойственная задачи либо обе не имеют решения, либо обе имеют решения.

Таким образом, двойственная задача имеет решение тогда и только тогда, когда не имеет решение система (44)–(50) и имеет решение система (13)–(16) вместе с исходной задачей (12)–(16).

Замечание 2. (Условия единственности решения двойственной задачи.) Согласно теореме 1 если исходная задача имеет решение, то оно единственно. При этом решение двойственной задачи по переменным, составляющим вектор y, также единственно, поскольку согласно теореме оптимальный вектор y связан с вектором x условиями (17).

По переменным, составляющим вектор u, и скалярам l j, j J L J LH, h j, j J H J LH решение двойственной задача может быть неединственным. Так, если имеет нетривиальные решения система, содержащая условия (44)–(49) и равенство

L LH H LH

то для некоторого оптимального решения y, u, l j, j J L J LH, h j, j J H J LH задачи (33)–(39) векторы y, u + u и скаляры l j + lj, j J L J LH, h j + h j, j J H J LH будут также составлять оптимальное решение при всяком вещественном 0, поскольку согласно (51) при возрастании целевая функция (33) не будет изменяться.

Таким образом, двойственная задача имеет единственное решение по переменным составляющим вектор u и скалярам l j, j J L J LH, h j, j J H J LH, если не имеет нетривиальных решений система, содержащая условия (44)–(49) и неравенство

L LH H LH

Самосопряженная задача оптимизации Рассмотрим задачу минимизации дифференцируемой выпуклой функции, переменными которой являются векторы x R n, y R n, u R m и при линейных ограничениях (13)–(16), (34)–(39).

Задачу (53), (13)–(16), (34)–(39) будем называть самосопряженной задачей оптимизации. Целевая функция (53) является суммой целевых функций (12) и (33). Ограничения представляют собой объединение ограничений исходной и двойственной задач оптимизации.

j J H J LH составляют решение самосопряженной задачи оптимизации тогда и только тогда, когда вектор x является решением исходной задачи оптимизации, а векторы y, u и скаляры l j, j J L J LH и h j, j J H J LH составляют решение двойственной задачи оптимизации. Двойственная задача к самосопряженной задаче оптимизации совпадает с ней же.

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

Замечание 4. Оптимальное значение целевой функции самосопряженной задачи равно нулю.

Действительно, при справедливости (13), (34)–(37) выполняется:

Согласно свойствам преобразования Лежандра-Фенхеля при выполнении y j = f j ( x j ), j J справедливо равенство:

где F j ( x j ) Z и j ( y j ) Z – пара сопряженных функций при j J.

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

Условия дополняющей нежёсткости (27), (29) справедливы в точке оптимума самосопряженной задачи. Следовательно, целевая функция (56) равна нулю в этой точке.

Замечание 5. Самосопряженная задача равносильна задаче минимизации дифференцируемой выпуклой функции при линейных ограничениях (13)–(16), (34)–(39).

Действительно, равенство (54) можно переписать в виде:

Равенство (58) справедливо при всех допустимых решениях задачи (57), (13)–(16), (34)–(39), поэтому целевая функция этой задачи совпадает с целевой функцией самосопряженной задачи на множестве допустимых решений. Ограничения этих задач также совпадают.

Эквивалентные формы представления условий оптимальности Система уравнений и неравенств (13)–(18), (24)–(30) (или (13)–(17), (27), (29), (34)–(39)), а также система (13)–(23), (или (13)–(17), (34)–(39), содержат условия оптимальности для исходной и двойственной задач оптимизации, а также для самосопряженной и симметричной задач.

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

1. Согласно условию (31) уравнения (17) можно заменить следующими:

2. Из свойств преобразования Лежандра-Фенхеля следует, что условия (17) можно заменить набором условий:

причем, поскольку для функций F j ( x j ) Z, j ( y j ) Z, j J, связанных преобразованием Лежандра-Фенхеля, справедливы неравенства (2), набор ограничений в (60) можно представить в виде одного ограничения 3. В системе (13)–(17), (27), (29), (34)–(39), условия (17) равносильны следующему ограничению:

4. В системе (13)–(17), (27), (29), (34)–(39), условия дополняющей нежесткости (27), (29) равносильны следующему ограничению:

Действительно, при (13), (34)–(37) условие (63) равносильно условию которое при справедливости условий (14)–(16), (28), (30) равносильно набору условий (27), (29).

5. Используя специфику системы (13)–(23), её можно свести к проблеме решения системы уравнений с меньшим количеством переменных.

Так, выразив из (17)–(21) вектор x через вектор u, придем к системе из m нелинейных уравнений относительно вектора переменных u R m :

где y (u) – n -компонентная вектор-функция:

(y (u)) – n -компонентная вектор-функция:

причем для компоненты вектор-функции y (u) заданы условием:

Вычислив вектор u в результате решения системы (65), затем прямым используя равенство y = y (u), а также (59) и (22), (23).

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

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

§2.2. Обсуждение свойств двойственных задач оптимизации Класс целевых функций двойственных задач оптимизации, который исследовался в предыдущем параграфе, выбран не случайно. Строгая выпуклость и дифференцируемость целевой функции исходной задачи и ограниченность множеств Лебега X = {x R n : P(x) } при любом вещественном гарантирует, что:

1) исходная задача оптимизации имеет единственное решение, 2) двойственная задача оптимизации имеет единственное решение по переменным, составляющим вектор y.

Класс рассмотренных в §2.1 задач оптимизации прост в описании, при этом удобен для моделирования различных систем потокораспределения и изучения их свойств.

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

В главе 4 исследуются свойства модели оценки возможностей ЕСГ или ЕСН по удовлетворению потребителей в чрезвычайных ситуациях. Эта модель описывается задачей оптимизации, в которой целевая функция выпукла и дифференцируема, но не является строго выпуклой. Это означает, что решение исходной задачи в общем случае неединственно.

Для модели оценки возможностей ЕСГ или ЕСН из главы 4 имеют большое значение двойственные оценки к ограничениям исходной задачи.

Они могут быть найдены, в частности, на базе условий оптимальности Куна-Таккера для исходной задачи.

Глава 3. Реализация и исследование вариантов алгоритмов внутренних точек Особенностью алгоритмов внутренних точек [17, 18, 19, 20, 44, 45, 47, 48, 58, 174] является то, что приближения к оптимальному решению задачи, итеративно генерируемые этим алгоритмом, лежат внутри области, задаваемой ограничениями-неравенствами. Этого эффекта добиваются различными способами. Например, используют идею барьеров или идею штрафов.

В этой главе приводится описание и результаты исследований нескольких вариантов реализации прямого и двойственного алгоритмов внутренних точек для решения задач оптимизации с выпуклой целевой функцией и линейными ограничениями: равенствами и неравенствами. Исследуемые алгоритмы имеют в своей основе алгоритм внутренних точек [18], предложенный И.И. Дикиным [17] с изменениями вычислительного процесса, введенными В.И. Зоркальцевым [43].

Прямой алгоритм решает исходную задачу оптимизации вида (12)–(16), а двойственный алгоритм – двойственную задачу оптимизации вида (33)– (39). Оба алгоритма на каждой итерации решают вспомогательную задачу оптимизации для поиска направления корректировки текущего приближения. В её целевой функции используется квадратичная аппроксимация целевой функции решаемой задачи и квадратичные функции штрафа, заменяющие ограничения-неравенства, с меняющимися по итерациям весовыми коэффициентами. Весовые коэффициенты должны сходиться к нулю при приближении к равенству данного ограничения-неравенства. Вспомогательная задача поиска направления корректировки сводится в исследуемых алгоритмах к проблеме решения системы линейных уравнений. Для решения последней используется метод квадратного корня (называемый также методом Холецкого). Этот метод учитывает симметричность и положительную определенность матрицы системы линейных уравнений.

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

В этой главе сравниваются в экспериментальных расчетах два способа задания весовых коэффициентов: квадратичные весовые коэффициенты и линейные, деленные на множители Лагранжа, которые вычисляются на предыдущей итерации. Подобные способы задания весовых коэффициентов введены в [17, 44, 45] и исследовались на задачах линейного программирования [9, 44, 45, 47, 121]. Целью исследований данной главы является выявление наиболее эффективных способов задания весовых коэффициентов в алгоритмах для задач выпуклой оптимизации c линейными ограничениями, в том числе двусторонними неравенствами на переменные.

§3.1. Прямые алгоритмы внутренних точек Описываемый далее алгоритм предназначен для решения исходной задачи оптимизации (12)–(16). Считаем, что матрица A имеет ранг m (то есть A – матрица полного ранга). Для реализации алгоритма необходимо, чтобы целевая функция в (12) была дважды дифференцируемой. Обозначим f j( x j ) – вторую производную функции F j ( x j ), j J.

Задан вектор начального приближения x 0 R n, удовлетворяющий ограничениям-неравенствам (14)–(16) в строгой форме.

Алгоритм итеративно будет повторять перечисленный в пунктах 1 – набор действий. При этом алгоритм будет находиться на одном из двух этапов: на этапе ввода в область допустимых решений или на этапе оптимизации в области допустимых решений.

Пункт 1. Вычисление вектора невязки ограничений (13) для текущего k -го приближения x k R n :

Вычислим величину: A = max{ ri k : i I }. Задана величина > 0 – паk раметр алгоритма, характеризующий максимальную допустимую невязку ограничений-равенств (13). Если для компонент вектора r k выполняется неравенство:

Для компонент вектора x без ограничений-неравенств в задаче (12)– (16) найдем величину = max jk : j J.

Если справедливо условие max{ L, H,, A }<, где – параметр максимально допустимой погрешности вычислений, то условия оптимальности решаемой задачи оптимизации выполнены с требуемой точностью.

В этом случае завершаем работу алгоритма, иначе переходим к пункту 4.

Пункт 4. Определение шага корректировки решения до ближайшей границы допустимой области, задаваемой ограничениями-неравенствами. Шаг до ближайшей границы определяется по формуле LH = min(L, H ), где Пункт 5. Выбор итоговой величины шага корректировки решения.

Возможны два случая:

1) Алгоритм находится на этапе ввода в область допустимых решений.

Вычислим шаг корректировки:

Здесь – параметр метода, который используется, чтобы после корректировки приближение к решению оставалось внутри допустимой области, задаваемой ограничениями-неравенствами.

2) Алгоритм на этапе оптимизации в области допустимых решений.

Найдем величину P, решив задачу одномерной минимизации целевой функции (12) из точки x k по направлению x :

Вычислим шаг корректировки:

Пункт 6. Вычисление следующего приближения. Осуществим итеративный переход, используя направление корректировки x и шаг :

Переходим к следующей итерации, начиная с пункта 1.

§3.2. Двойственные алгоритмы внутренних точек В [44, 48] введены и подробно рассмотрены двойственные варианты алгоритмов внутренних точек для задач линейного программирования.

Вначале эмпирически была замечена, а затем теоретически доказана [58] (на задачах линейного программирования) интересная особенность: при использовании прямого алгоритма двойственные переменные быстрее сходятся к оптимальным значениям, чем исходные переменные. Отсюда вытекает гипотеза, что лучше воспользоваться двойственным алгоритмом внутренних точек, решающим двойственную задачу оптимизации, если требуется быстрее получить решение исходной задачи оптимизации с заданной точностью. В диссертации верность этой рекомендации проверяется на классе задач оптимизации с выпуклой целевой функцией.

Описываемый далее алгоритм предназначен для решения двойственной задачи оптимизации (33)–(39). Для реализации алгоритма необходимо, чтобы целевая функция в (33) была дважды дифференцируемой. Обозначим j ( y j ) – вторую производную функции j ( y j ), j J.

Зададим начальное приближение искомых векторов y 0 R n, u 0 R m ры начального приближения удовлетворяли равенствам (34)–(37) и неравенствам (38), (39) в строгой форме. Из вида системы (34)–(39) заключаем, что нет необходимости итерационными методами решать эту систему поскольку, задав значения компонент вектора u 0 и скаляров l 0, h 0 для соотj j ветствующих j найдем компоненты вектора y 0 из (34)–(39) прямым счетом. Таким образом, алгоритм будет работать на одном этапе – этапе оптимизации в области допустимых решений.

Пункт 1. Поиск направления корректировки текущего приближения.

Найдем векторы y, u и скаляры l j, j J L J LH h j, j J H J LH, являющиеся оптимальным решением задачи:

H LH L LH H LH

Здесь 1 – параметр, представленный некоторым малым числом.

Для вычисления знаменателей q k и p k функций штрафа в целевой функции (83) при экспериментальных расчетах использовались два способа.

1) Квадратичные весовые коэффициенты:

2) Линейные весовые коэффициенты, деленные на множители Лагранжа:

Здесь величины jk 1, k 1 являются приближениями к множителям Лагранj это компонента вектора множителей Лагранжа x k 1 ограничений-равенств (34)–(37). Вектор x k 1 вычисляется на предыдущей (т.е. на k 1 ) итерации алгоритма (для первой итерации алгоритма зададим 0 = 1, 0 = 1 ).

Найдем решение задачи (83), (84), используя правило множителей Лагранжа. Запишем систему уравнений, содержащую условия оптимальности для задачи (83), (84). В неё войдут условия (84)–(87), а также:

Выразим компоненты вектора y и скаляры l j, j J L J LH и h j, j J H J LH из уравнений (92)–(94), подставим полученные выражения в систему (84)–(87), выразим из получившихся уравнений вектор двойственных оценок x и подставим в уравнение (95). Получим систему линейных уравнений относительно вектора u :

Здесь k – диагональная n n матрица, на главной диагонали которой записаны величины вида (( j ( y k )+ 1 ) 1 + q k + p k ), j J ; k – диагональная на главной диагонали. Здесь для q k, p k справедливы соотношения:

Матрица AH k A T – симметричная, положительно определенная (напомним, что матрица A имеет полный ранг). Используем для решения системы (96) метод Холецкого.

Решив систему (96), получим вектор u. Затем вычислим вектор двойственных переменных x, по правилу:

А компоненты вектора y и скаляры l j, j J L J LH h j, j J H J LH вычислим по правилам:

Пункт 2. Проверка выполнения критерия остановки алгоритма.

Проверим выполнение для задачи (33)–(39) условий оптимальности Куна-Таккера. Рассчитаем следующую величину:

Вычислим:

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

Пункт 3. Определение шага корректировки до ближайшей границы допустимой области, задаваемой ограничениями-неравенствами. Шаг до ближайшей границы определяется по формуле LH = min(L, H ), где:

Пункт 4. Выбор итоговой величины шага корректировки. Найдем величину P, решив задачу одномерной минимизации целевой функции (33) по направлению, задаваемому векторами y, u и скалярами l j, h j :

Вычислим коэффициент шага корректировки решения по правилу:

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

Переходим к следующей итерации, начиная с пункта 1.

§3.3. Численные эксперименты на задачах потокораспределения Было выполнено несколько программных реализаций алгоритмов внутренних точек на языке С++. В том числе, двух вариантов прямого алгоритма, описываемого в §3.1, и двух вариантов двойственного алгоритма, описываемого в §3.2 (с квадратичными и линейными весовыми коэффициентами). Реализованные алгоритмы адапрированы для расчета модели гидравлической системы с автоматическими регуляторами расхода, а также для расчета нелинейной модели оценки возможностей отраслевых систем ТЭК в чрезвычайных ситуациях. Далее приводятся результаты численных экспериментов, проведенных с полученными реализациями алгоритмов.

Исследование зависимости скорости счета от размера входных данных для одного вида весовых коэффициентов. С помощью прямого алгоритма внутренних точек для нелинейной модели оценки возможностей ЕСГ или ЕСН в чрезвычайных ситуациях (описание модели – в главе 4) было проведено несколько серий расчетов. В каждой серии были рассчитаны задачи различного размера. В алгоритме использовались видоизмененные квадратичные весовые коэффициенты, вычисляемыми по правилам:

где k = 1, если k p ; k = k p + 1, если k > p. Здесь k – номер итерации, p – число итераций на этапе ввода в область допустимых решений.

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

Исходные данные задач формировались случайным образом с использованием разработанной автором программной среды EasyLink. Эта среда позволяет, кроме случайного формирования векторов исходных данных, сформировать матрицу инциденций графа сети при помощи визуальных инструментов. Расчеты производились на ПК с процессором Intel PentiumГгц. Результаты численных экспериментов приведены в таблице 1. Допустимая погрешность условий оптимальности равна 0.01.

Таблица 1. Результаты вычислений для рассчитанных серий задач Число уз- Число дуг, Кол-во решен- Среднее по се- Среднее затраn В серии задач, помеченных в таблице 1 звездочкой, входят два реальных примера для нелинейной модели оценки возможностей ЕСГ по снабжению потребителей в чрезвычайных ситуациях. По результатам расчетов можно построить два графика, которые представлены на рисунке 1. На рисунке символом y обозначены формулы трендов; R 2 – корреляция между точками тренда и расчетными данными.

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

Среднее по серии число итераций Рисунок 1. Зависимость числа итераций и времени счета алгоритмом внутренних точек от числа переменных задачи Зависимость числа итераций от числа переменных можно представить в виде функции n, где n – число переменных задачи, – константа.

Увеличение времени счета с ростом числа переменных можно аппроксимировать функцией n1 / 2 m 3, где – константа, m – число ограниченийравенств задачи.

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

Для дуг с ограничениями-неравенствами использовались два вида весовых коэффициентов: квадратичные коэффициенты, вычисляемые по правилу (70)– (72) и линейные коэффициенты, деленные множители Лагранжа, которые вычисляются по правилу (73)–(75). Кроме того, для дуг без ограниченийнеравенств на этапе ввода в область допустимых решений использовались чине k, вычисляемой по правилу (76). В таблице 2 приведены характеристики задач.

Таблица 2. Номер задачи потокораспределения и его характеристики В таблице 3 приводятся результаты тестирования прямого алгоритма с квадратичными коэффициентами функций штрафа вида (70)–(72). Номера задач соответствуют номерам в таблице 2. Допустимая погрешность равна 0.01. Сравниваются два варианта задания коэффициентов d k при j J в целевой функции вспомогательной задачи на этапе ввода в область допустимых решений. Расчеты производились на ПК с процессором Intel Core-i5 3,2 Ггц.

Таблица 3. Результаты расчетов задач прямым алгоритмом с квадратичными коэффициентами функций штрафа Сравнивая число итераций, выполненных алгоритмом на этапе ввода в область допустимых решений, приходим к выводу, что коэффициенты d k, при j J, равные величине k, вычисляемой по правилу (76), использовать предпочтительней, чем равные единице.

Далее в таблице 4 приводятся результаты тестирования прямого алгоритма с линейными коэффициентами функций штрафа, деленными на множители Лагранжа. Эти коэффициентами вычислялись по правилу (73)–(75).

Номера задач соответствуют номерам в таблице 2. Допустимая погрешность равна 0.01. Также как и в предыдущей таблице сравниваются два варианта задания коэффициентов d k, j J.

Таблица 4. Результаты расчетов задач прямым алгоритмом с линейными коэффициентами функций штрафа Из таблицы 4 видно, что коэффициенты d k при j J, вычисляемые по правилу (76), использовать в этом случае, также как и в предыдущем, предпочтительней.

Сравнивая результаты расчетов в таблицах 3 и 4 приходим к выводу, что количество итераций, выполненных алгоритмом, с квадратичными коэффициентами функций штрафам вида (70)–(72) значительно превосходит на абсолютном большинстве примеров задач число итераций, выполненных алгоритмом, с линейными коэффициентами функций штрафа, деленных на множители Лагранжа (вида (73)–(75)).

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

Для рассмотренных вариантов реализации алгоритма время, затрачиваемое алгоритмом на одну итерацию, находится в зависимости от числа ограничений-равенств в задаче (12)–(16). Это связано с тем, что на каждой итерации решается система линейных уравнений относительно вектора двойственных переменных u R m. Отметим, что в двойственном алгоритме на каждой итерации решается система линейных уравнений относительно вектора u R m, поэтому указанное свойство для него также выполняется.

Сравнение по числу итераций прямого и двойственного алгоритмов с разными весовыми коэффициентами В таблице 5 приведены результаты численных расчетов с использованием четырех вариантов алгоритмов внутренних точек: прямых и двойственных с двумя видами весовых коэффициентов. Использовались квадратичные весовые коэффициенты: (70)–(72) и (88), (89), а также линейные, деленные на множители Лагранжа (73)–(75) и (90), (91). Критерием остановки алгоритмов было выполнение условий оптимальности (13)–(23) с максимальной невязкой 0,1.

Таблица 5. Результаты расчетов задач потокораспределения с использованием четырех вариантов алгоритмов внутренних точек Характеристики задач Расчеты показывают, что прямой и двойственный алгоритмы с линейными весовыми коэффициентами в среднем в два раза быстрее (по числу итераций) своих аналогов с квадратичными коэффициентами. Двойственные алгоритмы в среднем в полтора раза быстрее своих прямых аналогов.

Число итераций для двойственного алгоритма меньше, чем во всех остальных алгоритмах для примерно 90% решенных примеров.

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

Критерием остановки алгоритмов было выполнение условий оптимальности (13)–(23) с максимальной невязкой 0,01.

В таблице 6 приводятся результаты для прямого алгоритма. Норма отклонения приближенного решения от точного по переменным исходной задачи вычислялась по формуле: max | x k x* |, где x* – j-ая компонента вектора-решения задачи (12)–(16), вычисленного заранее; x k – j-ая компоj нента вектора-приближения к решению на последней итерации. Норма отклонения по переменным двойственной задачи вычислялась по формуле:

max{| uik ui* |}, где ui* – i-ая компонента вектора множителей Лагранжа i =1,...,m ограничений (13), вычисленного заранее; uik – i-ая компонента вектора приближения к вектору множителей Лагранжа на последней итерации.

Значения векторов x * и u * вычислялись заранее тем же алгоритмом, при этом критерий останова для них устанавливался строже.

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

Норма отклонения приближенного решения от точного по переменным двойственной задачи вычислялась по формуле:

где ui*, yt*, lt*, ht*, – компоненты векторов, составляющих решение задачи (33)–(39), вычисленные заранее; uik, ytk, ltk, htk – компоненты векторовприближений на k -ой итерации. Норма отклонения приближенного решения от точного по переменным исходной задачи вычислялась по формуле:

max | x k x* |, где x* – j-ая компонента вектора множителей Лагранжа огj j j j =1,...,n раничений (34)–(37), вычисленного заранее; x k – j-ая компонента вектораj приближения к вектору множителей Лагранжа.

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

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

Численные эксперименты с реализацией алгоритма внутренних точек, учитывающей свойства разреженности матрицы системы линейных уравнений при разложении Холецкого Вычислительная схема метода внутренних точек включает решение на каждой итерации системы линейных алгебраических уравнений (СЛУ) с симметричной положительно определенной матрицей коэффициентов. Для таких матриц можно применять метод Холецкого, скорость сходимости которого выше, чем у метода Гаусса. Однако стандартная схема реализации метода Холецкого не учитывает, что время счета можно значительно сократить для матриц с большим количеством нулей (т.е. для разреженных матриц). К таким матрицам относится матрица коэффициентов СЛУ, получаемая из матрицы инциденций для задач потокораспределения.