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

Введение к работе

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

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

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

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

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

1. выпуклая максимизация (или вогнутая минимизация) на допустимом мнояестве;

2. оптимизация на дополнениях выпуклых мноаеств (обратно-выпуклое программирование);

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

4. минимизация лишшщиевых функций.

Известные-численные метода глобальной оптимизас:-:. т«го!е, например, как методы отсечений, внешней и — уі_;н:і-_і а.^с-_::_:> мации, вегвей и границ, характеризуются чистотой геометрических построений с одной стороны, ~ другой, отсутствием аналитических эквивалентов очевиднч : неметрических построений, а такие отсутствием связей с -.- jзмеиной теорией экстремума и классическими методами or-.- і.зации.

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

а) решение задачи выпуклой максимизации достигается в
крайней точке допустимого множества;

б) решение является точкой Куна-Таккера;

в) значение двойственной задачи является нижней оценкой
для исходной задачи.

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

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

Для этого необходимы:

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

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

3. Новые методы исследования глобальной сходимости, а также сравнительной эффективности построенных алгоритмов.

Цель работы. Диссертационная работа посвящена созданию теории глобального экстремума и методов поиска глобального решения в задачах выпуклой максимизации,обратно-выпуклого программирования и поровденкых этими задачами невыпуклых задачах оптимального управления (ОУ).

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

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

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

4. Развит аппарат выпуклого анализа (например, дано описание элементов поляры множества Лебега выпуклой функции, даны различные аналитические эквиваленты включения некоторого мне— кества в другое выпуклое множество).

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

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

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

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

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

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

Реализация. Методы, разработанные в диссертации, использовались:

8. При разработке пакета программ глобальной оптимизации на ВЦ Иркутского университета.

9. При разработке пакета прикладных программ для решения задач энергетики в Сибирском энергетическом институте СО РАН. Работа выполнена в рамках НИР "Теория и методы оптимизации управляемых процессов" по постановлению СФТМН Президиума АН СССР Л II0O-494-I2I6 от 05.12.85 г. & госрегистрации 01870004239, а также проекта "методы линейно-квадратичных аппроксимаций и их программное обеспечение для решения задач оптимального управления", получившем гранд Министерства науки, высшей школы и технической политики РФ на 1992-1993 гг.

Результаты, изложенные в диссертации, являются частью спецкурса "Дополнительные главы методов оптимизации", читаемого на математическом факультете Иркутского университета.

Апробация работы. Результаты диссертации докладывалась на международном семинаре "Функциональный анализ и его стклскекия"

(Константин, Алжир, 1987 г.), на УП-й Всесоюзной конференции по проблемам теоретической кибернетики (Горький-Н.Новгород, 1988 г.) международной школе-семинаре по методам оптимизации и их приложениям (Иркутск, Байкал, 1989 г.), всесоюзной конференции по дифференциальным уравнениям и оптимальному управлению (Ашхабад, I9S0 г.), международном семинаре по негладким и разрывным задачам оптимизации и управления (Владивосток,

1991. г.), школе-семинаре "Разрывные динамические системы" (Ужгород, 1991 г.), на 15-й конференции IF IP по моделированию систем и оптимизации (Цюрих, Швейцария), на Ш-ем международном семинаре по глобальной оптимизации (Иркутск, Байкал,

1992. г.).

Материалы диссертации неоднократно докладывались и обсуждались на следующих семинарах:

в отделе вычислительных методов и оптимизации Института кибернетики АН Украины (Киев);

по недифференцируемой оптимизации Института вычислительной математики-процессов управления при факультете Ш-ПУ Санкт-Петербургского университета;

по методатл оптимизации кафедры вычислительной математики ФВМК Московского университета им. М.В.Ломоносова;

по методам оптимизации в отделе прикладной математики ШЖ РАН (Москва);

по оптимальному управлении Института математики АН Бело-руси (Минск);

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

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