«СИСТЕМНЫЕ ИССЛЕДОВАНИЯ В ЭНЕРГЕТИКЕ Ретроспектива научных направлений СЭИ–ИСЭМ Ответственный редактор член-корреспондент РАН Н.И. Воропай НОВОСИБИРСК НАУКА 2010 УДК 621.311.1 ББК 31.2 С 34 Системные исследования в ...»

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

В некоторых случаях условия (1.43), (1.47) достаточны для того, чтобы данное значение x было оптимальным решением задачи (1.42), (1.43). В частности, это имеет место для задач с выпуклой целевой функцией f0 и линейными функциямиограничениями.

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

Центральная идея Чурквеидзе состояла в использовании квадратичных аппроксимаций вида ( i fi ( x )) в качестве добавок к минимизируемым функциям. В данном случае величина i выполняет роль «маяка», к которому должно стремиться значение функции fi.

В частности, для задачи (1.42), (1.43) получаем следующую вспомогательную функцию:

Несложно видеть, что данная функция содержит в качестве составной части функцию Лагранжа (1.44). Действительно, Появление дополнительных квадратичных составляющих весьма существенно.

Они объясняют и использование термина «модифицированная функция Лагранжа».

На рассматриваемом примере хорошо можно пояснить суть метода вспомогательных функций (модифицированной функции Лагранжа). Пусть на итерации k имеется значение k вектора множителей. Решая задачу безусловной оптимизации, находим вектор чения, x. Вместо регуляризирующей составляющей ( x j x j ) вводятся другие квадратичные добавки, как это делал Ш.С. Чурквеидзе, для противодействия «нехорошим свойствам» целевой функции.

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

ректировка вектора. Значение ik должно быть увеличено, если fi < 0 (что будет стимулировать к увеличению f ( x ) на следующей итерации) или уменьшено, если > 0. В частности, можно положить Смысл корректировок состоит в том, чтобы достичь допустимого решения вспомогательной задачи, при котором f ( x ) = 0. Пусть при некотором Rn. Причем f ( x ) = 0, т.е. нет необходимости в корректировке.

Тогда, как несложно убедиться, вектор будет состоять из множителей Лагранжа решения x задачи (1.42), (1.43), удовлетворяющего необходимым условиям оптимальности.

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

Приведем один из возможных вариантов метода вспомогательной функции (модифицированной функции Лагранжа) с переменными весами. При этом одновременно проиллюстрируем устройство метода Чурквеидзе для задач с ограничениями в форме неравенств. Рассмотрим модификацию задачи (1.42), (1.49), когда вместо ограниченийравенств (1.49) вводятся ограничения-неравенства На k -ой итерации решения такой задачи предлагается использовать следующую вспомогательную функцию где i – некоторые положительные веса. Здесь символом ()+ обозначена операция срезки: для вещественного Введение срезки как раз обусловлено ограничениями в виде неравенств. Поскольку в приведенной вспомогательной функции срезка в квадрате, она не вызывает особых вычислительных проблем: функция ( ) 2 является дифференцируемой и выпуклой.

