lopt4 (Лекционный курс)

Лекция 4 (продолжение лекции 3)Б. МЕТОД КОНФИГУРАЦИЙПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x ∗ ∈ R n , что f ( x ∗ ) = min f ( x) .x∈R nСтратегия поискаМетод конфигураций, или метод Хука–Дживса (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 , … , d n – координатные направления:⎛1 ⎞⎜ ⎟⎜0⎟d1 = ⎜ ⎟ ,⎜ ⎟⎜0⎟⎝ ⎠⎛0⎞⎜ ⎟⎜1 ⎟d 2 = ⎜ ⎟ ,...,⎜ ⎟⎜0⎟⎝ ⎠34⎛0⎞⎜ ⎟⎜0⎟dn = ⎜ ⎟ .⎜ ⎟⎜1 ⎟⎝ ⎠При поиске по направлению d i меняется только переменная xi , а остальные переменныеостаются зафиксированными.x243Δ22f ( x) = ( x1 + 1) + x 22 = 42f (x ) = 19xx∗−1314 x171562x0x1811 Δ132571012x1−113 11 12−216Рис.

5АлгоритмШаг 1. Задать начальную точку x 0 , число ε > 0 для остановки алгоритма,начальные величины шагов по координатным направлениям Δ1 , … , Δ n ≥ ε , ускоряющиймножитель λ > 0 , коэффициент уменьшения шага α > 1 . Положитьy 1 = x 0 , 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;б) если в п.

“а” шаг неудачен, то делается шаг в противоположном направлении.Если 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;в) если в пп. “а” и “б” шаги неудачны, положить y i +1 = y i .Шаг 3. Проверить условия:а) если i < n , то положить i = i + 1 и перейти к шагу 2 (продолжитьисследующий поиск по оставшимся направлениям);б) если i = n , проверить успешность исследующего поиска:35• если f ( y n +1) < f ( x k ) , перейти к шагу 4;• если f ( y n +1) ≥ f ( x k ) , перейти к шагу 5.Шаг 4. Провести поиск по образцу.

Положитьx 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 ,кромеx i (k ), i = 1,... , n + 1 , т.е.i = h,где точкаx h (k )– наихудшая в системеf (x h (k )) = max f (x i (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 системы точек).36Шаг 2. Среди вершин найти «наилучшую» x l и «наихудшую» x h ,соответствующие минимальному и максимальному значениям функции:( )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+2f 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многогранник будет содержать вершины x 1 , 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 , то выполнить операцию сжатия (рис. 6, в):()x n +5 = x n + 2 + β x h − x n + 2 .Заменить вершину x h на x n +5 , положить k = k + 1 и перейти к шагу 2 (при n = 2многогранник будет содержать вершины x 1 , x 3 , x 7 );37x2 = xhxn+2 = x 4x2 = xh1x =xx 3 = x n +1 = x sx1 = x ll(x n +3 = x 5xn+2 = x 4(x 3 = x n +1 = x sx n +3 = x 5) ( )f xn+4 ≥ f xl) ( )f xn+4 < f xlx n+4 = x 6абx2 = xhx2 = xhx n +5 = x 7x1 = x lx 3 = x n +1xn+2 = x 4x1 = x l= xsx 3 = x n +1 = x sxn+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∈R38nГ.1. Адаптивный метод случайного поискаСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k +1 = x k + t k ξ k ,где t k > 0 – величина шага; ξ k – случайный вектор единичной длины, определяющийнаправление поиска; k – номер итерации. На текущей итерации при помощигенерирования случайных векторов ξ k получаются точки, лежащие на гиперсферерадиуса t k с центром в точке x k (рис. 7).

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