Методы оптимизации. Азарнова Т.В - 50 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

52
Метод линеаризации основан на замене в окрестности точки x
k
нелинейной функции
)
(
x
f
линейной функцией
T
k
xc
. Из формулы Тейлора
следует, что
Tkkk
xxxfxfxf ))(()()( −∇+≈ . Положим
TkT
k
xxfxc )( ∇=
.
Рассмотрим задачу линейного программирования
Ω
→ min
T
k
xc
Обозначим −
k
z решение к - той ЗЛП. Тогда направление
kkk
xzl −= в
исходной задаче будет подходящим. Формула пересчета имеет вид
k
k
kk
lxx α +=
+
1
, где шаг
k
α
ищется по правилу наискорейшего спуска с
учетом условия 10
≤
≤
k
α
( при таком выборе
k
α
точка
1
+
k
будет выпуклой
линейной комбинацией точек
k
z и
k
, что обеспечивает ее допустимость).
В качестве критериев останова алгоритма применяются стандартные
критерии: .||||,||)(||
11
εε <−<∇
+
+
kkk
xxxf
Алгоритм
Шаг 0. Зафиксировать
−
Ω
∈
0
начальное приближение.
Положить к =0.
Шаг 1. Решить задачу линейного программирования
Ω
→∇= min)(
TkT
k
xxfxc ,
найти
k
z .
Шаг 2. Зафиксировать вектор
kkk
xzl −= в качестве направления
поиска.
Шаг 3. Вычислить
)(
1
0
minarg
kk
k
lxf α
α
α +
≤≤
=
.
Шаг 4. Положить
k
k
kk
lxx α +=
+
1
Шаг 5. Проверить условия останова и , если они выполнены , вычисления
прекратить и взять точку
1k
+
в качестве искомого решения. Иначе
положить k=k+1 и перейти на шаг 1.
Пример 1. Решить методом линеаризации задачу нелинейного
программирования
min,)2()4(),(
22
→−+−= yxyxf
)2(,42
)1(,3
≤+
≤
+
yx
yx
0
,
≥
y
x
Решение. Данная задача была графически решена в § 2: x*=(5/2,1/2).
Для решения задачи методом линеаризации выберем x
0
Ω
∈
,
например, x
0
=(0,0). Вычислим 
                                              52
     Метод линеаризации основан     на замене в окрестности точки xk
нелинейной функции f (x) линейной функцией c k x T . Из формулы Тейлора
следует, что f ( x) ≈ f ( x k ) +∇ f ( x k )( x −x k ) T . Положим c k x T =∇ f ( x k ) x T .
     Рассмотрим задачу линейного программирования
                                       c k x T → min
                                                   Ω
                k
Обозначим z −решение к- той ЗЛП. Тогда направление                       l k =z k −x k в
исходной задаче будет подходящим. Формула пересчета имеет вид
x k +1 =x k +α k l k , где шаг α k ищется по правилу наискорейшего спуска с
учетом условия 0 ≤α k ≤1 ( при таком выборе α k точка x k +1 будет выпуклой
линейной комбинацией точек z k и x k , что обеспечивает ее допустимость).
 В качестве критериев останова алгоритма применяются стандартные
критерии: || ∇ f ( x k +1 ) ||<ε, || x k +1 −x k ||<ε.

                                         Алгоритм
Шаг 0. Зафиксировать x 0 ∈Ω −начальное приближение.
     Положить к=0.
Шаг 1. Решить задачу линейного программирования
                         c k x T =∇ f ( x k ) x T → min ,
                                                           Ω
                    k
         найти z .
Шаг 2. Зафиксировать вектор l k =z k −x k в качестве направления
      поиска.
Шаг 3. Вычислить α k =arg min f ( x k +α l k ) .
                        0≤α ≤1
                  k +1
Шаг 4. Положить x      =x k +α k l k
Шаг 5. Проверить условия останова и, если они выполнены, вычисления
      прекратить и взять точку x k +1 в качестве искомого решения. Иначе
       положить k=k+1 и перейти на шаг1.

Пример 1. Решить методом линеаризации задачу нелинейного
программирования
 f ( x, y ) =( x −4) 2 +( y −2) 2 → min,
x +y ≤3, (1)
x +2 y ≤4, (2)
x, y ≥0
Решение. Данная задача была графически решена в §2: x*=(5/2,1/2).
Для решения задачи методом линеаризации выберем x0 ∈Ω ,
                           например, x0=(0,0). Вычислим

Страницы