Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
10 Многомерная безусловная минимизация функций
Докажем необходимые условия существования локального минимума функции.
Разложим функцию в окрестности точки минимума в ряд Тейлора, ограничиваясь линейными членами разложения:
, (10.1)
где R часть ряда разложения, которая зависит от приращения вектора переменных 2-го и более высокого порядка; индекс * при производных есть признак их вычисления в точке локального минимума ; - значения функции цели, вычисленные в точках и , соответственно.
Данное соотношение можно записать в следующем виде:
.
Получим приращение функции цели в окрестности точки локального минимума:
=.
Так как - точка локального минимума, то в окрестности этой точки приращение функции цели неотрицательно:
=.
Предположим, что изменяется только одна переменная xr, а остальные переменные остаются неизменными, тогда
. (10.2)
Из данного соотношения следует, что в точке локального минимуму производная от функции цели по переменной равна нулю:
. (10.3)
Докажем это утверждение от противного.
Пусть .
Тогда, выбирая приращение , противоположное по знаку производной , получим:
, (10.4)
что противоречит выражению (10.2), а, следовательно, и предпосылке, что x* - точка локального минимума.
Таким образом, справедливость утверждение (10.3) доказана.
Проведя аналогичные рассуждения для каждой из переменной , , получим необходимые условия точки локального минимума:
, . (10.5)
В матричном виде необходимые условия точки локального минимума запишутся в следующем виде:
, (10.6)
где = - градиент функции.
Таким образом, в точке локального минимума градиент функции равен нулю.
Условие (10.6) будет выполняться также в точке локального максимума и в седловой точке.
Точка, для которой выполняется равенство , называется стационарной точкой функции .
Таким образом, условие (10.6) называется условием стационарности точки.
Геометрически условие (10.6) означает, что гиперплоскость, касательная к функции в точке оптимума, параллельна гиперплоскости определения этой функции. Так, для функции одной переменной это – касательная линия, параллельна оси х; для функции двух переменных – плоскость, параллельная плоскости х1 и х2 .
На рис.10.1 приведены различные примеры стационарных точек для функции одной переменной. Стационарная точка не обязательно должна быть экстремальной. Примером такой точки может служить точка перегиба функции на рис.10.1,б.
Рис. 10.1. Примеры стационарных точек функции одной переменной
На рис. 10.2 приведена функция двух переменных
. (10.7)
Функция (10.7) изображена в виде эквипотенциальных кривых на координатной плоскости х10х2. Каждая эквипотенциаль функции = уi представляет собой проекцию на плоскость х10х2 линии пересечения поверхности функции с горизонтальной плоскостью, отстоящей от плоскости на расстоянии уi . Таким образом, все точки эквипотенциальной кривой соответствуют одному и тому же значению уi.
Как видно из рисунка, функция (10.7) имеет четыре стационарные точки, в каждой из которых её частные производные равны нулю, т.е. выполняется необходимое условие локального экстремума (10.6). При этом одна стационарная точка, расположенная в первом квадранте, соответствует точке локального минимума функции. Другая, симметричная первой и расположенная в третьем квадранте, соответствует точке локального максимума функции. Две оставшиеся стационарные точки, расположенные во втором и четвёртом квадрантах и симметричные между собой, представляют собой типичные примеры седловых точек, в которых по одной переменной функция достигает максимума, по другой – минимума.
Рис. 10.2. Эквипотенциальные кривые и стационарные точки функции двух переменных (10.7)
Как видим, выполнение условия (10.6) в некоторой точке не гарантирует наличия экстремума функции в этой точке.
10.2 Достаточные условия точки локального минимума
Равенство нулю градиента функции – это необходимое, но недостаточное условие для существования локального экстремума.
Определим достаточные условия для точки локального минимума.
Экстремальная точка, как было доказано ранее, всегда является стационарной. Поэтому для доказательства достаточных условий точки локального минимума будем оперировать с функцией в окрестности её стационарной точки .
Разложим функцию в окрестности стационарной точки в ряд Тейлора, ограничиваясь квадратичными членами разложения:
, (10.8)
где R часть ряда разложения, которая зависит от приращения вектора переменных третьего и большего порядка; индекс «» при производных есть признак их вычисления в стационарной точке .
Данное соотношение можно записать в следующем виде:
. (10.9)
Перепишем выражение (10.9) в матричном виде:
, (10.10)
где Н матрица Гесса (симметрическая матрица порядка , элементами которой являются вторые частные и смешанные производные , , минимизируемой функции ):
;
– матрица Гесса с элементами, вычисленными в стационарной точке ;
– дифференциальная квадратичная форма в стационарной точке ;
- градиент функции, вычисленный в стационарной точке .
Приращение функции в стационарной точке будет равно:
=. (10.11)
Так как в стационарной точке градиент функции равен нулю, т.е. , то приращение функции (10.11) можно представить в следующем виде:
= . (10.12)
Данное соотношение является основным для определения достаточных условий существования локальных экстремумов.
Величина называется дифференциальной квадратичной формой. Она представляет собой скалярную величину и может быть выражена через частные производные второго порядка следующим образом:
= . (10.13)
Знак квадратичной формы полностью определяется характером матрицы Гесса Н. В результате исследования свойств матрицы Гесса можно определить характер стационарной точки .
Если квадратичная форма положительна для всех , то она (и матрица Н соответственно) называется положительно определённой.
Приращение функции в стационарной точке положительно, т.е.
, следовательно стационарная точка является точкой локального минимума функции .
Таким образом, достаточным условием точки локального минимума является положительная определенность матрицы Гесса.
Если квадратичная форма отрицательна для всех , то она (и матрица Н соответственно) называется отрицательно определённой.
Получаем условие наличия локального максимума в стационарной точке xо:
. (10.14)
Достаточное условие для точки локального максимума (при выполнение необходимых условий) заключается в отрицательной определённости матрицы Гесса в этой точке.
Если квадратичная форма при различных приращениях может принимать любые значения (положительные, отрицательные или нулевое), то она (и матрица Н соответственно) называется неопределённой.
В этом случае функция не имеет экстремума в стационарной точке. Это характерно для всех седловых точек функции.
Если квадратичная форма неотрицательна (неположительна) для всех , то она (и матрица Н соответственно) называется полуопределённой.
Полуопределённость матрицы Гесса имеет место в стационарных точках функции, которые образуют долины или гребни функции.
Таким образом, точка удовлетворяет необходимым и достаточным условиям точки локального минимума, если в этой точке градиент функции равен нулю, и имеет место положительная определенность матрицы вторых производных функции ( матрицы Гесса), вычисленных в этой точке.
Свойство строго выпуклых функций
Существует большой класс непрерывных функций, для которых необходимые условия локального экстремума одновременно являются и достаточными. Это класс строго выпуклых.
Строго выпуклая функция обладает следующим свойством. Если она в какой-либо точке дважды дифференцируема, её матрица вторых частных производных положительно определена.
Строго выпуклая функция в качестве стационарной точки может иметь только точку минимума и при этом единственную.
Следовательно, если функция является строго выпуклой и дважды дифференцируемой, то выполнение необходимых условий автоматически влечёт и выполнение достаточных, т.е. . Более того, стационарная точка функции является не только локальным минимумом, но и глобальным.
Основой определения вида стационарной точки является установление характера дифференциальной квадратичной формы , или, что то же самое, установление характера матрицы Гесса.
Наиболее часто характер квадратичной формы определяют с помощью критерия Сильвестра.
Введём понятие главных определителей матрицы.
Главные определители матриц – это определители матриц, которые образуются вдоль главной диагонали (с верхнего левого угла в правый нижний).
Для матрицы главными определителями являются:
;; ... ;
Согласно критерию Сильвестра:
матрица А положительно определена в том и только в том случае, если все главные определители матрицы положительны;
матрица А отрицательно определена в том и только в том случае, если все нечётные главные определители матрицы отрицательны, а все чётные – положительны;
если или и имеется j, для которого , то матрица не строго определена (локальный экстремум в стационарной точке может быть или не быть);
во всех остальных случаях матрица считается неопределенной.
Все методы решения задачи безусловной оптимизации можно разделить на два класса: классические и прямого поиска.
Классические методы, которые в литературе ещё называют непрямыми, точными или косвенными, позволяют найти оптимальную точку косвенным путём – через решение системы уравнений, в общем случае нелинейной. При этом, если решение системы производится не приближенными методами, то получают точные значения координат экстремальных точек оптимизируемой функции.
Методы прямого поиска, которые также называют просто прямыми, поисковыми, пошаговыми, итерационными, вычислительными, приближенными или неклассическими, решают задачу безусловной оптимизации путём постепенного поэтапного приближения к точке экстремума. Решение получают приближённым, но с наперёд заданной точностью.
Рассмотрим классический метод решения задачи безусловной оптимизации, который носит название метод Эйлера. Метод позволяет выявить все экстремальные точки оптимизируемой функции (как локальные минимумы, так и локальные максимумы), и таким образом дать общее представлении о поведении гиперповерхности функции в гиперпространстве .
Метод Эйлера основан на использовании необходимых и достаточных условиях существования экстремума.
Алгоритм метода заключается в следующем.
1. Берут частные производные оптимизируемой функции по каждой переменной хi и, в соответствии с необходимым условием для точки локального экстремума, приравнивают нулю: ;
3. Берут все вторые частные и смешанные производные от функции и вычисляют их в каждой стационарной точке. По вычисленным производным формируют матрицу Гесса для каждой стационарной точки.
4. Исследуют характер матриц Гесса и устанавливают вид соответствующих стационарных точек:
5. Вычисляют значения функции в каждом локальном минимуме. Затем путём сравнения вычисленных значений находят абсолютный минимум функций.