при заданном После этого пересчитываем веса, например по правилу Согласно этому правилу, если ограничение с номером i не выполняется в точке при большем нарушении ограничения. Если же i -е ограничение выполняется меньше будет значение коэффициентов i. С ростом значения fi ( x ограничения уменьшается во вспомогательной задаче через увеличение коэффициентов i. Уменьшение значения fi ( x вспомогательной задаче через сокращение весового коэффициента i.

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

При одинаковых, неизменных по итерациям значениях весов i получим исходный метод вспомогательной функции Чурквеидзе, для которого доказана при некотоk рых условиях сходимость векторов x к оптимальному решению рассматриваемой заk дачи, векторов – к множителям Лагранжа ограничений задачи.

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

В.П. Булатов. Методы отсечений и погружений. Основные научные результаты В.П. Булатова сосредоточены в разработке и теоретическом исследовании класса методов, которые он назвал методами отсечения и погружения. Воспользуемся следующей классификацией разрабатывавшихся им алгоритмов [100–104], которуюон ввел в докторской диссертации. Все алгоритм назовем методами отсечения. Они состоят из двух классов: «методов погружения» и «методов центрированных отсечений».

Методы погружений В.П. Булатов разделял на два типа. Первый из них – метод последовательного погружения надграфика целевой функции. Рассматривается задача где x – вектор переменных из R ; – целевая функция; K – множество допустимых решений. В.П. Булатов обычно рассматривал случай, когда K – компакт, т.е. замкнутое и ограниченное множество в R. Хотя некоторые его алгоритмы могут работать и в случае, если K – неограниченное множество, но это, действительно, малосущественное обобщение.

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

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

Исходная идея метода последовательного погружения состоит в замене задачи (1.60) на эквивалентную ей задачу минимизации линейной функции с увеличенным на единицу количеством переменных. Введем функцию где – дополнительная переменная. Тогда задача (22) становится равносильной задаче при условиях где Суть метода состоит в том, что в процессе решения используется некоторая аппроксимация множества K n+1.

при условиях Пусть x, – решение задачи. Если это не оптимальное решение (1.62), (1.63), то переходим путем отсечения точки ( x, ) от K n+1 к другому множеству K n+1.

Отсечение должно быть таким, чтобы при этом не отбросить оптимальное решение задачи (1.62), (1.63).

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

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

Второе, более обще направление в методах «погружения» названо последовательным погружением допустимого множества. Это обобщение рассчитано и на случай, когда в ограничениях задачи присутствуют «плохие» ограничения. На самом деле этот случай можно свести к предыдущему. Пусть у задачи (1.60) имеются дополнительные ограничения где gi – некоторые «нехорошие» функции, например невыпуклые или недифференцируемые. Введем функцию Затем рассмотрим задачу (24)–(25), у которой множество K n+1 определено условием В итоге приходим к рассмотренному первому случаю.

Метод центрированных отсечений. В 1979 г. в «Докладах Академии наук (ДАН) СССР» вышла статья математика Хачияна Л.Т. из ВЦ АН «Полиномиальные алгоритмы в линейном программировании». В ней рассматривалась модификация предложенного ранее известными математиками А.С. Немировским, Д.Б. Юдиным и Н.З. Шором метода эллипсоидов. Суть метода заключалась в том, что допустимая область, содержащая оптимальное решение, погружалась в некий n -мерный эллипсоид.

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

Изначально метод эллипсоидов был разработан им для задач выпуклого программирования, частными случаями которого, как известно, являются задачи линейного программирования. В статье Л.Т. Хачияна в ДАН и затем более подробно в "Журнале вычислительной математики и математической физики" приводился один важный для алгоритмов оптимизации результат – алгоритм эллипсоидов позволяет решать задачи линейного программирования за полиномиальное время. Было доказано, что данный алгоритм позволяет найти требуемое решение не более чем за M (n)4,5 элементарных вычислительных операций (сложение, вычитание, умножение, деление), где M – некоторая большая положительная константа, n – размерность решаемой задачи (максимальное из значений числа переменных и числа ограничений задачи). Далее считаем, что n – число переменных.

Когда Дж. Данциг разработал алгоритм симплекс-метода для решения задач линейного программирования, он какое-то время, как писал сам, боялся его публиковать.

Его одолевали сомнения, что при решении реальных, а не тестовых задач, алгоритм симплекс-метода будет неэффективным из-за того, что объем вычислений при его использовании будет расти экспоненциально от размерности задачи, т.е. будет выражаться зависимостью вида M 2kn при некоторых M > 0, k > 0. Причем Дж. Данцигу были уже известны примеры задач, для которых объем вычислений изменялся именно по этому закону. Насколько «страшна» экспоненциальная (степенная) зависимость, мы можем понять, если вспомним известную притчу об изобретателе шахмат, который предложил очень простое условие оплаты за это изобретение – начиная с одного зерна удваивать количество зерен в уплату ему за каждую следующую из 63 клеток шахматной доски. В итоге получалось так, что во всей Индии не набрать столь много зерен (пшеницы и риса).

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

Вместе с тем результат Л. Т. Хачияна очень важен в теоретическом плане, в том числе как конструктивное доказательство того, что задачи линейного программирования можно решать гарантированно за полиномиальное время. Хотя пользоваться методом эллипсоидов для решения «реальных» задач линейного программирования, как считал сам Хачиян, не следовало бы – алгоритмы симплекс-метода на «реальных» задачах существенно эффективнее.

В.П. Булатов в самом начале истории о возможности решения задач линейного программирования за полиномиальное время расспросил Л.Т. Хачияна, как тот получил такой результат, и пригласил его на ближайшую Байкальскую школу. Тут же В.П. Булатову пришла в голову простая мысль – аппроксимировать множество решений не только эллипсоидами. В результате его обсуждения с еще двумя ведущими математиками СЭИ (И.А. Александровым и Е.Г. Анциферовым) родился метод «центрированных отсечений», основанный на аппроксимации области, содержащей точку оптимума, n -мерным симплексом. Симплексом называется телесный линейный многогранник в n -мерном пространстве, содержащий ровно n + 1 вершину. Симплексом или «простейшим» он назван потому, что в n -мерном пространстве не может быть выпуклого телесного линейного многогранника с меньшим количеством вершин.

Разделение на каждой итерации многогранника на две части (содержащую и не содержащую точу оптимума) осуществлялось гиперплоскостью, проходящей через «центр тяжести» многогранника. Отсюда и название алгоритма – метод центрированных отсечений.

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

1.7. Актуальные направления теории и методов исследования Вводные замечания. В данном разделе представлены некоторые актуальные направления исследования операций, развиваемые в настоящее время применительно к традиционным и новым проблемам в системных энергетических исследованиях. В последние годы нередко высказывается на разных уровнях скептические замечания о целесообразности продолжения исследований в ИСЭМ по прикладной математике. Такую точку зрения иногда обосновывают произошедшими расширениями возможностей современной вычислительной техники и располагаемым в ней математическим обеспечением.

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

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

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

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

Теоремы об альтернативных системах линейных неравенств. Приложения в моделях расчета режимов и анализа надежности ЭЭС. Широко распространено предубеждение, что теория и методы решения систем линейных неравенств, линейной оптимизации являются полностью завершенными разделами математики. Такое утверждение можно, например, встретить в обзорной по теории и методам оптимизации книге известного специалиста в этой области Б.Т. Поляка [105]. Действительно, изучение систем линейных неравенств имеет уже почти полуторавековую историю, начиная с работ конца XIX в. П. Гордана, Г. Минковского, Дж. Фаркаша [106]. В середине XX в.

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

Вместе с тем неверно полагать, что теория линейных неравенств (линейное программирование можно рассматривать как составную часть теории линейных неравенств) – окончательно завершенный раздел современной математики. Также нельзя считать «окончательно» завершенной теорию линейных уравнений, которую можно рассматривать как составную часть теории линейных неравенств (любое линейное уравнение представимо в виде линейных неравенств, обратное неверно).

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

На русском языке имеется только одна монография С.Н. Черникова [106], непосредственно посвященная теории линейных неравенств. К ней можно добавить относительно недавно вышедшую книгу Н.И. Еремина [109], ученика С.Н. Черникова. Большое количество учебной литературы по линейному программированию не компенсирует необходимость в монографиях и учебниках по линейным неравенствам.

Давно назрела необходимость введения теории систем линейных неравенств в вузовские курсы линейной алгебры (в развитие изучаемой теории систем линейных уравнений). Эта идея активно пропагандируется через кафедру «Математической экономики» в рамках учебно-научного комплекса ИСЭМ – ИГУ. В этой связи было подготовлено учебное пособие «Системы линейных неравенств» [110].

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

Иногда эти теоремы (имеющие десятки существенно разных формулировок) обобщенно называют леммой (или теоремой) Фаркаша по фамилии венгерского математика, опубликовавшего в 1902 г. одну из первых работ в этой области (несколько раньше аналогичные результаты были получены Минковским и еще раньше Горданом [106]).

Частный случай представляет известная теория Фредгольма об альтернативных системах линейных уравнений.

Многие теоремы об альтернативах имеют такой вид: каждой системе линейных неравенств можно поставить в соответствие (по строго определенным правилам, см.

[110]) другую систему линейных неравенств (существенно иного вида, с другим набором переменных). Альтернативность состоит в утверждении, что одна и только одна из этих систем совместна. Если одна совместна (имеет решение), то другая заведомо несовместна. Если одна несовместна (не имеет решения), то другая заведомо совместна.

Теоремы об альтернативных системах линейных неравенств имеют приложение во многих областях математики. Они содержат (даже в значительно большем объеме, чем обычно приводятся в учебниках, см. [110]) теорию двойственности линейного программирования (которая является основой всей теории оптимизации). Большую пользу из них можно извлечь для многих областей вычислительной математики. Приведем некоторые из этих областей приложений, используемые при разработке и реализации моделей в ИСЭМ СО РАН.

1. На основе теорем об альтернативных системах линейных неравенств создаются новые эффективные численные методы оптимизации и регуляризации. Это направление приложения теории альтернативных систем линейных неравенств развивается, в частности, в работах А.И. Голикова и Ю.Г. Евтушенко в ВЦ РАН [111, 112], а также в работах ИСЭМ СО РАН [113–115].

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

Такие «лишнее» неравенства принято называть неравенствами-следствиями (этот термин отражает тот факт, что решение, удовлетворяющее всем остальным неравенствам, обязательно удовлетворяет и «неравенству-следствию»).

В некоторых работах теоремы об альтернативных системах неравенств имеют вид утверждений о свойствах неравенств-следствий. В частности, в книгах С.Н. Черникова и Н.И. Еремина [106, 109] используются именно утверждения о свойствах неравенствследствий вместо равносильных им утверждений об альтернативных системах линейных неравенств.

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

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

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

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

Приложения в алгоритмах расчета режимов электроэнергетических систем.

Рассмотрим систему линейных уравнений и неравенств относительно вектора переменных x R n :

Заданными здесь являются матрица A размером m n, векторы b R m, x R n, x R n, причем x < x.

Поскольку каждая компонента вектора переменных x ограничена сверху и снизу соответствующими компонентами векторов x и x, заведомо известно, что множество решений этой системы ограниченное, т.е. может быть пустым вследствие противоречивости (несовместности) условий. В силу ряда полезных свойств такой системы есть резон их выделить в качестве особого объекта исследований. Такая система названа в [110] линейной системой с двусторонними ограничениями-неравенствами.

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

Целесообразность особого выделения линейных систем с двусторонними ограничениями-неравенствами выявилась в результате исследования задачи поиска допустимых режимов электроэнергетических систем. Линеаризованная вспомогательная задача поиска направления улучшения решения в обсуждавшемся в предыдущем разделе методе приведенного градиента приводит к системе вида (1.71). Это, как оказалось в процессе исследований, дает большие преимущества. В частности, очень привлекательный вид у альтернативной системы линейных неравенств. Она имеет следующую формулировку: найти векторы u R m, v R n, w R n, удовлетворяющие условиям где Отметим, что система (1.72), (1.73) равносильна задаче безусловной минимизации функции от вектора u R m где символы () +, () обозначают операции неотрицательной и неположительной срезки для компонент вектора: для y R n Если будет найдено значение вектора u, при котором то тем самым будет найдено решение системы (1.72), (1.73). Если будет установлено, что оптимальное значение функции f существует (оно может быть только неотрицательным), то будет доказана несовместность системы (1.72), (1.73).

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

Алгоритмы F1 и F2 осуществляют монотонное улучшение решения исходной системы линейных неравенств (1.71). Алгоритмы G1 и G2 основаны на «альтернативном подходе» – они монотонно улучшают решения задачи (1.72), (1.73). Алгоритмы F и G1соответсвтуют исходным наиболее известным вариантам метода внутренних точек, предложенным в [76, 116] и получившим название в зарубежной литературе affine scaling method и dual affine scaling method. Алгоритмы F2, G2 являются модификациями исходных вариантов, предложенные в [116, 117] в целях повышения устойчивости вычислительного процесса к погрешностям счета.

Таблица 1.2. Число итераций, необходимое для получения решения или идентификации несовместности прямыми и двойственными алгоритмами внутренних точек Совместные (30x80)–(41х80) 9.5(3–13) 13.4(7–17) 10.2(6–13) 5.9(3–8) Несовместные (30x80)–(41х80) 1.6(1–5) 1.6(1–7) 1(все 1) 1(все 1) На основе представленных в таблице результатов (и аналогичных результатов в сериях других экспериментов [114, 115]) можно сделать три важных вывода. Вопервых, эти примеры демонстрируют высокую вычислительную эффективность введения критерия несовместности на базе теорем об альтернативных неравенствах. Несовместность стала выявляться на первых итерациях. Использовавшийся ранее критерий, основанный на обнаружении факта сходимости к ненулевому значению итеративно уменьшаемого по норме вектора невязок ограничений системы, требовал значительно большего объема вычислений и был менее надежен.

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

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

Оптимальные решения с минимальным набором активных ограничений: использование их свойств в модели оценки дефицита мощности электроэнергетической системы. Пусть – множество оптимальных решений задачи линейного программирования. Переменные величины в ней составляют вектор x R n. Заданными являются векторы b R m, c R n, матрица A размера m n. Рассматривается задача двухкритериальной оптимизации с лексикографическими упорядоченными целевыми функциями: из множества X требуется выбрать вектор, доставляющий минимум некоторой функции (x).

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

Для многих приложений особый интерес представляют решения систем линейных неравенств с минимальными наборами активных ограничений [110]. Напомним, что активными для данного решения системы неравенств называются такие ограничения, которые для него выполняются в форме равенств. Пусть x1 и x 2 два решения некоторой системы линейных неравенств. Тогда в силу выпуклости множества решений таковым будет и вектор ~ = 0,5( x1 + x 2 ). При этом для вектора ~ активными окажутся только те неравенства, которые были активными и для решения x1 и для решения x 2.

Отсюда следует, что у системы линейных неравенств имеются такие решения, при которых активными являются те и только те неравенства, которые активны при любом другом решении системы. Такие особые решения называются решениями с минимальными (далее не уменьшаемыми по составу) наборами активных ограничений. Подмножество таких решений совпадает с областью относительно внутренних точек множества решений системы линейных неравенств. Напомним,что относительной внутренностью некоторого выпуклого множества Q R n называется множество внутренних точек области Q относительно минимального линейного многообразия, содержащего это множество Q. Относительная внутренность Q следуя Рокафеллару [122] обозначается riQ.

Если в результате решения задачи первого этапа рассматриваемой двухкритериальной проблемы найдено не произвольное оптимальное решение, а относительно внутренняя точка множества оптимальных решений вектор x из множества riX, то задача второго этапа существенно упрощается. Нет необходимости вводить ограничение, фиксирующее на оптимальном уровне значение целевой функции задачи первого этапа, и следует просто исключить из рассмотрения переменные, принявшие граничные значения с номерами из множества J = { j : x j = 0}. Задача второго этапа приобретает следующий вид Она имеет на одно ограничение меньше, чем ранее рассмотренная задача, и имеет меньше переменных. Условие x j = 0 для j J означает, что все эти переменные в данной задаче фактически не рассматриваются.

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

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

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

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

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

где « » правило перехода (часто неоднозначное), обычно на основе построения функции Лагранжа задачи L. Двойственные задачи оказываются полезными для многих целей:

• для доказательства оптимальности полученных решений;

• для теоретического обоснования алгоритмов оптимизации;

• для разработки новых алгоритмов оптимизации;

• для интерпретации полученных решений;

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

Все эти аспекты теории двойственности активно используются в исследованиях, проводимых в ИСЭМ СО РАН по разработке и обоснованию методов вычислений, по разработке и изучению свойств моделей энергетики. В данном разделе представим одно из направлений теории двойственности, формируемое в ИСЭМ СО РАН, – теории симметричной двойственности [119, 120].

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

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

• обсуждавшиеся выше теоремы об альтернативных системах линейных неравенств (этого достаточно для вывода всех фактов симметричной двойственности линейного программирования);

• сопряженные функции Лежандра-Фенхеля.

Пусть F (x), ( y ) – дифференцируемые функции от векторов x R n, y R n.

Градиенты этих функций обозначим f ( x) = F ( x), ( y ) = ( y ). Функции F и называются сопряженными по Лежандру [121], если f и – взаимнообратные отображения Функции F и – сопряженные по Фенхелю[121], если Сопряженные функции по Фенхелю являются непосредственным обобщением сопряженных по Лежандру. Если F и – сопряженные функции по Лежандру, то, как несложно увидеть, они будут сопряженными и по Фенхелю. Далее будем использовать только дифференцируемые сопряженные функции, которые будем называть сопряженными функциями Лежандра-Фенхеля.

Приведем пару задач минимизации выпуклой дифференцируемой функции при линейных ограничениях, обладающих свойством симметричной двойственности. Пусть F и – выпуклые сопряженные функции Лежандра–Фенхеля, A матрица m n, c вектор из R n, b вектор из R m. Искомые величины в первой задаче составляют вектор x R n, во второй задаче – векторы y R n, u R m.

1. Исходная задача (S ) :

при ограничениях 2. Двойственная задача ( S * ) :

при ограничениях Отметим, что у задач S и S разный состав переменных. Двойственная к двойственной задаче будет совпадать с исходной S ** = S. Поэтому имеется условность, какую из этих задач называть исходной, какую – двойственной.

Отметим, если x – оптимальное решение задачи S, векторы u, y оптимальные решения задачи S *, то u вектор множителей Лагранжа ограничений-равенств в (1.75), y = f (x ). То есть в качестве решения задачи S можно рассматривать тройку векторов x, u, y.

Для задачи S * вектор x будет соответствовать множителям Лагранжа ограничений (1.77). Значит, в качестве решения задачи S * также следует рассматривать те же три вектора y, u и x (поскольку множители Лагранжа ограничений можно и полезно включать в состав решения задачи оптимизации).

Заметим, если исключить из целевой функции задачи S составляющую F (x) и исключить составляющую ( y ) из целевой функции задачи S *, а также вектор переменных y из ограничений (1.77), задачи S и S * перейдут во взаимно-двойственные задачи линейного программирования. Этот факт подчеркивает, что симметричная двойственность нелинейных задач оптимизации является развитием симметричной двойственности для задач линейного программирования.

Частный случай представляет симметричная двойственность задач квадратичного программирования, широко используемых во многих приложениях. Задачи S и S * становятся взаимно-двойственными задачами квадратичного программирования, если где Q симметричная положительно определенная матрица размера n n.

Далее будем рассматривать случай сепарабельных целевых функций:

где Здесь f j, j взаимно-обратные непрерывные возрастающие функции от вещественного аргумента, изменяющиеся от до + и равные нулю в нуле.

На основе условий оптимальности задач S или S * можно прийти к следующей системе уравнений и неравенств (будем называть ее системой R ):

Переменными здесь являются компоненты векторов x R n, y R n и u R m. Доказаны [119] следующие утверждения • система R, исходная S и двойственная S * задачи оптимизации либо все имеют решении, либо все не имеют решение;

• они не имеют решение в том случае, если противоречивы ограничения (1.78), а это равносильно неограниченности сверху значения целевой функции задачи S * на множестве допустимых решений этой задачи;

• если векторы x, u, y – решения одной из этих задач, то они являются решением и остальных двух задач, причем векторы x, y имеют единственное значение среди всех решений этих задач;

• для любых векторов x, u, y, удовлетворяющих ограничениям (1.75), (1.78), сумма значений целевых функций (1.74), (1.76) взаимно-двойственных задач S и S * неотрицательная • для оптимальных решений x, u, y задач S и S * сумма значений целевых функций (1.74), (1.76) равна нулю Приведенные утверждения означают равносильность задач оптимизации S, S * и задачи поиска решения системы R. Поиск решения всех этих трех задач можно осуществлять на основе решений любой из них, что позволяет использовать наиболее эффективные методы вычислений. Например, если m намного меньше n, то есть резон для поиска решения задачи S или системы R использовать алгоритмы решения задачи S *.

Отметим, что задача S * сводится к проблеме безусловной минимизации выпуклой функции от m переменных:

Найдя решение этой задачи u, можем затем, определить векторы На основе соотношений (1.81), (1.82) можно сформулировать следующую равносильную S и S * задачу оптимизации:

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

Вторая особенность – двойственная к задаче (1.84) совпадает с ней самой. Поэтому задача (1.84) названа самосопряженной (двойственной к самой себе) задачей оптимизации.

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

при ограничениях (1.75), (1.76). Для этой задачи также заведомо известно оптимальное значение целевой функции, что позволяет использовать эффективные критерии останова для алгоритмов ее решения. Интересным свойством этой задачи является также то, что множители Лагранжа ее ограничений равны нулям.

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

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

Пусть c = 0, F ( x) = 0.5 x 2. Тогда исходная задача S является задачей поиска нормального решения системы линейных уравнений и неравенств (1.75). Отметим, что в этом случае j ( y ) = 0.5 y 2 и задача (1.83) имеет очень привлекательный в вычисj лительном отношении вид. Поиск нормального решения системы линейных уравнений и неравенств (1.75) на основе решения задачи (1.83) – один из вариантов развиваемых А.И. Голиковым и Ю.Г. Евтушенко альтернативного подхода: конструирования алгоритмов решения систем линейных неравенств [111, 112].

2. Регуляризация в линейном программировании. Пусть при заданном > 0. Тогда задача (1.85), (1.75) будет регуляризацией по Тихонову задачи линейного программирования Эта регуляризация противодействует неразрешимости из-за неограниченности снизу целевой функции на области допустимых решений или возможной неограниченности решений задачи (1.83). Это же противодействует возможной вырожденности решения двойственной к (13) задачи или противоречивости ограничений двойственной задачи.

Если функция (1.85) соответствует задаче S, то сопряженной к ней соответствующей задаче S * является функция Задача S * будет регуляризацией в целях преодоления возможной несовместности ограничений следующей задачи линейного программирования:

Отметим, что задачи (1.86), (1.88) – взаимно-двойственные задачи линейного программирования. Один вид регуляризации одной из этих задач будет соответствовать автоматически регуляризации второго типа для другой задачи.

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

Приведенная выше взаимосвязь двух видов регуляризации рассматривалась в [123]. Для целей регуляризации кроме (1.85), (1.87) можно использовать и другие сопряженные функции, в частности суммы взвешенных квадратов при выполнении следующих условий на весовые коэффициенты: h j > 0, d j > 0, h j d j = 1 для j = 1,..., n. Выбор весовых коэффициентов позволяет воздействовать на роли отдельных переменных и ограничений в регуляризации.

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

Модель потокораспределения задается в виде направленного графа:

i = 1,..., m номера узлов, j = 1,..., n номера ветвей, A матрица инциденций узлов и ветвей. Вектор b состоит из заданных узловых расходов – объемов, поставляемых в систему или из системы среды (мощности для электрических цепей, объемов товаров для транспортных систем), причем bi = 0. Вектор c состоит из заданных величин приращения давления на ветвях (для электрических цепей – электродвижущие силы;

для транспортных систем величины c j – фиксированные (например, таможенные) тарифы при перевозке на данной дуге).

Переменные составляют вектор x – расход среды (сила тока) по ветвям, y – перепад давления (перепады напряжения) на ветвях, обусловливающие расход среды (силу тока) на этих ветвях, u – вектор давлений (напряжений) в узлах. Для транспортных систем x – вектор объемов потоков товара по ветвям, y – полный перепад цен на данной ветви, вектор u с обратным знаком – цены товара в узлах. Отметим, что если в гидравлических (электрических) цепях поток по дуге осуществляется от большего давления (напряжения) к меньшему, то транспортный поток осуществляется от меньшего уровня цен к большему. Поэтому в экономической системе удобнее для интерпретации использовать вместо вектора u вектор u.

При описании моделей потокораспределения часто ограничения-неравенства на перетоки не вводятся. Тогда задача S приобретает следующий вид (будем называть эту задачу MS ):

Если полученная в результате решения данной задачи компонента x j отрицательная, то это означает, что по соответствующей ветви осуществляется поток в объеме x j в направлении обратном принятому в качестве положительного.

Соответственно в двойственной задаче S * ограничения-неравенства приобретают вид равенства (обозначим эту модификацию двойственной задачи MS * ):

Аналогом системы уравнений и неравенств R будет следующая система уравнений (назовем ее система MR ) Решением этой системы являются три вектора x R n, y R n, u R m, которые также можем рассматривать в качестве решения задач оптимизации MS и MS *. Вектор u состоит из множителей Лагранжа ограничений задачи MS, вектор x – из множителей Лагранжа ограничений задачи MS *.

Для задач оптимизации MS, MS * и системы MR справедливы все утверждения, сформулированные относительно задач S, S * и системы R [124, 125]. Причем все утверждения справедливы при произвольной матрице A и любых векторах b и c. В частности, для разрешимости этих задач необходимо и достаточно существования решения у системы линейных уравнений Ax = b, что равносильно отсутствию решения у системы AT u = 0, bT u = 1. Для гидравлических цепей, когда A – матрица инциденций узлов и ветвей, для совместности системы Ax = b будет достаточно, если рассматриm ваемый граф связанный и выполняется условие bi = 0.

Это позволяет в частности выяснить вопрос о существовании и единственности решения задачи потокораспределения [125]. Если система Ax = b совместна, то решение существует, оно единственное относительно векторов x и y. Относительно вектора u оно будет неединственное, поскольку rankA < n для матрицы инциденций (сумма ее векторов строк дает нулевой вектор). Ранее, опираясь на свойства модели в форме графа, удавалось получать только частные утверждения. Так Б.Н. Пшеничным было доказано существование решения для случая «пассивной» гидравлической цепи, когда c = 0 [126]. А.П. Меренков [31] доказал такое утверждение: если решение модели потокораспределения существует, то оно единственное относительно векторов x и y.

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

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

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

Пусть на рынке одного товара (например, электроэнергии) существуют два производителя (например, две генерирующие компании). Пусть x1 и x2 – объемы товара, выпускаемого первым и вторым производителем соответственно; B1 (x1 ), B2 ( x2 ) – издержки, c – рыночная цена. Прибыль каждого производителя определяется функциями Оптимальный выпуск каждого производителя находится из максимизации прибыли каждого из них:

Делая стандартное предположение о том, что f1 ( x1 ) и f 2 (x2 ) – вогнутые дифференцируемые функции, получим оптимальные решения x1 и x2 задач (1.91) и (1.92) соответственно. Из (1.89), (1.90) и условий оптимальности f1(x1 ) = 0, f 2( x2 ) = 0 следует, что x и x2 удовлетворяют равенствам Полученные решения x10 и x2 можно считать равновесными, поскольку каждый из производителей действует оптимальным для себя образом. В приведенном примере нет ничего необычного, за исключением того, что общая задача в исходной постановке (1.91), (1.92) посредством условий оптимальности сведена к системе (1.93), (1.94). Состояния равновесия определяются условиями (1.91), (1.92), которые представляют собой систему из двух задач оптимизации.

Очевидно, что технически задачи (1.91) и (1.92) могут быть записаны в виде одной:

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

Предположим теперь, что на рынке задан фиксированный спрос P. Тогда задача (1.91), (1.92) переходит в следующую Смысл условий (1.96) – (1.98) состоит в совмещении трех требований: первый производитель максимизирует свою прибыль, второй производитель так же максимизирует свою прибыль и одновременно с этим они производят столько продукции, чтобы удовлетворить заданный спрос. Система (1.96) – (1.98) состоит из двух задач оптимизации и одного линейного уравнения. Эта система может оказаться несовместной, сделать ее совместной можно только за счет подбора параметра c. Из условий (1.93), (1.94) следует, что оптимальные решения x1 и x2 зависят от c, т.е.

Следовательно, сохраняя основной принцип, состоящий в том, что оба производителя действуют оптимальным для себя образом, необходимо подобрать параметр c (цену) таким образом, чтобы выполнялось равенство (1.98). Поскольку, как правило, функции предполагаются возрастающими, существует такое значение параметра c 0, при котором справедливо равенство Представить (1.96) – (1.98) в виде одной задаче оптимизации уже не удается. Если действовать по аналогии с (1.95), то получим задачу Решив ее как обычную задачу оптимизации с ограничением-равенством (применяя метод множителей Лагранжа), получим, в частности, следующие соотношения для оптимальных (в смысле задачи (1.101), (1.102)) значений x1 и x2 :

Из этих соотношений видно, что x1 и x2 не зависят от c, а это противоречит оптимальному поведению производителей, так как на самом деле они всегда ориентируются на рыночную цену c (см. (1.93), (1.94)). Качественное отличие задачи (1.96) – (1.98) от задачи (1.101) – (1.102) состоит в том, что в первом случае выполнение условия (1.98) достигается при оптимальных для каждого участника значениях x10 и x2 соответственно. В этом случае главным является оптимальность для каждого, и если выполнение равенства (1.98) невозможно ни при каких оптимальных значениях x1 и x2, то оно никогда невыполнимо.

Во втором случае равенство (1.98) всегда выполнимо, но может быть нарушен (и, как правило, нарушается) принцип оптимальности для каждого. При этом (опять же, как правило) один из участников не будет удовлетворен сложившейся ситуацией и будет пытаться исправить ее в свою пользу, что означает, что данная ситуация не является равновесной, поскольку есть постоянная тенденция к ее изменению. Наличие равенства (1.98) кардинально меняет положение дел. В силу этого равенства невозможно независимое решение задач (1.96) и (1.97) при фиксированном значении c. Связность переменных в равенстве (1.98) определяет взаимозависимость задач (1.96) и (1.97).

Предметом равновесного программирования являются задачи вида (1.96)–(1.98) в более сложной постановке. Например, вместо первой переменной может рассматриваться вектор x1 = x1,..., x1, вместо второй переменной – вектор x 2 = x12,..., xn, вмеn сто задачи (1.95) – задача аналогично вместо задачи (1.97) – задача а вместо (1.98) – условие где F1 x1, F2 x 2 и g x1, x 2 – некоторые нелинейные функции. Если задачи (1.103) – (1.104) и (1.105) – (1.106) можно свести к эквивалентным равенствам как это было возможно выше, то получаем эквивалентную систему нелинейных уравнений (1.107), (1.108), (1.109).

В более общем виде приведенные рассуждения можно выразить следующим образом. Многие задачи технического и экономико-математического моделирования формально определим как задачи нахождения точки, принадлежащей пересечению некоторых множеств Dk, k = 1,..., s из R n. В большинстве случаев множества Dk определяются следующим образом где f k (x) – некоторые функции, т.е. упомянутая задача есть задача нахождения решения системы уравнений. Для задач равновесного программирования характерно то, что некоторые из множеств Dk определяются как множества оптимальных решений задач оптимизации, зависящих от некоторого экзогенного параметра. В этом случае вместо системы уравнений возникает смешанная система задач оптимизации и уравнений.

Задачи равновесного программирования отличает наличие так называемых экстремальных связей. Экстремальными связями, определяющими экстремальное отображение, называются связи между переменными w и x типа x M (w), где M (w) – множество оптимальных решений некоторой параметрической экстремальной задачи где X – некоторое подмножество пространства R n, w – векторный параметр.

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

Наличие экстремальной связи приводит к следующим затруднениям:

a) в подавляющем большинстве случаев множество M (w) задано неявно и в некоторых случаях не имеет внутренности;

b) во многих случаях множество M (w) не является выпуклым.

