Глобальная минимизация квазивогнутых функций на выпуклых множествах

• Автор: Морозова, Елена Юрьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 135 с. : ил.

ОГЛАВЛЕНИЕ
Введение

Основные обозначения и определения.

ГЛАВА 1. Минимизация негладкой функции нескольких

переменных

1.1. Алгоритм бисекции для нахождения минимума

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

1.1.1. Постановка задачи.

1.1.2. Декомпозиция множеств и функций по сечениям

1.1.3. Описание алгоритма

1.1.4. Обоснование алгоритма.

1.1.5. Результаты численных экспериментов
1.1.5.1. Примеры минимизации негладких функций
1.1.5.2. Контрпример для алгоритма НелдераМида
1.1.5.3. Пример минимизации функции ДеннисаВуда.
1.2. Алгоритм безусловной минимизации непрерывной
строго унимодальной функции
1.2.1. Постановка задачи и описание алгоритма
1.2.2. Примеры работы алгоритма
1.2.2.1. Контрпример для алгоритма НелдераМида
1.2.2.2. Пример минимизации негладкой функции
1.2.2.3. Пример минимизации функции ДеннисаВуда. ГЛАВА 2. Метод статистических испытаний для решения задачи
минимизации квазивогнутой функции на выпуклом многогранном множестве
2.1. Общие свойства задач квазивогнутого программирования
2.2. Постановка задачи и основные утверждения.
2.3. Моделирование равномерного распределения на
выпуклой оболочке конечного подмножества векторов евклидова пространства.
2.4. Описание основного алгоритма и его обоснование
2.5. Вычислительные эксперименты. Примеры
2.5.1. Пример минимизации вогнутой функции.
2.5.2. Математическая модель задачи минимизации эксплуатационных расходов при организации вагонопотоков
2.5.3. Пример минимизации квазивогнутой функции
2.5.4. Определение диаметра выпуклого многогранного множества
ГЛАВА 3. Методы решения задачи транспортного типа
с квазивогнутой функцией стоимости
3.1. Свойства транспортного многогранника
3.2. Метод статистических испытаний для решения задачи транспортного типа с квазивогнутой функцией стоимости
3.2.1. Модификация алгоритма минимизации квазивогнутой функции на выпуклом многогранном множестве
3.2.2. Постановка задачи и описание алгоритма
3.2.3. Решение задачи при вырожденном опорном плане
3.2.4. Тестовая задача нахождения диаметра многогранника бистохастических матриц
3.3. Детерминированный метод поиска глобального минимума квазивогнутой функции на транспортном многограннике
ГЛАВА 4. Алгоритм глобальной минимизации квазивогнутой
функции на выпуклом множестве
4.1. Общие замечания.
4.2. Постановка задачи и краткое описание структуры алгоритма
4.3. Описание предварительного этапа.
4.4. Описание и обоснование процедуры построения многогранника, содержащего выпуклое множество
4.5. Пошаговое описание алгоритма
4.6. Результаты вычислительных экспериментов
4.6.1. Пример минимизации вогнутой функции на выпуклом множестве, задаваемом нелинейными ограничениями .
4.6.2. Пример минимизации вогнутой функции на выпуклом множестве, задаваемом нелинейными и линейными ограничениями
4.6.3. Пример минимизации вогнутой функции, когда оптимальное решение достигается в точке, лежащей
на границе только одного из ограничений.
Заключение
Литература


Сложность алгоритма заключается в том, что число линейных подзадач растет с каждой итерацией. В дано расширение алгоритма для минимизации вогнутой функции на произвольном выпуклом множестве. МакКормик в показал, что подход выпуклых огибающих может быть применен для факторизуемых функций. Детальное описание факторизуемых функций может быть найдено в . Решению различных задач вогнутой минимизации в контексте параллельных вычислений посвящены работы , . Несмотря на существование достаточно большого числа разнообразных методов глобальной минимизации вогнутых функций на выпуклых множествах, возможности применения этих методов для решения конкретных
задач ограничены предположениями о принадлежности некоторым специальным классам как оптимизируемых функций, так и допустимых множеств , , 3. В работе предлагаются новые методы решения задач вогнутого программирования, не накладывающие дополнительных ограничений на дифференцируемость целевой функции и позволяющие применять их для более общего класса функций негладких и даже разрывных квазивогнутых функций. Один из предлагаемых в данной работе методов глобальной минимизации квазивогнутой функции на произвольном выпуклом множестве базируется на последовательном применении алгоритма нахождения минимума выпуклой функции на симплексе для вычисления оценок снизу и сверху оптимального значения задачи вогнутой минимизации. Описание этого алгоритма представлено в первой главе. Также представлена модификация этого алгоритма для случая минимизации строго унимодальной функции нескольких переменных в отсутствие ограничении. Предложенный в первой главе алгоритм относится к классу методов прямого поиска, основной особенностью которых является то, что они не требуют вычисления производной целевой функции. Направление минимизации полностью определяется последовательными вычислениями значений функции, что позволяет использовать эти методы для негладких функций. Такие ситуации часто встречаются в практически важных задачах оптимизации, что предопределяет широкое применение этих методов при решении важных прикладных оптимизационных задач. Методы прямого поиска наиболее известны как методы безусловной оптимизации, однако, существуют модификации этих методов и для задач с ограничениями , . Ниже
приведен краткий обзор методов прямого поиска минимума функции в отсутствие ограничений. В настоящее время одним из наиболее популярных методов прямого поиска минимума функции является метод НелдераМида , являющийся развитием метода Спендли, Хекста и Химсворта . Идея метода состоит в сравнении значений функции в вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры, использующей три основных операции отражения, растяжения и сжатия. Теоретическое исследование этого метода в настоящее время далеко от завершения. Так, в получен ряд результатов о сходимости, в частности, доказано, что оригинальный метод НелдераМида сходится для строго выпуклых функций одной переменной, кроме того, доказано, что в случае двух переменных диаметр симплекса сходится к нулю. Однако, вопрос о сходимости алгоритма к единственной точке даже для строго выпуклых квадратичных функций двух переменных например, для таких функций, как x,x2 2 остается открытым. Л2, для которого алгоритм НелдераМида со специальным выбором начальной конфигурации симплекса сходится к точке, не являющейся точкой минимума, даже в случае, когда семейство параметризовано так, что функции являются строго выпуклыми и имеют непрерывные производные до третьего порядка. При этом происходит эффект внутреннего сжатия, когда симплексы, генерируемые алгоритмом Нелдера Мида стягиваются к прямой линии, ортогональной направлению наискорейшего спуска и не содержащей точки минимума см. Подобного рода примеры представлены также в . Тем не менее, метод НеледраМида продолжает активно использоваться на практике реализация этого метода имеется в пакете , приложение iii x, что, в свою очередь, способствует появлению его многочисленных модификаций , , , , , 6.