Содержание к диссертации
ввданиЕ 6
Глава I. МЕТОДЫ ОПОРНЫХ ВЫПУМЫХ ШОЖЕСТВ В ВЫПУКЛОМ
ПРОГРАММИРОВАНИИ 18
I. Методы минимизации выпуклой функции на выпук
лом многограннике 18
Постановка задачи 18
Аппроксимация надграфика пересечением выпуклых опорных множеств . 18
аппроксимация графика минимизируемой функции кусочно-линейными формами 21
Обсуждение методов . 26
Приложение методов 29
2. Методы минимизации на выпуклых множествах ... 32
Аппроксимация допустиглого множества пересечением выпуклых опорных множеств 32
Аппроксимация границы допустимой области семейства опорных плоскостей 35
3. Методы погружения без вложения 39
Методы опорных множеств 39
Метод опорного конуса 45
Глава 2. МЕТОДЫ ЦЕНТРИРОВАННЫХ ОТСЕЧЕНИЙ В ВЫПУКЛОМ
ПРОІТАММИРОВАНИИ 50
I. Введение 50
2. Методы центров тяжести 51
3. Задача покрытия Л -мерным симплексом усеченного
/Z -мерного ортогонального симплекса 54
- Постановка задачи 54
Редукция к экстремальной задаче 54
Решение экстремальной задачи 57
Гарантированная оценка уменьшения объема . . 58
4. Первый алгоритм решения задачи 60
5. Задача оптимального покрытия П -мерным симплек
сом правильного усеченного симплекса 62
Постановка задачи 62
Редукция к экстремальной задаче 62
Решние экстремальной задачи 65
Гарантированная оценка уменьшения объема ... 68
6. Второй алгоритм решения задачи 71
7. Метод чебышевских точек 73
Идея методов 74
Первый метод решения задачи (1.1)-(1.2) ... 74
Второй метод решения задачи (1.1)-(1.2) ... 76
8. Комментарии 79
Глава 3. МЕТОДЫ ПОИСКА ЛОКАЛЬНОГО РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ
ВОГНУТОГО ПРОГРАММИРОВАНИЯ 66
I. Задача вогнутого программирования ........ $6
2. Метод локального решения задачи вогнутого програм
мирования с ограничениям в форме неравенств . . . . &7
3. Метод локального решения задачи вогнутого програм
мирования с ограничениями в форме равенств .... 33
Глава 4. МЕТОДЫ РЕШЕНИЯ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ (ГЛОБАЛЬ
НЫЙ ПОИСК) 9<Ь
I. Минимизация вогнутой функции на многограннике
- Метод решения задачи (I.I), (1.2) 9G
- Некоторые интерпретации метода
2. Минимизация функции, удовлетворяющей условию Лип
шица на ограниченной области ./4?
3, Методы аппроксимации HS
4. Отсечения в w
5. Метод поиска абсолютного минимума в выпукло-вогнутых задачах математического программирования . . . 435 6. Достаточные условия сходимости методов погружения 44Ц Глава 5. МИНИМИЗАЦИЯ ФУНКЦИЙ НА ДОПУСТИМОЙ ЦЕЛОЧИСЛЕННОЙ
РЕШЕТКЕ ВЫПУКЛОГО ШОГОГРАННИКА 449
I. Методы отсечения 449
Описание метода 4$0
Обоснование правильности отсечений 455
Сходимость метода 456
2. Эффективные правильные отсечения 459
- Критерии эффективности отсечений 4S9
3. Связь с методом Гомори и другими методами .... /66
4. Отсечения по ортогональному конусу П1
Глава 6. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕБЖ НЕКОТОРЫХ ИГРОВЫХ ЗАДАЧ
I. Методы решения минимаксных задач і7$
Методы решения задачи I ІН
Методы решения задачи 2 /7-7
2. Методы поиска минимума выпуклой функции при ограни
чениях под знаком 4пиг fff?4JC). 4В4
Первый метод решения задачи (2.1) /42
Второй метод решения задачи (2.1) 4*4
3. Методы поиска точек равновесия игр 4Ь лиц .... 4&ь
Свойства точек равновесия Ш
Первый метод поиска точки; равновесия 4&7
Второй метод /94
4. Численные методы поиска максимина (мшшмакса) . . . /А2
Глава 7. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ ОПТИМАЛЬ
НЫХ ПРОЦЕССОВ 200
I. Решение задач с обыкновенными дифференциальными
связями 200
2. Решение некоторых задач оптималтного управления
с распределенными параметрами . . 208
3. Минимизация вогнутой функции на конечном состоянии линейной системы обыкновенных дифференциальных
уравнений 218
Глава 8. (ПРИЛОЖЕНИЕ). ПРИМЕНЕНИЕ МЕТОДОВ ОТСЕЧЕНИЯ ПРИ
ИССЛЕДОВАНИИ БОЛЬШИХ СИСТЕМ ЭНЕРГЕТИКИ 222
I. Выпуклое программирование 222
Задача распределения резервов мощности в электроэнергетических системах (ЭЗС) 222
задача оптимального распределения водных ресурсов 225
Оптимизация нормальных режимов электроэнергетических систем 231
2. Многоэкстремальные задачи 233
- Оптимизация трассировки трубопроводных систем 233
3. Целочисленное программирование 238
- Задача выбора оптимального числа работающих
агрегатов электростанции 238
4. Игровые задачи 241
- Задача выбора коэффициентов усиления регулято
ров возбуждения в ЭЭС 241
5. Оптимальное управление .... 242
- Управление переходными процессами в ЭЭС . . . 242
ЗАКЛЮЧЕНИЕ 2
ЛИТЕРАТУРА
Введение к работе
Данная работа возникла в связи с рассмотрением ряда актуальных вопросов, связанных с большими системами энергетики.
При исследовании больших систем энергетики приходится привлекать аппарат из самых различных областей математики. Однако., в теории больших систем энергетики можно выделить ряд актуальных практических задач, носящих в основном оптимизационный характер.
В большей части эти задачи являются нелинейными, динамическими, дискретными, имеющшли высокую размерность и недостаточную исходную информацию.
Рассмотрение подобных задач стимулировало развитие в СЭИ СО АН СССР эффективных численных методов решения широкого класса задач теории оптимальных систем. Ряд таких методов, а также примеры решаемых шли задач приведены в данной диссертационной работе,
По существу, здесь методами погружения, которые будут определены ниже, исследуется решение следующей задачи.
Найти
ОС = о/та тт.
(I)
р = ^С&)
гг.
где Ч*(эв) - скалярная непрерывная функция вектора осе с. -} № *"* *- - некоторое компактное множество. Мшшмизация Ч*&$) наХг понимается в глобальном смысле.
Очевидно, что способы задания функции т&9и множества *? относят задачу (I) к тому или иному классу теории экстремальных задач. Например:
I) если множество
где fyCay - выпуклые скалярные функции; ^гу - выпуклая скалярная функция вектора ОС6Г , то задача (I) интерпретируется как задача выпуклого программирования;
если а: - множество целочисленных точек некоторого выпуклого замкнутого ограниченного многогранника, а *&]- с jz , то задача (I) есть задача линейного целочисленного программирования;
если 7< - множество достижимости некоторой системы дифференциальных уравнений, то задача (I) есть задача теории оптимальных процессов;
если
где Yс *z , то задача (I) есть антагонистическмя игра двух лиц и т.д.
Очевидно также, что численные методы, реализующие решение задачи (I), по возможности должны учитывать специфику задания как функции так и множества лс . Как правило, эффективность этих методов существенно зависит от меры учета этой специфики.
В настоящее время теория и методы оптимизации достаточно хорошо развиты. Укажем здесь лишь несколько основных монографий [i-IOJ . Вместе с тем следует отметить, что практическая эффек-/ тивность большинства методов оставляет желать лучшего. Такие методы как;проекции градиента, функций штрафа, возможных направлений и др. работоспособны лишь на классе задач выпуклого программирования и в остальных ситуациях, в лучшем случае, сходятся
*/
кунеобходимым условиям оптимальности. То же самое можно сказать и про теорию оптимальных процессов.
На мой взгляд,однопараметрические методы минимизации (максимизации) в принципе не могут быть обобщены (распространены) на решение более широкого класса оптимизационных задач. Именно в силу этих причин для решения задачи целочисленного программирования или глобальной оптимизации получила применение совершенно иная техника. Например, последовательный анализ вариантов [IIJ и более частные схемы [l3,I6J динамического программирования [I3J , отсечения [l4J , ветвей и границ і5,Іб] ; развертка кривой Пеано[і7], покрытия и разбиения [l9-2J и др. Ниже будет предложен единый подход к решению как одноэкстремальных, так и многоэкстремальных задач. Прежде чем перейти к краткой аннотации работы, дадим некоторые определения вычислительных схем, которыми мы будем заниматься в дальнейшем.
Методы отсечения разделим на два класса:
Методы погружения 9
Методы центрированных отсечений и перейдем к описанию первых из них.
Цусть в задаче (I) множество а: обладает достаточно ^хорошими свойствами и задано явно. Тогда основные вычислительные трудности ее решения, очевидно, связаны или с "трансцендентными" свойствами самой минимизируемой функции (недифференцируемость, разрывность, "овражный" характер линий уровня и др.), или со способом ее задания (например, в задаче 4) задана неявно).
Определим надграфик функции ^-РСх) как множество
Очевидно, что задача (I) эквивалентна следующей задаче: найти
0^C^/7Z^/^^/^^f/(S **''J.
(2)
Минимизируемая функция в задаче (2) линейна, следовательно, если трудность решения задачи (I) определяется "плохими" свойствами ^ФСх.) t то трудность решения задачи (2) - соответствующими свойствами надграфика функции ^РМ . Итерационный процесс решения
задачи (2) оперирует не с надграфиком ^РС*~) , а с некоторой его аппроксимацией. О п рєдБлє-име:
Цусть уже найдено множество ^.^/ОТ< & и J^ ,
^ n*t . Определим к #+, ^>лг такое, что X , XhH
^* " = ^//r2/*W/: Ж, *»н ^ &
(3)
Если существует Лі^— Л? -с^сг... у такое, что
-iirn JcZ+,= р , Me k!t9 (4)
то итеративный процесс (3) назовем методом последовательного погружения надграфика целевой функции.
Определение (3) метода последовательного погружения надграфика целевой функции, вообще говоря, не является настолько содержательным, чтобы можно было лишь на его основе строить алгоритмы и доказывать их сходимость. Но уже относительно незначительная информация о методах задания множеств *\+j дает возможность сформулировать соответствующие теоремы о сходимости итерационных процессов [92].
Сформулированные теоремы о достаточных условиях сходимости методов погружения еще не дают рецептов решения задачи (I), так как, вообще говоря, вспомогательные задачи (3) также являются многоэкстремальными. В работе рассматривается такой класс задач (I), для которого удается построить эффективные алгоритмы, реализующие схему (3), при этом используются современные достижения в области выпуклого программирования, теории оптимальных систем, теории игр и дискретной оптимизации.
Диссертация состоит из введения, семи глав, заключения и приложения, изложенных на 256 страницах машинописного текста, включая в себя I таблицу, 12 рисунков, II страниц цитированной литературы и 15 страниц приложения.
В первой главе рассмотрен ряд параметрических алгоритмов погружения, для решения задач выпуклого программирования, не требующих информации о способе задания множества *? . При минтшзации выпуклой функции приводится пример построения п+< , как пересе-чения опорных к Аг выпуклых множеств, т.е. множеств, имеющих хотя бы одну общую с *< граничную точку. Причем при доказатель-
стве теоремы сходимости не используется информация о способах за-
Т\пн
дания f<
Затем для решения задачи выпуклого программирования рассматриваются параметрические методы аппроксимации ^ф) кусочно-линейными формами Ґ23]. Основная идея аппроксимации - использование представления выпуклой области пересечением всех ее опорных полупространств. Как и в большинстве итеративных процессов, выбор стратегии на каждом шаге зависит от значения некоторого параметра, Вводится понятие локально-оптимальных алгоритмов аппроксимации и приводятся примеры таких алгоритмов [23,24J.
В третьей главе рассматривается задача математического программирования с ограничениями в форме равенств и неравенств. Дает-
ся ее редукция к некоторой специальной задаче математического программирования (задача с "дырой"), строится эффективный алгоритм решения последней [25].
Четвертая глава посвящена методам решения многоэкстремальных задач. В рамках методов последовательного погружения надгра-фика функции строятся алгоритмы решения задачи на поиск абсолютного минимума функции, удовлетворяющей условию Липшица на выпуклом замкнутом ограниченном многограннике. Методами последовательного погружения допустимого множества изучаются задача минимизации вогнутой функции на многограннике, задача максимизации выпуклой функции на корнях системы нелинейных алгебраических уравнений и задача на поиск абсолютного минимума вогнутой функции, удовлетворяющей условию Липшица на произвольном множестве эвклидова пространства. Доказывается конечность предлагаемых итеративных процессов.
Предлагаются новые схемы отсечений в (п+f)-мерном пространстве. Для минимизации вогнутой функции на многограннике рассматривается алгоритм, имеющий двухстороннюю оценку погрешности прибли женного решения. Доказываются теоремы сходимости. Приводятся дальнейшие обобщения.
В пятой главе рассматривается задача минтлизации скалярной функции на целочисленной решетке выпуклого многогранника. Предложен новый класс отсечений. Введены отсечения, зависящие от векторного параметра. Дается понятие оптимальных отсечений и приводятся примеры построения таких отсечений. Доказываются теоремы о сходимости предлагаемых алгоритмов к решению за конечное число шагов.
Методы решения ряда задач теории игр, приводимые в шестой главе, также используют идеи погружения надграфиков соответствую-
щих функции в множестве более простой структуры. Исследуется ряд численных методов поиска седловых точек, точек равновесия и оптимальных стратегий в иерархических играх. Доказываются соответствующие теоремы о сходимости исследуемых итерационных процессов.
Наконец, в седьмой главе приводятся примеры аппроксимации терминального функционала в пространстве управляющих воздействий кусочно-линейными формами. Исследуются вопросы сходимости.
В работе, параллельно, рассматриваются методы последовательного погружения допустимого множества. Определим класс этих методов.
Пусть найдены векторе и множество^ %\ Определим И -ЭА?такое, что ОС ^ h< и вычислим
ос*н=а*$ nun, faГэс) -*«*> **'J. (5)
Если существует множество индексов A/Osr такое, что
Лип Жк= ^^ г , * А7/ ,
где rrr- множество граничных точек /г, то итеративный процесс (5) назовем методом последовательного погружения допустимого множества.
Введение последовательности множеств гс аналогично (3) продиктовано неудобством задания исходного множества лг , т.е. желанием производить операции с множествами более простой природы. Структуру и методы построения последовательности //с J, как правило, определяет способ задания исходного множества А?. Более того, специфика задания учитывается при реализации последовательности f№ J и во многом определяет эффективность предлагаемых вычислительных процессов.
Предположим, что множество Ас задано системой неравенств
-15-
$={*,: gjCbj** о, J^C^j (7)
Обозначим QOx)- /r?4X QjC-zcj . Тогда задача (I) будет иметь
ґпіп {<Р(эс) . ос е >J
Допустим, что минимум ^C^cJ достигается на границе ri. Погрузим множество^ в некоторое компактное множество ^простой структуры. Допустим, что минимум ^РСх>/достигается на границе *?. Пусть уже найдены множество л? о Лги вектор ОС . Определим множество *< —' ЛС такое, что эс (^ /< и вычислим л
Если существует множество индексов'v/<^ л такое, что
4imgCoc^)^o , */к*, (9)
/с —»^
то итеративный процесс (8) назовем методом последовательного погружения допустимого множества в смысле (9). Этот способ задания множества А: позволяет, не привлекая выпуклость, формулировать теоремы о достаточных условиях сходимости методов погружения [92].
Схемы (5), (6), (8), (9) - (14) методов погружения интерпретируется в работе для решения задач выпуклого программирования, задач теории жрр,целочисленного программирования, задач теории оптимальных процессов и задач на поиск абсолютного минимума вогнутых функций на множествах эвклидова пространства, формулируются достаточные условия сходимости этих методов.
Аналогичные методы в выпуклом программировании изучались разными авторами. Одна из первых - работа Келли [26J. Затем были
опубликованы работы Вайнотта J27J, Зойтендейка [28] и автора [29-3 ij. Методы, позволяющие отбрасывать несущественные дополнительные ограничения, одновременно описаны в [29-33J. Систематическое изложение методов погружения в выпуклом программировании приведено в [92J. При решении многоэкстремальных задач методы отсечения, по-видимому, впервые были использованы в работе Х.Туя [34J. Наиболее общая схема, аналогчиная (5)-(6), приведена С.А.Пиявским [22J. Методы минимизации вогнутой функции рассматривались также в [35]. Первые результаты автора в этом направлении опубликованы в [36,37J. Алгоритмы отсечения в целочисленном программировании восходят к работам Данцига [38], Гомори [39J. Сейчас предложены различные модификации процесса Гомори, ускоряющие его сходимость [40J. Принципиально отличные отсечения получены в [4IJ и [24,42J. Их отличие заключается в различном выборе вспомогательного множества. Наиболее общая схема, аналогичная (4), в целочисленном программировании предложена Емеличевым [43J.
Кроме работ [44-46J, автору не известны примеры исследования методов типа (5), (6) или (8), (9) (14) для решения задач теории игр. Не получили широкого распространения методы, реализующие схемы (5), (6) или (8), (9) & при решении задач теории оптимальных процессов. Задачи с "дырой", рассматриваемые во второй главе, изучались в [25].
Перейдем теперь к характеристике методов центрированных отсечений. Рассмотрим задачу выпуклого программирования. Основная идея методов состоит в следующем. Допустимое множество или часть его, содержащая точку оптимума, погружается в некоторое вспомогательное множество более простой структуры. На этом множестве задается некоторая его мера симметрии (асимметрии) и точка симметрии. Через точку симметрии проводится отсекающая плоскость. Затем
идентифицируется часть вспомогательного множества, содержащая точку оптимума. Эта часть множества погружается в другое вспомогательное множество простой структуры возможно меньшей меры и процесс повторяется. Очевидно, для сходимости методов необходимо, чтобы соблюдался принцип сокращения меры, т.е. отношение меры каждого последующего вспомогательного множества к предыдущему было меньше единицы.
Знаменатель прогрессии итерационного процесса (отношение объемов) в методе центров тяжести симплексов, рассмотренном во второй главе как и в [88-90J, зависит лишь от размерности пространства: более того, в среднем он оказывается меньшим, чем в [86-90].
По существу методы центрированных отсечений - это попытка переноса методов деления отрезка пополам на многомерный случай. Там же, во второй главе, приведен метод чебышевских точек и его различные модификации.
Устанавливается связь центрированных отсечений с отсечениями, использующими метод последовательного погружения надграфика целевой функции.
В последней главе приводятся постановки ряда прикладных задач, для решения которых применялась методика, рассматриваемая в диссертационной работе. Вычислительные схемы ряда методов описаны в монографиях [54-5
Внедрение. На базе предложенных численных методов под научным руководством автора разработано программное обеспечение для ЭВМ БЭСМ-6 для решения различных оптимизационных задач. Сотрудниками лаборатории методов оптимизации СЭИ СО АН СССР И.А.Александровым, Ю.Я.Даниленко, І.И.Касинской, П.Т.Семеней разработаны алгол-программы Ї59,60]; JI08-II0) реализующие названные здесь подходы. Программа метода аппроксимации границы допустимой области
для решения задачи выпуклого программирования (автор Л.И.Касин-ская) принята в ГФАП. Программа метода опорного конуса для решения задачи выпуклого программирования (авторы Е.Г.Анциферов, Т.И.Наумова, Г.ПЛугунова) внедрена в ВЦ института Энергетики г.Лейпцига, ГДР. Последняя версия метода опорного конуса для решения общей задачи выпуклого программирования (авторы И.А.Александров и П.Т.Семеней) использовалась для решения одной задачи стохастического программирования, связанной с оптимальным распределением, водных ресурсов при планировании производства сельскохозяйственной продукции (модель разработана в ВЦ АН СССР, г.Москва).
Предложенный автором метод опорной гиперплоскости применялся в Отделе энергетики АН МССР для оптимизации режима гидротепловой энергосис темы (г.Кишинев).
Методы погружения при глобальной оптимизации использовались в институте нефтехимической и газовой промышленности им.И.М.Губкина (г.Москва) при оптимизации системы газосырьевых комплексов.
Сотрудниками лаборатории методов оптимизации СЭИ СО АН СССР по предложенным в работе методам разработан ряд программ на БЭСМ-6, которые использовались Д7ія решения следующих прикладных задач: распределение резервов мощности в электроэнергетических системах, оптимальное распределение водных ресурсов, оптимизация трассировки трубопроводных систем, выбор оптимального числа работающих агрегатов электростанции, выбор коэффициентов усиления регуляторов возбуждения в электроэнергетической системе и управление переходными процессами в электроэнергетических системах [47-53] , [106-10.
Результаты, нашедшие отражение в диссертации, докладывались на ЇЇ,У ж УП-Х Всесоюзных школах по методам оптимизации и теории управления в 1967-1983 гг., І-УІ Сибирских школах-семинарах по
-\7-
методам оптимизации и их приложениям в 1969-1983' гг., І-УІ Всесоюзных конференциях по проблемам теоретической кибернетики (г.Новосибирск, I969-I98I гг.), І-ІІІ Всесоюзных конференциях по теории игр и исследованию операций, П-ІУ Всесоюзных конференциях по теории игр и исследованию операций, Л-ІУ Всесоюзных симпозиумах по экстремальным задачам 1965-1969 гг., І-ІУ конференциях по методам математического программирования и программному обеспечению (г.Свердловск, 1970-1984 гг.), координационном совещании руководителей разработок пакетов программ и диалоговых систем оптимизации, г.Гродно, 1979 г.), ХУІ Международной конференции "Математическая оптимизация" (п.Зеяяин, ГДР, 1984 г.), Международной конференции по стохастическому программированию (г.Киев, 1984 г.), а также на ряде научных семинаров ВЦ АН СССР, ИМ СО АН СССР, ИММ УНЦ АН СССР, ИК АН УССР.
Основное содержание диссертации освещено в 16 статьях, одной монографии и одном препринте.
-и*
