Задачи выпуклого программирования

1. Задачи выпуклого программирования

2.

Постановка задачи выпуклого программирования
f x1, x2 ,..., xn max (min) (1)
gi x1, x2 ,..., xn bi (i 1, ..., m)
x j 0 ( j 1, ..., n),
(2)
f X (1 ) X f ( X ) (1 ) f ( X ).
2
1
2
1
0 1
f X (1 ) X f ( X ) (1 ) f ( X ).
2
1
2
1
0 1

3.

Область
допустимых
значений
(2)
регулярности, если найдется такой вектор
обладает
свойством
xk , что все функции
qi ( xk ) bi (i 1, m) .
ЗНЛП называется задачей выпуклого программирования,
если функция (1) либо выпуклая, либо вогнута, а все функции g i
выпуклы.
Теорема Любой локальный экстремум
программирования является глобальным .
задачи
Функцией Лагранжа L называется следующая функция:
m
L( x ,..., x , y ,..., y ) f ( x ,..., x ) y [b g ( x ,..., x )].
1
n 1
m
1
n
i i i 1
n
i 1
выпуклого

4.

Седловой точкой функции Лагранжа L называется вектор X (0) ,Y (0) ,
для которого выполняется следующее условие:
L( x ,..., x , y (0) ,..., y (0) ) L( x(0) ,..., x(0) , y (0) ,..., y (0) ) L( x(0) ,..., x(0) , y ,..., y )
1
n 1
m
1
n 1
m
1
n 1
m
x , y 0.
j i
Теорема Куна–Таккера Для задачи выпуклого программирования,
ОДЗ которой обладает свойством регулярности, план X (0) ( x(0),..., x(0) )
1
n
является оптимальным тогда и только тогда, когда вектор
Y (0) ( y(0),..., y(0) ), ( y (0) 0, i 1,m) такой , что точка ( X (0) ,Y (0) ) является
1
n
i
седловой точкой функции Лагранжа.

5.

Если функции f и g непрерывно дифференцируемы, то
аналитически уравнения для теоремы Куна–Таккера выглядят
следующем образом:
L
0 0
( j 1, n)
x
j
L
0 0
x (0)
( j 1, n)
j
x
j
x
0,
( j 1, n)
j
L0
0
(i 1, m)
y
i
L
0 0
y (0)
(i 1, m)
i
y
i
y 0,
(i 1, m)
i

6.

Пример:
Найти максимальное значение функции:
f 2x 4x x 2 2x 2
1
2 1
2
x 2 x 8
1
2
2 x x 12
2
1
x ,x 0
1 2
L 2x 4x x 2 2x 2 y [8 x 2x ] y [12 2x x ]
1
2 1
2 1
1
2 2
1 2
L
0
x
1
L
0
x
2
L
0
y1
L
0
y
2
2 2 x y 2 y 0
1
1
2
4 4 x 2 y y 0
2
1
2
8 x 2 x 0
1
2
12 2 x x 0
1
2
x (2 2 x y 2 y ) 0
1 1
2
1
x (4 4 x 2 y y ) 0
2
2
1 2
y (8 x 2 x ) 0
1
2
1
y2 (12 2 x1 x2 ) 0
x , x , y , y 0
1 2 1 2

7.

L
0
x
1
L
0
x
2
L
0
y1
L
0
y
2
2 2 x y 2 y v 0
1 1
2 1
4 4 x 2 y y v2 0
2
1
2
8 x 2 x w 0
1
2
1
x v 0
1 1
x v 0
2 2
y w 0
1 1
y w 0
2 2
12 2 x x w 0
1 2
2
Решаем методом искусственного базиса
Mz1 Mz 2 max
z1 , z 2 0
x1( 0 ) 1, x 2( 0 ) 1, w1 5, w2 11
y1 y 2 v1 v 2 z1 z 2 0
x * (1,1), f max 3.