4 Численные методы поиска безусловного экстремума. Методы первого и второго порядка (1013403)

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

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

Лекция 4МЕТОДЫ ПЕРВОГО ПОРЯДКАПостановка задачиПусть дана функция 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 2d 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 ,xjkk1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.1k  x k 1  x  x jkЕсли выбранное условие при текущем t k не выполняется, шаг уменьшается вдвое  f x  и точка x jk  t k  e k 1 вычисляется заново.

Легко видеть, что при фиксиро  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 ,xjk 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 .tkx k 1  x  x jk46Данная задачаявляется задачей одномерной минимизации функции  f x   и может быть решена либо с использованием усt k   f  x jk  t k ek1xjk k 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d 2условия минимума 0 и последующей проверкой достаточного условия 0,dt kd tk 2либо численно как задача   t k  mint k   a, b , где интервал a , b  задается пользователем.49З а м е ч а н и е.

Для уменьшения числа обращений матрицы Гессе применяетсяупрощенный метод Ньютона, в котором обращение осуществляется один раз – в началь-ной точке x 0 :   x k 1  x k  t k H 1 x 0 f x k , k  0, 1, .В. МЕТОД МАРКВАРДТАСтратегия поискаСтратегия метода Марквардта (Marquardt) состоит в построении последовательности точек x k , k  0,1,  , таких, что f x k 1  f x k , k  0,1,  . Применяется в слу-   чаях, когда на какой-либо итерации (итерациях) выполняется условие det H ( x k )  0 , чтоприводит к значительным погрешностям вычисления обратной матрицы. Точки последовательности x k вычисляются по правилу  x k 1  x k  H x k   k E f x  , k  0,1, ,1kгде точка x 0 задается пользователем, E – единичная матрица,  k – последовательность  положительных чисел, таких, что матрица H x k   k E1положительно определена.Как правило, число  0 назначается как минимум на порядок больше, чем самый E  f x   f x ,большой элемент матрицы H x 0 , а в ряде стандартных программ полагается  0  104 .  1kkkто  k 1 .

В противном случаеf  x k  H x k   k2 k 1  2 k . Легко видеть, что алгоритм Марквардта в зависимости от величины  k накаждом шаге по своим свойствам приближается либо к алгоритму Ньютона, либо к алгоритму градиентного спуска.Если50.

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

Тип файла PDF

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

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

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