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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

29
Предположим противное. Тогда из (9) следует, что
WÌÎ"³- )*,(,0)*(
e
yByyyc
T
, (10)
где )*,(
e
yB – шар с центром в y* и радиуса
e
. В силу того, что y* – внут-
ренняя точка, такой шар существует. Из (10) следует, что
0
=
c
.
Но 0),(
0
¹
cc . Мы пришли к противоречию. Значит, 0
0
>
c .
Положив в (10)
(),zwyy
=ÎW
и разделив неравенство на
0
c , получим, что
)*(*)()(
0
yy
c
c
ywyw
T
-+£ .
Из последнего неравенства следует, что вектор –
0
c
c
является субгра-
диентом функции w точке y*. Утверждение доказано.
Утверждение 2. Точка y* является точкой максимума для выпуклой
вверх функции RRw
m
®ÌW: тогда и только тогда, когда в этой точке
существует субградиент wÑ
€
равный нулю.
Доказательство. Пусть y* является точкой максимума функции w.
Тогда из определения максимума следует следующее неравенство
W
£
yywyw *),()( , а значит, непосредственно из определения субгради-
ента следует, что нуль является субградиентом функции w в точке y*.
Обратно, пусть субградиент
w
Ñ
)
в точке y* равен нулю. Непосредст-
венно из определения субградиента следует, что y* является точкой мак-
симума. Утверждение доказано.
Для функции w определенной с помощью (6) в любой точке 0
³
y
можно предложить следующую схему вычисления субградиента. Введем
следующее обозначение )}(),(:{ ywyxxX
=
F
=
. Отметим, что выполняются
следующие соотношения
å
=
Î"+£
m
i
ii
Sxxfyxyw
1
),()()(
j
,
å
=
Î"+=
m
i
ii
Xxxfyxyw
1
),()()(
j
.
Вычитая из неравенства равенство, получим выполнение следующего
неравенства
å
=
Î"-£-
m
i
iii
Xxxfyyywyw
1
),()()()( . 
    Предположим противное. Тогда из (9) следует, что
                      c T ( y * � y ) � 0, �y � B( y*, � ) � � ,                         (10)
где B ( y*, � ) – шар с центром в y* и радиуса � . В силу того, что y* – внут-
ренняя точка, такой шар существует. Из (10) следует, что c � 0 .
Но (c0 , c) � 0 . Мы пришли к противоречию. Значит, c0 � 0 .
    Положив в (10) z � w( y), y � � и разделив неравенство на c0 , получим, что
                                                  cT
                                 w( y ) � w( y*) � ( y * � y ) .
                                                  c0
                                                                           c
    Из последнего неравенства следует, что вектор –                           является субгра-
                                                                           c0
диентом функции w точке y*. Утверждение доказано.
    Утверждение 2. Точка y* является точкой максимума для выпуклой
вверх функции w : � � R m � R тогда и только тогда, когда в этой точке
существует субградиент �€w равный нулю.
      Доказательство. Пусть y* является точкой максимума функции w.
Тогда из определения максимума следует следующее неравенство
w( y ) � w( y*), �y � � , а значит, непосредственно из определения субгради-
ента следует, что нуль является субградиентом функции w в точке y*.
                                  �
    Обратно, пусть субградиент � w в точке y* равен нулю. Непосредст-
венно из определения субградиента следует, что y* является точкой мак-
симума. Утверждение доказано.
     Для функции w определенной с помощью (6) в любой точке y � 0
можно предложить следующую схему вычисления субградиента. Введем
следующее обозначение X � {x : � ( x, y ) � w( y )} . Отметим, что выполняются
следующие соотношения
                                                    m
                             w( y ) � � ( x) � � y i f i ( x), �x � S ,
                                                   i �1
                                                   m
                             w( y ) � � ( x) � � y i f i ( x ), �x � X .
                                                   i �1

    Вычитая из неравенства равенство, получим выполнение следующего
неравенства
                                            m
                         w( y ) � w( y ) � � ( y i � y i ) f i ( x), �x � X .
                                            i �1




                                              29

Страницы