Нелинейное программирование и выпуклое программирование

1.

Нелинейное программирование
Математическая модель
X Rn
Z ( X ) f ( x1 , x2 , xn ) max min
i ( x1 , x2 , xn ) bi
i 1, 2, k
i ( x1 , x2 , xn ) bi
хотя бы одна из функций
f
Условный экстремум
i k 1,...., m
Ограничения в виде равенств
и нелинейная
Функцией Лагранжа
Задачи с локальным, глобальным и условным экстремумом.
L( x1 , x2 , , xn , 1 , 2 , , m )
Необходимые признак
F
0 (i 1, 2, ... , n) M 0 ( x10 , x20 , .... , xn0 )
xi
2F
x1 x2
2F
2
x2
2F
x3 x2
.....
2F
2F
x1 x3
2F
x2 x3
2F
2
x3
.....
2F
m
f ( x1 , x2 , , xn ) i bi i ( x1 , x2 , , xn )
Достаточный признак
2F
2
x1
2F
x2 x1
Н 2F
x3 x1
.....
2F
НП включает разделы:
– выпуклое программирование;
– квадратичное программирование;
– целочисленное программирование;
– стохастическое программирование;
– динамическое программирование
i 1
Необходимый признак
2F
x1 xn
2F
.....
x2 xn
2F
.....
x3 xn
.....
.....
2F
.....
Главные миноры матрицы
Гессе имеют определенный
знак.
L
0, j 1; 2; ; n
xj
L
0, i 1; 2; ; m
i
1

2.

Модели выпуклого программирования
Z ( X ) f ( x1 , x 2 , x n ) max
i ( x1 , x 2 , x n ) bi ; i 1, 2, m ,
x j 0; j 1, 2, n ,
f x1 , x2 , xn i x1 , x2 , xn нелинейные функции n переменных.
Множество M R
n
называется выпуклым, если для любых точек X 1 , X 2 M и любого
0;1
выполняется условие X1 1 X 2 М
Функция F X f x1 , x2 , xn заданная на выпуклом множестве М п-мерного пространства, называется выпуклой
(выпуклой вниз) на этом множестве, если для любых
X 1 , X 2 M и числа 0;1 выполняется неравенство F X1 1 X 2 F X1 1 F X 2
2

3.

Для дифференцируемых функций
Функция F X f x1 , x2 , xn
*
является выпуклой в точке x если матрица ее вторых частных производных
положительно определена.
Критерий Сильвестра
Матрица А является положительно определенной, если все ее угловые миноры больше нуля
Матрица А является отрицательно определенной, если знаки угловых миноров чередуются
1 n mi 0
Условие Слейтера
Говорят, что множество допустимых решений задач нелинейного программирования (ЗНП) удовлетворяет условию
регулярности, если существует, по крайней мере одна точка
Х 0, принадлежащая области допустимых решений
такая, что i ( Х 0 ) bi ; i 1, 2, m