Перейдем теперь к формальной постановке задачи равновесного программирования [128, 129].

Пусть – некоторое множество из R n, задана функция (v, w), определенная на декартовом произведении. Зафиксируем v и рассмотрим задачу математического программирования Обозначим W (v) – множество (возможно, пустое) оптимальных решений задачи (1.110)–(1.111):

Решение задачи (1.110) – (1.111) определяет точечно-множественное (или многозначное) отображение v W (v). Поскольку множество W (v) есть множество точек минимума задачи (1.110) – (1.111), такое отображение называют экстремальным.

Задача равновесного программирования формулируется следующим образом:

найти неподвижную точку точечно-множественного отображения v W (v) или установить, что такой точки не существует.

Другими словами, требуется найти вектор v * такой, что или доказать, что в множестве такой точки не существует. Возвращаясь к обозначениям (1.110) – (1.111), задачу равновесного программирования можно переписать следующим образом: найти v* :

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

Другое определение задачи равновесного программирования дано в [132]. Пусть K R n, требуется найти x K :

где функция f ( x, y ) определена на R n R n и обладает свойством Задачи (1.113) и (1.114) эквивалентны, т.е. задачу (1.115) можно представить в виде (1.114) и наоборот. Если ввести функцию то задачу (1.113) можно переопределить следующим образом: найти вектор v * такой, что что совпадает с определением (1.114). C другой стороны, из (1.114) и свойства (1.115) следует, что f ( x, y ) f ( x, x ), т.е.

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

