Все известные численные методы отыскания экстремума нелинейных функций в зависимости от используемой информации для получения следующей точки можно разделить на три основные группы.
Прямые методы, использующие только текущие значения оптимизируемой функции.
Методы первого порядка, использующие дополнительно и значения первой производной функции.
Методы второго порядка, требующие знания и второй производной оптимизируемой функции.
Рассмотрим сначала поисковые методы оптимизации без ограничений, а потом перейдем к рассмотрению методов оптимизации с ограничениями (т.е. задач НП).
Градиентные методы представляют собой одну из наиболее распространенных групп методов поиска безусловного экстремума. Все они используют значения градиента функции . Итак, они принадлежат к методам первого порядка.
Пусть требуется найти
Обозначим вектор-градиент функции в точке через :
Пусть поиск экстремума начинается с некоторой произвольной точки . Тогда движение представляющей точки по градиентному методу описывается следующимим рекуррентным соотношением:
(6.1.1)
где – величина шага на -й итерации.
В различных вариантах градиентного метода используются различные способы выбора скаляра . Этот выбор может, в частности, зависеть и от степени близости к точке минимума .
В том случае, если величина шага определяется из условия
(6.1.2)
где
то соответствующий метод носит название метода наискорейшего спуска (он предложен О.Коши).
Согласно этому методу, в качестве нового приближения выбирается такая точка, расположенная в направлении , в которой функция принимает минимальное значение. Затем определяется новое значение градиента в точке , и процедура повторяется вновь. Метод наискорейшего спуска часто называют полношаговым методом.
Заметим, что метод наискорейшего спуска в общем случае не обладает какими-то оптимальными свойствами, например, способностью отыскивать оптимальное решение за минимальное число шагов или при минимальном объеме вычислений. Это можно проиллюстрировать на примере минимизации квадратичной функции:
минимизировать (6.1.3)
где матрица – положительно определенная. В этом случае для всех и и, следовательно, достигает минимума при .
Так как
(6.1.4)
то в соответствии с методом наискорейшего спуска нужно найти
(6.1.5)
Возьмем производную в выражении (6.1.5) по и получим оптимальную величину шага:
Если обратиться к геометрической интерпретации (рис.6.1), то станет ясно, что луч , исходящий из точки в направлении , не проходит через точку минимума . Следовательно, за один шаг точки нельзя достигнуть , если только точка не оказывается лежащей на одной из полуосей эллипса, задаваемого функцией . Если же вести поиск по направлению , то искомой точки можно достигнуть за один шаг при , так как
Рис. 6.1. Рис. 6.2.
Таким образом, в данном случае метод наискорейшего спуска оказывается хуже, чем метод, согласно которому поиск производится в направлении . При использовании метода наискорейшего спуска траектория приближения к точке будет зигзагообразной.
Введем вектор . Тогда вектор-градиент ортогонален к вектору , поскольку был выбран путем минимизации . Таким образом, последовательность точек , вырабатываемых методом наискорейшего спуска, зигзагообразно приближается к точке (рис.6.2). Заметим, что вектор на рис.6.2 параллелен, вектор параллелен и т.д.
Градиентные методы, включая метод наискорейшего спуска, используют линейную аппроксимацию целевой функции (6.1.1). Методы вторых производных, в частности метод Ньютона, возникли из квадратичной аппроксимации .
Рассмотрим схему Ньютона. Направление поиска в методе Ньютона выбирается следующим образом. Найдем квадратичную аппроксимацию функции в окрестности точки , путем разложения ее в ряд Тэйлора:
(6.1.6)
где – матрица Гессе функции , представляющая собой матрицу частных производных в точке
(6.1.7)
Заменим в разложении (6.1.6) на , а на и получим квадратичную аппроксимацию через
Найдем направление , в котором будет минимальна. Для этого продифференцируем по каждой из компонент , и приравняем к 0 полученные выражения. В результате приходим к соотношениям
(6.1.8)
где – матрица, обратная матрице Гессе в точке . Тогда переход от в по методу Ньютона будет описываться соотношением
(6.1.9)
Заметим, что в (6.1.9) как направление, так и величина шага определены. Если – квадратичная функция вида , то и для достижения точки минимума достаточно только одного шага. Но в общем случае минимума нельзя достичь за один шаг, и поэтому уравнение поиска (6.1.9) обычно приводят к стандартному виду
(6.1.10)
где – единичный вектор, путем введения длины шага как параметра:
(6.1.11)
Уравнение (6.1.11) применяется итеративно до тех пор, пока не будет удовлетворен критерий окончания процесса.
Критерий, гарантирующий сходимость метода Ньютона, в предположении, что – дважды дифференцируемая функция, заключается в том, что матрица, обратная матрице Гессе, должна быть положительно определенной. Как известно, матрица – положительно определена для строго выпуклых функций. В случае функции более общего вида метод Ньютона может привести к направлениям поиска, расходящимся от точки минимума.
Это объясняется тем, что симметричная матрица положительно определена тогда и только тогда, когда все ее собственные значения – положительны.
Если все собственные значения матрицы положительны, то локальная квадратичная аппроксимация в точке представляет собой эллипсоид. С другой стороны, если пара собственных значений имеет противоположные знаки, то, как видно из рис.6.3, квадратичная аппроксимация представляет собой седло. В этом случае
Рис. 6.3.
вектор, определяемый уравнением (6.1.11), будет направлен к седловой точке, вместо точки минимума функции .
Рассмотрим геометрическую интерпретацию локальной квадратичной аппроксимации и проиллюстрируем важность требования положительной определенности . Квадратичная функция произвольного вида может быть преобразована к новой системе координат путем переноса начала системы координат в точку экстремума функции и последующего поворота осей для достижения симметрии.
Рис. 6.4.
Указанные преобразования системы координат к главным осям позволяют получить выражения для целевой функции в каноническом виде относительно координат , причем это выражение значительно проще исходного, так как в нем отсутствуют члены первого порядка и перекрестные члены вида .
Рассмотрим случай, когда.
Квадратичная аппроксимация функции будет иметь вид
(6.1.12)
Уравнение (6.1.12) преобразуется в каноническое уравнение вида
(6.1.13)
где – значение в искомой точке минимума. На рис.6.4 представлено преобразование системы координат к главным осям, где иллюстрируется результат масштабирования так, что линии уровня функции становятся окружностями.
Элементы матрицы Гессе целевой функции связаны с коэффициентами уравнения (6.1.12) очевидными соотношениями:
С другой стороны, коэффициенты в уравнении (6.1.13) являются собственными значениями матрицы . Матрица, обратная , дает меру кривизны функции в окрестности точки . Исследуем характер функции в зависимости от знаков и соотношения между ними. Соответствующие результаты представлены в табл.6.1 (а-е). В частности, если , то линии уровня – эллипсы, причем если , то линии уровня вытягиваются вдоль оси , и наоборот. Если центр расположен на оси на бесконечности и коэффициент - отрицателен, то линии уровня представляют собой параболы (рис.6.3,е).
Каждая из вырожденных поверхностей, называемых оврагом или хребтом, имеет место, когда один из коэффициентов по абсолютной величине много больше другого.
№ |
Соотношение между коэффициен-тами |
Знаки |
Тип линий уровня |
Геометричес-кая интерпретация поверхности |
Характерис-тика центральной точки |
Иллюстра-ция поверх-ности |
|
1 |
|
- |
- |
Окруж-ность |
Круговой холм |
Максимум |
Рис. 6.3, а |
2 |
|
+ |
+ |
Окруж-ность |
Круговая впадина |
Минимум |
Рис. 6.3, а |
3 |
|
- |
- |
Эллипс |
Эллиптичес-кий холм |
Максимум |
Рис. 6.3, б |
4 |
|
+ |
+ |
Эллипс |
Эллиптическая впадина |
Минимум |
Рис. 6.3, б |
5 |
|
+ |
- |
Гипербола |
Симметричное седло |
Седловая точка |
Рис. 6.3, в |
6 |
|
- |
+ |
Гипербола |
Симметричное седло |
Седловая точка |
Рис. 6.3, в |
7 |
|
+ |
- |
Гипербола |
Вытянутое седло |
Седловая точка |
Рис. 6.3, г |
8 |
|
- |
Прямая |
Стационарный хребет1 |
Нет |
Рис. 6.3, д |
|
9 |
|
+ |
Прямая |
Стационарный овраг1 |
Нет |
Рис. 6.3, д |
|
10 |
|
- |
Парабола |
Поднимающийся хребет1, 2 |
На |
Рис. 6.3, е |
|
11 |
|
+ |
Парабола |
Спадающий овраг1, 2 |
На |
Рис. 6.3, е |
1 – вырожденная поверхность.
2 – к каноническому выражению для функции нужно добавить два линейных члена.
Допустим, что необходимо минимизировать и процесс минимизации начинается в точке с начальным направлением . Тогда вектор определяется соотношением
(6.1.14)
где длина шага находится из условия минимума относительно
(6.1.15)
После того как вычислены и , для продолжения процесса минимизации , необходимо выбрать новое направление. Это направление называется сопряженным к старому направлению , если выполняется условие:
В общем случае система линейно независимых направлений называется сопряженной по отношению к некоторой положительно определенной матрице , если
(6.1.16)
Отметим, что сопряженность – это понятие, аналогичное к ортогональности, так как если , где – единичная матрица, то в соответствии с (6.1.16) .
Для некоторой матрицы всегда существует, по крайней мере, одна система из взаимосопряженных направлений, так как сами собственные векторы матрицы представляют такую систему.
В дальнейшем при использовании сопряженных направлений нам потребуется следующее полезное соотношение для квадратичной функции:
(6.1.17)
Чтобы убедиться в его справедливости, рассмотрим матрицу . Умножив ее справа на и положив , получим следующее соотношение:
(6.1.18)
Таким образом, соотношение (6.1.17) доказано.
Справедливо следующее утверждение [2; 50]: если используются сопряженные направления, то любая квадратичная функция переменных может быть минимизирована ровно за шагов, по одному шагу в каждом из сопряженных направлений. При этом порядок использования направлений несущественен.
Докажем это утверждение.
Пусть целевая функция задана в виде . При этом , и в точке минимума .
На -м шаге поиска в результате применения формул (6.1.14) получим
(6.1.19)
На каждом шаге, минимизируя по в направлении , определяем значения длины шага
В результате для получим выражение
(6.1.20)
Так как все произведения равны нулю (при ), то
Таким образом,
(6.1.21)
Выразим векторы через систему сопряженных векторов :
(6.1.22)
(6.1.23)
Подставив (6.1.22) и (6.1.23) в (6.1.21), получим
Таким образом, точка – результат –го шага поиска, совпадает с точкой минимума . Итак, утверждение доказано.
Введем следующее определение. Метод обладает свойством квадратичного окончания, если его применение гарантирует достижение минимума квадратичной функции за точно определенное число шагов. Так, в случае метода сопряженных направлений требуется шагов, тогда как в методе Ньютона – один шаг.
Рассмотрев основные свойства метода сопряженных направлений, перейдем к описанию основаных на этом понятии алгоритмов.
Метод сопряженного градиента. В методе сопряженного градиента (Флетчера-Ривса) строится последовательность направлений поиска, являющихся линейными комбинациями текущего направления и предыдущих направлений , причем таких, чтобы сделать направления поиска сопряженными. При этом для вычисления нового направления поиска в точке используется только текущий и предпоследний градиенты.
Рассмотрим идею метода. Пусть исходным направлением поиска будет . Положим и построим
(6.1.24)
где – весовой коэффициент, который выбирается так, чтобы сделать векторы сопряженными по отношению к :
(6.1.25)
Чтобы исключить из (6.1.25), воспользуемся очевидным соотношением
где а также соотношением
Следовательно,
Вследствие рассмотренных свойств все перекрестные члены исчезают (равны нулю) так, что
(6.1.26)
Направление поиска представляется в виде линейной комбинации , причем так, чтобы оно было сопряженным к . Повторив вышеприведенные выкладки для случаев получим:
Рис. 6.5.
В заключение приведем вычислительную схему алгоритма.
В точке вычисляем .
На -м шаге с помощью одномерного поиска в направлении находим минимум . Это определяет точку .
|
Направление определяется из соотношения
(6.1.28)
После –й итерации (при ) процедура циклически повторяется с заменой на .
Алгоритм заканчивается, когда , где – произвольная, достаточно малая константа.
Достоинством алгоритма сопряженных градиентов является то, что здесь не требуется находить обратную матрицу . Кроме того, соответствующая программа для ЭВМ требует относительно небольшого объема памяти.
Траектория движения представляющей точки при использовании метода сопряженных градиентов для минимизации функции Розенброка приводится на рис.6.5, числа возле точек траектории обозначают номера итераций.