lopt5 (1013497)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 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З а м е ч а н и е.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций