<<
>>

11.2. Классические градиентные схемы

Рассмотрим некоторые конкретные методы (11.2) и отвечающие им функции релаксации.

Простой градиентный спуск (ПГС). Формула метода

+ 1 = ХК _ _ С0П81)

Соответствующая функция релаксации

Л(Л) = 1 - Кк линейна и представлена на рис.

11.2.

ПГС имеет вид

(11.12)

(11.13)



Рис. 11.2. Функция релаксации метода простого градиентного спуска


Пусть собственные значения матрицы Ак расположены в замкнутом ин­тервале [т, М], причем 0 < га < М, так что г|(х) = М / т» 1. В этом слу­чае условие (11.9), очевидно, выполняется, а неравенства (11.7) сводятся к требованию

|/г(Л.)| ... > > > ... > сг|Л„|,

а » 1, характерные для овражной ситуации. Тогда для точки хк е где — дно оврага, имеем согласно (11.10)

/=п-г+1

что может быть существенно меньше Са.

В результате соответствующие малым собственным значениям из окре­стности Х = 0 слагаемые в выражении (11.8) почти не будут убывать, а продвижение будет сильно замедленным. Это и определяет низкую эф­фективность метода (11.12).

В области X < О функция (11.13) удовлетворяет условиям релаксации при любом значении параметра Л. Параметр Л в методе ПГС выбирается из условия монотонного убывания функционала на каждом шаге итераци­онного процесса. При отсутствии убывания величина Л уменьшается до восстановления релаксационности процесса. Существуют различные стратегии выбора Л, однако при больших т\ все эти методы, включая и метод наискорейшего спуска

хкн = а^ тт - М'(хк)],

Л>0

малоэффективны даже при минимизации сильно выпуклых функциона­лов. Так же, как и в методе покоординатного спуска, здесь возможна си­туация "заклинивания", представленная на рис. 11.3.

Рис. 11.3. "Заклинивание" метода простого градиентного спуска: Дх;") > Дх;')


Как указывалось в разд. 9.2, метод ПГС представляет определенный ин­терес как средство оценки локальной степени овражности в окрестности точки замедления алгоритма. Выведем соответствующие соотношения.

Пусть замедление метода ПГС при минимизации некоторого функцио­нала У(х) произошло в окрестности некоторой точки х°. Тогда можно предположить, что достаточно длинный отрезок последовательности {хА}, построенный из точки хс, будет оставаться в области ||х - х°|| < С о и для J{x) справедлива квадратичная аппроксимация

Дх)=1/2(Ах,х)-(Ь,х). (11.15)

Метод (11.12) для аппроксимации (11.15) примет вид

хк+{ = хА' - к{Ахк - Ъ) = Вхк + g, (11.16)

где В = Е - ; # = кЬ.

Записывая (11.16) для двух последовательных номеров к и вычитая полу­ченные равенства, приходим к соотношению

ук = - хк = В(хкк-1) = Вк1-х°) = Вку\ (11.17)

Согласно степенному методу определения максимального собственного числа симметричной матрицы в результате проведения процесса (11.17) может быть получена оценка максимального собственного числа матри­цы В.

||/+,||/1|/||шах(5)| (* -> со). (11.18)

Пусть шаг Л в итерационном процессе (11.16) выбирается из условия ре- лаксационности, тогда можно заключить, что И = 21 М. Пусть ^(А) е е [-га, М], М > т> 0. В результате имеем шах|Ху(5)| = 1 + тк. Следова­тельно, для достаточно больших к

Ц/+11| /1|/1| = р\хк+{)|| / \\Г(хк)|| = \1к «1 + тк (11.19)

Приходим к требуемой оценке степени овражности функционала У(х) в окрестности точки х°:

Г|( х°) = М/т = 21(11к- 1).

Рассуждая аналогично для случая \{А) е 0[га,М], получаем вместо (11.19) равенство рк~\ -тк 0, либо при X < 0. Положение ее при Л = 0 соответствует остановке процесса. В указанных условиях эффективный выбор кк оказывается затруднительным.