При помощи функции (v, w), введенной в (1.116), и неравенства (1.117) задачу равновесного программирования можно переформулировать следующим образом. Требуется найти оптимальное решение задачи математического программирования где (v) – функция оптимального значения (иногда ее еще называют функцией параметрического оптимума) задачи параметрической оптимизации т.е.

Таким образом, задача равновесного программирования сводится к задаче оптимизации, но в отличие от последней, целевая функция в (1.118) – (1.119) задана неявно.

В (1.112) задача равновесного программирования была сформулирована как задача поиска неподвижной точки экстремального отображения. Покажем, что обычная задача поиска неподвижной точки может быть сформулирована как задача равновесного программирования. Пусть задана вектор-функция F ( x) = ( f1 ( x),..., f 2 ( x) ), компонентами которой являются непрерывные скалярные функции f i (x) векторного аргумента x = (x1,..., xn ) отображающая выпуклое компактное множество R n в себя. По теореме Брауэра существует вектор x* такой, что Для того чтобы представить задачу поиска неподвижной точки в виде задачи равновесного программирования, функцию (v, w) определим следующим образом;

Нетрудно показать, что вектор v – неподвижная точка отображения F : тогда и только тогда, когда v есть решение задачи равновесного программирования (1.113) с функцией (v, w), определенной в (1.124). Линейность функции (v, w) по второму аргументу позволяет в некоторых случаях задачу поиска неподвижной точки свести к обычной задаче математического программирования. Пусть – выпуклый многогранник, т.е. – выпуклая оболочка своих крайних точек:

wi – крайние точки. Используя (1.125) и линейность функции (v, w) по w (см.

(1.124)), функцию (v) определм следующим образом:

Стандартным образом, вводя дополнительную переменную v0, задачу (1.118) – (1.119) можно переписать в следующем эквивалентном виде:

что равносильно Пусть v0, v* – оптимальное решение задачи (1.127) – (1.129). Если v0 < 0, то неподвижной точки не существует, если v0 = 0, то v* – неподвижная точка.

Нетрудно показать, что обычная задача математического программирования может быть записана в виде (1.113). Для этого достаточно считать w = x, v = x* ( x* – оптимальное решение задачи), функцию (v, w) определить как (v, w) = (v) и положить = X.

Рассмотрим еще несколько примеров сведения известных задач системного анализа к задаче равновесного программирования.

Пусть заданы выпуклые компактные множества X R n и Y R m функция L( x, y ), определенная на декартовом произведении X Y. Пара x*, y* называется седловой точкой функции L( x, y ), если выполняются неравенства Известно, что существование седловой точки эквивалентно условиям Условия выполнения равенств (1.131) составляют основное содержание так называемых теорем о минимаксе. Так как выполнение неравенств (1.130) сводится к (1.131), в дальнейшем будем рассматривать условия выполнения теорем о минимаксе. Введем в рассмотрение векторы v = ( x, y ), w = ( p, q ) и функцию (v, w) = L( p, y ) L(x, q ). В принятых обозначениях задача проверки выполнимости условий (1.131) эквивалентна задаче равновесного программирования (1.113). Более того, если функция L(x, y ) выпукла по первому аргументу и вогнута по второму, то функция (v, w) выпукла по w, что автоматически означает, что в данном случае теорема о минимаксе справедлива и что функция L(x, y ) имеет седловую точку.

Многие условия оптимальности основаны на применении так называемых теорем об альтернативах. В общем случае смысл этих теорем состоит в следующем. Для двух множеств D и Q справедливо, что Определим множества D и Q следующим образом где f i (x) – выпуклые непрерывные функции, R+ = { y : yi 0, i = 1,..., k }. Предполоk жим, что D = o. Тогда для любого x из X существует номер l {1,..., k } такой, что f l ( x) 0. Следовательно, Введем множество Условие (1.132) эквивалентно следующему что, в свою очередь, эквивалентно неравенству Используя теорему о минимаксе, поменяем местами операции min и max Это означает существование вектора S такого, что откуда и следует условие Q = o. Тот факт, что из D = o следует Q = o доказывается аналогично.

Решение вариационных неравенств. Задано отображение F : R n R n. Требуется найти точку v* K, где K R n :

Нетрудно видеть, что задача (1.133) эквивалентна (1.114), если ввести функцию Нелинейная задача дополнительности. Пусть задано отображение F : R n R n.

Требуется найти вектор v* 0 такой, что Введением функции (1.133) задача (1.134) снова сводится к задаче (1.114).

Нахождение равновесия по Нэшу. Рассматривается некооперативная игра n лиц.

