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

Общий подход к решению задач нелинейного программирования.

 

К задачам нелинейного программирования относятся такие задачи на условный экстремум, в которых нелинейны либо целевая функция , либо, по крайней мере, одна из функций, образующих область допустимых решений, либо нелинейны и целевая функция и функции-ограничения.

Задача нелинейного программирования (задача НП) в общем виде формулируется следующим образом :

(1.1)
Найти максимум функции

z = f (x1 ,x2 ,…, xn )

при условиях

1(x1 ,x2 ,…, xn ) 1,

(1.2)
2(x1 ,x2 ,…, xn ) 2,

m(x1 ,x2 ,…, xn ) m,

 

 

где хотя бы одна из функций f, 1, 2,.., m нелинейна.

Предположим, что все эти функции дифференцируемы. Тогда для определения условного экстремума могут быть использованы методы дифференциального исчисления. Процесс решения будет состоять

1) в определении внутри допустимого множества всех стационарных точек функции f, удовлетворяющих условию =0; j=1,2,…, n;

2) определении той стационарной точки, которая доставляет наибольшее значение функции f внутри области;

3) нахождении максимума функции f внутри каждой границы области и выборе наибольшего ее значения по всем границам;

4) нахождении наибольшего значении функции f в вершинах области;

5) нахождении глобального максимума функции f.

Как видим, решение задачи НП значительно сложнее решения задачи линейного программирования. Для решения последней требовалось исследовать значение целевой функции лишь в вершинах области, да и то не во всех.

 

 

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

 

Определение I. Множество называется выпуклым, если отрезок, соединяющий любые две точки множества, также принадлежит этому множеству. Ниже приводятся графические примеры выпуклых (a) и невыпуклых (b) множеств. ( рис. 1)

 

p1 p2
p1 p2
y2 a b

 


 

p1

p2

 


 

 

0 рис. 1 x1

(2.1)
Всякая точка Р отрезка, соединяющего точки Р1, Р2, выражается через эти точки следующим образом:

P = (1 - λ)P1 + λ P2, 0 ≤ λ ≤ 1.

Каждой точке отрезка соответствует определенное значение λ. Равенство называется выпуклой комбинацией точек Р1 и Р2. Поэтому можно дать другое определение выпуклого множества: множество называется выпуклым, если оно содержит любую выпуклую комбинацию любых двух точек Р1 и Р2, из этого множества.

Определение II. Функция f называется выпуклой на заданном выпуклом множестве, если выполняется следующее неравенство:

f [(1 – λ)P1 + λ P2] ≥ (1 - λ) f (P1) + λ f (P2).

 

Ниже изображена выпуклая функция Z= f (x1, x2) (рис. 2).

z

 

 


M1 M M2

 

 


0 x2

 

P1 P P2

 

x1

рис. 2

 

(2.2)
Причем M1 = f (P1), M2 = f (P2), M = f (P). Согласно определению выпуклой функции можно записать

M ≥ (1 - λ) M1 + λ M2.

Неравенство означает, что все точки поверхности функции, соответствующие отрезку Р1, Р2, лежат не ниже отрезка М1М2. Если функция выпуклая, то такое свойство будет выполняться обязательно.

 

Определение III. Функция f называется вогнутой на заданном выпуклом множестве, если выполняется следующее неравенство:

f [(1 – λ)P1 + λ P2] ≤ (1 - λ) f (P1) + λ f (P2).

 

На рис. 2 изображена вогнутая функция Z= f (x1, x2). Причем M1 = f (P1), M2 = f (P2),

(2.3)
M = f (P). Согласно определению вогнутой функции можно записать

M ≤ (1 - λ) M1 + λ M2.

 

Неравенство означает, что все точки поверхности функции, соответствующие отрезку Р1Р2, лежат не выше отрезка М1М2. Для вогнутых функций такое условие выполняется всегда.

Выпуклые и вогнутые функции имеют большое значение в нелинейном программировании вследствие следующих очевидных свойств этих функций.

1.Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция.

2.Локальный максимум строго выпуклой функции является ее глобальным максимумом и достигается в единственной точке выпуклого множества, в котором задана функция (рис. 3)

3. Локальный минимум строго вогнутой функции является ее глобальный минимум и достигается в единственной точке выпуклого множества, в котором задана функция (рис. 3)

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

5.Если функции i (x1, x2,…, xn); i=1,2,…,m - выпуклые (вогнутые), то множество, образуемое условиями

i (x1, x2,…, xn) ≤ bi ; xj ≥ 0 ; i=1,2,…,m ; j=1,2,…,n,

будет выпуклым (вогнутым).

y

y = f (x)

y = f (x)

 


0 рис. 3 x

 

 

y

 


y1 = f1 (x)

y2 = f2 (x)

 

 


0 x

рис. 4

Все эти свойства делают практически возможным отыскание решения задачи ВП. Схема решения такова. Вначале целевая функция исследуется на экстремум внутри выпуклой области. Если такой экстремум существует, то он будет глобальным. В случае отсутствия экстремума внутри области исследуется значение целевой функции на границе области. Более эффективным будет применение к решению задачи ВП метода множества Лагранжа. Ниже будет показано, что необходимое условие экстремума функции Лагранжа будет также и достаточным условием.