Аналогичным недостатком обладают многие из аппроксимирующих ме­тод Ньютона квазиньютоновских алгоритмов и совпадающих с ними при минимизации квадратичных функционалов методов сопряженных направлений. Все эти методы по эффективности приближаются к методу ПГС, если функционал /(х) в окрестности хк не является выпуклым.

Традиционное возражение против метода Ньютона, связанное с необхо­димостью выполнения операции вычисления вторых производных целе­вого функционала, для реальных задач оптимизации оказывается менее существенным.

Метод Левенберга. Если известно, что собственные значения матрицы Ак расположены в интервале [-га, М], где М » га, то можно построить ме­тод, имеющий нелинейную функцию релаксации (рис. 11.5)

Я(Х) = Л' / (Л' + X) (Л' > 0, Л = 1 / Л'), (11.21)

удовлетворяющую требованиям (11.7) при \/Х е [-га, М\, если Ы > га.

Соответствующий метод предложен Левенбергом и имеет функцию

Н(Х, К) = [1 - ад] / Х = (Л' + ху].

Схема метода (11.2) с указанной функцией Н имеет вид

= хк - [Н'Е + J\xk)l]J\xk). (11.22)

Скаляр Л' на каждом шаге итерационного процесса подбирается так, чтобы матрица h,E + Jf\xk) была положительно определена и чтобы

|**+1 - ск' гДе ск может меняться от итерации к итерации.

Я ▲
--------- 1-

—/71

Рис. 11.5. Функция релаксации метода Левенберга

X

Из последнего выражения следует, что мы имеем, по существу, классиче­скую регуляризованную форму метода Ньютона с параметром регуляри­зации Л'. Данная форма метода Ньютона применялась Левенбергом для решения задач методом наименьших квадратов. Существенно позже данный метод применялся Маркуардтом для решения общих задач нели­нейной оптимизации и иногда встречается его описание в литературе под названием "метод Маркуардта".

(11.24)

Реализация метода (11.22) сводится к решению на каждом шаге линейной алгебраической системы

[Л'Е+ /"(**)] А** =-Ахк) (Ахк±хк+1к). (11.23)

Главный недостаток метода заключается в необходимости достаточно точного подбора параметра А', что сопряжено с известными вычисли­тельными трудностями. Значение ш, как правило, неизвестно и не может быть вычислено с приемлемой точностью. При этом оценка для ш суще­ственно ухудшается при возрастании размерности п. Лучшее, что обычно можно сделать на практике, это принять

//>тах

<< | >>
Источник: Черноруцкий И. Г.. Методы принятия решений. — СПб.: БХВ-Петербург, — 416 с.. 2005

Еще по теме 11.2. Классические градиентные схемы:

  1. ГРАДИЕНТНЫЕ МЕТОДЫ
  2. 11.1. Общая схема градиентных методов. Понятие функции релаксации
  3. 6. ГРАДИЕНТНЫЕ МЕТОДЫ
  4. 6. Градиентные методы
  5. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКА
  6. МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМ
  7. Глава 11. Градиентные стратегии конечномерной оптимизации
  8. Методы спуска. Приближенное решение задач выпуклого программирования градиентным методом
  9. Схемы сертификации
  10. Пропозициональные схемы
  11. 13.4. Пенсионные схемы
  12. Аналитические схемы
  13. 6.5. Налоговые оптимизационные схемы
  14. ЛОГИКА И СПЕЦИФИКАЦИИ ОРГАНИЗАЦИОННОЙ СХЕМЫ
  15. 1.5. Финансовые схемы
  16. Логика схемы
  17. 39.КАКОВЫ ОСНОВНЫЕ СХЕМЫ ОТНОШЕНИЙ ИНДИВИДОВ ПРИ САМООРГАНИЗАЦИИ?
  18. 4.5. Модель структурной схемы
  19. Схемы проектного финансирования
  20. Статья 13. Реализация схемы территориального планирования Российской Федерации