Метод наискорейшего спуска

Пусть - дифференцируемая функция, заданная на , а - некоторая текущая точка. Правил, касающихся выбора начальной точки (начального приближения) , не существует, однако по возможности она должна находиться вблизи от искомого оптимального плана . Если - нестационарная точка (т. е. ), то при движении в направлении функция на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения от шагового множителя , полагая

(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 (а, следовательно, для любой точки х) согласно формулы, выражающей производную по направлению через градиент, находим

.

Следовательно, для любой точки х отличной от , справедливо неравенство , т.е. - точка глобального максимума.

Поскольку выпуклые функции обладают столь «полезными» оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел математического программирования получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве.

Не нашли, что искали? Воспользуйтесь поиском по сайту: