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

                      4.2 Двойственный алгоритм Удзавы

       Рассмотрим следующую задачу
                                             � ( x) � min                                 (1)
                                           f i ( x) � 0, i � 1, m;                        (2)
                                                      x�S.        (3)
       Функция Лагранжа для задачи (1)–(3) записывается следующим обра-
зом:
                                                         m
                             � ( x, y ) � � ( x) � � y i f i ( x ), x � S , y � 0 .       (4)
                                                         i �1

       По определению задача двойственная к (1)–(3) имеет вид
                                 max min � ( x, y ) .                                     (5)
                                             y�0      x�S

       Введем следующее обозначение
                                      w( y ) � min � ( x, y ), y � 0 .                    (6)
                                                x�S

       В введенных обозначениях задача (5) может быть переписана в виде
                                    max w � y � .                    (7)
                                                   y�0

     Как было показано, двойственная задача (7) является задачей выпук-
лого программирования.
     Определение 1. Если для функции w : � � R m � R существует вектор
€w( y 0 ) � R m такой, что выполняется неравенство
�
                                             € T w( y 0 )( y � y 0 ), �y � �, y 0 � � ,
                         w( y ) � w( y 0 ) � �                                            (8),
то вектор �€w( y 0 ) называется субградиентом функции w в точке y 0 .
    Утверждение 1. Для любой выпуклой функции w : � � R m � R в любой
внутренней точке y* � � существует субградиент.
    Доказательство. Для определенности будем считать, что функция w
выпукла            вверх.           Рассмотрим      подграфик     функции    w
X � {( z, y ) � R n �1 : z � w( y )} . В силу выпуклости функции w множество X
является выпуклым. Тогда в точке �w � y * �, y * � существует опорная гиперп-
лоскость, то есть существует вектор (c0 , c) � R n �1 , (c0 , c) � 0 , что
                           c 0T w( y*) � c T y* � c0T z � c T y, �( z , y ) � X .         (9)
       Покажем, что        c0 � 0 .         Положив в (9) y=y*, получим, что
c0T ( w( y*) � z ) � 0 . Так как w( y*) � z � 0 , то c0 � 0 . Покажем, что c0 � 0 .
                                                   28