Минимизация функции, имеющих вогнутую миноранту на компактном множестве, и их свойства Хамисов, Олег Валерьевич

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

Актуальность темы^-. Шюгоэкстремальные задачи широко встречается в различных областях науки и техники. По определении задача многоэкстремальной глобальной оптимизации состоит в отыскании глобального минимума вещественнозначной функции, которая имеет несколько отличных локальных минимумов. Допустимая область в Е^п обычно определяется системой неравенств. Хорошо известно, что многие задачи, возникающие в различных прикладных исследованиях, являются по существу многоэкстремальными. Стандартные методы нелинейного программирования не приводят к успеху при решении таких задач. В большинстве случаев это связано с многоэкстремальностью и в меньшей степени зависит от гладкости, размерности или других свойств целевой функции и допустимой области. Используя такие локальные понятия как градиент, субградиент или матрица вторых производных при решении достаточно сложных нногоэкстремальных задач, мохно надеяться лишь на получение локального решения. Кроме того, классические методы, как, правило не дают оценки отклонения локального решения от глобального. По этой причине возникла необходимость в разработке новой техники решения многоэкстремальных задач. К настоящему времени созданы три мощные вычислительные схемы, которые составляют современную вычислительную базу решения задач глобальной оптимизации. Первая схема обьединяет различные методы отсечения, вторая - методы ветвей и границ, третья - методы аппроксимации. В сочетании с мощной современной вычислительной техникой эти методы или различные комбинации этих методов позволяют решать достаточно слохные многоэкстремальные задачи. Наиболее широкий класс задач, решаемых на основе данной вычислительной базы, составляют задачи, в которых целевая функция и функции-ограничения являются локально липшицевыми функциями. Известно, что большинство задач глобальной оптимизации, встречающихся на, практике, являются задачами данного класса. Однако эффективность методов решения таких задач существенным образом зависит от точности оценивания константы Липшица, а

,3

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

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

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

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

Научная новизна и ' практическая ценность результатов, полученных автором, состоит в следующем:

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

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

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

2. Из класса функций, имеющих вогнутую миноранту, выделен вахный подкласс функций для которых построение вогнутой миноранты мохет быть достаточно просто запрограммировано на ЭВМ. Данный

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

Апробация работы. Результаты работы докладывались на конференциях "Методы математического программирования и их программное обеспечение" (Свердловск, 1987, 1991)_t на международных семинарах "Методы оптимизации и их приложения" (Иркутск, 1989, 1992), на 15-й Международной конференции DTP по системному . моделированию и оптимизации (Цюрих, 1991), на международной конференции ISEMA-92 (Еензень, Китай, 1992), на втором советско-китайского семинаре (SEI-IPRI, Иркутск, 1992), на конференции молодых ученых СЭИ (Иркутск, 1991)., на научных семинарах СЭИ и ИММ УрО (Екатеринбург).

Структура работы. Диссертация состоит из введения, трех глав и закличения, списка литературы, содержащего 71 наименование. Она содержит 4 рисунка. Работа изложена на 64 страницах. Всего 68 страниц.