Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод градиентного спуска с постоянным шагом

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

Стратегия данного метода состоит в построении последовательности точек , таких, что

.

Точку задаёт пользователь. Остальные точки последовательности вычисляются по правилу:

,

где - градиент функции , вычисленный в точке .

Величина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия

или

.

Теорема 1 Пусть функция дифференцируема и ограничена снизу на , а ее градиент удовлетворяет условию Липшица

,

где L>0. Тогда при произвольной начальной точке для метода градиентного спуска с постоянным шагом имеем

.

Эта теорема гарантирует сходимость последовательности к стационарной точке , где . Следовательно, найденную в результате применения метода точку нужно дополнительно исследовать с целью ее классификации.

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

где - константы.

Алгоритм:

Шаг 1. Задать: начальную точку -малые положительные числа, M – предельное число итераций. Найти градиент в произвольной точке.

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

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

Шаг 4. Проверить выполнение критерия окончания :

а) если критерий выполняется, , расчет окончен;

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

Шаг 5. Проверить условие :

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

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

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

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

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

(или ):

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

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

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

:

а) если выполняются оба условия в двух последовательных итерациях с номерами k и k -1, то расчет окончен, найдена точка ;

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

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

Рисунок 4.1.

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

.

Если функция выпукла (строго выпукла), то есть найденное приближение точки .

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

 

Пример: Методом градиентного поиска с постоянным шагом найти локальный минимум функции

Решение:

1. Зададим , M: , , M =10.

Найдем градиент функции в произвольной точке

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

30. Вычислим : .

40. Проверим условие : .

50. Проверим условие : .

60. Зададим .

70. Вычислим : .

80. Сравним с . Имеем . Следовательно, условие для k = 0 не выполняется. Зададим и повторим шаги 7 и 8.

701. Вычислим : .

801. Сравним с . Вывод: . Переходим к шагу 9.

90. Вычислим и :

.

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

31. Вычислим : .

41. Проверим условие : .

51. Проверим условие : .

61. Зададим .

71. Вычислим :

.

81. Сравним с . Вывод: . Переходим к шагу 9.

91. Вычислим и :

.

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

32. Вычислим : .

42. Проверим условие : .

52. Проверим условие : .

62. Зададим .

72. Вычислим :

.

82. Сравним с . Вывод: . Переходим к шагу 9.

92. Вычислим и :

.

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

33. Вычислим : .

43. Проверим условие : .

53. Проверим условие : .

63. Зададим .

73. Вычислим :

.

83. Сравним с . Вывод: . Переходим к шагу 9.

93. Вычислим и :

.

Условия выполнены при k = 2, 3. Расчет окончен. Найдена точка ; .

Функция является дважды дифференцируемой, поэтому проведем проверку достаточных условий минимума в точке . Для этого проанализируем матрицу Гессе . Матрица постоянна и положительно определена, т.к. оба ее угловых минора и положительны. Следовательно, точка есть найденное приближение точки локального минимума , а значение есть найденное приближение значения . Заметим, что условие , есть одновременно условие строгой выпуклости функции на . Следовательно, , есть найденные приближения точки глобального минимума функции и ее наименьшего значения на .

Геометрическая интерпретация решения задачи представлена на рисунке 4.2.

Рисунок 4.2.


Дата добавления: 2015-07-20; просмотров: 618 | Нарушение авторских прав


Читайте в этой же книге: Общие принципы методов поиска безусловного экстремума | Метод конфигураций (метод Хука - Дживса) | Метод деформируемого многогранника | Метод вращающихся координат (метод Розенброка) | Метод сопряженных направлений (метод Пауэлла) | Метод Гаусса - Зейделя | Метод Ньютона | Метод Ньютона - Рафсона | Метод Марквардта | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Методы первого порядка| Метод наискорейшего градиентного спуска (Метод Коши)

mybiblioteka.su - 2015-2024 год. (0.015 сек.)