Методы выпуклых и вогнутых опорных функций в задачах глобальной оптимизации

• Автор: Хамисов, Олег Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Иркутск
• Количество страниц: 275 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

Предварительные замечания

Краткий обзор

ГЛАВА 1. ФУНКЦИИ С ВЫПУКЛЫМИ МАЖОРАНТАМИ И ВОГНУТЫМИ МИНОРАНТАМИ

1.1 Определение функций с вогнутой минорантой и сравнение с

другими классами функций

1.2. Методы построения вогнутых минорант

1.3 Выпуклые опорные мажоранты

1.4 Задачи с.т. и с.т.s. программирования. Локальный поиск

1.5 Задача с.т. программирования. Глобальный поиск

1.6 Использование свойств опорных функций
1.7 Декомпозиция целевой функции в глобальной оптимизации
ГЛАВА 2. ОПТИМИЗАЦИОННЫЕ И ВЫЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ С ОДНОМЕРНЫМИ с.т. ФУНКЦИЯМИ
2.1 Автоматическая глобальная одномерная с.т. оптимизация
2.2 Нахождение корней нелинейного уравнения методом вогнутых
опорных функций
2.3 Нахождение действительных корней полинома на отрезке
2.4 Редукция задач невыпуклого квадратичного программирования
к нахождению корней одномерного полинома
ГЛАВА 3. МЕТОДЫ ОТСЕЧЕНИЙ
3.1 Предварительные замечания
3.2 Отсечения в»п
3.3 Отсечения в Rn+
3.4 Вогнутое продолжение
3.5 О построении глубоких отсечений в целочисленном программировании
3.6 Комбинация отсечений в R” и R"+
3.7 Минимизация выпуклой недифференцируемой функции на выпуклом ограниченном множестве
ГЛАВА 4. МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ
4.1 Предварительные замечания

4.2 Минимизация невыпуклой квадратичной функции на многограннике
4.3 Задача линейного программирования с одним дополнительным
квадратичным ограничением-неравенством
4.4 Глобальная минимизации дважды непрерывно дифференцируемой функции на выпуклом многограннике
4.5 Двойственные оценки в задачах с.т. программирования
4.6 Метод ветвей и границ с отсечениями в Мп+
ГЛАВА 5. ПРИЛОЖЕНИЯ МЕТОДОВ с.т. ОПТИМИЗАЦИИ
5.1 Применение нелинейных опорных функций в задачах линейного
параметрического программирования
5.2 Решение задач равновесного программирования
5.3 Редукция некоторых задач дискретного программирования к
задачам с.т. оптимизации
5.4 Тестирование вспомогательных эвристических методов нулевого
порядка
Заключение
Список литературы
ВВЕДЕНИЕ
Предварительные замечания
В работе исследуется задача нахождения глобального минимума многоэкстремальной функции / на компактном подмножестве X пространства Мп,
f(x) —> min, х Е X,
обладающая следующими свойствами:
А1. минимизируемая функция / в каждой точке множества X имеет вогнутую опорную непрерывную функцию-миноранту;
А2. допустимое множество определено конечным набором ограничений-неравенств, в левых частях которых стоят функции, также имеющие вогнутые опорные непрерывные функции-миноранты в каждой точке X.
Часть работы посвящена задаче (0.1.1), для которой, помимо А1 и А2, предполагается выполнение следующих дополнительных условий:
АЗ. минимизируемая функция / в каждой точке множества X имеет выпуклую опорную непрерывную функцию-мажоранту;
А4. кроме конечного набора ограничений-неравенств, допустимое множество задано конечным набором ограничений-равенств, в левых частях которых ст,оят функции, имеюище вогнутые опорные непрерывные функции-миноранты и выпуклые опорные функции-мажоранты в каждой точке X.
Два раздела современной глобальной оптимизации методически наиболее тесно связаны с исследованиями, проведенными в работе: липшицевая оптимизация1 и d.c. оптимизация. Под задачей липшицевой оптимизации понимается задача нахождения глобального минимума липшицевой функции на компактном множестве, заданном ограничениями-неравенствами и (или) ограничениями-равенствами с липшицевыми функциями в левых частях. D.c. функция есть функция, представимая в виде разности двух выпуклых
1 Термин заимствован из англоязычной литературы - Lipschitz optimization.
(0.1.1)

Так как ф{х, у) непрерывна по х, то Хс(ф,у) - замкнутые множества. Пересечение любого числа замкнутых множеств есть множество замкнутое ([60]), следовательно Хс(/) также является замкнутым, что эквивалентно тому, что /(ж) полунепрерывна снизу на X ([24]). □
Заменив в доказательстве X на К”, получим следствие.
Следствие 1.1. Каждая с.т. функция полунепрерывна снизу. □
Таким образом, СМ(Х) есть подмножество множества полунепрерывных снизу на X функций. Как показывает следующий пример, обратное утверждение не всегда справедливо.
Пример 1.2. Определим на X = [0, 2] С К одномерную функцию /(ж) :
,м _ [ 1 - 0 < х <
ПХ) ~ 2 - у/1 - (х- 2)2, 1 < х < 2.
Нетрудно видеть, что /(ж) есть полунепрерывная снизу функция на X, однако построить вогнутую (непрерывную!) миноранту к /(ж) в точке у — 1 невозможно (см. Рис. 1.2).
Рис. 1.2. Пример полунепрерывной снизу функции, не являющейся с.т. функцией.

Следовательно, имеются некоторые “точки различия” между с.т. и полунепрерывными снизу функциями. Следует отметить, что точка у = 1 - единственная точка, в которой полунепрерывная снизу функция из рассмотренного примера не имеет вогнутой миноранты. Поэтому можно