Классические методы безусловной оптимизации
ТЕМА
Классические методы безусловной оптимизации
Введение
Как известно, классическая задача безусловной оптимизации имеет вид:
(1)
(2)
Существуют аналитические и численные методы решения этих задач.
Прежде всего вспомним аналитические методы решения задачи безусловной оптимизации.
Методы безусловной оптимизации занимают значительное место в курсе МО. Это обусловлено непосредственным применением их при решении ряда оптимизационных задач, а также при реализации методов решения значительной части задач условной оптимизации (задач МП).
1. Необходимые условия для точки локального минимума (максимума)
Пусть т.
доставляет минимальные значения функции
. Известно, что в этой точке
приращение функции неотрицательно, т.е.
. (1)
Найдем
, используя разложения функции
в окрестности т.
в ряд Тейлора.
, (2)
где
,
,
-
сумма членов ряда порядок которых относительно приращений
(двум) и выше.
Из (2) имеем:
(3)
Далее предположим, что
изменяется только одна переменная из множества переменных
. Например,
, тогда (3) преобразуется к виду:
(4)
Из (4) с очевидностью следует, что
(5)
Предположим, что
, тогда
(6)
С учетом (6) имеем:
. (7)
Предположим, что
положительно, т.е.
. Выберем при этом
, тогда произведение
, что противоречит (1).
Поэтому, действительно,
очевиден.
Рассуждая аналогично относительно
других переменных
получаем
необходимое условие для точек локального минимума функции многих переменных
![]()
(8)
Легко доказать, что для точки локального максимума необходимые условия будут точно такими же, как и для точки локального минимуму, т.е. условиями (8).
Понятно, что итогом
доказательства будет неравенство вида:
- условие неположительного приращения функции в
окрестности локального максимума.
Полученные необходимые условия
не дают ответ на вопрос: является ли стационарная точка
точкой минимума или точкой максимума.
Ответ на этот вопрос
можно получить, изучив достаточные условия. Эти условия предполагают
исследование матрицы вторых производных целевой функции
.
2. Достаточные условия для точки локального минимума (максимума)
Представим разложение
функции
в окрестности точки
в ряд Тейлора с точностью
до квадратичных по
слагаемых.
(1)
Разложение (1) можно представить более кратко, используя понятие: "скалярное произведение векторов" и "векторно-матричное произведение".
(1')


![]()
- матрица двух производных от целевой функции по
соответствующим переменным.
, ![]()
Приращение функции
на основании (1') можно
записать в виде:
(3)
Учитывая необходимые условия:
,
(4)
Подставим (3) в виде:
(4')
(5)
Квадратичная форма
называется дифференциальной
квадратичной формой (ДКФ).
Если ДКФ положительно
определена, то
и стационарная
точка
является точкой
локального минимума.
Если же ДКФ и матрица
, ее представляющая, отрицательно
определены, то
и
стационарная точка
является
точкой локального максимума.
Итак, необходимое и достаточное условие для точки локального минимума имеют вид

(эти же необходимые условия можно записать так:
,
,
)
- достаточное условие.
Соответственно, необходимое и достаточное условие локального максимума имеет вид:
,
(
),
.
Вспомним критерий, позволяющий определить: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.
3. Критерий Сильвестра
Позволяет ответить на вопрос: является ли квадратичная форма и матрица, ее представляющая, положительно определенной, или отрицательно определенной.
Далее изложение будет
относительно ДКФ и матрицы
ее
определяющей, т.е. ДКФ вида
.
,
-
называется матрицей Гессе.

Главный определитель матрицы
Гессе ![]()
![]()


![]()
и ДКФ, которую оно представляет, будут положительно
определенными, если все главные определители матрицы Гессе (
) положительны (т.е. имеет место следующая
схема знаков:
)
Если же имеет место
другая схема знаков для главных определителей матрицы Гессе
, например,
, то матрица
и ДКФ отрицательно определены.
4. Метод Эйлера – классический метод решения задач безусловной оптимизации
Этот метод основан на необходимых и достаточных условиях, изученных в 1.1 – 1.3; применим нахождению локальных экстремумов только непрерывных дифференцируемых функций.
Алгоритм этого метода достаточно прост:
1)
используя
необходимые условия формируем систему
в общем случае нелинейных уравнений. Отметим, что
решить аналитически эту систему в общем случае невозможно; следует применить
численные методы решения систем нелинейных уравнений (НУ) (см. "ЧМ").
По этой причине метод Эйлера будет аналитически-численным методом. Решая указанную
систему уравнений находим координаты стационарной точки
.;
2)
исследуем ДКФ и
матрицу Гессе
, которая ее
представляет. С помощью критерия Сильвестра определяем, является ли
стационарная точка
точкой
минимума или точкой максимума;
3)
вычисляем
значение целевой функции
в
экстремальной точке
![]()
Методом Эйлера решить следующую задачу безусловной оптимизации: найти 4 стационарные точки функции вида:
![]()
Выяснить характер этих точек, являются ли они точками минимума, или Седловыми (см. [3]). Построить графическое отображение этой функции в пространстве и на плоскости (с помощью линий уровня).
Далее эту функцию будем именовать типовой функцией, исследуя ее экстремальные свойства всеми изученными методами.
5. Классическая задача условной оптимизации и методы ее решения: Метод исключения и Метод множителей Лагранжа (ММЛ)
Как известно, классическая задача условной оптимизации имеет вид:
(1)
(2)
График, поясняющий
постановку задачи (1), (2) в пространстве
.
(1')
(2')
, ![]()

- уравнения линий уровня
Итак, ОДР
в рассматриваемой задаче представляет собой
некоторую кривую, представленную уравнением (2').
Как видно из рисунка,
точка
является точкой
безусловного глобального максимума; точка
- точкой условного (относительного) локального
минимума; точка
- точка
условного (относительного) локального максимума.
Задачу (1'), (2') можно
решить методом исключения (подстановки), решив уравнение (2') относительно
переменной
, и подставляя
найденное решение (1').
![]()
Исходная задача (1'),
(2') таким образом преобразована в задачу безусловной оптимизации функции
, которую легко решить методом
Эйлера.
Метод исключения (подстановки).
Пусть целевая функция
зависит от
переменных:
![]()
![]()
называются зависимыми переменными (или переменными состояния); соответственно можно ввести вектор

Оставшиеся
переменных
называются независимыми переменными решения.
Соответственно можно говорить о вектор-столбце:
и вектора
.
В классической задаче условной оптимизации:
(1)
(2)
Система (2) в соответствии с методом исключения (подстановки) должна быть разрешена относительно зависимых переменных (переменных состояния), т.е. должны быть получены следующие выражения для зависимых переменных:
(3)
Всегда ли система
уравнений (2) разрешима относительно зависимых переменных
- не всегда, это возможно лишь в случае,
когда определитель
,
называемый якобианом, элементы которого имеют вид:
, ![]()
не равен нулю (см. соответствующую теорему в курсе МА)

Как видно, функции
,
должны быть непрерывными дифференцируемыми
функциями, во-вторых, элементы определителя
должны быть вычислены в стационарной точке целевой
функции.
Подставляем
из (3) в целевую функцию (1), имеем:
![]()
(5)
Исследуемая функция
на экстремум можно произвести
методом Эйлера – методом безусловной оптимизации непрерывно дифференцируемой
функции.
Итак, метод исключения
(подстановки) позволяет использовать задачу классической условной оптимизации
преобразовать в задачу безусловной оптимизации функции
- функции
переменных при
условии (4), позволяющим получить систему выражений (3).
Недостаток метода
исключения: трудности, а иногда и невозможность получения системы выражений
(3). Свободный от этого недостатка, но требующий выполнения условия (4)
является ММЛ.
5.2. Метод множителей
Лагранжа. Необходимые условия в классической задаче условной оптимизации.
Функция Лагранжа ![]()
ММЛ позволяет исходную задачу классической условной оптимизации:
(1)
(2)
Преобразовать в задачу безусловной оптимизации специально сконструированной функции – функции Лагранжа:
, (3)
где
,
- множители Лагранжа;
.
Как видно,
представляет собой сумму, состоящую из
исходной целевой функции
и
"взвешенной" суммы функций
,
-
функции, представляющие их ограничения (2) исходной задачи.
Пусть точка
- точка безусловного экстремума
функции
, тогда, как
известно,
,
, или
(полный дифференциал функции
в точке
).
Используя концепция
зависимых и независимых переменных
- зависимые переменные;
- независимые переменные, тогда представим (5) в
развернутом виде:
(5')
Из (2) с очевидностью следует система уравнений вида:
,
(6)
Результат вычисления полного дифференциала для каждой из функций
![]()
Представим (6) в "развернутом" виде, используя концепцию зависимых и независимых переменных:
,
(6')
Заметим, что (6') в
отличии от (5') представляет собой систему, состоящую из
уравнений.
Умножим каждое
-ое уравнение системы (6') на
соответствующий
-ый множитель
Лагранжа. Сложим их между собой и с уравнением (5') и получим выражение:

(7)
Распорядимся множителями
Лагранжа
таким образом,
чтобы выражение в квадратных скобках под знаком первой суммы (иными словами,
коэффициенты при дифференциалах независимых переменных
,
)
равнялось нулю.
Термин
"распорядимся" множителями Лагранжа вышеуказанным образом означает,
что необходимо решить некоторую систему из
уравнений относительно