Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А
сокращением интервала неопределенности [ak, bk] и выбором новой совокупности “удачных точек” для (k + 1) – го шага из уже проведенных испытаний.
Таким образом, при поиске минимума унимодальной функции с высокой степенью точности ε необходимо последовательно применять сначала методы сокращения интервала неопределенности до тех пор, пока не будет получена совокупность “удачных точек”, и затем методы полиномиальной интерполяции.
2.3. Методы безусловной минимизации в пространстве Rn
Для численного решения задач безусловной минимизации
вида
f (x) min
x Rn
разработано много алгоритмов, использующих итерационные процедуры
x k 1 x k 
k y k ,
где yk - направление поиска точки xk+1 из точки xk, а число k -
величина шага в выбранном направлении. Работа таких алгоритмов на каждой итерации происходит по следующей схеме:
Шаг 1. Проверить условия останова и, если они выполнены,
вычисления прекратить и взять точку xk в качестве искомого решения.
Шаг 2. Зафиксировать ненулевой вектор yk в качестве направления поиска.
Шаг 3. |
Выбрать число |
k |
- величину шага. |
||
Шаг 4. |
Положить x k |
1 |
x k |
k y k . |
|
Для проверки условий останова на шаге |
1 на практике часто |
||||
используются следующие критерии: |
|
|
|||
|
||xk+1 - xk||< |
,|f(xk+1) - f(xk)|< , |
|| f (x k ) ||< , |
||
33
где - заданный параметр точности. Кроме того, при практической реализации эти алгоритмы полезно дополнять "дежурным"
критерием останова k Nmax , где Nmax - задаваемое заранее максимальное число итераций.
В качестве вектора yk на шаге 2 могут выбираться единичные орты (покоординатный спуск), антиградиент в точке xk
(градиентные |
методы) |
|
и |
|
другие |
||
направления. Величина шага |
k , |
как правило, выбирается так, |
|||||
чтобы |
выполнялось условие |
f (x k 1 ) |
f (x k ) . |
В частности, |
|||
чтобы |
гарантировать |
выполнение |
этого |
неравенства, |
можно |
||
выбирать
k |
arg min f (xk |
yk ) |
|
|
(будем в дальнейшем это называть правилом наискорейшего спуска).
Рассмотрим примеры алгоритмов, построенных в соответствии с предложенной схемой.
2.3.1. Метод покоординатного спуска
Этот метод заключается в последовательной минимизации целевой функции f(x) сначала по направлению первого базисного вектора е1 ,затем второго е2 и т.д. Таким образом, здесь
y k ek , |
k |
выбирается |
в соответствии с правилом |
|
наискорейшего спуска. После окончания минимизации по направлению последнего базисного вектора еn цикл может повторяться. Метод покоординатного спуска может быть методом нулевого порядка, т.к. он может не использовать в работе производных функции f(x). Таким образом, он может применяться для оптимизации недифференцируемых функций.
Алгоритм.
Шаг 0. Выбрать начальное приближение х0 в пространстве Rn , задать параметр точности . Найти
34
f(x0), положить j=1.
Шаг 1. Решить задачу одномерной минимизации
|
Ф( ) f (x0 |
e j ) |
min, |
|
|
|
R |
|
т.е. найти α*. |
|
|
|
Положить х1=х0+ α*еj, вычислить f (x ) . |
||
|
|
|
1 |
Шаг 2. |
Если j<n, то положить х0=х1, j=j+1 и перейти к шагу |
||
|
1, иначе к шагу 3. |
|
|
Шаг 3. |
Проверить выполнение критерия останова |
||
|
(например, ||x0-x1||< |
или |f(x0)-f(x1)|< ). Если он |
|
выполняется, то положить x*=x1, f*=f(x1) и закончить поиск. Иначе - положить х0=х1, f(x0)=f(x1), j=1 и перейти к шагу 1.
З а м е ч а н и е . Для приближенного решения вспомогательной задачи одномерной минимизации на шаге 1 алгоритма на практике, как правило, используются методы нулевого порядка (метод
перебора, деления отрезка пополам, золотого сечения). |
|
|||
Эффективность |
метода |
покоординатного |
спуска |
|
существенно зависит от свойств |
целевой функции. Если функция |
|||
сепарабельная, т.е. представима в виде |
|
|
||
|
|
n |
|
|
f (x1 ,.., xn ) |
fi (xi ) |
|
||
|
i |
1 |
, |
|
то через n шагов алгоритма |
находится оптимальное |
|||
решение. |
|
|
|
|
Пример1. Решить задачу методом покоординатного спуска.
f (x) 2x12 x22 min .
35
Рисунок 2.3.1.
Решение. Данная функция является сепарабельной (рис.2.3.1.). Выберем произвольную начальную точку, например, x0 = (3,3). В результате минимизации по направлению e1 , очевидно, получается точка x1=(0,3), а минимизация по направлению e2 приводит к оптимальному решению x* = (0,0) (рис.2.3.1).
Ответ: x1* 0; x2* 0; fmin 0.
Пример 2. Решить задачу
f (x) 2x12 x22 x1 x2 min
методом покоординатного спуска.
0.Зададим x0=(0.5,1), f(x0)=2. В качестве критерия
останова выберем критерий | f(x0) - f(x1) | < и зададим
=0.1.
1.В качестве первого направления выбираем e1. Решим задачу
Ф( ) 2(0.5 )2 (0.5 ) min
α* = -0.75. х1 = (-0.25,1), f(x1) = 0.375.
2. Полагаем х0 = х1 .
36
Рисунок 2.3.2.
3. В качестве следующего направления выбираем е2. Записываем задачу одномерной минимизации:
( ) (1 
)2 0.25(1 
) min .
α* = -0.875, х1 = (-0.25,0.125), f(x1) = 0.11.
4. Проверяем критерий останова:
|0.375-0.11| = 0.265> 
5.В качестве направления снова выбираем e1. Решим задачу одномерной минимизации по α:
( |
) 2 ( 0.25 |
)2 0.125 ( 0.25 |
) |
min . |
α* |
0.22. х1 = (-0.03,0.125), f(x1) 0.021. |
|
|
|
6.Полагаем х0 = х1 . |
|
|
|
|
7.В качестве направления выбираем е2. Записываем задачу одномерной минимизации:
37