<<
>>

МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА

Постановка задачи

Пусть дана функция /(х) , ограниченная снизу на множестве Яп и имею­щая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции /(х) на множестве допус­тимых решений X = Яп, т.е.

найти такую точку х* еЯп, что

Стратегия поиска

Стратегия решения задачи состоит в построении последовательности точек {х*|, к = 0,1,..., таких, что /(х*+1) lt; /(**)» ^ = 0,1,... . Точки последовательно­сти {х*} вычисляются по правилу

хк+1 = хк - гк У/(х*), (6.3)

где точка х° задается пользователем; величина шага ** определяется для каждого

значения к из условия

Ф(*к) = /(** - ‘к ?/(**)) -* ™ • (6.4)

Решение задачи (6.4) может осуществляться с использованием необходи­мого условия минимума = о с последующей проверкой достаточного условия шк

минимума Такой путь может быть использован либо при достаточно

простой минимизируемой функции lt;р(**), либо при предварительной аппрокси­мации достаточно сложной функции lt;р(/*) = /|х* полиномом Р^к)

(как правило, второй или третьей степени), и тогда условие = 0 замещается

№ л л й1Р Л

условием —- * 0, а условие —gt; 0 - условием —- gt; 0.

Жк (Ик

Другой путь решения задачи (6.4) связан с использованием численных ме­тодов, когда ищется ^ гт|т^lt;р(**) = ^ при /|х* У/*(х*)| (см* разд* 5.1). Гра­

ницы интервала [а, 6] задаются пользователем. При этом степень близости най­денного значения к оптимальному значению Рк, удовлетворяющему условиям

= 0, gt; 0, зависит от задания интервала \а,Ь] и точности методов одно-

dtk dtl

мерной минимизации [28].

Построение последовательности jx*J ,к = 0,1,..., заканчивается в точке

хк, для которой I V/(x*)| lt;еь где ej - заданное число, или, если кgt; М, М - предельное число итераций, или при двукратном одновременном выполнении неравенств ||x*+1-x*|lt;s2, |/(x*+1)-/(x*)| lt; вг» где е2 - малое положительное

число. Вопрос о том, может ли точка хк рассматриваться как найденное при­ближение искомой точки локального минимума х* решается путем дополни­тельного исследования.

Алгоритм

Шаг 1. Задать х°, ej gt; 0, б2gt; 0, предельное число итераций М. Найти гра­диент функции в произвольной точке V/(x) = I ^ ^ d/OO

V дх\ дхп

Шаг 2. Положить к = 0.

Шаг 3. Вычислить

Шаг 4. Проверить выполнение критерия окончания || V/(x* )i lt;ej:

а) если критерий выполнен, то х* = хк;

б) если критерий не выполнен, то перейти к шагу 5.

Шаг 5. Проверить выполнение неравенства кgt; М:

а) если неравенство выполнено, то х = хк;

б) если нет, то перейти к шагу 6.

Шаг 6. Вычислить величину шага t\ из условия Чgt;Ы = /(** - ‘к V/(x*)j -gt; nun.

Шаг 1. Вычислить xk+l = хк -t*k Шаг 8. Проверить выполнение условий

|x*+i _**||lt;(,2j |/(ж*+1)-/(ж*)|lt;е2:

а) если оба условия выполнены при текущем значении к и к = к -1, то расчет окончен, х* = xk+l;

б) если хотя бы одно из условий не выполнено, то положить к = к +1 и перейти к шагу 3.

Сходимость

Геометрическая интерпретация метода для п = 2 приведена на рис. 6.3.

Утверждение 6.2.

Пусть функция /(х) удовлетворяет условиям утвержде­ния 6.1. Тогда при произвольной начальной точке х° € Яп для метода наискорейшего градиентного спуска имеем | У/(х*)| -gt; 0 при к,оо [29].

Замечания 6.3.

1. Утверждение гарантирует сходимость последовательности |х*| к ста­ционарной точке х*, где = 0- Следовательно, найденная в результате при­

менения метода точка х* нуждается в дополнительном исследовании с целью ее классификации.

2. Метод наискорейшего спуска гарантирует сходимость последовательно­сти |х*| к точке минимума для сильно выпуклых функций [29].

Скорость сходимости

Оценки скорости сходимости получены только для сильно выпуклых функций, когда последовательность {х*} сходится к точке минимума функции

/(х) со скоростью геометрической прогрессии (линейная сходимость):

||х*+1 -х*!*'^ ||х* -**||» где Л/и т - оценки наибольшего и наименьшего

собственных значений матрицы #(х) функции /(х) [29].

Замечания 6.4.

1. Процедура решения задачи совпадает с описанной в разд. 6.1.

2. Относительно процедуры поиска глобального минимума функции /(х) остается справедливым замечание 6.2.

Пример 6.2. Найти локальный минимум функции f(x) = 2х2 + ххх2 + х2.

? I. Определение точки хк, в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим х°, е,, е2, М : х° = (0,5;1)Г; = ОД; е2 = 0,15; М « 10. Найдем

градиент функции в произвольной точке V/(x) = (4xt + х2;х{ + 2х2)т.

2. Положим к = 0.

3°. Вычислим V/(x0): V/(x°) = (3;2,5)r.

4°. Вычислим |v/(x°)|: | V/(x°)| = 3,9 gt;0,1. Переходим к шагу 5.

5°. Проверим условие к^М: к = 0lt;\0 = М, переходим к шагу 6.

6°. Следующая точка находится по формуле

х1 = *° - t0Vf(x°) = (0,5; 1)г - /0(3; 2,5)г = (0,5 - 3*0; 1 - 2,5. t0)T.

Подставим полученные выражения х* = 0,5 - 3*0 , х2 = 1 - 2,5 • /0 для коор­динат в f(x): ф(*0) = 2• (0,5-3*о)2 + (0,5-3*0)• (1 -2,5• *0) + (1 -2,5• /0)2. Найдем

минимум функции ф(*0) по *0 с помощью необходимых условий безусловного экстремума:

= 4. (0,5 - 3f0) • (-3) + (-3) • (1 - 2,510) + (-2,5) • (0,5 - 3/0) + 2 • (1 - 2,5 • /0) • (-2,5) =

dt0

= -15,25 + 63,25 -*о=0. Отсюда = 0,24. Так как ^ = 63,25 gt; 0, найденное

Щ

значение шага обеспечивает минимум функции ф(*0) по *0.

Заметим, что можно получить формулу для вычисления наилучшей вели­чины шага t*k на любой итерации из условия

ф(М = /(** - tk V/(x*)) -gt;#9632; min.

Имеем

Vf[xk) = (4х,* + х$; х,* + х$ ; хк - tkVf(xk) = |х* - tk {4xf + xf); х* - tk (xf + xf)] , ф(/*) = 2(х!* -tk(4xf +xf))2 +(x,* -f*(4x,‘ + xf))(xf-tk(xf + xf)) +

+(4-ы4+4))2-

Из условия ш о получаем

dtk

______________ (4Х|* + х2* Г + (х,* + 1х2к f______________

4 (4х,* + х2* )* +2 (4х,* + х2* )(х,* + 2х2* )+ 2 (х,* + 2х2* ]Р Определим /о: *0 = 0*24 •

7°. Найдем х1 = х° - /5 У/(х°): х1 = (0,5; 1)г - 0,24(3; 2$)Т = (- 0,22; 0,4)г.

8°. Вычислим Цх1 -^°|- Ц*1 -х0|| = 0,937 gt;0,15. Вычислим [/(х1)-/(*°)|: |/(х‘)- /(х°)| = 1,83 gt; 0,15. Вывод: полагаем к = 1 и переходим к шагу 3.

31. Вычислим У/^х1): У/(х!| = (-0,48;0,58)Г.

41. Вычислим | У/(х1 )| = 0,752 gt; 0,1.

51. Проверим условие кgt; М: /с = 1 lt; 10 = Л/.

61. Определим /*: = 0,546 (см. п. 6°).

71. Найдем х2 = х1 - $ У/^х1):

х2 = (-0,22;0,4)Г - 0,546 (-0,48; 0,58)Г = (0,04;0,08)Г.

8*. Вычислим ||х2 -х‘|, |/(х2)- /(х')|:

|х2 - х‘| = 0,41 gt; 0,15; |/(х2)-/(х‘)| = 0,156 gt; 0,15.

Полагаем к = 2 и переходим к шагу 3.

32. Вычислим У/(х2): У/(х2) = (0,24;0,2)г.

42. Вычислим | У/(х2)||: |У/(х2)| = 0,312 gt; 0,1.

52. Проверим условие кpound; М: к = 2lt;10 = М.

6 2. Определим /5 = 0,24 (см. п. 6°).

72. Найдем х3 = х2 - г\ У/(х2):

х3 =(0,04;0,08)г -0,24 (0,24; 0,2)Г = (-0,0176;0,032)Г.

82. Вычислим |х3 — дс2||, |/(х3)-/(х2)|*

||х3 - х21| = 0,0749 lt; 0,15; | /(х3)- /(х2)| = 0,0116 lt; 0,15.

Полагаем к = 3 и переходим к шагу 3.

33. Вычислим У/(х3|: У/(х3) = (-0,012;-0,0816)Т.

43. Вычислим |у/(*3)|: ||у/(х3)|| = 0,082 lt;0,1. Расчет окончен. Найдена

точка х3 = (-0,0176;0,032)Г, /(*3) = 0,00127. На рис. 6.2 полученные точки выде­лены и соединены сплошной линией.

II. Анализ точки х3.

В примере 6.1 было показано, что функция /(х) является строго выпуклой и, следовательно, точка х3 является найденным приближением точки глобаль­ного минимума х*. #9632;

6.2.

<< | >>
Источник: Пантелеев А. В., Летова Т. А.. Методы оптимизации в примерах и задачах: Учеб. посо- бие/А. В. Пантелеев, Т. А. Летова. — 2-е изд., исправл. — М.: Высш. шк.,— 544 с.: ил.. 2005

Еще по теме МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА:

  1. Метод наискорейшего спуска
  2. Методы спуска. Приближенное решение задач выпуклого программирования градиентным методом
  3. МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМ
  4. ГРАДИЕНТНЫЕ МЕТОДЫ
  5. 11.1. Общая схема градиентных методов. Понятие функции релаксации
  6. 10.1. Методы покоординатного спуска
  7. 10.2. Методы обобщенного покоординатного спуска
  8. 6. ГРАДИЕНТНЫЕ МЕТОДЫ
  9. 6. Градиентные методы
  10. 10.3. Реализация методов обобщенного покоординатного спуска
  11. МЕТОД ПОКООРДИНАТНОГО СПУСКА
  12. 10.5. Реализация методов обобщенного покоординатного спуска на основе рекуррентных алгоритмов оценивания
  13. 11.2. Классические градиентные схемы
  14. 10.4. Алгоритмы обобщенного покоординатного спуска