1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 4
Текст из файла (страница 4)
Если h ÎU ( x , f ) , тогдаf ' ( x ), h £ 0 .Доказательство. Пусть выполнено условие (18). Тогдаf ( x + ah ) - f ( x ) = f ' ( x ), ah + o(a ) = a ( f ' ( x ), h +при всех достаточно малых a > 0 , то есть h ÎU ( x , f ) .(19)o(a ))<0aПусть h ÎU ( x , f ) и f ' ( x ), h > 0 . Тогда с помощью только что проведенного рассуждения убеждаемся, что h – направление возрастания. Полученное противоречие показывает, что в рассматриваемом случае справедливонеравенство (19). ▄Геометрически условие (19) означает, что вектор h составляет тупой уголс градиентом f ' ( x ) .Метод, определяемый итерационной формулой (8), называется методомспуска, если вектор hk задает направление убывания функции f в точке x k :а a k ³ 0 и такое, чтоhk Î U ( x k , f ) , k = 0,1,2,K ,f ( x k +1 ) £ f ( x k ) , k = 0,1,2,K .Простейшим примером метода спуска является градиентный метод, в ко-тором hk = - f ' ( x k ) . Если f ' ( x ) ¹ 0 , то - f ' ( x ) ÎU ( x , f ) в силу леммы 4.Приведем несколько вариантов выбора длины шага в методах спуска, которые не исчерпывают множества всех применяемых на практике способов.Коэффициенты a k в методе (8) можно определять из условияf ( x k + a k hk ) = min a f ( x k + ahk ) ,17где для методов спуска, то есть при hk Î U ( x k , f ) , минимум берется поa ³ 0 .
Такой способ выбора a k является в некотором смысле наилучшим,ибо он обеспечивает достижение наименьшего значения функции вдоль заданного направления. Однако он требует решения на каждом шаге одномерной задачи минимизации. Эти задачи решаются, как правило, приближенно спомощью численных методов, что приводит к значительному объему вычислений. В простейших случаях величины a k удается найти в явном виде.Пример 1.1Ax, x + b, x , где A2определеннаяматрица.ТогдаРассмотрим задачу минимизации функции f (x ) =–симметрическаяположительно1f ( x k + ahk =)A( x k + ahk ), x k + ahk + b, x k + ahk =2a21 kAhk , hk + Ax k + b, hk a +Ax + b, x k .22Легко проверить, что минимум этой функции по a достигается при=a k = - Ax k + b, hk / Ahk , hk .Если hkk– направление убывания, то из леммы 4 и равенстваkf ¢( x ) = Ax + b имеем a k = -Ax k + b, hkAhk , hk= -f ¢( x k ), hkAhk , hk³ 0 .
Следова-тельно, f ( x k + a k hk ) = min f ( x k + ahk ) = min f ( x k + ahk ) .a ³0a ÎRИногда величины a k выбирают до начала вычислений. Так, в ряде методов достаточно чтобы выполнялись условияa k > 0, k = 0,1,K;¥åa kk =0=¥,¥åa k2 < ¥ ,k=0например, можно взять a k = C /( k + 1) , где C = const > 0 . На интуитивномуровне эти условия можно пояснить следующим образом. Условие сходимости ряда¥å a k2накладывают, чтобы добиться достаточно быстрой сходимо-k=0сти последовательности {a k }kÎN к нулю с целью обеспечения сходимостиметода в окрестности точки экстремума x * . Условие же расходимости ряда{a k }kÎN призвано обеспечить достижение точки экстремума x * даже принеудачном выборе начального приближения x 0 , то есть при большом расстоянии от x 0 до x * .18В некоторых методах коэффициенты a k можно выбирать постоянными:ak º a > 0 .Приведем еще один адаптивный способ выбора коэффициентов a k , называемый дроблением шага. Если hk – направление убывания, то дроблениешага можно осуществлять следующим образом.Выбираются некоторые константы b > 0 , 0 < l < 1 (часто l = 1 / 2 ).
Длякоэффициента a = b проверяется выполнение условияf ( x k + ahk ) < f ( x k ).(20)Если оно выполнено, то полагают a k = a . Если нет, то производится дробление шага, то есть принимается a = lb , и вновь проверяется выполнение условия (20). Процесс дробления продолжается до тех пор, пока условие (20) неокажется выполненным. Этот процесс не может быть бесконечным, поскольку hk – направление убывания. Первое a , при котором условие выполнено,и принимается за a k .19ГЛАВА 2ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИВ этой главе рассматривается задача безусловной минимизации, приводится описание методов нулевого, первого и второго порядков. В качествепредставителя методов нулевого порядка описывается метод покоординатного спуска [2, 6].
Хотя скорость сходимости этого метода, как правило, невысокая, благодаря простоте и небольшим требованиям к гладкости целевойфункции его можно использовать для решения задач. Другой подход для минимизации негладких функций, основанный лишь на вычислении значенийфункции, дает метод случайного поиска [2], который также излагается в этойглаве.Также рассматриваются такие классические методы минимизации, какградиентный метод и метод Ньютона [2, 3, 6, 7, 9]. Эти методы важны видейном отношении.
Оба они явным образом основаны на идее замены оптимизируемой функции в окрестности текущего приближения первыми членами ее разложения в ряд Тейлора. В градиентном методе берут линейнуючасть разложения, в методе Ньютона – квадратичную часть.§ 1. Метод покоординатного спускаМетод покоординатного спуска применяется для решения экстремальныхзадач, в которых целевая функция либо не обладает нужной гладкостью, либоявляется гладкой, но вычисление производных слишком трудоемко. В такихслучаях желательно иметь методы решения, которые используют лишь значения функции. Далее приводится описание метода покоординатного спускадля следующей задачи:f ( x ) ® inf .(1)nxÎRПусть ei = (0, K,0,1,0,K,0) – i -ый единичный координатный вектор, x 0 –начальное приближение, a 0 > 0 – начальная длина шага.
Пусть x k Î R n –текущее приближение, a k > 0 – текущая длина шага, l Î (0,1) – фиксированное число.Метод покоординатного спуска – итеративный процесс. На каждой итерации метода в качестве направления спуска используется один из единичныхкоординатных векторов. Так как таких векторов ровно n, то множество всехитераций естественно разбивается на группы из n итераций. Занумеруем итерации так, чтобы t -ая группа начиналась с итерации с номером (t - 1)n + 1 , апоследняя итерация этой группы заканчивалась номером tn .Опишем итерацию с номером k , где(t - 1)n + 1 £ k £ tn .20Сначала проверяется можно ли улучшить текущее приближение, сдвигаясь внаправлении координатного вектора ek - ( t -1)n с длиной шага a k -1 . Если удается улучшить значение целевой функцииf ( x k -1 + a k -1ek -( t -1) n ) < f ( x k -1 ) ,(2)то пересчитывается текущее приближение по формулам(3)x k = x k -1 + a k -1ek -( t -1) n , a k = a k -1 .В противном случае проверяется вектор - ek - ( t -1)n .
Если выполняется неравенствоf ( x k -1 - a k -1ek -( t -1) n ) < f ( x k -1 ) ,(4)тогдаx k = x k -1 - a k -1ek -( t -1) n , a k = a k -1 .(5)Если выполняется (2) или (4), то будем говорить, что итерация k удачная.В случае неудачной итерации k положим x k = x k -1 ,ìla , если k = tn и все итерации группы неудачные,a k = í k -1(6)если k ¹ tn или были удачные итерации внутри группы.îa k -1 ,Пусть в t -ой группе не оказалось ни одной удачной итерации и шаг дробится. В этом случае выполняются неравенстваf ( x k -1 + a k -1ei ) ³ f ( x k -1 ) , f ( x k -1 - a k -1ei ) ³ f ( x k -1 ) , i = 1,K , n .
(7)Если в данной группе из n итераций реализовалась хотя бы одна удачнаяитерация, то тогда на последней итерации группы длина шага не дробится исохраняется еще на протяжении n итераций следующего цикла, так какдробление возможно только на последней итерации цикла.Теорема 1. Пусть функция f (x ) выпукла на R n и f Î C 1 ( R n ) , а начальное приближение таково, что множество M ( x 0 ) = {x Î R n | f ( x ) £ f ( x 0 )}ограничено.
Тогда последовательность {x k }kÎN имеет хотя бы одну предельную точку, и любая предельная точка этой последовательности есть оптимальное решение задачи.Доказательство. В задаче (1) по теореме Вейерштрасса (глава 1) существует оптимальное решение x * Î R n . Из условий (2)–(6) следуетf ( x k ) £ f ( x k -1 ) , k= 1,2,K , откуда получаем, что {x k }kÎN Î M ( x 0 ) и суще-ствует lim f ( x k ) ³ f * = f ( x * ) .
Покажем, что lim a k = 0 . Допустим проk ®¥k ®¥тивное. Пусть a k = a > 0 для всех k ³ k 0 , то есть процесс дробления конечен.21Зададим сетку с шагом a :nM a = {u Î M ( x 0 ) | u = x k0 + a å ri ei , ri = 0, ±1,±2,K, i = 1, K, n} .i =1Понятно, что, начиная с номера k 0 , любой цикл из n итераций содержитхотя бы одну удачную итерацию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
