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

Задать начальную точку x1 , величину шага x  0 , 1 и  2 – малые положительные числа, характеризующие точность.Шаг 2. Вычислить x 2  x1   x .Шаг 3. Вычислить f  x1   f1 и f  x 2   f 2 .Шаг 4. Сравнить f  x1  с f  x 2  :а) если f  x1   f  x 2  , положить x 3  x1  2  x (рис. 4, а);б) если f  x1   f  x 2  , положить x 3  x1   x (рис. 4, б).Шаг 5. Вычислить f  x3   f 3 .Шаг 6. Найти Fmin  min f1 , f 2 , f 3  , x min  x i : f  x i   F min .Шаг 7. Вычислить точку минимума интерполяционного полинома, построенногопо трем точкам:1 x 22  x 32 f1  x 32  x12 f 2  x12  x 22 f 3,x 2 x 2  x 3  f1  x 3  x1  f 2  x1  x 2  f 3и величину функции f x  (рис. 4).32Если знаменатель в формуле для x на некоторой итерации обращается в нуль, торезультатом интерполяции является прямая. В этом случае рекомендуется обозначитьx1  x min и перейти к шагу 2.Шаг 8.

Проверить выполнение условий окончания:F min  f x f x x min  xx 1 , 2 .Тогда:а) если оба условия выполнены, процедуру закончить и положить x   x ;б) если хотя бы одно из условий не выполнено и x  [ x1 , x 3 ] , выбрать наилучшуюточку ( x min или x ) и две точки по обе стороны от нее. Обозначить эти точки вестественном порядке и перейти к шагу 6;в) если хотя бы одно из условий не выполнено и x  [ x1 , x 3 ] , то положить x1  xи перейти к шагу 2.fff ( x)f ( x)f  x1 f x3 f x f x 2 f x 2 f x f x3 f  x1 xxx1 x x 2  x x 3xx3аxx1xx2xбРис. 4З а м е ч а н и е.

Для решения задачи одномерной минимизации также применяются: метод равномерного поиска, метод деления интервала пополам, метод Фибоначчи,кубической интерполяции.Б. МЕТОД КОНФИГУРАЦИЙПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x   R n , чтоf ( x  )  min f ( x) .xR n33Стратегия поискаМетод конфигураций, или метод Хука–Дживса (Hooke–Jeeves), представляетсобой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Исследующий поиск ориентирован на выявление локального поведения целевой функции и определение направления ее убывания вдоль&оврагов[. Полученная информация используется при поиске по образцу при движениивдоль &оврагов[.Исследующий поиск начинается в некоторой начальной точке x 0 , называемойстарым базисом.

В качестве множества направлений поиска выбирается множествокоординатных направлений. Задается величина шага, которая может быть различнойдля разных координатных направлений и переменной в процессе поиска. Фиксируетсяпервое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение функции в пробной точке меньше значения функции висходной точке, шаг считается удачным.

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

5). Величина ускоряющего шага задается ускоряющим множителем  . Успех поиска по образцу определяется с помощью исследующего поиска из полученной точки(например из точек 6, 11, 15 на рис. 5). Если при этом значение в наилучшей точкеменьше, чем в точке предыдущего базиса, то поиск по образцу удачен (точки 6, 11 #результат удачного поиска по образцу, а точка 15 # неудачного). Если поиск по образцу неудачен, происходит возвратв новый базис, где продолжается исследующийпоиск с уменьшенным шагом. На рис. 5 удачный поиск отображается сплошными линиями, а неудачный # штриховыми, числа соответствуют порождаемым алгоритмомточкам.Обозначим через d1, , dn # координатные направления:1  0d1    , 0 0 1 d 2    ,..., 0 0 0dn    . 1  При поиске по направлению d i меняется только переменная xi , а остальные переменные остаются зафиксированными.x234432f ( x )   x1  1 x 22242f x   19x1x025816x210x1314 x171 1312x1113 11 12216Рис.

5АлгоритмШаг 1. Задать начальную точку x 0 , число   0 для остановки алгоритма, начальные величины шагов по координатным направлениям 1, , n   , ускоряющий  0,  1.множителькоэффициентуменьшенияшагаПоложить10y  x , i  1, k  0 .Шаг 2. Oсуществить исследующий поиск по выбранному координатному направлению:а) если f ( y i   i d i )  f ( y i ) , т.е.f ( y1i ,, y ii   i , , y ni )  f ( y1i ,, y ii ,, y ni ) ,шаг считается удачным. В этом случае следует положить y i 1  y i   i d i иперейти к шагу 3;б) если в п. œаB шаг неудачен, то делается шаг в противоположном направлении.Еслит.е.f ( yi  i di )  f ( yi ) ,f ( y1i ,, y ii   i ,, y ni )  f ( y1i ,, y ii , , y ni ) , шаг считается удачным.

