ВУЗ:
Составители:
Рубрика:
35
Ф (α )=f(x
0
+ α
e
j
)
R∈
→
α
min
, т.е. найти α *.
Положить х
1
= х
0
+ α *е
j
, вычислить f(x
1
).
Шаг 2. Если j<n, то положить х
0
= х
1
, j=j+1 и перейти к шагу 1, иначе
к шагу 3.
Шаг 3. Проверить выполнение критерия останова (например, ||x
0
-x
1
||<
ε
или |f(x
0
)-f(x
1
)|<
ε
). Если он выполняется , то положить x*=x
1
, f*=f(x
1
) и
закончить поиск. Иначе - положить х
0
=х
1
, f(x
0
)=f(x
1
), j=1 и перейти к шагу
1.
Замечание . Для приближенного решения вспомогательной задачи
одномерной минимизации на шаге 1 алгоритма на практике, как правило,
используются методы нулевого порядка (метод перебора, деления отрезка
пополам , золотого сечения).
Эффективность метода покоординатного спуска существенно зависит
от свойств целевой функции. Если функция сепарабельная , т.е. представима
в виде
∑
=
=
n
1i
iin1
xfxxf )(),..,( , то через n шагов алгоритма находится
оптимальное решение.
Пример 1. Решить задачу min2)(
2
2
2
1
→+= xxxf методом
покоординатного спуска.
x
1
x
0
x* 3
Пример 2. Решить задачу min2)(
21
2
2
2
1
→++= xxxxxf методом
покоординатного спуска.
Решение.
0. Зададим x
0
=(0.5,1), f(x
0
)=2. В качестве критерия останова выберем
критерий |f(x
0
)-f(x
1
)|<
ε
и зададим
ε
=0.1.
1. В качестве первого направления выбираем e
1
. Решим задачу одномерной
минимизации по α :
.min)5.0()5.0(2)(
2
→+++=Φ ααα
α*=-0.75, х
1
=(-0.25,1), f(x
1
)=0.375.
2. Полагаем х
0
= х
1
.
3. В качестве следующего направления
выбираем е
2
. Записываем задачу
Решение.
Данная функция является
сепарабель
ной . Выберем
произвольную начальную точку ,
например, x
0
=(3,3).
В результате
минимизации по направлению e
1
,
оче
видно, получается точка
x
1
=(0,3), а ми
нимизация по
направлению e
2
приводит к
оптимальному решению x*=(0,0).
x
0
x
1
1
35
Ф(α)=f(x0+ α ej) → min , т.е. найти α*.
α∈R
Положить х1=х0+ α*еj, вычислить f(x1).
Шаг 2. Если j
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
