<<
>>

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

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

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

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

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

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

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

хк+1 =хк _,Лу/(х*), к = 0,1,... , (6.1)

где точка х° задается пользователем; ?/(**) - градиент функции /(х), вычис­ленный в точке хк; величина шага tk задается пользователем и остается посто­янной до тех пор, пока функция убывает в точках последовательности, что кон­тролируется путем проверки выполнения условия /(х*+1|- /(**) lt; 0 или

/(х*+1) - /(х*) lt; - е | У/(х* I ,0 lt; е lt; 1 [29]. Построение последовательности |х*|

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

lt;е2, где е2 - малое положительное число. Вопрос о том, может

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

Алгоритм

Шаг 1. Задать х°, 0lt;еlt;1, е^О, е2 gt; 0, М - предельное число итераций.

(дДх) дПх)\т

Найти градиент функции в произвольной точке У/(х) =

Зх, дх„ )

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

Шаг 3. Вычислить V/*(**)#9632;

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

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

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

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

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

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

Шаг 6. Задать величину шага ^k.

Шаг 7. Вычислить хк+1 = хк - ^ У/*^^

Шаг 8. Проверить выполнение условия

/(**!lt; 0 (или /(хЛ+1)~/(хА:)lt;-е| У/’(-^Д:)|2) •

а) если условие выполнено, то перейти к шагу 9;

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

Шаг 9. Проверить выполнение условий

|**+1 lt; е2» |/(х:А:+1)”/(хА:)| lt;е2:

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

* к.+1

расчет окончен, х = х ;

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

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


Сходимость

Утверждение 6.1. [29] Пусть функция /(х) дифференцируема и ограничена снизу на Rn, а ее градиент удовлетворяет условию Липшица IIV/M “ Y/Ху) || ^ ^ И х “ У И gt; У eRn, где Ьgt; 0. Тогда при произвольной началь­ной точке х° е Rn для метода градиентного спуска с постоянным шагом имеем

lim ||v/(x*)| = 0. (6.2)

k -gt; оо 11

Замечания 6.1.

1. Утверждение 6.1 гарантирует сходимость последовательности |x*J

к стационарной точке х*, где V/(x*J = 0.

Следовательно, найденная в результате

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

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

3. При решении примеров итерационный процесс подбора удачной вели­чины tk отражается в индексации шагов 7 и 8. Первый индекс совпадает с номе­ром к, а второй с числом делений текущей величины tk пополам.

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

Оценки скорости сходимости получены только для сильно выпуклых функций, когда последовательность |х*| сходится к точке минимума /(х) со скоростью геометрической прогрессии:

/(**) - /(**) * $*(/(*°) - /(*’)). |х*-дфс {Jqf,

где q е(0,1), С gt; О - константы [39].

Процедура решения задачи

1. Используя алгоритм градиентного спуска с постоянным шагом, найти

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

2. Провести анализ точки хк с целью установить, является ли точка хк найденным приближением решения задачи. Процедура анализа определяется на­личием у функции /(х) непрерывных вторых производных. Если /(х) е С2, то следует провести проверку выполнения достаточных условий минимума: #(х*)gt;0. Если н{хк^ gt; 0, то точка хк есть найденное приближение искомой

точки х*. Если /(х) 6 С1, то следует провести проверку функции /(х) на выпук­лость в szlig;-окрестности точки хк, используя критерий выпуклости для функций f(x) eC1: функция f(x) выпукла (строго выпукла) в том и только в том случае, если /(x + y);gt;/(x)+(V/(x),y), Vx,y eszlig;; (/(х + у) gt; /(x) + (v/(x),y)); (эквивалентное определение см. в § 1). Если функция /(х) выпукла (строго вы­пукла), то хк есть найденное приближение точки х*.

Замечание 6.2. Если требуется найти глобальный минимум функции /(*), то для строго выпуклой /(х) решение этой задачи аналогично поиску ло­кального минимума функции. В случае, когда /(х) имеет несколько локальных

минимумов, поиск глобального минимума осуществляется в результате перебора всех локальных минимумов.

Пример 6.1. Найти локальный минимум функции /(х) = 2х{2 + х{х2 + х22.

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

1. Зададим х°, г{, е2, М: х° = (0,5;1)Г, sj - 0,1; е2 = 0Д5; М = 10. Найдем

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

2. Положим pound; = 0.

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

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

5°. Проверим условие к gt; М: amp; = 0lt;10 = Л/. Переходим к шагу 6.

6°. Зададим /0 = 0,5.

7°. Вычислим х1: х1 =(0,5;1)г -0,5(3;2,5)Г = (-1;-0,25)Г;

8°. Сравним /(х1) с /|х°) = 2. Имеем /(х1) gt; /(*°)gt; Вывод: условие

/(x*+1 ) lt; /|х*) для к = 0 не выполняется. Зададим /° = 0,25, переходим к по­вторению шагов 7, 8.

701. Вычислим х1: х1 = (0,5; lf -0,25(3; 2$)Т = (- 0,25; 0375)Г; /(х1) = 0,171.

801. Сравним /(х1) и /(*0)- Вывод: /(х1) lt; /(*°)- Переходим к шагу 9.

9°. Вычислим Цх1 — х°| и l/^1)“/^0)^

||х! - х°| = 0,976 gt; 0,15; [/(х1)- /(х°)| = 1,829 gt; 0,15.

Вывод: полагаем ^ = 1 и переходим к шагу 3.

З1. Вычислим уф1): V^x1) = (-0,625;0,51)Г.

41. Вычислим I У/*(х1 )||: | V/Ix1 )|| = 0,81. Переходим к шагу 5.

51. Проверим условие кgt;М: А: = 1 lt; 10 = Л/. Переходим к шагу 6.

6 1. Зададим /| = 0,25.

7 1. Вычислим х2: х2 = (-0^5; 0375)[10]-0Д5(-0,625; 0^)Г = (-0,094; 0Д5)7; /(х[11]) = 0,056.

8 1. Сравним /(х2) с /(х1). Вывод: /(х2) lt; /(х1)- Переходим к шагу 9.

9 1. Вычислим ||х2 -х1|| и |/(х2)- /(х1)]:

||х2 - х!|» 0,2 gt; 0,15; [/(к2)“/!*1)! = °Д15 lt; °Д[12]-

Вывод: полагаем к = 2 и переходим к шагу 3.

3 2. Вычислим У/|х2): У/(х2) = (-0,126;0,406)Г.

4 2. Вычислим ||у/(х2)||: |у/(х2)| = 0,425 gt; ОД. Переходим к шагу 5.

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

6 2. Зададим /2 = 0Д5.

7 2. Вычислим х3: х3 = (-0,094;0,25)г-0,25(-ОД26;0,406)Г = (-0,063;ОД5)Г; /(х[13]) = 0,021.

8 [14]. Сравним /|х3| и /|х2|. Вывод: /(х3| lt; /(х2). Переходим к шагу 9.

9 2. Вычислим |х3 - х2| и |/(х3)-/(х2)|:

|х3 - х2| = 0,105 lt; 0,15; |/(х3)-/(х2)| = 0,035 lt; 0,15.

Вывод: полагаем к = 3 и переходим к шагу 3.

3 3. Вычислим У/^х3): У/(х3) = (-0,102;0,237)7\

Рис. 6.2


На рис. 6.2 полученные точки соединены пунктирной линией.

И. Анализ точки х4.

Функция /(х) = 2х\ +Х]Х2 +х22 является дважды дифференцируемой, по­этому проведем проверку достаточных условий минимума в точке х4. Для этого проанализируем матрицу Гессе Н - ^ . Матрица постоянна и является по­

ложительно определенной (т.е. Н gt; 0) , так как оба ее угловых минора Д х = 4 и Д2 =7 положительны. Следовательно, точка х4 = (-0,038;0,091)Г есть найденное приближение точки локального минимума х* = (0,0)г, а значение /(*4) = 0,0076 есть найденное приближение значения /(х*) = 0. Заметим, что условие Нgt; 0, есть одновременно условие строгой выпуклости функции /(х) = 2Х12 + Х^2 + х22 на Я2 (см. § 1). Следовательно, х4 = (-0,038;0,091)Г, /(*4) = 0,0076 есть найден­ные приближения точки глобального минимума /(х) и ее наименьшего значе­ния на В2. #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. Планирование бизнеса: создание желаемого будущего, шаг за шагом
  15. 9.5. МЕТОД ПОСТОЯННЫХ ПРОЦЕНТОВ
  16. 3.3.Методы разделения затрат на переменные и постоянные части.
  17. 7.2.2. Методы деления смешанных затрат на переменные и постоянные компоненты
  18. 10.4. Алгоритмы обобщенного покоординатного спуска