5.3. Методы с экспоненциальной релаксацией

Начало систематического изучения методов описываемого класса было положе­но в книге [49]. Далее рассматривается другой подход к построению и анализу алгбритмов, основанный на понятии функции релаксации.

Исходя из вышеизложенных требований к функциям релаксаций, естественно рассмотреть экспоненциальную зависимость вида (рис. 5.5)

для которой условие (5.7) выполняется при любых значениях параметра h. Кро­ме того реализуется предельное соотношение (5.9), что позволяет эффективно регулировать норму вектора продвижения независимо от расположения спек­тральных составляющих матрицы Gk на вещественной оси А,.

Функция (5.27) обобщает ранее рассмотренные функции релаксации и являет­ся в определенном смысле оптимальной. Действительно, разлагая экспонен­ту (5.27) в ряд Тейлора и ограничиваясь двумя первыми членами разложениями, получим

что совпадает с (5.22) при А - А'. И аналогично, полагая ехр (-ХА) = 1 - ХА, при­ходим к зависимости (5.13). Для достаточно больших значений параметра А име­ем ехр (-ХА) = 0 при любых X > т > 0, что позволяет говорить о вырождении ме­тода в классический метод Ньютона без регулировки шага.


Для представления схемы метода в виде (5.2) необходимо определить соответст­вующую функцию

однако возможны и другие способы выбора hk.

Принципиальная схема ЭР-метода была получена исходя из анализа локальной квадратичной модели минимизируемого функционала. Представляет интерес

выяснение возможностей метода в глобальном смысле, без учета предположений о квадратичной структуре/ (х).

Можно доказать, что алгоритм (5.29), (5.30) сходится практически при тех же ограничениях на минимизируемый функционал, что и метод наискорейшего спуска [29], имея в определенных условиях существенно более высокую ско­рость сходимости.

Следующая теорема устанавливает факт сходимости ЭР-метода для достаточно ши­рокого класса невьшуклых функционалов в предположении достижимости точки ми­нимума (условие 2) и отсутствия точек локальных минимумов (условие 3) [49].

Теорема 5.2. Пусть

J(x)e C2(Rn)\

