Элементы теории двойственности. Чернышова Г.Д - 30 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

30
Из последнего соотношения следует, что ))(),..,(()(
1
xfxfxf
m
=
,
где
X
x
Î
, является субградиентом функции w в точке
y
.
Таким образом, для вычисления субградиента в точке
0
³
y
необхо-
димо решить задачу )y,x(min
Sx
F
Î
. Пусть
x
является решение этой задачи.
Тогда mixf
i
,..,1),(
=
являются координатами субградиента функции w в
точке
y
.
Покажем, что найденная точка
является решением следующей за-
дачи
min
)
x
(
®
j
;,1),()( mixfxf
ii
=£ (11)
S
x
Î
.
Очевидно, что точка
x
является допустимой в этой задаче. Кроме то-
го, для любой допустимой в (11) точки x справедлива следующая цепочка
неравенств
åå å
== =
=-F£-F=-+£
m
i
ii
m
i
m
i
iiiii
xxfyyxxfyyxxfxfyxx
11 1
)()(),()(),())()(()()(
jjj
.
Так как для любой допустимой в задаче (11) точки x выполняется не-
равенство )()( xx
j
j
£
, то отсюда следует, что точка
x
является решением
задачи (11).
Схема двойственного алгоритма Удзавы
Шаг 0. Задать начальные значения .0,,0
00
=³ Nxy
Шаг 1. Положить ),(minarg
1 N
Sx
N
yxx F=
Î
+
. Проверка на останов. Оста-
новка алгоритма может осуществляться по следующим критериям
а) mixf
N
i
,..,1,|)(|
1
="£
+
e
;
б)
e
£
-
+
||||
||||
1
N
NN
x
xx
;
в) По числу итераций
max
N .
Шаг 2. Положить
1
()()
NN
wyfx
+
Ñ=
)
.
Шаг 3. Вычислить
1+N
y по формуле
1
[()]
NNN
yywy
a
++
=+Ñ
)
.
Знак «+» означает, что берется проекция на положительную ось. Уве-
личить N на единицу. Переход к шагу 1. 
      Из последнего соотношения следует, что                                           f ( x) � ( f 1 ( x),.., f m ( x)) ,
где x � X , является субградиентом функции w в точке y .
      Таким образом, для вычисления субградиента в точке y � 0 необхо-
димо решить задачу min �( x , y ) . Пусть x является решение этой задачи.
                                   x�S

Тогда f i ( x ), i � 1,.., m являются координатами субградиента функции w в
точке y .
    Покажем, что найденная точка x является решением следующей за-
дачи
                              � ( x ) � min
                                                f i ( x) � f i ( x ), i � 1, m;                                  (11)
                                                            x�S.
     Очевидно, что точка x является допустимой в этой задаче. Кроме то-
го, для любой допустимой в (11) точки x справедлива следующая цепочка
неравенств
                     m                                            m                            m
� ( x ) � � ( x ) � � y i ( f i ( x ) � f i ( x)) � � ( x , y ) � � y i f i ( x) �� ( x, y ) � � y i f i ( x) � � ( x) .
                    i �1                                         i �1                          i �1

    Так как для любой допустимой в задаче (11) точки x выполняется не-
равенство � ( x ) � � ( x) , то отсюда следует, что точка x является решением
задачи (11).

                   Схема двойственного алгоритма Удзавы
      Шаг 0. Задать начальные значения y 0 � 0, x 0 , N � 0.
      Шаг 1. Положить x N �1 � arg min
                                    �
                                       � ( x, y N ) . Проверка на останов. Оста-
                                                      x S

новка алгоритма может осуществляться по следующим критериям
    а) | f i ( x N �1 ) |� � , �i � 1,.., m ;
         || x N �1 � x N ||
      б)                    �� ;
              || x N ||
      в) По числу итераций N max .
                                    �
      Шаг 2. Положить � w( y N ) � f ( x N �1 ) .
      Шаг 3. Вычислить y N �1 по формуле
                                                                �
                                              y N �1 � [ y N � �� w( y N )]� .
    Знак «+» означает, что берется проекция на положительную ось. Уве-
личить N на единицу. Переход к шагу 1.
                                   30

Страницы