1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 5
Текст из файла (страница 5)
На каждой удачной итерации переходим оттекущей точки сетки x k к соседней точке x k +1 . Так как при этомf ( x k ) > f ( x k +1 ) , то посетим каждую точку сетки не более одного раза, следовательно, сетка M a содержит бесконечное множество разных точек, чтопротиворечит ограниченности множества M ( x 0 ) . Откуда следует, что процесс дробления длины шага a k бесконечен и lim a k = 0 .k ®¥Пусть k1 < k 2 < K < k m < K – номера итераций, на которых дробится длина шага, и выполняются неравенства (7). Так как {x k m }km ÎN Î M ( x 0 ) , и множествоM (x0 )ограничено,тогдаможносчитать,чтосуществу-ет lim x = x) .
Из формулы конечных приращений и (7) получаем для всехkmm ®¥kf ¢( x k m + q k m a k m ei ), a k m ei = f ( x k m + a k m ei ) - f ( x k m ) ³ 0 , следовательно,для m Î N , i = 1, K , n справедливо f x¢i ( x k m + q k m a k m ei ) ³ 0 , где 0 £ q k m £ 1 .Аналогично получим, что для всех mf ¢( x k m - q k m a k m ei ),-a k m ei = f ( x k m - a k m ei ) - f ( x k m ) ³ 0и, следовательно, для m Î Nи i = 1,K , nf x¢i ( x km - q km a km ei ) £ 0 , где0 £ q km £ 1 .По условию, частные производные f x¢i ( x ) – непрерывные функции на R n .Поэтому из условийlim a k m = 0 иm ®¥lim x km = xˆ имеемm ®¥f x¢i ( xˆ ) = 0 ,i = 1,K , n . Откуда f ¢( xˆ ) = 0 и, следовательно, x̂ является оптимальным решением задачи, так как f – выпуклая функция.
▄Данный метод не требует знания градиента, но сходимость можно гарантировать лишь для гладких функций. Если целевая функция не являетсягладкой, то метод покоординатного спуска может не сходиться к множествурешений задачи.22§ 2. Методы случайного поискаОсновная особенность этого метода состоит в том, что в процессе вычисления приближений x k используются случайные вектора в качестве направления движения. Например,x k +1 = x k + a k x , k = 0,1,K,(8)где a k > 0 – длина шага, x = (x1 ,K, x n ) – реализация n -мерной случайнойвеличины x с заданным распределением. Например, xi – независимые случайные величины, равномерно распределенные на отрезке [-1,1] .
Таким образом, любая реализация метода случайного поиска использует генераторслучайных чисел, который по любому запросу выдает реализацию случайного вектора x с заданной функцией распределения.Рассмотрим задачу f ( x ) ® min , где Q Í R n . Пусть известно k -ое приxÎQkближение x Î Q , k = 0,1, K . Далее приводится описание нескольких вариантов метода случайного поиска.Алгоритм с возвратом при неудачном шагеИдея этого алгоритма заключается в следующем. На каждом шаге беретсянекоторая реализация случайной величины x и вычисляется векторv k = x k + ax , где a = const > 0 – длина шага.
Если v k Î Q и f ( v k ) < f ( x k ) ,то предлагаемый шаг считаем удачным. В этом случае x k +1 = v k . Еслиv k Î Q , но f ( v k ) ³ f ( x k ) , или v k Ï Q , то шаг является неудачным, тогдаx k +1 = x k .полагаемkx = xk +1= L= xk+NЕслинатекущейитерацииоказывается,чтодля достаточно большого N , то алгоритм останавли-kвается и x является искомым приближением.Алгоритм наилучшей пробыПусть x1, K, x s – реализации случайного вектора x . Величины a и s > 1являются параметрами алгоритма. Пусть i0 – индекс, определяемый условиемf ( x k + ax i0 ) =Далее полагаем xk +1kminx +ax i ÎQ, 1£i £ sf ( x k + ax i ), k = 0,1,K .k= x + axi0 .Алгоритм статистического градиентаПусть x1, K, x s – реализации случайного вектора x . Вычислить разности23Df ki = f ( x k + gx i ) - f ( x k ) для всех x k + gx i Î Q , k = 0,1, K , i = 1, K , s .
Пусть1pk =å xi Df ki .g x k +gx ÎQ,1£i £ siЕсли x k + apk Î Q , то x k +1 = x k + apk . В противном случае выбрать но-вый набор x1¢,K, x s¢ реализаций случайного вектора x и повторить все действия.Величины s > 1 , a > 0 , g > 0 – параметры алгоритма, g – длина шага сет-ки. Вектор pk называется статистическим градиентом. Если Q = R n , s = n ивекторы xi равны единичным векторам ei , i = 1, K , s , то данный алгоритмоказывается разностным аналогом градиентного метода.Так как функция распределения случайного вектора x не зависит от номера итерации, то предложенные выше варианты метода случайного поисканазывают методами случайного поиска без обучения.
Эти алгоритмы не обладают способностью учитывать результаты предыдущих итераций и, соответственно, обнаруживать более перспективные направления убывания минимизируемой функции. Как результат, они медленно сходятся.Идея заключается в том, что для повышения эффективности случайногопоиска надо научиться использовать на каждой итерации информацию, полученную при поиске минимума на предыдущих итерациях. При этом хотелосьбы научиться перестраивать вероятностные свойства поиска так, чтобы направления x , обеспечивающие более быстрое убывание целевой функции,выбирались бы с большей вероятностью.Методы случайного поиска, которые обладают способностью приспосабливаться к конкретным особенностям минимизируемой функции, назовемметодами случайного поиска с обучением.
Так как в этом случае функцияраспределения вектора x пересчитывается в зависимости от номера итерациии предыдущих результатов, то итерационный процесс (8) записывается теперь в видеx k +1 = x k + a k x k , k = 0,1,K.(9)На нулевой итерации функция распределения вектора x выбирается сучетом априорной информации о целевой функции.
Если такая информациянедоступна, то нулевую итерацию начинают со случайного вектораx 0 = (x10 , K, x n0 ), где x10 ,K, x n0 – независимые случайные величины, равномерно распределенные на отрезке [-1,1] .24Алгоритм покоординатного обученияПусть x ( w) = (x1 ( w), K, x n ( w)) – семейство случайных векторов, зависящих от параметров w = ( w1 , K, wn ) . Для каждого i Î {1, K, n} случайная величина xi = 1 с вероятностью pi и xi = -1 с вероятностью ( 1 - pi ), гдеесли wi < -1,ì0,ï1pi = í (1 + wi ), если | wi | £ 1,ï2если wi > 1.î1,Пусть x 0 задано, x1 вычисляется по формуле (9) при k = 0 , где беретсякакая-либо реализация случайного вектора x 0 = x ( 0) для значений парамет-ров w0 = (0, K,0) .
Приближение x 2 также вычисляется по формуле (9) приk = 1 с помощью случайного вектора x1 = x ( 0) .Пусть известны приближенияwk -1=( w1k -1 , K, wnk -1 ) , гдеwik = bwik -1 - dx 0 , x1 , K , x kи значения параметровk ³ 1 . Положимsign[( f ( x k -1 ) - f ( x k - 2 ))( xik -1 - xik - 2 )] ,(10)где i = 1, K , n , k = 2,3,K.С помощью параметра b ³ 0 управляют памятью алгоритма. Параметрd ³ 0 управляет скоростью обучения, при этом предполагается, чтовеличины b и d не могут быть равными нулю одновременно.
Приближениеx k +1 определяется по формуле (9) для реализации случайного вектораx k = x ( w k ) для набора значений параметров w k = ( w1k , K, wnk ) .Из формул для вычисления вероятностей pi и параметров wik следует,что,еслиf ( x k -1 ) < f ( x k - 2 ) ,товероятностьвыборанаправления( x k -1 - x k - 2 ) на следующем шаге увеличивается. В противном случае этавероятность падает. Итак, с помощью формул (10) происходит обучениеалгоритма.Величина b > 0 в (10) регулирует влияние предыдущих значенийпараметров на обучение; при b = 0 влияние предыдущих состояний w k -1 неучитывается.
Величина d > 0 в (10) регулирует скорость обучения; при d = 0обучения не происходит.§ 3. Градиентные методыВектор - f ¢( x k ) является направлением наискорейшего убывания функции f (x ) и называется антиградиентом. Выбирая в качестве направления25спуска pk антиградиент функции f (x ) в точке x k , приходим к итерационному процессу видаx k +1 = x k - a k f ¢( x k ), a k ³ 0.Все итерационные процессы, в которых направление движения на каждомшаге совпадает с антиградиентом (градиентом) функции, называются градиентными методами и отличаются друг от друга способами выбора длинышага a k .
Существует много различных способов выбора длины шага a k , нонаиболее распространены три из них. Первый называется методом с постоянным шагом: a k = a . Второй – методом с дроблением шага. Он связан спроверкой на каждом шаге неравенства2f ( x k - a k f ¢( x k )) - f ( x k ) £ ea k f ¢( x k ) ,где e – некоторая константа из интервала (0,1) .В третьем методе при переходе из точки x k в точку x k +1 минимизируетсяпо a функция f ( x k - af ¢( x k )) :a k = arg min f ( x k - af ¢( x k )) .a ³0Это метод наискорейшего спуска.Следующая теорема содержит достаточные условия сходимости метода спостоянным шагом.Теорема 2 (первая теорема сходимости).
Пусть функция f дифференцируема в R n , ограничена снизу величиной f * > -¥ , выполняется условиеЛипшица для градиента f ¢(x )f ¢( x ) - f ¢( y ) £ L x - yи длина шага a удовлетворяет условию 0 < a < 2 / L . Тогдаf ¢( x k ) ® 0 при k ® ¥ и f ( x k +1 ) £ f ( x k ) ,при любом выборе начального приближения x 0 .Доказательство. Воспользуемся формулой конечных приращений1f ( x + y ) = f ( x ) + ò f ¢( x + ty ), y dt ,0которую перепишем в следующем виде:1f ( x + y ) = f ( x ) + f ¢( x ), y + ò f ¢( x + ty ) - f ¢( x ), y dt .0kСделаем подстановки x = x , y = -af ¢( x k ) .
Тогда из неравенства Коши-26Буняковского a, b £ a b и условия Липшица получимf ( x k +1 ) £ f ( x k ) + f ¢( x k ),-af ¢( x k ) +1+òf ¢( x k - taf ¢( x k )) - f ¢( x k ), -af ¢( x k ) dt £02£ f ( x k ) - a f ¢( x k ) +1òf ¢( x k - taf ¢( x k )) - f ¢( x k ) af ¢( x k ) dt £021£ f ¢( x k ) - a f ¢( x k ) + ò L taf ¢( x k ) af ¢( x k ) dt =02= f ( x k ) - a f ¢( x k ) + La 2 f ¢( x k )21ò tdt =022= f ( x k ) - a (1 - La / 2) f ¢( x k ) = f ( x k ) - g f ¢( x k ) ,где g = a (1 - La / 2) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
