УМК (1013374), страница 8
Текст из файла (страница 8)
Если же значение функциив полученной точке меньше, чем в центре, шаг считается удачным и дальнейший поискпродолжается из этой точки.x2x∗y4 = x2y3y 3 = x1y2y1x0y1y2x1Рис. 841Г.3. Метод наилучшей пробыСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k +1 = x k + t k ξ k ,где t k > 0 – величина шага; ξ k – случайный вектор единичной длины, определяющийнаправление поиска; k – номер итерации. На текущей итерации при помощигенерирования случайных векторов ξ k получается M точек y 1 ,..., y M , лежащих нагиперсфере радиуса t k с центром в точке x k (рис.
9). Среди полученных точеквыбирается точка y m , в которой значение функции наименьшее. Если в выбранной точкезначение функции меньше, чем в центре, то дальнейший поиск продолжается из этойточки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор,пока он не станет меньше заранее заданной величины R .x2yMx∗ymy3x0y M −1y1y2x1Рис. 942Лекция 5МЕТОДЫ ПЕРВОГО ПОРЯДКАПостановка задачиПусть дана функция f ( x) , ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках.Требуется найти локальный минимум функции f ( x) на множестве допустимыхрешений X = R n , т.е. найти такую точку x ∗ ∈ R n , чтоf ( x ∗ ) = minn f ( x) .x∈ RА.
МЕТОД ГРАДИЕНТНОГО СПУСКА С ПОСТОЯННЫМ ШАГОМСтратегия поиска{ }) < f (x ) , k = 0,1,… . Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,… , таких, что f x k +1kkчисляются по правилу( )x k +1 = x k − t k ∇f x k , k = 0,1,… ,( )где точка x 0 задается пользователем; ∇f x k – градиент функции f ( x ) , вычисленный вточке x k ; величина шага t k задается пользователем и остается постоянной до тех пор,пока функция убывает в точках последовательности, что контролируется путем проверки() ( )() ( )( )выполнения условия f x k +1 − f x k < 0 или f x k +1 − f x k < − ε ∇f x kПостроение последовательности( )∇f x k{x }k2,0 < ε < 1 .заканчивается в точке x k , для которой< ε1 , где ε1 – заданное малое положительное число, или k ≥ M , где M – пре-дельное число итераций, или при двукратном одновременном выполнении двух нера-() ( )венств x k +1 − x k < ε 2 , f x k +1 − f x k< ε 2 , где ε 2 – малое положительное число.Вопрос о том, может ли точка x k рассматриваться как найденное приближение искомой точки минимума, решается с помощью дополнительного исследования.Геометрическая интерпретация метода для n = 2 приведена на рис.
1.43x2C1 > C 2 > C 3f ( x ) = C1x0− ∇f ( x 0 )x1x∗x2f (x ) = C3f (x ) = C 20x1Рис. 1З а м е ч а н и я.1. Методы первого порядка при определенных условиях гарантируют сходимость{ } к стационарной точке x , где ∇f (x ) = 0 . Следовательно, най∗последовательности x k∗денная в результате применения метода точка x ∗ нуждается в дополнительном исследовании с целью ее классификации.2. Условия окончания процесса поиска для большинства методов первого и второго порядков одни и те же (совпадают с применяемыми в методе А).Б. МЕТОД НАИСКОРЕЙШЕГО ГРАДИЕНТНОГО СПУСКАСтратегия поиска{ }) < f (x ) , k = 0,1,… .
Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,… , таких, что f x k +1kkчисляются по правилу( )x k + 1 = x k − t k ∇f x k ,где точка x 0 задается пользователем; величина шага t k определяется для каждого значения k из условия(.( )) → mintϕ(t k ) = f x k − t k ∇f x kkЭта задача может решаться с использованием необходимого условия минимумаdϕd 2ϕ= 0 и последующей проверкой достаточного условия минимума> 0 . Другой2dt kdt k44путьсвязанmin ϕ ( t k ) =t k ∈ ⎡⎣ a, b ⎤⎦ции.сиспользованиемmint k ∈ ⎡⎣ a, b ⎤⎦(( ))kf x − t k ∇f xkчисленныхметодов,когдаищетсяс помощью методом одномерной минимиза-Геометрическая интерпретация метода для n = 2 приведена на рис.
2.C1 > C 2x2f ( x ) = C1x0− ∇f ( x 0 )x1f (x ) = C 2x1Рис. 2В. МЕТОД ПОКООРДИНАТНОГО СПУСКАСтратегия поиска{ }) < f (x ) , k = 0,1,…. Точки последовательности { x } вы-Стратегия решения задачи состоит в построении последовательности точек x k ,(k = 0,1,…, таких, что f x k +1kkчисляются по циклам в соответствии с правилом⎛ ∂ f (x ) ⎞⎟x jk +1 = x jk − t k ⎜⎜⋅ e k +1 ,⎟x∂jk+1k⎠x =x⎝где j – номер цикла вычислений; j = 0,1, 2,… ; k – номер итерации внутри цикла,k = 0,1, … , n − 1 ; ek +1 , k = 0,1, … , n − 1 – единичный вектор, (k + 1) -я проекция которогоравна 1; точка x 00 задается пользователем; величина шага t k выбирается из условия⎛⎞2⎛ ∂ f (x ) ⎞⎟ − f x jk < 0 или f x jk +1 − f x jk < − ε ∇f x jk⎟f ⎜ x jk − t k ⎜⎜⋅e.k+1⎟⎜⎟⎝ ∂ x k +1 ⎠ x = x jk⎝⎠Если выбранное условие при текущем t k не выполняется, шаг уменьшается вдвое⎛ ∂ f (x ) ⎞⎟⋅ e k +1 вычисляется заново.
Легко видеть, что при фиксирои точка x jk − t k ⎜⎜⎟⎝ ∂ x k +1 ⎠ x = x jk( )() ( )( )ванном j за одну итерацию с номером k изменяется только одна проекция точки x jk ,45имеющая номер k + 1 , а в течение всего цикла с номером j , т.е. начиная с k = 0 и кончая k = n − 1 , изменяются все n проекций точки x j 0 .
После этого точке x jn присваивается номер x j +1, 0 и она берется за начальную точку для вычислений в ( j + 1) -м цикле.Полученные в результате вычислений точки могут быть записаны как элементыпоследовательности{x l },l = n⋅ j +kгде–порядковый{x l } = {x 0 = x 00 , x1 = x 01,..., x n = x 0n = x10 , x n+1 = x11, x n+2 = x12 ,...} .номерточки,т.е.Геометрическая интерпретация метода для n = 2 приведена на рис. 3.x2f (x ) = C 2C1 > C 2xx 0001− ∇f ( x 00 )x 02x∗f ( x ) = C1x1Рис.
3Г. МЕТОД ГАУССА–ЗЕЙДЕЛЯСтратегия поискаСтратегия метода Гаусса–Зейделя (Gauss–Seidel) состоит в построении последова-({ }довательности { x } вычисляются по правилу) ( )тельности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … .
Точки послеk⎛ ∂ f (x ) ⎞⎟x jk +1 = x jk − t k ⎜⎜⋅ e k +1 ,⎟x∂jk⎝ k +1 ⎠ x = xгде j – номер цикла вычислений, j = 0,1, 2, … ; k – номер итерации внутри цикла,k = 0,1, … , n − 1 ; ek +1 – единичный вектор, (k + 1) -я проекция которого равна 1; точкаx 00 задается пользователем, величина шага t k выбирается из условия⎛⎞⎛ ∂ f (x ) ⎞⎟⎟⋅eϕ(t k ) = f ⎜ x jk − t k ⎜⎜k +1 ⎟ → min .⎟⎜tkx∂jk⎝ k +1 ⎠ x = x⎝⎠46Данная задачаявляется задачей одномерной минимизации функции⎛⎞⎛ ∂ f (x ) ⎞⎟ и может быть решена либо с использованием ус⎟e⋅ϕ(t k ) = f ⎜ x jk − t k ⎜⎜k+1⎟⎜⎟x∂jkk+1⎠x =x⎝⎝⎠2d ϕdϕ= 0,> 0 , либо численно с использованием методов одномерной минимиловийdt kdt k 2зации, как задача ϕ ( t k ) →mint k ∈ ⎡⎣ a, b ⎤⎦.При фиксированном j за одну итерацию с номером kизменяется только однаjkпроекция точки x , имеющая номер k + 1 , а в течение всего цикла с номером j , т.е.
начиная с k = 0 и кончая k = n − 1 , изменяются все n проекций точки x j 0 . После этоготочке x jn присваивается номер x j +1,0 и она берется за начальную точку для вычисленийв ( j + 1) -м цикле.Полученные в результате вычислений точки могут быть записаны как элементыпоследовательности{ xl} ,l = n⋅ j +kгде–порядковыйномерточки,т.е.{x l } = {x 0 = x 00 , x1 = x 01,..., x n = x 0n = x10 , x n +1 = x11, x n + 2 = x12 ,...} .Геометрическая интерпретация метода для n = 2 приведена на рис. 4.f ( x ) = C1x2C1 > C 2x 01x 00x 02f ( x) = C 2x1Рис. 4Д.
МЕТОД ФЛЕТЧЕРА–РИВСАСтратегия поискаСтратегия метода Флетчера–Ривса (Fletcher–Reeves) состоит в построении после-({ }последовательности { x } вычисляются по правилу:) ( )довательности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точкиk47x k +1 = x k + t k d k , k = 0,1,… ;( )( )∇f (x ))∇f (xd 0 = −∇f x 0 ; d k = − ∇f x k + β k −1 d k −1 , k ≥ 1 ;2kβ k −1 =k −12.Точка x 0 задается пользователем, величина шага t k определяется для каждого()значения k из условия ϕ(t k ) = f x k + t k d k → min .tkРешение задачи одномерной минимизации может осуществляться либо из условияd 2ϕdϕ= 0,> 0 , либо численно с использованием методов одномерной минимизации,d tkdt k 2когда решается задача ϕ ( t k ) →.mint k ∈ ⎡⎣ a, b ⎤⎦Для квадратичных функций f ( x ) с матрицей Гессе H > 0 метод Флетчера–Ривсасходится к точке минимума за число шагов, не превышающее n – размерность вектора x .Для неквадратичных функций, как правило, используется алгоритм Полака–Рибьера (Polak–Ribiere), когда величина β k −1 вычисляется следующим образом:β k −1( ( )[ ( ) (( )⎧ ∇ f x k , ∇ f x k − ∇f x k − 1⎪⎪2=⎨∇f x k −1⎪⎪⎩ 0, k ∈ J ,) ] ),k ∉ J,где J = {0, n, 2n, …} .
В отличие от алгоритма Флетчера–Ривса алгоритм Полака–Рибьерапредусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов. Геометрическая интерпретация метода для n = 2 изображена на рис. 5.x2x00f ( x) = C10d = −∇f ( x )− ∇f ( x 1 )x1β0ddC1 > C 2f ( x) = C 210x∗0x1Рис. 548МЕТОДЫ ВТОРОГО ПОРЯДКАА. МЕТОД НЬЮТОНАСтратегия поискаСтратегия метода Ньютона (Newton) состоит в построении последовательности то-{ }()( )чек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точки последовательностивычисляются по правилу( ) ( )x k +1 = x k − H −1 x k ∇f x k , k = 0, 1,… ,где x 0 – задается пользователем, а направление спуска d k определяется для каждого( ) ( )значения k по формуле d k = − H −1 x k ∇f x k , величина шага t k = 1 .З а м е ч а н и е. Для квадратичных функций при определенных условиях [1,2] метод сходится к стационарной точке за одну итерацию.Б.
МЕТОД НЬЮТОНА–РАФСОНАСтратегия поискаСтратегия метода Ньютона–Рафсона (Newton–Raphson) состоит в построении по-{ }() ( )следовательности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … . Точкипоследовательности вычисляются по правилу( ) ( )x k +1 = x k − t k H −1 x k ∇f x k , k = 0,1, … ,где x 0 задается пользователем, а величина шага t k определяется из условия(( ) ( )) → min .ϕ(t k ) = f x k − t k H −1 x k ∇f x ktkЭта задача может решаться либо аналитически с использованием необходимогоd 2ϕdϕусловия минимума= 0 и последующей проверкой достаточного условия> 0,dt kd tk 2либо численно как задача ϕ ( t k ) →mint k ∈ ⎡⎣ a, b ⎤⎦, где интервал [a , b ] задается пользователем.49З а м е ч а н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
