Введение к работе
Актуальность темы. Современное развитие производства, техники, внедрение передовых технологий приводят к новым раннее не исследованным оптимизационным задачам и к тому, что оптимизация различных систем продолжает оставаться одной из наиболее актуальных проблем прикладной математики.
Среди экстремальных задач принято выделять выпуклые и невыпуклые, принципиальное различие которых в том, что классические необходимые условия оптимальности такие, например, как правило множителей Лагранжа, в выпуклых задачах являются и достаточными для глобальной оптимальности.
В невыпуклых же задачах оптимизации классические условия оптимальности доставляют только необходимые условия локального экстремума, в то время как практиков зачастую интересуют только глобальные решения.
Как следствие, в традиционных численных методах решения экстремальных задач обычно доказывается сходимость к стационарной точке или, в лучшем случае, к локальному экстремуму и только для выпуклых задач при предположениях определенной регулярности удается доказать глобальную сходимость традиционных алгоритмов.
В теории и методах невыпуклых экстремальных задач, которым посвящена обширная литература, в настоящий момент принято различать следующие классы невыпуклых задач оптимизации:
-
выпуклая максимизация (или вогнутая минимизация) на допустимом множестве;
-
обратно-выпуклое программирование;
-
d.c.-программирование.
Известные численные методы глобальной оптимизации такие, например, как методы отсечений, внешней и внутренней аппроксимации, ветвей и границ, характеризуются простотой геометрических построений с одной стороны, а с другой - отсутствием аналитических эквивалентов очевидных геометрических построений, а также отсутствием связей с современной теорией экстремума и классическими методами оптимизации.
Актуальность работы определяется необходимостью решения важной задачи использования конструктивной теории условий глобальной оптимальности для задач выпуклой максимизации и на ее основе построения для таких задач численных методов глобальной оптимизации с исследованием их глобальной сходимости и верификацией их эффективности.
Для этого необходимы:
-
Специальный аппарат исследования задач выпуклой максимизации, отражающий специфику этих задач и естественным образом порождающий условия глобальной оптимальности.
-
Нетрадиционные способы конструирования численных методов глобальной оптимизации в рассматриваемом классе задач, позволяющие использовать новую информацию о задаче в виде условий глобальной оптимальности.
-
Новые методы исследования глобальной сходимости, а также сравнительной эффективности построенных алгоритмов.
Цель работы. Цель диссертационной работы заключается в развитии теории и методов глобального поиска для задач выпуклой максимизации, разработанных Стрекаловским А.С, для квадратичной задачи о назначениях и для задач оптимального управления.
Методы исследования. Для решения рассматриваемой задачи в диссертации используется аппарат выпуклого анализа, математического программирования и оптимального управления.
Научная новизна. В диссертации применены новые методы глобального поиска в задачах выпуклой максимизации для ранее не исследованных этими методами комбинаторной (квадратичной) задачи о назначениях и невыпуклых задач оптимального управления.
Практическая значимость. Полученные в работе результаты позволяют находить субоптимальные решения в квадратичной задаче о назначениях сравнительно большой размерности и позволяют находить глобальные решения в невыпуклых задачах оптимального управления, имеющих широкое поле приложений.
Апробация работы. Основные результаты диссертации докладывались автором и его научным руководителем на конференциях:
-
Ш-е совещание по глобальной оптимизации, 10-14 декабря, 1995, Зегед, Венгрия [4], [6];
-
8-ая Франко-Германская конференция по оптимизации, 21-26 июля, 1996, Триер, Германия [5];
-
Байкальский международный студенческий форум "Безопасное развитие регионов", 30 июня-5 июля, 1997, Иркутск [1];
-
Международная конференция "Проблемы оптимизации и экономические приложения", 1-5 июля, 1997, Омск [2];
-
Ляпуновские чтения, 29-31 октября, 1997, Иркутский вычислительный центр СО РАН, Иркутск;
-
11-ая Байкальская международная школа-семинар " Методы оптимизации и их приложения", 1-12 июля, 1998, Иркутск, Байкал [3].
Результаты работы обсуждались на семинарах:
лаборатории глобальной оптимизации ИДСТУ СО РАН,
лаборатории исследования операции ИСЭМ СО РАН,
объединенном семинаре по методам оптимального управления кафедр методов оптимизации и вычислительной математики ИГУ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, списка литературы из 128 наименований и трех приложений. Основные результаты опубликованы в работах [4-Й-