Введение к работе
Актуальность темы Современное развитие производства, техники, внедрение передовых технологий приводят к новым раннее не исследованным оптимизационным задачам, и к тому, что оптимизация различных систем продолжает оставаться: одной из наиболее актуальных проблем прикладной математики.
Среди экстремальных задач принято выделять выпуклые и невыпуклые, принципиальное различие которых в том, что классические необходимые условия оптимальности, такие, например, как правило множителей Лагранжа, в выпуклых задачах являются и достаточными для глобальной оптимальности.
В невыпуклых же задачах оптимизации классические условия оптимальности доставляют только необходимые условия локального экстремума, в то время как, практиков зачастую интересуют только глобальные решения.
Как следствие, в традиционных численных методах решения экстремальных задач обычно доказывается сходимость к стационарной точке или, в лучшем случае, к локальному экстремуму, и только для выпуклых задач при предположениях определенной регулярности удается доказать глобальную сходимость традиционных алгоритмов.
В теории и методах невыпуклых экстремальных задач, которым посвящена обширная литература, в настоящий момент принято различать следующие классы невыпуклых задач оптимизации:
выпуклая максимизация (или вогнутая минимизация) на допустимом множестве;
обратно-выпуклое программирование;
d.c.-программирование (минимизация разности двух выпуклых функций);
минимизация липщицевых функций.
Известные численные методы глобальной оптимизации, такие, например, как методы отсечений, внешней и внутренней аппроксимации, ветвей и границ, характеризуются простотой геометрических построений с одной стороны, а с другой, отсутствием аналитических эквивалентов очевидных геометрических построений, а также отсутствием связей с современной теорией экстремума и классическими методами оптимизации.
Актуальность работы определяется необходимостью решения важной задачи использования конструктивной теории условий глобальной оптимальности для задач обратно-выпуклого программирования, и на ее основе построения для таких задач численных методов глобальной оптимизации с исследованием их глобальной сходимости и верификацией их эффективности.
Для этого необходимы:
-
Специальный аппарат исследования задач обратно-выпуклого программирования, отражающий специфику этих задач и естественным образом порождающий условия глобальной оптимальности.
-
Нетрадиционные способы конструирования численных методов глобальной оптимизации в рассматриваемом классе задач, позволяющие использовать новую информацию о задаче в виде условий глобальной оптимальности.
-
Новые методы исследования глобальной сходимости, а также сравнительной эффективности построенных алгоритмов.
Цель работы. Диссертационная работа посвящена развитию теории и построению методов поиска глобального решения в задачах обратно-выпуклого программирования, комбинирующих традиционные численные методы локальной оптимизации и вычислительные процедуры, вытекающие из необходимых и достаточных условий глобальной оптимальности, полученных А.С. Стрекаловским.
Методы исследования. Для решения рассматриваемой задачи в диссертации используется аппарат выпуклого анализа и математического программирования.
Научная новизна Результаты диссертации развивают новый способ поиска глобального решения обратно-выпуклых задач, связанный с условием оптимальности, полученным для таких задач. Кроме того, в диссертации предложен общий метод решения задачи обратно-выпуклого программирования и доказана его сходимость.
Практическая значимость. Полученные в работе результаты позволяют находить глобальные решения в обратно-выпуклых задачах и задачах целочисленного программирования возникающих на практике.
Апробация работы Результаты диссертации докладывались на научных семинарах по методам оптимизации кафедры вычислительной математики факультета ВМиК МГУ им. М.В. Ломоносова, кафедры высшей математики ИГЭА, лаборатории исследования операции СЭИ СО РАН и на объединенном семинаре по методам оптимального управления кафедр методов оптимизации и вычислительной математики ИГУ, на международной 17-й конференции IFIP-95 по моделированию систем и оптимизации (Прага, Чехия), на 10-й международной школе-семинаре по методам оптимизации и приложениям на Байкале (Иркутск, 1995 г.), в Ш-м международном совещании по глобальной оптимизации (Зегед, Венгрия) и на 8-ой совместной Франко-Германской конференции по оптимизации (Триер, ФРГ).
Структура и объем работы Диссертационная работа состоит из введения, трех глав, списка литературы из 170 наименований. Основные результаты опубликованы в работах [1-5].