Постановка задачи выпуклого программирования

Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки.

Функция F (X) = F (), определённая на выпуклом множестве М n -мерного пространства, называется выпуклой на этом множестве, если

(5.21)

для любых точек и любого числа .

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

Свойства выпуклых функций

1) Если F (Х) – выпуклая функция, то - F (Х) вогнутая.

2) Постоянная функция F (Х) = С и линейная функция F (Х) = ax + b являются всюду выпуклыми и всюду вогнутыми.

3) Если F_i (Х) – выпуклые функции (), то функция также выпуклая.

4) Если F (Х) – выпуклая функция, то область решений неравенства F (Х) < является либо выпуклым множеством, либо пустым.

5) Если функции () выпуклые (), то область решений системы неравенств является выпуклым множеством, либо пустым.

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

7) Всякая дифференцируемая строго выпуклая (вогнутая) функция имеет не более одной стационарной точки. При этом для выпуклой (вогнутой) функции стационарная точка –это всегда точка локального и глобального минимума (максимума).

8) Дважды дифференцируемая функция F (Х) = F () является выпуклой тогда и только тогда, когда

(5.22)

, .

Критерий Сильвестра: Условие (5.22) выполняется тогда и только тогда, когда неотрицательны все главные миноры матрицы вторых частных производных, т.е. определители

, , .

Если все , то неравенство (5.22) выполняется как строгое и, соответственно, функция F (Х) является строго выпуклой.

Если в задаче математического программирования (5.1) – (5.2) целевая функция F (Х) и все функции () системы ограничений являются выпуклыми или вогнутыми, то задача называется задачей выпуклого программирования (ЗВП).

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

F (Х) = F () → min (max)

и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений

, ,

где () - выпуклые на некотором множестве М функции.

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

· всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является и глобальным;

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

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

В общем случае множество оптимальных решений ЗВП – выпуклое множество.

Пример. Решить графически задачу:

F () = → min,

Решение. 1) Покажем, что данная задача является ЗВП. Частные производные функции F (): , , , , . Матрица вторых частных производных имеет вид А = . Её главные миноры: . Условия критерия Сильвестра выполняются, следовательно, функция F () является выпуклой, а поставленная задача является ЗВП.

2) Решим ЗВП графическим методом. ОДР данной задачи – многоугольник ОABC (рис. 45).

Построим линию уровня F () = С и определим направление убывания функции F (). Уравнения линий уровня имеют вид:

= С.

При С = 1 линия уровня = 1 определяет окружность с центром в точке (1, 2) и радиусом R = 1. Значение функции F возрастает при перемещении от центра окружности, убывает - при перемещении к центру окружности. Следовательно, минимум функции F достигается в точке (1, 2), которая является стационарной точкой. F_min (1, 2) = 0.

C (3, )

Рис.2. Графическое решение ЗВП

Заметим, что максимум функции F достигается в точках О и В:

F_max (0, 0) = (3, 3) = 5.

Поиск по сайту: