3 Численные методы поиска безусловного экстремума. Методы нулевого порядка. Методы одномерной минимизации (1013401), страница 3

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

Текст из файла (страница 3)

6, в):x n 5  x n  2   x h  x n  2 .Заменить вершину x h на x n 5 , положить k  k  1 и перейти к шагу 2 (при n  2многогранник будет содержать вершины x1 , x 3 , x 7 );37x2  xhxn2  x 4x2  xh1x xx 3  x n 1  x sx1  x llxxn2  x 4n 3xx 3  x n 1  x sx n 3  x 5  f xn4  f xl5  f xn4  f xlx n4  x 6абx2  xhx2  xhx n 5  x 7x1  x lxn2x 3  x n 14xx 3  x n 1  x sx1  x l xsxn2  x 4x n 3  x 5x n 3  x 5вгРис. 6    в) если f x l  f x n 3  f x s , то вершину x h заменить на x n  3.

При этомследует положить k  k  1 и перейти к шагу 2;  г) если f x n  3  f x h , выполнить операцию редукции (рис. 6, г). Формируется новый многогранник с уменьшенными вдвое сторонами и вершиной x l :x j  x l  0,5 x j  x l , j  1,  , n  1 .При этом следует положить k  k  1 и перейти к шагу 2.З а м е ч а н и е.

Нелдер и Мид рекомендуют использовать параметры  1;   0,5;   2 ; Павиани (Paviani):   1 ; 0,4    0,6 ; 2,8    3 ; Паркинсон иХатчинсон (Parkinson, Hutchinson):   2;   0,25;   2,5 . В последнем случае врамках операции отражения фактически выполняется растяжение.Г. МЕТОДЫ СЛУЧАЙНОГО ПОИСКАПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x   R n , чтоf ( x  )  min f ( x) .xR n38Г.1. Адаптивный метод случайного поискаСтратегия поискаЗадается начальная точка x 0 .

Каждая последующая точка находится по формулеx k 1  x k  t k  k ,где t k  0 # величина шага; k # случайный вектор единичной длины, определяющий направление поиска; k # номер итерации. На текущей итерации при помощи генерирования случайных векторов k получаются точки, лежащие на гиперсфере радиуса t k с центром в точке x k (рис.

7). Если значение функции1не меньше, чем в центре, шаг считается неудачным (точки y , yв полученной точке2при поиске из x 0 ;y 1 , y 3 при поиске из x 1 ). Если число неудачных шагов из текущей точки достигаетнекоторого числа M , дальнейший поиск продолжается из той же точки, но с меньшимшагом до тех пор, пока он не станет меньше заранее заданной величины R . Если жезначение функции в полученной точке меньше, чем в центре, шаг считается удачным,и в найденном направлении делается увеличенный шаг, играющий роль ускоряющегошага (как при поиске по образцу в методе конфигураций).

Если при этом значениефункции снова меньше, чем в центре, направление считается удачным и дальнейшийпоиск продолжается из этой точки (точки z 3  x 1при поиске из x 0 , z 4  x 2при поиске из x 1 ). Если же значение функции не стало меньше, чем в центре,направление считается неудачным и поиск продолжается из старого центра (в точкеy 2 при поиске из x 1 функция меньше, чем в x 1 , а в точке z 2 уже не меньше, поэто-му направление z 2  x 1 # неудачное).x2xy3z4  x2z 3  x14yy2y3y1x0y1z2y2x1Рис. 739АлгоритмШаг 1.

Задать начальную точку x 0 , коэффициенты расширения   1 и сжатия0    1 , M # максимальное число неудачно выполненных испытаний на текущейитерации, t 0  1 # начальную величину шага, R - минимальную величину шага, N #максимальное число итераций. Положить k  0, j  1 .Шаг 2. Получить случайный вектор  j  1 j ,  , n jвеличина, равномерно распределенная на интервале  1,1 .y j  x k  tkШаг 3. ВычислитьjjT, где i j # случайная.Шаг 4. Проверить выполнение условий:   а) если f y j  f x k , шаг удачный. Положить z j  x k   y j  x kи опре-делить, является ли текущее направление y j  x k удачным:   f z j  f xk , еслитонаправлениепоискаудачное.Положитьx k 1  z j , t k 1   t k , k  k  1 и проверить условие окончания. Еслиk  N , положить j  1 и перейти к шагу 2.

Если k  N , поиск завер-шить: x   x k ;   f  y   f  x  , шаг неудачный и перейти к шагу 5. если f z j  f x k , направление поиска неудачное, перейти к шагу 5;б) еслиjkШаг 5. Оценить число неудачных шагов из текущей точки:а) если j  M , следует положить j  j  1 и перейти к шагу 2;б) если j  M , проверить условие окончания:    если t k  R , процесс закончить: x   x k , f x   f x k ; если t k  R , положить t k   t k , j  1 и перейти к шагу 2.З а м е ч а н и я.1.

Величина i j , равномерно распределенная на интервале  1,1 , генерируетсяобычно с помошью датчиков псевдослучайных чисел на ЭВМ. Вырабатывается случайная величина ij , равномерно распределенная на  0,1 , а затем используется линейное преобразование: ij  2 ij  1 .2. Шумер и Стейглиц (Schumer, Steiglitz) рекомендуют следующие параметрыалгоритма:   1,618;   0,618; M  3n . При   1 точка z j на шаге 4 совпадает сy j , т.е.

аналог поиска по образцу не производится. Начальный шаг t 0  R можно задать произвольно.3. Если выполнено условие окончания t k  R , то в качестве ответа можно ис-пользовать любую точку внутри шара с радиусом t k и центром в точке x k .40Г.2. Метод случайного поиска с возвратом при неудачном шагеСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k 1  x k  t k  k ,где t k  0 # величина шага; k # случайный вектор единичной длины, определяющий направление поиска; k # номер итерации. На текущей итерации при помощи генерирования случайных векторов k получаются точки, лежащие на гиперсфере радиуса t k с центром в точке x k (рис. 8).

Если значение функциив полученной точкене меньше, чем в центре, шаг считается неудачным (точки y 1, y 2 при поиске из x 0 ;y 1 , y 2 , y 3 при поиске из x 1 ), происходит возврат в текущий центр и поиск продолжается. Если число неудачных шагов из текущей точки достигает некоторого числа M ,дальнейший поиск продолжается из той же точки, но с меньшим шагом до тех пор,пока он не станет меньше заранее заданной величины R.

Если же значение функции вполученной точке меньше, чем в центре, шаг считается удачным и дальнейший поискпродолжается из этой точки.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 1y1y2Рис.

942x1.

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

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