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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

51
k
Tkk
zyxf ≤∇ ))(( ,
(
)
,,))((
k
k
Tkk
j
xIjzyxg ∈≤∇
n1i1y1
k
i
,, =≤≤− .
Шаг 5. Если 0y
k
= или
ε
≤
k
z , то положить
k
x
x
=
*
. Иначе для
найденного вектора
k
y определить
(
)
m10k
β
β
β
α
,...,,min
=
,
где
0
β
выбирается из условия )(min)(
kk
0
k
0
k
yxfyxf ββ
β
+=+
>
, а
m1j
j
,,
=
β
- максимально возможное перемещение из точки
x
вдоль
направления
y
с учетом
-го ограничения, которое найдено из условия
0yxg
ij
=
+
)(
β
.
Шаг 6. Найти очередное приближение
k
k
k1k
yxx α +=
+
.
Пример 2. Найти минимум в задаче
(
)
(
)
min→−+−
2
2
2
1
5x4x
01xx
21
≤
−
+
0x0x
21
≥
≥
, .
Решение.
1. Возьмем в качестве начальной точки
(
)
9500x
0
,;= . Легко проверить, что
данная точка принадлежит допустимому множеству, причем
{
}
2xI
0
= )( .
Положим
03
0
,
=
ε
,
0
k
=
.
2. Найдем
(
)
188xf
0
,;)( −=∇ . Так как ε>∇ )(
k
xf , то продолжим решение
задачи . Для нахождения
0
y вычислим
(
)
01xg
0
2
;)( −=∇ и составим
задачу линейного программирования
min
→
0
z
0
0
2
0
1
zy18y8 ≤−− ,
0
0
1
zy ≤−
1y1
0
1
≤≤− , 1y1
0
2
≤≤− .
3. Решая полученную задачу симплексным методом, получим 1y
0
1
= ,
1y
0
2
= , 0z
0
=
.
Метод линеаризации (Франка Вулфа )
Рассмотрим задачу минимизации выпуклой нелинейной функции на
множестве, задаваемом линейными ограничениями :
Ω
≥
≤
→
0x
bAx
xf min)(
                                                   51
                  k        k T
             ∇ f ( x )( y ) ≤z k ,
                                                                   ( )
                                 ∇ g j ( x k )( y k ) T ≤z k , j ∈I x k ,
                                       −1 ≤ y ik ≤1, i =1, n .
        Шаг 5. Если y k =0 или z k ≤ε , то положить x * =x k . Иначе                               для
найденного вектора y k определить
                         α k =min (β0 , β1 ,..., βm ),
где     β0     выбирается         из    условия         f ( x k +β0 y k ) =min f ( x k +βy k ) ,     а
                                                                            β >0
β j , j =1, m - максимально возможное перемещение из точки x вдоль
направления y с учетом i -го ограничения, которое найдено из условия
g j ( x +βi y ) =0 .
     Шаг 6. Найти очередное приближение x k +1 =x k +α k y k .
Пример 2. Найти минимум в задаче
                          (x1 −4 )2 +(x 2 −5 )2 → min
                              x1 +x 2 −1 ≤0
                              x1 ≥0, x 2 ≥0 .
Решение.
1. Возьмем в качестве начальной точки x 0 =(0;0,95 ). Легко проверить, что
   данная точка принадлежит допустимому множеству, причем I ( x 0 ) ={2}.
   Положим ε =0,03 , k =0 .
2. Найдем ∇ f ( x 0 ) =(−8;8,1). Так как ∇ f ( x k ) >ε , то продолжим решение
      задачи. Для нахождения y 0 вычислим ∇ g 2 ( x 0 ) =(−1;0 ) и составим
      задачу линейного программирования
                                 z 0 → min
                                        −8 y 10 −8,1 y 20 ≤z 0
                                              − y 10 ≤z 0
                                   −1 ≤ y 10 ≤1 , −1 ≤ y 20 ≤1 .
3. Решая полученную задачу симплексным методом, получим                                     y 10 =1 ,
      y 20 =1 , z 0 =0 .
                      Метод линеаризации (Франка Вулфа)
    Рассмотрим задачу минимизации выпуклой нелинейной функции на
множестве, задаваемом линейными ограничениями:
                              f ( x) → min
                                             Ax ≤b �
                                                     � Ω
                                             x ≥0 �

Страницы