множество X* = {дг*'| J(x*) = minJ(x)} непусто;

для любого є > 0 найдется такое 8 > 0, что \\g(x) \\ > 8, если х £ S(X*), где

собственные числа матрицы G (х) заключены в интервале [-М, М], где М > 0 не зависит от х.

Тогда независимо от выбора начальной точки хР для последовательности {хк}, построенной согласно (5.29), (5.30), выполняются предельные соотношения

lim d{xky X.) = 0; (5.32) lim J (xk) = J(x*), & -> <x>. (5.33)

Доказательство. Используя соотношения

Левое неравенство (5.35) следует из представления минимального собственного

(Вх,х)

числа X любой симметричной матрицы В в виде X = min-^      ^, а правое — из

Следовательно, последовательность является монотонно невозрастающей и ограниченной снизу величиной /(#*), поэтому она имеет предел njk + х - Jk —> О при k -> оо. Из (5.37) следует || gk |р <

А так как по условию > 5 при х/1 є 5(Х*), то найдется такой номер JV, что od1 є S(X*) при k>N,n, следовательно, справедливо утверждение (5.32).

Обозначим через хк проекцию х? на множество X*. Тогда по теореме о среднем Л -Kxk) = {g(xkc\xk -xk), где xkc =xk +Xk(xk -xk),Xk є [0,1] Учитывая,

что g (xk) = 0, получим

Jk -J(xk) = (g(xkc)-g(xklxk -xk) < ^(xkc)-g(xk)\\jxk ~xk \\<ld2(xk,X.).

И в силу (5.32) получаем (5.33). Теорема доказана.

Замечание 1. Утверждения теоремы, очевидно, выполняются, если hk выбирать не из условия (5.31), а из условия J[xk -H(Gk,hk)gk] = min J[xk -H(Gk,h)gk],

_          ' he[0,h]

где A > 0 — произвольное число. Действительно, легко видеть, что равенство (5.37)
только усилится, если брать любое другое значение hx (может быть, даже боль-
шее, чем         с меньшим значением функционала, чем при h = —, и в то же

le(e -1) М

, 1

время, если при п = — сходимость имеет место, то она сохраняется и при мень-М

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

Замечание 2. Утверждения (5.32), (5.33) сохраняются также при замене условия (5.31) на следующее:

Действительно, из (5.38) будем иметь

Получено неравенство, аналогичное (5.37), и далее доказательство проводится по той же схеме с заменой а на а.

В случае сильной выпуклости функционала J(x) удается получить оценку ско­рости сходимости.

Теорема 5.3. Пусть:

J(x) є C2(Rn);

для любых xf у е Rn выполняются условия X||z/||2 < (G(x)yf у) < Л||г/||2, \\G(x + у)^ G(y) || < L \\х\\,Х > О, L > 0.

Тогда независимо от выбора начальной точки хР для метода (5.29) справедливы соотношения (5.32), (5.33), и оценка скорости сходимости

Доказательство содержится в книге [49].

Таким образом, установлена квадратичная скорость сходимости, характерная для Н-методов.

5.3.1. Реализация методов

с экспоненциальной релаксацией

Алгоритм вычисления матричных функций (5.30) может быть основан на ис­пользовании известного рекуррентного соотношения

Я (G, 2А) = Я (G,h)[2E - GH (G, А)]. (5.39)

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

Формула (5.39) используется также для получения обратной матрицы G"1, так как выполняется предельное соотношение:

lim Я (С, А) = С-1,А->оо.

Этот факт еще раз указывает на связь ЭР-метода с методом Ньютона, который является предельным вариантом рассматриваемого алгоритма при условии по­ложительной определенности матрицы G. Практический выбор параметра h при известной матрице G или ее аппроксимации может осуществляться различными способами. В каждом из них приближенно реализуется соотношение (5.31). Наиболее простой прием, приводящий к так называемым системным алгорит­мам оптимизации, заключается в следующем.

Задаются некоторой малой величиной А0, такой, что матрица H(Gk, h0) может быть заменена отрезком соответствующего степенного ряда:

H(Gk\) = h0j:(-Gky~\ (5.40)

Далее последовательно наращивают h с помощью соотношения (5.39), вычисляя каждый раз значение J[xk -H(Gk, 2gh0)J'k], q = 0,i .... Процесс продолжается до тех пор, пока функция убывает либо достаточно быстро убывает. Точка с ми­нимальным значением / принимается за При этом вместо точной реализа­ции соотношения (5.31) оптимальный шаг выбирается на дискретной сетке зна­чений hq = 2gh0, q = 0, 1, .... Как правило, предельное значение q не превышает 30-40. В самом деле, если функционал J (х) квадратичный и G (х) > 0, то опти­мальное значение параметра h = +<х>, q - +оо, aH(Gk,h) = G^\ и метод вырождает­ся в классический вариант метода Ньютона без регулировки шага. Однако в дей­ствительности при использовании (5.39) для построения матрицы H(Gk, h)

необходимое число итераций q оказывается конечной величиной, ибо все вычис­ления проводятся с ограниченной точностью, и процесс автоматически останав­ливается при попадании результата в достаточно малую окрестность решения. Количество обращений к рекуррентному соотношению (5.39) при этом оказыва­ется сравнительно небольшим, что подтверждается опытом практического при­менения (5.39) в качестве алгоритма построения обратной матрицы.

Сказанное подтверждается следующими рассуждениями для случая G > 0.

Соотношение (5.39) может быть преобразовано к виду

максимальное число итераций при реализации соотношения (5.39) зависит от

степени овражности tj и обычно не превышает указанных ранее значений.

В целом ряде случаев более эффективной оказывается реализация метода с эле­ментами адаптации, в которой значение J не вычисляется для всех промежуточ­ных значений q. Функционал вычисляется для трех значений q: q* - 1, q*, q* + 1 — с последующим выбором лучшего значения. Здесь q* — оптимальное значение q, полученное на предыдущей итерации по к. На первой итерации для определения q* необходимо вычислить весь ряд значений J.

С целью более точной локализации минимума на каждом шаге по k могут ис­пользоваться процедуры одномерного поиска по /г, например, известный из кур­са численного анализа метод золотого сечения. Для этого вначале изложенным ранее грубым способом определяется промежуток [hminl /гтах], содержащий опти­мальное в смысле (5.31) значение К. Далее полагаем <p(A) =J[xk -H(Gk,h)gk]. Тогда hmin - 2q'h0, hmax = 2q' + 2h0, hm = 2q' + lh0, причем предполагается, что

Ф (^min) > Ф (^*)> Ф (^тах) > Ф О1*)- ФиКСИруЯ ЧИСЛО ПЄрЄСЧЄТОВ q', ПОЛуЧИМ, ЧТО

выбирая новый параметр h'0 из промежутка h'0 є [A0, 4A0 ], где h0 — первоначаль­но выбранное значение, мы получим h - 2q'h'Q є [Amin, Amax]. Далее можно опреде­лить (p(/z) = q>(2q h'0) = 4/(Aq), и задача сводится к стандартней задаче минимиза­ции функции одной переменной ^Qi'q) на заданном промежутке.

Для приближенного вычисления матрицы Gk вторых производных в оптими­зационных задачах теории управления могут применяться методы, изложенные в 4.4, 4.5. Рассмотрим наиболее универсальный алгоритм, основанный на ко-нечноразностных соотношениях. В результате вычислений по формулам (4.14),

(4.15) приходим к матрице Gk =—~ и к вектору gk =—, где fik = 2sh sk — шаг

Р* Р дискретности. Как уже говорилось, производить деление матрицы Dk на p2, или вектора dk на Р* с целью получения Gk и gk нецелесообразно с вычислительной точки зрения. Поэтому далее принципиальная схема ЭР-метода будет преобра­зована к виду, удобному для непосредственного применения Dk и dk вместо Gk

Имеем

h          h Р|Л

H(Dk,ti) = \exp(-Dkx)dx =р^2/ехр(-С,р,2т)ф,2т =p,"2 ]exp(-Gkt)dt

или

VlH(tiGk,h) = H{Gk,hk),hk =fkh. (5.41)

С учетом (5.41) основное соотношение (5.29) приводится к виду

Xм =хк -H(Gk,hk)gk =хк -р*Я

= хк -2skH(Dk,h)dk,h= hk

Имеем также

H(Dk,2h) = H(Dhh)[2E-DkH(Dk,h)].

Оптимальное значение h находится непосредственно из соотношения

J(xk+i) = mmJ[xk+i -2skH(Dk,h)dk].

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

Алгоритм RELEX.

Шаг 1. Ввести исходные данные х°> s.

Шаг 2. Принять х := x?\J :=J (х); х1 := x,Ji :=J.

Шаг 3. Вычислить матрицу D = {Dy} и вектор d = {dy} в точке х по формулам A) =J(X + sei + sej)

и W принять nn: = -—-.

И

Шаг 4. Принять k = 0. Вычислить матрицу H = Я(Д h0)

H = ZK   \,     ■ (5.45)

Шаг 5. Принять xl := x - 2sHd;Jt :=J(pd)\ k:=k+ 1. Шаг 6. Если Jt<Ji, принять xl := x^Ji :=Jt.

Шаг 7. Если k > 20, перейти к шагу 8; в противном случае принять Н := Н (2Е - DH) и перейти к шагу 5;

Шаг 8. Проверить условия окончания процесса оптимизации в целом; если они выполняются, остановить работу алгоритма; в противном случае принять х := of, J :=Ji и перейти к шагу 3.

ляет более точно реализовать шаг 4 алгоритма, одновременно гарантируя выпол­нение (5.46).

Параметр sk может меняться в зависимости, например, от величины \\xk - xk ~ 11| так, как это было описано в 4.4. Возможны и другие способы регулировки шага.

5.3.2. Области применения и анализ влияния погрешностей

Обратимся к анализу влияния погрешностей вычислений при реализации ЭР-методов.

Рассмотрим итерационный процесс, определяемый рекуррентным соотноше­нием

xk^=xk-Hk(Ghhk)Gl^ = q(Gk)xk, (5.47)

где q (G) = Е - Я (G, h) G. Данный процесс является упрощенной моделью ЭР-ме­тода, характеризуя его локальные свойства. Здесь предполагается, что ищется минимум квадратичной формы

/(*) = |(G**>4

Оценим влияние погрешностей в представлении матрицы Gk на характеристики релаксационности последовательности {/(я*)}.

Кроме предположения о квадратичном характере J (х) в окрестности точки хк> мы неявно ввели еще одно допущение. А именно, заменяя в (5.47) матрицу Gk на возмущенную матрицу G + dG (индекс «k» у матрицы далее будем опускать), мы предполагаем, что ошибки в вычислении G и g определенным образом согласова­ны. В действительности эквивалентное возмущение dG у матрицы, определяю­щей величину градиента Gxk, может не совпадать с возмущением матрицы G, так как g и G вычисляются раздельно. Однако с позиций последующего анализа дан­ное отличие не является принципиальным.

Предположим, что собственные числа матрицы G разделены на две группы

Х{>..>Хп.г»\Хп_г+{\>..>\Хп\. (5.48)

Возмущение dG матрицы G приводит к появлению возмущений dX{ для собст­венных чисел и возмущений du1 для отвечающих им собственных векторов. Со­гласно результатам, полученным в 4.2, будем считать, что вариации собственных векторов происходят в пределах линейных оболочек

п-г п i'=l j=n-r+i

порожденных собственными векторами {и \ і є [1: п - г]}, [u\j є [п - г + 1, п]} ис­ходной невозмущенной матрицы G. В данном случае матрицы G и G + dG одно­временно не приводятся к главным осям, что вносит дополнительный элемент сложности в анализ влияния погрешностей.

Для выполнения неравенства f(dft + *) < /(^), согласно теореме 5.1, должны вы­полняться условия релаксационности

Теперь легко видеть, что если возмущение dXi таково, что собственное число ме­няет знак:

sign (Xt) * sign (Х{ + dXi), (5.52)

то условия (5.51), вообще говоря, нарушаются. Это приводит к резкому замедле­нию сходимости процесса оптимизации.

Пусть вариация dG матрицы G вызывается только погрешностями округления. Тогда неравенство (5.52) невозможно, если все малые собственные числа огра­ничены снизу величиной nXteM. Действительно, в этом случае sign (Хі) = = sign (Хі + dXi), так как \dXt\ < пХхгм й \ХІ Отсюда имеем следующее ограничение на степени овражности функционалов, эффективно минимизируемых ЭР-мето­дами:

Проведенный анализ показывает, что вычислительные погрешности при доста­точно больших значениях rj могут приводить к практически случайному ха­рактеру множителей релаксации для малых собственных чисел, что определяет резкое снижение эффективности метода. Из (5.53) следует, что трудности воз­растают при увеличении размерности п решаемой задачи и уменьшении длины разрядной сетки компьютера. Вычисления с двойной точностью приводят к

оценке ц(хк)<—и позволяют решать существенно более широкий класс

Как показывают результаты численных экспериментов, в отличие от мето­дов ОПС матричные градиентные схемы типа RELEX оказываются менее уни­версальными. Однако там, где они применимы, может быть получен заметный вычислительный эффект. Кроме того, как показано далее, на базе градиентных методов могут быть построены алгоритмы оптимального параметрического син­теза систем с большим числом управляемых параметров. Следовательно, рас­сматриваемые классы методов взаимно дополняют друг друга, не позволяя выде­лить какой-то один «наилучший» подход.


Авторы: 239 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

Книги: 268 А Б В Г Д Е З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я