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

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

(1)

– Неравенство Йенсена.

Геометрически неравенство Йенсена означает, что если взять любые две точки графика функции и соединить их хордой, то между этими точками график функций должен лежать ниже хорды.

Определение. Функция строго выпукла, если она выпукла и ее график не содержит прямолинейных отрезков.

– выпукла

– выпукла, но не строго

– строго выпукла

Определение. Функция называется вогнутой, если функция выпукла.

Критерии выпуклости:

1) выпукла в том и только в том случае, если ее график, т.е. является выпуклым подмножеством в .

2) Скалярный критерий выпуклости. Для того чтобы функция была выпукла, необходимо и достаточно, чтобы скалярная функция одной переменной была выпуклой.

3) Гладкий критерий выпуклости. выпукла в том и только в том случае, когда выполняется неравенство:

(2)

4) Функция в классе выпукла в том и только в том случае, когда

(3)

5) Если функция , и (4) , то строго выпукла. Поскольку , это –симметрическая матрица, то для проверки (3), (4) используются критерии Сильвестра неотрицательности и положительности квадратной матрицы.

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

1) Выпуклая функция непрерывна в каждой своей внутренней точке и имеет в ней производные по любому направлению.

2) Если функция выпукла, то ее множество уровня для любого конечного числа является либо множеством выпуклым, либо пустым.

3) Если функции выпуклы на , то и функция , то и функция является выпуклой.

 

 

Основная задача выпуклого программирования. Седловая точка и оптимальный план.

Рассмотрим задачу оптимизации (1),

в которой – вектор-функция, функции – выпуклые функции; – выпуклое множество простой структуры, то есть подмножество, которое задается с помощью простейших ограничений на одну переменную (). Задача называется основной задачей выпуклого программирования.

Любая задача выпуклого программирования может быть записана в форме (1). Для этого ограничения задачи разбиваются на сложные (содержащие несколько переменных) и простые. Сложные ограничения формируют основные ( – количество таких ограничений), а простые ограничения задают множество . В частности, если у задачи простых ограничений нет, то полагают . Докажем, что множество планов задачи (1) выпукло.

можно представить как – выпуклое как пересечение выпуклого множества. По параметрам задачи (1) построим функцию:

, (2)

. Функция называется функцией Лагранжа для задачи (1).

Определение. Пара , где

(3)

называется седловой точкой функции Лагранжа.

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

Доказательство. Пусть построена седловая точка. Тогда для нее выполняется неравенство (3), то есть

(3^*)

Рассмотрим левое неравенство (3^*), отбросив одинаковые константы :

(4)

1) Докажем, что является планом задачи (1). Поскольку известно, что , то нужно доказать, что . Предположим противное: . Положим в (4) . Тогда из (4): . . Противоречие доказывает 1).

2) Докажем, что выполняются условия дополняющей не жесткости:

. (5)

От противного . Положим в (4) . Тогда . Это невозможно, поскольку половина отрицательного числа всегда число большее, чем оно само.

3) Докажем, что – оптимальный план. Используем правую часть (3^*):

. – оптимальный план для основной задачи выпуклого программирования.

Ч.т.д.

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