Каждый игрок i обладает набором стратегий X i R ni и функцией потерь fi ( x1, x 2,..., xi,..., x n ), т.е. функция потерь i го игрока зависит не только от своей выбранной стратегии x i X i, но и от стратегий, выбранных другими игроками. Равновесие по Нэшу можно определить следующим образом. Равновесием x *i, i = 1,..., n игры n лиц является решение системы экстремальных включений Систему включений (1.135) можно рассматривать как обобщение системы нелинейных уравнений - каждое уравнение заменяется задачей оптимизации и все задачи параметрически связаны друг с другом, причем векторный параметр в одной задаче является переменной оптимизации в другой и наоборот. Следуя [133] введем нормализованную функцию где v есть набор векторов x i, а w есть набор векторов y i, i = 1,..., n. При помощи нормализованной функции (v, w) задача нахождения равновесия по Нэшу может быть записана в виде (1.113).

Подводя итог всему вышесказанному, следует отметить, что за последние 10 – лет сформировалось новое направление в системном анализе и исследовании операций – равновесное программирование. Задачи на поиск равновесия (или компромисса) рассматривались и ранее. Однако их математические формулировки были сделаны на разных языках – на языке математического программирования, на языке систем линейных и нелинейных уравнений, на языке вариационных неравенств, на языке задачи о дополнительности. Тем не менее, все эти постановки пронизывает одна идея – поиск неподвижной точки точечно-множественного (экстремального) отображения. Наиболее всеобъемлющей в этом смысле является постановка задачи равновесного программирования (1.113). Следующим результатом, по-видимому, можно считать распространение нормализованной функции (1.136) на решение задач вида (1.113), что дает возможность построения конструктивных методов решения задач равновесного программирования.

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

Рассмотрим следующую задачу оптимизации где f (x) – скалярная функция, X – компактное подмножество n -мерного пространства R n.

Определение 1. Будем говорить, что функция f (x) имеет верхнюю и нижнюю опорные функции в точке y X, если существуют функции ( x, y ) и ( x, y ), непрерывные по x и удовлетворяющие условиям Функцию ( x, y ) будем называть верхней опорной функцией функции f (x) в точке y, а функцию ( x, y ) – нижней опорной функцией функции f (x) в точке y.

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

Из Определения 1 следует, что функция f (x), имеющая верхнюю и нижнюю опорные функции на X, представима в виде Представление целевой функции в виде нижней или верхней огибающей некоторого семейства вспомогательных функций (1.139) позволяет использовать при решении задачи (1.137) – (1.138) свойства именно вспомогательных функций, сама же целевая функция этими свойствами может и не обладать.

ПРИМЕР 1. Предположим, что f (x) – выпуклая непрерывная функция. Тогда её можно представить как верхнюю огибающую семейства аффинных функций где p f ( y ), f ( y ) – субдифференциал f (x) в точке y. В этом случае нижняя опорная функция ( x, y ) определяется следующим образом Функция f (x) – нелинейна и не всегда дифференцируема, в то время как ( x, y ) есть линейная (и дифференцируемая) по x функция при каждом фиксированном y.

ПРИМЕР 2. Пусть задана следующая задача математического программирования, в которой x является векторным параметром из некоторого выпуклого компактного множества X, где Z – выпуклое компактное подмножество m -мерного пространства R m, w( x, z ) есть аффинная по x функция при каждом фиксированном z Z и непрерывная по z функция при каждом фиксированном x. Определим f (x) как функцию оптимального значения Функция f (x) задана неявно. Тем не менее, она конечна и выпукла, поскольку является поточечным максимумом семейства аффинных функций. Пусть x X и Тогда в силу (1.142) т.е. w( x, z ) может выполнять роль нижней опорной к f (x) функции в точке x.

ПРИМЕР 3. Предположим, что в задаче (1.140) – (1.141) функция w( x, z ) непрерывно дифференцируема по x при фиксированном z, а остальные условия сохранены.

Тогда повторяя рассуждения предыдущего примера, получим, что в данном случае неявно заданная функция оптимального значения имеет нижнюю опорную непрерывно дифференцируемую функцию, определяемую условиями (1.143) – (1.145).

Два последних примера показывают, что в общем случае для функции оптимального значения задачи (1.140) – (1.141) свойства нижней опорной функции определяются свойствами функции w( x, z ) относительно параметра x. При этом на данном этапе вопрос о том насколько сложна сама задача (1.140) – (1.141) при заданном параметре x является второстепенным. Если в дальнейшем потребуется оценить пределы f и f изменения оптимального значения задачи (1.140) – (1.141) то для этого необходимо будет решить две задачи В условиях ПРИМЕРА 2 задача (1.146) – (1.147) есть задача минимизации выпуклой функции на выпуклом множестве, т.е. задача выпуклого программирования, а задача (1.148) – (1.149) представляет собой задачу максимизации выпуклой функции на выпуклом множестве, т.е. задачу на поиск глобального максимума многоэкстремальной функции. Тем не менее, в некоторых случаях задача максимизации может даже оказаться проще задачи минимизации. Известно, что максимум выпуклой функции достигается в крайней точке допустимой области. Например, если X есть n -мерный симплекс, т.е.

выпуклая оболочка n + 1 точки, то для нахождения максимального значения f (x) достаточно n + 1 раз решить задачу (1.140) – (1.141), а затем из всех решений выбрать наибольшее.

Нетрудно видеть, что если функция f (x) имеет верхнюю и нижнюю опорные функции хотя бы в одной точке множества X, то, в силу непрерывности этих функций и компактности X, функция f (x) ограничена на X. Если функция удовлетворяет Определению 1 в любой точке множества X, то она непрерывна.

Определение 2. Верхним множеством Лебега L+f ( ) и нижним множеством Лебега Lf ( ) функции f (x) называются множества где – некоторая константа.

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

Теорема 1 ([362]). Если функция удовлетворяет Определению 1 на X, то она непрерывна на X.

Всюду в дальнейшем будем предполагать, что функция f (x) удовлетворяет Определению 1. Тогда, в силу теоремы Вейерштрасса задача (1.137) – (1.138) имеет решение. Через x* обозначим глобальный максимум, а через f * – глобальное максимальное значение: f * = f x*.

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

Теорема 2 ([362]). Если функции ( x, y ) и ( x, y ) дифференцируемы по x при каждом фиксированном y, то f (x) дифференцируема в любой точке x int( X ).

Следствие 1. Пусть в задаче (1.137)–(1.138) целевая функция f (x) имеет дифференцируемые по x опорные функции ( x, y ) и ( x, y ) при каждом фиксированном y из открытого множества S X, X – выпуклое множество.

