Лекция 6. Нелинейное программирование

Задачи выпуклого программирования.
Свойства выпуклых функций.
4. Графический способ решения.
5. Условия Куна-Такера.

Пример.

переменные должны удовлетворять ограничениям:
g1(x1,x2, …,хn) ≤b1,
…………………………
gm(x1,x2, …,хn) ≤bm,
gk+1(x1,x2, …,хn)=bk+1,
………………………
gp(x1,x2,

…,хn)=bp.
x1,x2,…,хn ≥0, хотя бы одна из функций f, gi нелинейная.

m)= f(x1,x2, …,хn)+
gi(x1,x2, …,хn),

положительно определённая, то

6 ед. продукта х1 и 8 ед. продукта х2. Определите

цены потребляемых благ, если известно, что доход потребителя равен 240 руб. Функция полезности потребителя имеет вид:

u(x1,x2)=
p1x1+p2x2=240, x1≥0, x2≥0

условие экстремума – равенство нулю частных производных:


Отсюда вытекает, что для

всех i в точке х рыночного равновесия выполняется равенство

8 ед., получим: p1=10руб., p2=22,5руб.

(1)
Z=f(x1,x2, …,хn )

(2)
Функции gi(x1,x2, …,хn) являются выпуклыми на выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута.
Задача выпуклого программирования состоит в отыскании такого решения системы (1), при котором (выпуклая) функция (2) достигает минимального значения , или вогнутая функция Z достигает максимального значения.

Функция F(X)=С и линейная функция F(X)=ax+b являются всюду выпуклыми и

всюду вогнутыми.
3) Если функции F i(X) –выпуклы, i=1,..,m, то при любых действительных числах i ≥0 функция  iF i(X) также является выпуклой.
4)Если F(X) –выпукла, то для любого числа  область
решений неравенства F(X)<  является либо выпуклым
множеством, либо пустым.
5)Если  i(X) –выпуклые при всех неотрицательных значениях переменных, то область решений системы неравенств  i(X)≤ bi , i=1,..,m, является выпуклым
множеством(если она не пуста).

М, непрерывна в каждой внутренней точке этого множества.
7) Всякая дифференцируемая

строго выпуклая (вогнутая) функция имеет не более одной стационарной точки (т.е. точки, в которой равны нулю все частные производные). Для выпуклой (вогнутой) функции стационарная точка является точкой локального и глобального минимума (максимума).
8)Дважды дифференцируемая функция F(X)=F(x1,.. Xn ) является выпуклой в том случае, когда

определения выпуклости функции применяют критерий Сильвестра:
Условие (*) выполняется тогда

итолько тогда, когда неотрицательны все главные миноры  к матрицы вторых частных производных (матрицы Гессе).
Если все  к >0, то неравенство (*) выполняется как строгое, и функция F(X) является строго выпуклой.

Z является строго выпуклой (строго вогнутой) и если область решений

системы ограничений не пуста и ограничена, то задача ВП всегда имеет единственное решение.
Минимум выпуклой (максимум вогнутой) функции достигается внутри области решений, если там имеется стационарная точка, или на границе этой области, если внутри неё нет стационарной точки.

+ x22 ≤25, x1 ≥0, x2 ≥0,

Максимум достигается в точке касания А окружности x12 + x22 =25 и линии уровня
x1+2x2 =C

А(√5,2√5)

…,хn)≤bi
имеют вид:

f(x1 x2 …xn) (1)
при ограничениях
gi(x1,x2, …,хn)≤bi , i=1,2,..,m

(2)
hi(x1,x2, …,хn)=0, i=1,2,..,k (3)

виде неравенств содержат вогнутые функции , а ограничения в виде

равенств содержат линейные функции . Тогда если существует решение , удовлетворяющее условиям Куна—Таккера (4) — (6), то X* — оптимальное решение задачи нелинейного программирования.
Проверить матрицу Гессе:
Если положительно определённая в стационарной точке , то – минимум. Если отрицательно определённая в стационарной точке , то – максимум.