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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

15
0xbx
axx
extrax2x
2
1
2
2
1
2
2
2
1
≥+
≤+
→−+−
,
)()(
(здесь a и b –произвольные числа)
§ 3. Теорема Куна -Таккера
Рассмотрим задачу оптимизации следующего вида:
fx
fxbim
x
ii
0
1
0
()max,
(),,,
→
≤=
≥
Ω
(1)
Эта задача допускает следующую эквивалентную перезапись:
ãäå),,(minmax
0
0
yx
y
x
Φ
≥
≥
−≥≥−+=Φ
∑
=
0,0,))}(()({),(
1
0
yxxfbyxfyx
m
i
iii
(2)
функция Лагранжа задачи (1).
Определение1. Двойственной задачей к задаче (1) называется задача вида
),(maxmin
0
0
yx
x
y
Φ
≥
≥
Определение 2. Точка (,),,,xyxRyR
nm0000
0≥∈∈ называется седловой
точкой функции Лагранжа, если выполняются неравенства
0yxyxyxyx
0000
≥∀Φ≤Φ≤Φ ,),,(),(),(
Определение 2'. Точка (,),,,xyxRyR
nm0000
0≥∈∈ называется седловой
точкой функции Лагранжа, если в этой точке
(x,y)
0x
0y
(x,y)
0y
0x
),y(x
00
Φ
≥
≥
=Φ
≥
≥
=Φ maxminminmax
Замечание 1. Определения 2 и 2' эквивалентны .
Теорема 1. (Достаточное условие экстремума).
Если (,),,xyxRyR
nm0000
0≥∈∈- седловая точка функции Лагранжа для
задачи (1), то
x
0
−
решение задачи (1).
Определение 3. Множество
Ω
называется регулярным (по Слейтеру ) если
существует точка
$
x
≥
0
такая что fxbim
ii
(
$
),,<∀=1
Определение 3'. Множество
Ω
называется регулярным, если для любого
i=1, m существует точка
$
,x
i
≥ 0
такая что fxb
i
i
i
(
$
)<.
Замечание 2. Определения 3 и 3' эквивалентны .
Необходимое условие экстремума для задач вида (1) формулируется в
теореме Куна- Таккера.
Теорема 2. ( теорема Куна-Таккера).
Пусть (1) является задачей выпуклого программирования, множество
Ω
регулярно по Слейтеру . Тогда если
x
0
−
решение задачи (1), то 
                                                        15
           2              2
   ( x1 −2 ) +( x 2 −a ) → extr
          x12 +x 2 ≤a,                                       (здесь a и b –произвольные числа)
         bx1 +x 2 ≥0


                      § 3. Теорема Куна-Таккера
Рассмотрим задачу оптимизации следующего вида:
                           f 0 ( x ) → max,
                            f i ( x ) ≤bi , i =1, m,�                                            (1)
                                                     � Ω
                            x ≥0                      �
Эта задача допускает следующую эквивалентную перезапись:
                           max min Φ( x, y ), ãäå
                                      x ≥0       y ≥0
                                      m
          Φ ( x , y ) ={ f 0 ( x ) + ∑ y i ( bi − f i ( x ))} ,        x ≥0 , y ≥0 −             (2)
                                      i =1
функция Лагранжа задачи (1).
Определение1. Двойственной задачей к задаче (1) называется задача вида
                           min max Φ ( x , y )
                                          y ≥0      x ≥0

Определение 2. Точка ( x , y ) ≥0, x 0 ∈R n , y 0 ∈R m , называется седловой
                                  0       0

точкой функции Лагранжа, если выполняются неравенства
                Φ( x, y 0 ) ≤Φ( x 0 , y 0 ) ≤Φ( x 0 , y ), ∀x, y ≥0
Определение 2'. Точка ( x 0 , y 0 ) ≥0, x 0 ∈R n , y 0 ∈R m , называется седловой
точкой функции Лагранжа, если в этой точке
                    Φ(x 0 ,y 0 ) =max min Φ(x,y) =min max Φ(x,y)
                                  x≥0 y≥0          y≥0 x≥0
За мечани е 1. Определения 2 и 2' эквивалентны.
Теорема 1. (Достаточное условие экстремума).
Если ( x 0 , y 0 ) ≥0, x 0 ∈R n , y 0 ∈R m - седловая точка функции Лагранжа для
задачи (1), то x 0 −решение задачи (1).
Определение 3. Множество Ω называется регулярным (по Слейтеру) если
существует точка x ≥0, такая что f i ( x)

Страницы