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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
существует ,0y
0
≥ ,
m0
Ry ∈ что (,)xy
00
удовлетворяет условиям а)-
d) теоремы 3.
Теорема 5 (Условия Ф . Джона) Пусть (1) является задачей выпуклого
программирования, множество
Ω
регулярно по Слейтеру , функции
fxim
i
(),,=0 являются непрерывно дифференцируемыми . Для того, чтобы
точка
x
0
была решением задачи (1) необходимо и достаточно, чтобы
существовал вектор yyR
m00
0≥∈,, такой что в точке (,)xy
00
выполняется
условие (3).
Замечание 8. Условие (3) означает, что градиент целевой функции является
линейной комбинацией градиентов активных ограничений, включая условия
неотрицательности . При этом градиенты , соответствующие ограничениям,
имеют в разложении неотрицательные коэффициенты , а градиенты ,
соответствующие условиям неотрицательности (т.е. единичные орты ) -
неположительные. Так, например, на рис. 5 в точке x* достигается максимум
функции
)( xf
0
, а в точке
x
ˆ
- нет (т.к. вектор
)
ˆ
( xf
1
∇
войдет в разложение (3) с
отрицательным коэффициентом).
*)( xf
1
∇
*)( xf
0
∇
x* *)( xf
2
∇
x
ˆ
Ω
Замечание 9. Если условия неотрицательности в задаче (1) отсутствуют, то
разложение (3) переписывается следующим образом:
∑
∈
∇=∇
)(
)()(
0
xIi
0
i
0
i
0
0
xfyxf
(3')
Связь между приведенными фактами и теоремами можно
проиллюстрировать в виде следующей таблицы
Ω - регулярно , (1) - ЗВП
,Ω∈
0
x
(1) - ЗВП, (1) - ЗВП,
−
)( xf
i
(1) - ЗВП
−
)( xf
i
−
)( xf
i
непрер.
x
0
является
решением задачи
(1)
(x
0
,y
0
) - седловая
точка функции
Лагранжа
,
y
x
Φ
)
ˆ
(xf
0
∇
)
ˆ
(xf
1
∇
)
ˆ
(xf
3
∇
Рис 5.
                                                        17
 существует y ≥0, y ∈R , что ( x 0 , y 0 ) удовлетворяет условиям а)-
                        0            0    m

 d) теоремы 3.
 Теорема 5 (Условия Ф. Джона) Пусть (1) является задачей выпуклого
 программирования, множество Ω             регулярно по Слейтеру, функции
  f i ( x ), i =0, m являются непрерывно дифференцируемыми. Для того, чтобы
 точка x 0 была решением задачи (1) необходимо и достаточно, чтобы
 существовал вектор y 0 ≥0, y 0 ∈R m , такой что в точке ( x 0 , y 0 ) выполняется
 условие (3).
 Замечание 8. Условие (3) означает, что градиент целевой функции является
 линейной комбинацией градиентов активных ограничений, включая условия
 неотрицательности. При этом градиенты, соответствующие ограничениям,
 имеют в разложении неотрицательные коэффициенты, а градиенты,
 соответствующие условиям неотрицательности (т.е. единичные орты) -
 неположительные. Так, например, на рис. 5 в точке x* достигается максимум
 функции f 0 (x) , а в точке x̂ - нет (т.к. вектор ∇f 1 (xˆ) войдет в разложение (3) с
 отрицательным коэффициентом).

                                              ∇ f 1 (x*)

                                                           ∇ f 0 (x*)
            ∇f 0 (xˆ)                         x*         ∇ f 2 (x*)
∇f 1 (xˆ)
                  x̂        Ω
∇f 3 (xˆ)



                            Рис 5.
 Замечание 9. Если условия неотрицательности в задаче (1) отсутствуют, то
 разложение (3) переписывается следующим образом:
                     ∇ f 0 ( x 0 ) = ∑ y i0 ∇ f i ( x 0 )       (3')
                                           i∈I ( x0 )
      Связь между приведенными фактами                                  и   теоремами     можно
 проиллюстрировать в виде следующей таблицы

                                     Ω - регулярно, (1) - ЗВП
        x0 является                                                         (x0,y0) - седловая
     решением задачи                                                         точка функции
             (1)                                                            Лагранжа Φ( x, y )

    x 0 ∈Ω,            (1) - ЗВП,                                       (1) - ЗВП,     f i (x) −
   (1) - ЗВП           f i (x) −                                           f i (x) −   непрер.

Страницы