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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
4. ТЕОРИЯ ДВОЙСТВЕННОСТИ
В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
4.1 Общие определения. Основные свойства
Рассмотрим задачу нелинейного программирования вида:
min)(
®
x
j
mixf
i
...1,0)(
=
£
(1)
S
x
Î
,
где mif
i
...1,,
=
j
– заданные функции,
S
– некоторое множество.
Построим для нее функцию Лагранжа:
å
=
³Î+=F
m
i
ii
ySxxfyxyx
1
.0,),()(),(
j
Исходная задача перепишется в виде:
),(maxmin
0
yx
y
sx
F
³
Î
.
Двойственная к ней задача по определению имеет вид:
),(minmax
0
yx
sx
y
F
Î
³
.
Введем обозначение: ).,(min)( yxy
sx
=
Î
w
Функцию )( y
w
называют
двойственной функцией.
Тогда двойственную задачу можно переписать в виде ).(max
0
y
y
w
³
Утверждение. Докажем, что )(max
0
y
y
w
³
является задачей выпуклого
программирования.
Доказательство.
Вначале докажем, что
å
=
Î"³"+£
m
i
ii
Sxyxfyxy
1
.,0),()()(
jw
(*)
Этот факт непосредственным образом вытекает из неравенства:
.,0),,(),(min Sxyyxyx
sx
Î
"
³
"
£
Î
Покажем теперь, что наша задача является задачей выпуклого про-
граммирования (
w
является выпуклой вверх функцией), т. е.
].1,0[),()1()())1((
2121
Î-+³-+
awaawaaw
yyyy (**)
Из (*) имеем: 
                    4. ТЕОРИЯ ДВОЙСТВЕННОСТИ
                В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

                 4.1 Общие определения. Основные свойства

     Рассмотрим задачу нелинейного программирования вида:
                                        � ( x) � min
                                     f i ( x) � 0, i � 1...m                            (1)
                                          x�S,
где � , f i , i � 1...m – заданные функции, S – некоторое множество.
     Построим для нее функцию Лагранжа:
                                                 m
                          � ( x, y ) � � ( x) � � y i f i ( x ), x � S , y � 0.
                                                i �1

     Исходная задача перепишется в виде:
                                         min max � ( x, y ) .
                                          x�s   y �0

     Двойственная к ней задача по определению имеет вид:
                                max min � ( x, y ) .
                                          y�0   x�s

     Введем обозначение: � ( y ) � min � ( x, y ). Функцию � ( y ) называют
                                    x�s

двойственной функцией.
    Тогда двойственную задачу можно переписать в виде max � ( y ).
                                                                                  y�0




     Утверждение. Докажем, что max � ( y ) является задачей выпуклого
                                                y�0

программирования.
    Доказательство.
    Вначале докажем, что
                                                 m
                             � ( y ) � � ( x) � � y i f i ( x ), �y � 0, �x � S .        (*)
                                                 i �1

     Этот факт непосредственным образом вытекает из неравенства:
                            min � ( x, y ) � � ( x, y ), �y � 0, �x � S .
                             x�s

    Покажем теперь, что наша задача является задачей выпуклого про-
граммирования ( � является выпуклой вверх функцией), т. е.
                � (�y 1 � (1 � � ) y 2 ) � �� ( y 1 ) � (1 � � )� ( y 2 ), � � [0,1]. (**)
     Из (*) имеем:

                                                23

Страницы