Если x* – локальное решение задачи (1.137–(1.138), то Следствие 2. Если дифференцируемая функция f (x) имеет дифференцируемую нижнюю опорную функцию ( x, y ), то При решении задачи (1.137)–(1.138) верхние и нижние опорные функции используются с разными целями. Нижняя опорная функция служит основой для итеративной процедуры локального улучшения, стартующей из некоторой начальной точки x 0.

LOCAL: ПРОЦЕДУРА ЛОКАЛЬНОГО УЛУЧШЕНИЯ.

L0. Задать некоторую стартовую точку x 0 X. Установить k = 0.

L1. Решить вспомогательную задачу Пусть x – оптимальное решение задачи (1.150) – (1.151).

На шаге L1 роль опорой точки играет x k. Точки x k и x k +1 удовлетворяют неравенству Из определения нижней опорной функции и последнего неравенства имеем т.е. процедура локального улучшения (которую в дальнейшем для краткости иногда будем называть процедурой L) генерирует неубывающую относительно целевой функции последовательность точек. Нетрудно видеть, что процедура L обладает следующими свойствами:

A. Поскольку последовательность f x k ограничена сверху и монотонно не убывает, существует предел f x который в общем случае зависит от стартовой точки x 0.

B. В силу компактности X последовательность x k состоит из множества сходящихся подпоследовательностей и для любой сходящейся подпоследовательности x Процедура локального улучшение не гарантирует в общем случае нахождения даже стационарной точки. В [363] введено определение полустационарной сверху точки.

Определение 3. Точка ~ называется полустационарной сверху точкой, если где функция os (t ) :

В случае дифференцируемости функции f (x) Определение 3 можно уточнить.

Теорема 3 ([362]). Пусть f (x) – дифференцируемая функция, а X – выпуклое множество. Если ~ – полустационарная сверху точка, то Из Теоремы 3 следует, что если некоторая точка x (1.153), то она удовлетворяет и неравенству (1.152), т.е. ~ является полустационарной сверху точкой. Следовательно, неравенство (1.153) можно использовать в качестве эквивалентного определения полустационарной сверху точки для дифференцируемых функций f (x).

Предположим теперь, что функция ( x, y ) также непрерывно дифференцируема по x при любом фиксированном y. Тогда полученное на шаге L1. решение x k +1 удовлетворяет неравенству Если итерационный процесс конечен, то x k = x k +1 и в силу Следствия 2 имеем т.е. точка x k удовлетворяет необходимым условиям оптимальности.

Теорема 4 ([362]). Если процедура локального улучшения генерирует бесконечную последовательность точек, то каждая предельная точка этой последовательности есть полустационарная сверху точка.

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

Теорема 5 ([362]). Если процедура локального улучшения генерирует бесконечную последовательность точек и выполняются следующие условия i. ( x, y ) сильно выпукла по x с константой > 0 равномерно по y ;

ii. градиент x ( x, y ) удовлетворяет условию Липшица с константой L равномерно по y.

Тогда последовательность x k сходится к стационарной точке задачи (1.137)– (1.138).

Выбор метода решения задачи (1.150)–(1.151) зависит от свойств функции ПРИМЕР 5. Предположим, что в задаче (1.137)–(1.138) функция f (x) дважды непрерывно дифференцируема и X выпуклое компактное множество. Тогда существует > 0 такое, что матрица 2 f ( x) + I неотрицательно определена для любого фиксированного x X, 2 f ( x) – матрица вторых производных, I – единичная матрица.

Используя представление функции f (x) в виде (1.154), выпуклость функции g (x), нижнюю опорную функцию ( x, y ) можно определить следующим образом Применим процедуру локального улучшения для решения задачи максимизации f (x) на X c функцией ( x, y ), определенной в (1.155). Функция ( x, y ) вогнута по x и поэтому вспомогательная задача (1.150)–(1.151) есть задача выпуклого программирования. В частности, если int( X ) 0 и все точки x k int( X ), k = 0,1,..., то решение задачи (1.150) – (1.151) удовлетворяет условию которое с учетом (1.155) можно переписать в следующем виде Итерационный процесс, определяемый соотношением (1.156), совпадает с методом наискорейшего подъема с фиксированной длиной шага.

Методику применения процедуры локального улучшения, использованную в ПРИМЕРЕ 4, можно распространить и на более общий случай.

ПРИМЕР 5. Пусть функция f (x) задана в следующем виде где g (x) – непрерывная выпуклая, не обязательно дифференцируемая функция, w(x) – дифференцируемая функция. Тогда в силу выпуклости g (x) справедливо неравенство где p g ( y ), g ( y ) – субдифференциал функции g (x) в точке y. Из (1.157) и (1.158) следует, что нижняя опорная функция ( x, y ) может быть определена следующим образом Соответствующая задача (1.150)–(1.151) может уже не быть задачей выпуклого программирования, но целевая функция в этой задаче дифференцируема и для ее решения можно применять эффективные методы локального подъема, использующие информацию о первых производных.

Перейдем к обсуждению вопроса о нахождении глобального максимума в задаче (1.137) – (1.138). Для этой цели используется верхняя опорная функция ( x, y ). Если Если задано несколько точек x X, i = 0,..., k, то или и по аналогии с (159) Неравенство (1.160) определяет оценку сверху глобального максимального значения функции f (x) на X и служит основой для приводимой ниже процедуры нахождения глобального максимума.

GLOBAL: ПРОЦЕДУРА НАХОЖДЕНИЯ ГЛОБАЛЬНОГО МАКСИМУМА.

Задать стартовую точку x 0 X, точность > 0. Установить k = 0, G0.

G1. Решить задачу – глобальный максимум задачи (1.161)–(1.162);

тимальное значение, т.е. k = min x k +1, x j вить k = k + 1 и перейти на шаг G1.

На каждой итерации процедуры GLOBAL выполняется двусторонняя оценка глобального максимального значения Процедура нахождения глобального максимума является обобщением метода опорных плоскостей в выпуклом программировании [364] и метода Пиявского в глобальной оптимизации [365].

Для гарантирования нахождения глобального максимума достаточно, чтобы множество функций x, x j, j = 0,1,... было равномерно ограничено и равностепенно непрерывно.

Определение 4. Множество функций f (x), называется равномерно ограниченным на множестве X, если существует константа K > 0 такая, что Определение 5. Множество функций f (x), называется равностепенно непрерывным, если для любого > 0 существует > 0 такое, что Теорема 6. Если множество функций x, x j, j = 0,1,... равномерно ограничено и равностепенно непрерывно, то любая предельная точка последовательности x k, j = 0,1,... есть точка глобального максимума задачи (1.137)–(1.138).

Справедливость Теоремы 6 следует из доказательства теоремы о погружении надграфика целевой функции, приведенной в [102].

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

Введем, как и ранее, в рассмотрение функцию Предположим, что функция (v, w) непрерывна, а множество – выпуклое компактное множество. Перепишем задачу (1.163) в виде:

найти v* :

что, в свою очередь, эквивалентно неравенству:

Если ввести вспомогательную функцию то для проверки неравенства (1.164) достаточно решить задачу В общем случае функция P (v) может быть многоэкстремальной. Пусть v есть глобальный минимум в задаче (1.166) – (1.167). Если P v* < 0, то задача равновесного программирования не имеет решения. В противном случае v* есть точка равновесия. В силу построения P (v) 0 v. Тогда если v* – точка равновесия, то Следовательно, (1.168) можно использовать в качестве необходимого и достаточного условия глобальной оптимальности в том случае, если точка равновесия существует. В силу (1.165) задача (1.166) – (1.167) есть задача оптимизации с неявно заданной целевой функцией. Для того чтобы вычислить значение целевой функции P (v), необходимо решить задачу (1.165). Тем не менее, поскольку P (v) есть «функция минимумов», этот факт может быть использован для разработки итеративной процедуры решения задачи (1.166) – (1.167).

Пусть v D – некоторая произвольная точка. Решим задачу (1.165). Пусть w – оптимальное решение. Если P (v ) = 0, то v есть точка равновесия. Если нет, то из (1.165) имеем Будем говорить, что функция (v, w ) есть опорная функция мажоранта функции P (v).

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

Шаг 1. Решить задачу Пусть wk – глобальный минимум задачи (1.169)–(1.170).

Шаг 2. Если v k, wk = 0, то v k есть точка равновесия, перейти на Шаг 6.

Шаг 3. Решить задачу – глобальный минимум задачи (1.171) – (1.172); k – соответствующее опПусть v тимальное значение, т.е. k = min v k +1, w j.

Шаг 4. Если k < 0, то точки равновесия не существует, перейти на Шаг 6.

Шаг 5. Установить k = k + 1 и перейти на Шаг 1.

Если число итераций конечно, то либо будет найдена точка равновесия, либо будет установлено, что точки равновесия не существует.

На каждой итерации решаются две задачи математического программирования – (1.169)–(1.170) и (1.171)–(1.172). В частности, если функция (v, w) выпукла по w и вогнута по v, то предлагаемая процедура находит седловую точку (v, w) на множестве.

В данном примере функция P (v) из может быть записана в виде:

Равновесие по Нэшу достигается в точке с координатами v1 = существуют и другие точки равновесия, что видно из рис. 1.3, где изображена функция P(v1,v2 ) (точкой равновесия здесь будет любая точка, в которой функция P(v1,v2 ) обращается в ноль).

ПРИМЕР 7. Рассмотрим некооперативную игру двух лиц со следующими функциями потерь и множествами стратегий:

В данном примере не удается выписать явный вид функции P (v1, v 2 ).

Стартовой точкой была точка v10 = 5, v2 = 5. При этом соответствующий глобальный минимум по x = (w1, w2 ) в задаче (1.169)–(1.170) достигался в точке w10 = 5,957, w2 = 6,014. График первой функции-мажоранты v, w0 приведен на рис. 1.4.

Горизонтальная плоскость соответствует нулевому уровню. Следовательно, точки равновесия принадлежат области, в которой значения первой функции-мажоранты не меньше нуля. Приближенное решение было получено за 10 итераций. Точность полагалась равной = 0,01. Результаты вычислений приведены в таблице 1.3, в которой k – номер итерации; v и w соответствуют v k и wk ; f – значения функций потерь;

(v, w) – величины v k, wk = P v k (если v k, wk, то получено -оптимальное решение); k – оптимальное значение, полученное на Шаге 3 (если точка равновесия существует, то эти значения стремятся к нулю).

Таблица 1.3. Итеративное нахождение равновесия по Нэшу Предложенная выше методика применялась к решению ряда конкретных задач равновесного программирования, связанных с энергетическим моделированием [366– 370].

1.8. Методы решения некорректных задач в системных Начало 60-х годов прошлого столетия, благодаря основополагающим работам А.Н. Тихонова, М.М. Лаврентьева и В.К. Иванова, ознаменовалось становлением новой математической дисциплины – теория и методы решения некорректно поставленных задач. Такие задачи характеризуются тем, что их решения могут не существовать (в нужных классах) или быть неединственными, а в случае существования и единственности заведомо неустойчивы, так что малые в том или ином смысле погрешности исходных данных приводят к неприемлемо большим погрешностям приближенного решения.

Выяснилось, что множество некорректных задач не же множества корректных.

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

К началу 1970-х годов количество работ по некорректным задачам превышало многие сотни, а к концу 90-х и число монографий стало, по-видимому, трехзначным.

Первые работы СЭИ СО АН СССР, которые можно отнести к данной тематике [134, 135], связаны с исследованием устойчивости решения задачи линейного программирования (ЛП):

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

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

Практически все отметили постоянно встречающееся «свойство «пологости» функционала в зоне оптимума». Одним из первых в СЭИ, кто осознал важность введения регуляризующего слагаемого в целевой функционал для обеспечения его сильной выпуклости, был не профессиональный математик, а энергетик Ш.С. Чурквеидзе. Им предложен оригинальный метод решения задачи ЛП, а также задачи минимизации выпуклой сепарабельной функции при линейных ограничениях, названный автором методом вспомогательных функций [92, 137, 138]. Позднее подобная разновидность метода штрафных функций развивалась в работах А.В. Крянева, Б.Т. Поляка, Н.В Третьякова.

К этому времени относится серия работ по итерационным методам решения операторных уравнений где A – линейный вполне непрерывный оператор, действующий в вещественном гильбертовом пространстве H. В [139] для исследования устойчивости итерационного процесса (предполагается, что А неотрицателен и самосопряжен) к возмущениям исходных данных доказана следующая Лемма. Пусть последовательность неотрицательных чисел zn +1 удовлетворяет неравенству где Тогда для того чтобы достаточно выполнения условий Эта лемма, являющаяся дискретным аналогом леммы Я.И. Альбера [140], в дальнейшем сыграла существенную роль в развитии идеологии итеративной регуляризации.

В работах [141, 142] рассмотрены методы типа стохастической аппроксимации, когда правая часть (1.173) трактуется как случайная величина со значениями в H, а на В 1960–1970-х годах в СЭИ, в частности Р.И. Ивановским, интенсивно развивалась тематика, связанная с автоматическим управлением техническими объектами. Рассматривалась и важная в линейной теории автоматического регулирования задача деконволюции свертки заключающаяся в определении входного сигнала x (t ) динамической системы по известным, как правило, приближенно выходному сигналу y (t ) и переходной (импульсной) характеристике K (t ).

Интегральное уравнение Вольтерра I рода частным случаем которого является (1.176), в свою очередь, можно трактовать как частный случай интегрального уравнения Фредгольма I рода если положить в (1.178) Известно, что уравнение (1.178) с непрерывным на квадрате 0, T 0,T ядром K (t, s ) некорректно поставлено в любых "разумных" функциональных пространствах.

В силу этого попытки применить какой-либо квадратурный метод для получения численного решения (1.178) обречены на неуспех – возникающие после дискретизации (1.178) системы линейных алгебраических уравнений (СЛАУ) плохо обусловлены, а при стремлении шага квадратуры к нулю число обусловленности матрицы СЛАУ стремится к бесконечности из-за неограниченности обратного к вполне непрерывному оператору Фредгольма.

В случае (1.177) ситуация принципиально иная. Если что означает разрыв первого рода ядра K1 t, s уравнения Фредгольма на диагонали s = t, то оператор Вольтерра, рассматриваемый действующим из C 0,T в C[0,T ] = { y (t ) : y (t ) C[0,T ], y (0) = 0}, имеет ограниченный обратный:

где На этот факт внимание автора раздела обратил А.Б. Бакушинский. Он же предложил технику исследования сходимости и устойчивости численных методов решения (1.177). Вообще влияние А.Б. Бакушинского на развитие вольтерровской тематики в СЭИ и, более общо, на развитие "некорректного" направления исследований в академической и вузовской науке Байкальского региона трудно переоценить. Он был в числе лекторов первой и второй Байкальских школ-семинаров по методам оптимизации и их приложениям, организованных СЭИ в 1969 г. в бухте Песчаной и в 1972 г. в Хакусах.

Основы теории регуляризующих алгоритмов (РА), которые им тогда интенсивно разрабатывались, остаются актуальными и в настоящее время. Идея рассмотрения итерационного процесса (1.174) как дискретного аналога схемы установления Я.И. Альбера также принадлежит ему.

В работе [143] показано, что при заданных исходных данных в (1.177) с погрешностью, измеряемой в норме L2, квадратурный метод правых прямоугольников порождает РА, если шаг сетки h трактовать как параметр регуляризации, согласованный с мерой L2 -погрешности. Получены оптимальные асимптотические оценки: при h( ) 5 Ch -погрешность сеточного решения имеет порядок O ( 5 ). Результаты [143] обобщают известные факты о регуляризующем свойстве шага конечноразностных аппроксимаций в задаче численного дифференцирования эмпирической функции. Анализ иных квадратурных формул приведен в [144]. В частности, установлено, что квадратуры, имеющие порядок аппроксимации O (h p ), p > 1, например формулы Грегори и Симпсона, приводят к расходимости численных методов решения уравнения (1.177), так как при K (t, s ) const соответствующие характеристические уравнения имеют корни, большие единицы. С другой стороны, для квадратуры средних прямоугольников ( p = 2) регуляризующее свойство процедуры дискретизации сохраняется. В [145] результаты [143] перенесены на более широкий класс уравнений (1.178), когда разрыв I рода на диагонали s = t претерпевает не само ядро K1 (t, s ), а его производная по t некоторого порядка n. Таким свойством обладают функции Грина краевых задач для обыкновенных дифференциальных уравнений ( n + 1) -го порядка. В [146] получено обобщение [143] на случай систем линейных интегральных уравнений Вольтерра I рода, когда K (t, s ) в (1.177) – ( m m ) -матрица, f (t ) и (t ) – соответственно заданная и искомая вектор-функции. Показано, что если условие (1.180) заменить на то квадратуры прямоугольников также порождают РА. Например, в случае средних прямоугольников при h( ) погрешность сеточного решения имеет порядок O ( 3 ). В [147] показано, что если с целью дополнительного подавления влияния C -погрешности исходных данных на устойчивость численного решения ввести традиционный параметр регуляризации ( ) по схеме М.М. Лаврентьева–А.М. Денисова, то условие = o ( h ) необходимо для сходимости метода квадратур в Ch -норме, поэтому шаг является основным параметром регуляризации, определяющим асимптотику погрешности сеточного решения, а – вспомогательным.

В цикле работ [148]–[154] рассматривалось n -мерное интегральное уравнение Вольтерра I рода В [148] получена оценка нормы оператора, обратного к оператору Vn, рассматриn) ваемому действующим из C n в C n, из которой следует корректность по Адамару уравнения (1.181) на паре (C n, C n ). Кубатурные методы численного решения двумерного уравнения вида (1.181) ( n = 2) рассмотрены в [149, 151], а в [150, 152–154] развита техника получения неулучшаемых оценок решений линейных интегральных и разностных неравенств, которые лежат в основе исследования устойчивости решения исходного интегрального уравнения и его сеточных аналогов.

Например, в [150] показано, что неулучшаемая оценка непрерывных решений интегрального неравенства J 0 функция Бесселя нулевого порядка, i мнимая единица.

Неулучшаемость понимается в том естественном смысле, что (1.183) становится точным равенством, если в (1.182) знак заменить на =, т.е. мажоранта в (1.183) является точным решением соответствующего уравнения.