В этомслучае следует положить y i 1  y i   i d i и перейти к шагу 3;в) если в пп. œаB и œбB шаги неудачны, положить y i 1  y i .Шаг 3. Проверить условия:а) если i  n , то положить i  i  1 и перейти к шагу 2 (продолжить исследующий поиск по оставшимся направлениям);б) если i  n , проверить успешность исследующего поиска: если f ( y n 1)  f ( x k ) , перейти к шагу 4; если f ( y n 1)  f ( x k ) , перейти к шагу 5.Шаг 4.

Провести поиск по образцу. Положить35x k 1  y n 1 ,y 1  x k 1   ( x k 1  x k ) ,и перейти к шагу 2.Шаг 5. Проверить условие окончания:а) если все  i   , то поиск закончить: x   x k ;i  1, k  k  1б) для тех i , для которых  i   , уменьшить величину шага:  i i. Положить y 1  x k , x k 1  x k , k  k  1, i  1 и перейти к шагу 2.З а м е ч а н и е. В алгоритме можно использовать одинаковую величину шагапо координатным направлениям, т.е. вместо  1 ,  2 ,  ,  n применять  .В. МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКАПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x   R n , чтоf ( x  )  min f ( x) .xR nСтратегия поискаВ основу метода деформируемого многогранника, или метода Нелдера–Мида(Nelder–Mead), положено построение последовательности систем n  1 точекx i (k ), i  1,...

, n  1 , которые являются вершинами выпуклого многогранника. Точкисистемы x i (k  1), i  1,... , n  1 , на ( k  1 )-й итерации совпадают с точками системыx i (k ), i  1,... , n  1 , кромеii  h , где точкаhx h (k )# наихудшая в системеix (k ), i  1,... , n  1 , т.е. f (x (k))  max f (x (k)) . Точка x h (k ) заменяется на дру1  i  n 1гую точку по специальным правилам, описанным ниже.

В результате многогранникидеформируются в зависимости от структуры линий уровня целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума. Построение последовательности многогранников заканчивается, когда значения функции в вершинах текущего многогранника отличаются от значения функции в центре тяжести системы x i (k ), i  1,... , n  1; i  h ,не более чем на величину   0 .АлгоритмШаг 1. Задать координаты вершин многогранника x 1, , x n 1 ; параметры отражения  , сжатия  , растяжения  ; число   0 для остановки алгоритма. Положитьk  0 (последующие шаги 2–6 соответствуют текущему номеру k системы точек).Шаг 2.

Среди вершин найти &наилучшую[ x l и &наихудшую[ x h , соответствующие минимальному и максимальному значениям функции:36 f xl minj  1, , n  1  f xj ;f xh maxj  1, , n  1 ,f xjа также точку x s , в которой достигается второе по величине после максимального значение функции f x s .Шаг 3. Найти &центр тяжести[ всех вершин многогранника, за исключением&наихудшей[ x h : 1 n 11  n 1x n2    x j  x h    x j .n  j 1 n j 1j hШаг 4. Проверить условие окончания:12 2 1 n 1jn2а) если   f x  f x   , процесс поиска можно завер1nj 1шить и в качестве приближенного решения взять наилучшую точку текущего  многогранника: x   x l ;б)если    , продолжать процесс.Шаг 5.

Выполнить операцию отражения &наихудшей[ вершины через центртяжести x n  2 (рис. 6, а):x n 3  x n 2   x n 2  x h .Шаг 6. Проверить выполнение условий:  а) если f x n 3  f x l , выполнить операцию растяжения (рис. 6, б):x n  4  x n  2   x n 3  x n  2 .Найти вершины нового многогранника:   если f x n  4  f x l , то вершина x h заменяется на x n4 (при n  2 многогранник будет содержать вершины x1 , x 3 , x 6 ). Затем следует положитьk  k  1 и перейти к шагу 2;   если f x n  4  f x l , то вершина x h заменяется на x n  3 (при n  2 многогранник будет содержать вершины x 1, x 3 , x 5 ). Далее следует положитьk  k  1 и перейти к шагу 2;б) если    f x s  f x n 3  f x h , то выполнить операцию сжатия (рис.