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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

16
существует yyR
m00
0≥∈,, что (,)xy
00
- седловая точка функции
Лагранжа.
Теорема 3. (дифференциальный вариант теоремы Куна –Таккера )
Пусть (1) является задачей выпуклого программирования, а функции
fxim
i
(),,=0 являются непрерывно дифференцируемыми . Для того, чтобы
точка
mn
RyRxyx ∈∈≥
0000
,,0),( была седловой точкой функции Лагранжа,
необходимо и достаточно , чтобы в ней выполнялись условия:
=Φ∇
≥Φ∇
=Φ∇
≤Φ∇
==
Φ
=≥
Φ
==
Φ
=≤
Φ
0yyxd
0yxc
0xyxb
0yxa
m1i0y
y
yx
d
m1i0
y
yx
c
n1j0x
x
yx
b
n1j0
x
yx
a
T000
y
00
y
T000
x
00
x
i
i
00
i
00
j
j
00
j
00
))(,()
,),()
,))(,()
,),()
,
,,
),(
)
,,,
),(
)
,,,
),(
)
,,,
),(
)
∂
∂
∂
∂
∂
∂
∂
∂
Замечание 3. Из теоремы 1 следует, что при выполнении условий теоремы
3 точка
0
x
, являющаяся решением системы a)-d) ,будет решением задачи (1).
Замечание 4. Если в задаче (1) ищется минимум функции fx
0
(), то знак
неравенств а) меняется на противоположный.
Замечание 5. Знаки неравенств с ) связаны со знаками неравенств в
ограничениях задачи (1) и по сути являются эквивалентно переписанными
исходными неравенствами .
Замечание 6. Неравенства b) и d) называются условиями дополняющей
нежесткости .
Замечание 7. Если условия выпуклости в задаче нарушаются , то система
a) – d) может не иметь решения.
Теорема 4. Пусть (1) является задачей выпуклого программирования,
функции fxim
i
(),,=0 являются непрерывно дифференцируемыми . Если в
точке (,)xy
00
0≥ выполняются условия а)-d) теоремы 3, то справедливо
разложение
∑∑
∈
∈
−∇=∇
)(
)(
)()(
0
0
xJj
j0
j
xIi
0
i
0
i
0
0
evxfyxf
, (3)
где
0
),(
00
0
≥
Φ
−=
j
j
x
yx
v
∂
∂
- неотрицательные коэффициенты ,
−
j
e
j-тый орт,
)(
0
xI - множество индексов ограничений, активных в точке
0
x
, т.е
})(:{)(
i
bx
i
fixI
00
== , }:{)( 0xjxJ
0
j
0
== . И наоборот, если в точке
(,
$
)xy
00
, где ,Ω∈
0
x ))(,(
ˆ
00
i
0
xIiyy ∈= , выполняется равенство (3), то 
                                                          16
существует             0          0
                                       y ≥0, y ∈R , что ( x 0 , y 0 ) - седловая точка функции
                                         m

Лагранжа.
Теорема 3. (дифференциальный вариант теоремы Куна –Таккера )
             Пусть (1) является задачей выпуклого программирования, а функции
 f i ( x ), i =0, m являются непрерывно дифференцируемыми. Для того, чтобы
точка ( x 0 , y 0 ) ≥0, x 0 ∈R n , y 0 ∈R m была седловой точкой функции Лагранжа,
необходимо и достаточно, чтобы в ней выполнялись условия:
                � ∂Φ( x 0 , y 0 )
                 � a)                                  ≤0, j =1, n,
                  �                      ∂ x   j
                    �                       0      0                       � a)∇ x Φ( x 0 , y 0 ) ≤0,
                                     ∂Φ ( x    , y   )
                      � b)                             x j =0, j =1, n, �
                       ��                ∂x j                               �� b)∇ x Φ( x 0 , y 0 )( x 0 ) T =0,
                          �                                            , �                     0   0
                            � ∂Φ( x , y )   0      0
                                                                              � c)∇ y Φ( x , y ) ≥0,
                             � c)                      ≥0,i =1, m,             �
                              �          ∂ y  i
                                                                                               0   0    0 T
                                                                                 �� d )∇ y Φ( x , y )( y ) =0
                                � ∂Φ( x 0 , y 0 )
                                 � d)                  y i =0,i =1, m
                                  ��      ∂y i
Замечание 3. Из теоремы 1 следует, что при выполнении условий теоремы
3 точка x 0 , являющаяся решением системы a)-d) ,будет решением задачи (1).
Замечание 4. Если в задаче (1) ищется минимум функции f 0 (x ) , то знак
неравенств а) меняется на противоположный.
Замечание 5. Знаки неравенств с) связаны со знаками неравенств в
ограничениях задачи (1) и по сути являются эквивалентно переписанными
исходными неравенствами.
Замечание 6. Неравенства b) и d) называются условиями дополняющей
нежесткости.
Замечание 7. Если условия выпуклости в задаче нарушаются, то система
a) – d) может не иметь решения.
Теорема 4. Пусть (1) является задачей выпуклого программирования,
функции f i ( x ), i =0, m являются непрерывно дифференцируемыми. Если в
точке ( x 0 , y 0 ) ≥0 выполняются условия а)-d) теоремы 3, то справедливо
разложение
                        ∇ f 0 ( x 0 ) = ∑ y i0 ∇ f i ( x 0 ) − ∑ v 0j e j , (3)
                                             i∈I ( x0 )            j∈J ( x 0 )

           ∂Φ( x 0 , y 0 )
где v 0j =−                      ≥0 - неотрицательные коэффициенты, e j −j-тый орт,
              ∂x j
I ( x 0 ) -множество индексов ограничений, активных в точке                                       x 0 , т.е
I ( x 0 ) ={i : f i ( x 0 ) =bi } , J ( x 0 ) ={ j : x 0j =0} . И наоборот, если в точке
( x 0 , y 0 ) , где x 0 ∈Ω, yˆ 0 =( yi0 , i ∈I ( x 0 )) , выполняется равенство (3), то

Страницы