Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

b)

x

3y

extr

(x

5) 2

( y

3) 2

9,

(x

5) 2

( y

3) 2

36,

x

y 8,

x

0, y

0

c)

| x

5 |

y

extr

5x

3y

24,

f 0 (x)

max,

f i (x)

bi ,i 1, m,

x 0

(3.3.1)

Эта задача допускает следующую эквивалентную

перезапись:

max min Ф(x, y),

x 0 y 0

m

(3.3.2)

где Ф(x, y) { f0 (x)

yi (bi fi (x))}, x 0, y 0

i 1

Ô (x, y0 ) Ô (x0 , y0 ) Ô (x0 , y),

x, y 0.

Определение 2'. Точка

(x 0 , y 0 ) 0, x 0 Rn , y 0

Rm ,

Ô(x0 , y0 )

max minÔ(x, y)

min maxÔ(x, y).

x 0

y

0

y 0

x 0

З а м е ч а н и е . Определения 2 и 2' эквивалентны.

Теорема 1 . (Достаточное условие экстремума).

Если

(x0 , y0 )

0, x0

Rn , y0

Rm

- седловая

точка

функции Лагранжа для задачи (3.3.1), то

x0

-

решение

задачи

(3.3.1).

Определение 3. Множество

называется регулярным (по

Слейтеру) если существует точка xˆ

0 , такая что

Определение

3'. Множество

называется регулярным,

_____

если для любого i

1, m существует точка xˆ 0 такая что

f

i

(xi )

b

i .

Замечание. Определения 3 и 3' эквивалентны.

Необходимое условие экстремума для задач вида (3.3.1)

формулируется в теореме КунаТаккера.

Теорема 2 . ( теорема Куна-Таккера).

Пусть

(3.3.1)

является

задачей

выпуклого

программирования, множество

регулярно по Слейтеру. Тогда

Теорема

3 . (дифференциальный вариант теоремы Куна –

Таккера )

Пусть

(3.3.1)

является

задачей

выпуклого

_____

программирования, а

функции

fi (x), i 0, m

являются

непрерывно дифференцируемыми. Для того, чтобы Точка

(x0 , y0 )

0, x0 Rn , y0

Rm ,

условий теоремы 3

точка x0 , являющаяся решением системы a )--

d) ,будет решением задачи (3.3.1).

З а м е ч а н и е

2.

Если в

задаче (3.3.1)

ищется минимум

функции

f0 (x) ,

то

знак

неравенств

а) меняется на

Т е ор е м а 4.

Пусть (3.3.1)

является задачей выпуклого

_____

программирования,

функции

fi (x), i 0, m,

являются

f

0

(x0 )

y0 f

(x0 )

0e j ,

(3.3.3)

i

i

j

i I ( x0 )

j J ( x0 )

где

v 0j

(x 0 , y 0 )

0

x j

- неотрицательные

коэффициенты,

e j

j-тый орт,

I (x0 )

-

множество индексов ограничений,

активных в

точке

x0

,

т.е

I (x0 ) {i : fi (x0 ) bi }, J (x0 ) { j : x0j

0}.

И наоборот, если в точке

(x 0 , y 0 )

, где

x

0

,

y0

( y0 , i I (x0 ))

ˆ

i

,

выполняется равенство (3.3.3), то существует

y0

0,

y0

R m ,

что (x0 , y0 ) удовлетворяет условиям а)-d) теоремы 3.

Теорема 5

(Условия Ф. Джона)

Пусть

(3.3.1)

является

задачей

выпуклого

программирования,

множество

регулярно по

Слейтеру,

______

функции

fi (x), i

0, m,

являются

непрерывно

дифференцируемыми. Для того,

чтобы точка x 0 была решением

y0 0,

y0 Rm , такой что в точке (x0 , y0 ) выполняется условие

(3.3.3).

З а м е ч а н и е

1. Условие (3.3.3) означает, что градиент

целевой

функции

является линейной комбинацией градиентов

Так, например, на

рис.3.3.1

в

точке x* достигается

максимум функции f0 (x) ,

а в точке

x

ˆ

ˆ -

нет (т.к. вектор f1 (x)

f0 (x0 )

yi0 fi (x0 )

i

I ( x0 )

(3.3.3')

Теорема 6 . (Теорема Куна-Таккера для задач с линейными

ограничениями). Пусть (3.3.1)

является задачей

выпуклого