 |
Метод наискорейшего спуска
|
|
|
|
Пусть 
- дифференцируемая функция, заданная на 
, а 
- некоторая текущая точка. Правил, касающихся выбора начальной точки (начального приближения) 
, не существует, однако по возможности она должна находиться вблизи от искомого оптимального плана 
. Если 
- нестационарная точка (т. е. 
), то при движении в направлении 
функция 
на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения от шагового множителя 
, полагая 
(9)
или, в координатной форме,
. (10)
Чтобы добиться наибольшего из возможных значений f при движении по направлению , нужно выбрать такое значение 
, которое максимизирует функцию 
. Для вычисления , используется необходимое условие экстремума 
. Заметим, что если для любого 
, то функция не ограничена сверху (т. е. не имеет максимума). В противном случае, в силу (10) получаем
, (11)
что, в свою очередь, дает
. (12)
Если считать, что следующая точка 
соответствует оптимальному значению 
, то в ней должно выполняться условие , и следует находить из условия 
или
. (13)
Условие (13) означает равенство нулю скалярного произведения градиентов функции 
точках 
и .Геометрически это условие может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на Рис. 2.2. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке вектор 
, являясь градиентом, перпендикулярен линии уровня, проходящей через данную точку. Следовательно, вектор 
является касательным к этой линии. Таким образом, движение в направлении градиента следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции.
|
|
|
После того как точка найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора должны быть близки к нулю.
Метод дробления шага
Для нахождения шага l, в методе наискорейшего спуска требуется решить уравнение (13), которое может оказаться достаточно сложным. Поэтому часто ограничиваются «подбором» такого значения l, что 
. Для этого задаются некоторым начальным значением 
(например, 
и проверяют условие 
. Если оно не выполняется, то полагают
и т. д. до тех пор, пока не удается найти подходящий шаг, с которым переходят к следующей точке . Критерий завершения алгоритма, очевидно, такой же, как и в методе наискорейшего спуска.
Оптимизационные задачи для выпуклых функций
Общим недостатком рассмотренных выше методов безусловной оптимизации было, с одной стороны, то, что они позволяют отыскивать только точки возможного локального экстремума, а с другой - то, что найденные решения могут существенно зависеть от начального приближения. Поиск глобального оптимума подразумевает перебор найденных точек, который, в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений .
Рис. 2.1
Рис. 2.2
Однако существует один класс функций, для которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции.
Определение. Функция 
называется выпуклой в области D, если для любых двух точек 
и любого 
выполняется неравенство
(14)
если же
(15)
то функция называется вогнутой.
Геометрический смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на Рис. 2.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки 
и 
, а график вогнутой - выше этого отрезка.
|
|
|
Рис. 2.3
Можно доказать, что достаточным условием выпуклости функции 
является положительная определенность матрицы
называемой также матрицей Гессе, во всех точках 
. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе. В частности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства 
.
Как следует из геометрической интерпретации, для выпуклой функции локальный экстремум, если он существует, совпадает с глобальным. Справедлива теорема.
Теорема 2.2. Если выпуклая (вогнутая) на функция и 
, то - точка глобального минимума (максимума)
Доказательство. Доказательство достаточно провести для случая вогнутой функции, т. к. для противоположного случая оно будет аналогичным с точностью до знака.
Пусть 
- произвольная точка, отличная от точки . Тогда, для любого 
, в силу вогнутости функции выполнятся неравенство
откуда следует
.
Если ввести вектор 
и обозначить 
, то длина вектора 
будет равна 
. Следовательно,
.
Устремляя 
и учитывая, что вектор l сонаправлен с , получим
.
По условию теоремы . Это означает, что для любого вектора l (а, следовательно, для любой точки х) согласно формулы, выражающей производную по направлению через градиент, находим
.
Следовательно, для любой точки х отличной от , справедливо неравенство 
, т.е. - точка глобального максимума.
Поскольку выпуклые функции обладают столь «полезными» оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел математического программирования получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве.
|
|
|
