Алгоритмы методов поиска экстремумов
Классификация методов программирования
ААААААААААА
Необходимые и достаточные условия безусловного экстремума (§ 20)
Дадим общее определение задачи поиска экстремума и основные положения. Безусловного и условного.
Градиент и матрица
Гессе
.
Положительная определённость.
Выпуклые множества и функции. Условие Липшица.
Постановка задачи.
Рассматриваются функции
– дважды непрерывно дифференцируемые.
Стратегия решения
задачи состоит в нахождении точек
локальных экстремумов и вычисления
значений функции
в этих точках с помощью следующих
средств:
необходимых условий первого и второго порядка (порядок используемых производных);
достаточных условий.
Необходимые условия
(1-го порядка):
– точка локального минимума (максимума),
.
Это стационарная точка.
Необходимые условия
(2-го порядка):
– точка локального минимума (максимума),
.
Достаточные
условия:
– точка локального минимума (максимума).
Определитель матрицы Гессе, угловые миноры, главные миноры.
Для проверки
определённости знака матрицы Гессе
обычно используют 2 способа:
А) Критерий Сильвестра (с помощью угловых
и главных
миноров) – проверка достаточных (и
необходимых) условий экстремума:
.
.
Б) Критерий проверки необходимых условий 2-го порядка:
.
.
Способ «по собственным значениям матрицы Гессе»:
.
.
Для скалярной
функции (одной переменной) имеется более
определённый критерий необходимости
и достаточности.
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Найти стационарные точки, т.е.
.Найти матрицу Гессе во всех стационарных точках
.
– локальный
минимум (максимум) (проверка через
угловые миноры или собственные числа);
– нет экстремума
(проверка через главные миноры или
собственные числа);
– возможен
локальный минимум (максимум), требуется
дальнейшее исследование, обычно, на
основе разложения в ряд Тейлора (проверка
через главные миноры или собственные
числа);
Глобальные экстремумы находятся сравнением локальных. Строго выпуклые функции имеют ровно 1 минимум.
ЗАНЯТИЕ № 2 – 14 февраля 2013.
1.3 «Необходимые и достаточные условия условного экстремума».
1.3.1. Постановка
задачи и основные определения. Пусть
:
Основным методом решения таких задач является «Метод множителей Лагранжа».
Функцией Лагранжа называется
– обобщённая
функция Лагранжа.
– классическая
функция Лагранжа.
Далее теория
использует функцию Лагранжа в качестве
целевой функции с параметрами
(которые необходимо также определить):
– градиент функции
Лагранжа (классической или обобщённой).
– второй дифференциал
функции Лагранжа (классической или
обобщённой).
– первый дифференциал
ограничения.
Ограничение
называется активным в точке
,
если
(иначе – пассивным).
Различают линейно
независимые или линейно зависимые в
точке
градиенты ограничений:
.
При линейной зависимости точку
называют «регулярной».
1.3.3. Условный экстремум типа равенств
Стратегия решения
аналогична решению задачи без ограничений,
но требует для определения точек
экстремума
нахождения значений m
линейно независимых параметров из m+1
параметра
– для чего имеется дополнительно
необходимых m
уравнений.
Проверяемые условия делятся (аналогично случаю безусловного экстремума) на необходимые и достаточные:
Необходимые условия 1-го порядка:
стационарность
;допустимость
;регулярность
,
т.е. линейная независимость (
).
Условия стационарности и допустимости образуют систему n+m уравнений с n+m+1 неизвестными. Её решения называются условно-стационарными точками.
Как избавиться от
одного лишнего неизвестного? Если точка
регулярная, т.е.
(
– нерегулярная точка), то на это
и делят уравнение для градиента и
получают необходимое. Если про регулярность
неизвестно (проверка затруднена), то
просто рассматривают два случая:
,
и тоже всё нормально.
В регулярной точке,
имеем уравнение без
,
т.е.классическое, тогда
– т.е. антиградиент
целевой функции равен линейной комбинации
градиентов ограничений.
Отсюда виден физический смысл этих векторов и коэффициентов . Точка экстремума является точкой касания линии уровня целевой функции и кривой, описывающей ограничение. Если точка не является точкой касания, то всегда можно пройти по градиенту вдоль ограничения с увеличением функции (по антиградиенту с уменьшением функции).
Для нерегулярной точки в функции Лагранжа исчезает член с целевой функцией и ограничения становятся линейно зависимыми, т.е. вырожденными. Тогда, надо избавиться от лишних ограничений, оставив максимальное линейно независимое их множество.
Необходимые условия 2-го порядка:
пусть выполнены необходимые условия 1-го порядка, т.е. – регулярная точка и найдено решение
системы уравнений
,
;
Достаточные условия 2-го порядка:
пусть – решение системы уравнений , ;
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Составить обобщённую функцию Лагранжа .
Составить систему уравнений , .
Решить систему, т.е. найти условно стационарные точки для двух случаев: . Если удаётся проверить условие линейной независимости градиентов ограничений
,
то отсутствует случай
.Записать выражение для 2-го дифференциала классической функции Лагранжа в точке :
.Записать систему уравнений для дифференциалов ограничений:
.
Из предыдущей
системы выразить любые m
дифференциалов
через остальные n-m
и подставить в
:
– локальный
минимум (максимум);
– нет экстремума;
–
возможен локальный
минимум (максимум), требуется дальнейшее
исследование, обычно, на основе разложения
в ряд Тейлора и нахождения следующих
дифференциалов.
Глобальные экстремумы находятся сравнением локальных. Строго выпуклые функции имеют ровно 1 минимум.
ЗАДАЧИ. № 3.5, ….
ЗАНЯТИЕ №3-4 – 14, 21 февраля 2013.
1.3.4. Условный экстремум типа неравенств
1. Постановка задачи и основные определения. Пусть :
Проверяемые условия делятся (аналогично случаям безусловного экстремума и ограничениям типа равенства) на необходимые и достаточные:
Необходимые условия 1-го порядка:
стационарность ;
допустимость
;неотрицательность для минимума
(неположительность для максимума
);дополняющая нежёсткость
;регулярность , т.е. линейная независимость ( ).
Уже из этих условий
видно, что решение задачи с ограничениями
типа неравенств обладает рядом
существенных, усложняющих отличий,
главным из которых является условие
дополняющей нежесткости
с дополнительным условием одинаковости
знаков всех коэффициентов
.
Определим
– множество индексов ограничений,
активных в точке
,
т.е. в которых неравенства реализуются
равенствами:
,
т.е. – положением точки на границе
данного ограничения. Таким образом,
если ограничение неактивно
,
то соответствующее ему
.
Это соотношение является ключом к
решению задачи.
Заметим ещё, что для выпуклых функций приведённые необходимые условия являются и достаточными, а множество допустимых решений – выпукло.
Достаточные условия минимума (максимума) 1-го порядка:
пусть точка – регулярная, т.е. ;
;
.
Необходимые условия минимума (максимума) 2-го порядка:
пусть выполнены необходимые условия 1-го порядка, т.е. – регулярная точка и найдено решение системы уравнений для необходимых условий 1-го порядка;
Достаточные условия минимума (максимума) 2-го порядка:
пусть выполнены необходимые условия 1-го порядка, т.е. – регулярная точка и найдено решение системы уравнений для необходимых условий 1-го порядка;
.
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Составить обобщённую функцию Лагранжа .
Составить систему уравнений , , ( ), ;
Решить систему, т.е. найти условно стационарные точки для двух случаев: . Если удаётся проверить условие линейной независимости градиентов ограничений , отсутствует случай ;
Решение для обоих случаев делается для всех возможных
комбинаций удовлетворения условий
дополняющеё нежесткости;Определить число активных l ограничений в точке ;
;Если
,
то работаем с дифференциалом 2-го
порядка;Записать выражение для 2-го дифференциала классической функции Лагранжа в точке : .
Записать систему уравнений для дифференциалов активных ограничений:
.Используя эти условия исследовать знак 2-го дифференциала
:
– локальный минимум (максимум);
– нет экстремума;
– возможен локальный минимум (максимум), требуется дальнейшее исследование, обычно, на основе разложения в ряд Тейлора и нахождения следующих дифференциалов.
Глобальные экстремумы находятся сравнением локальных. Строго выпуклые функции имеют ровно 1 минимум.
ПРИМЕР 3.12.
ЗАНЯТИЕ № 5 – 7 марта 2013.
1.3.4. Условный экстремум смешанного типа: равенства и неравенства
1. Постановка задачи и основные определения. Пусть :
Исследование задачи получается простой комбинацией условий двух типов. Все формулировки аналогичны. Поэтому приведём только Алгоритм решения задачи.
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Составить обобщённую функцию Лагранжа .
Составить систему уравнений , , ;
Решить систему, т.е. найти условно стационарные точки для двух случаев: , а также для всех возможных комбинаций удовлетворения условий дополняющей нежесткости (если удаётся проверить условие линейной независимости градиентов ограничений , то отсутствует случай );
Проверить выполнение ограничений неравенств в стационарных точках:
,
Определить число активных l ограничений в точке ;
;
– может быть min, max.
Если , то работаем с дифференциалом 2-го порядка;
Записать выражение для 2-го дифференциала классической функции Лагранжа в точке : .
Записать систему уравнений и неравенств для дифференциалов активных ограничений:
.Используя эти условия исследовать знак 2-го дифференциала :
– локальный минимум (максимум);
– нет экстремума;
– возможен локальный минимум (максимум), требуется дальнейшее исследование, обычно, на основе разложения в ряд Тейлора и нахождения дифференциалов более высокого порядка.
ЗАНЯТИЕ № 6 – 14 марта 2013.