1. Элементы выпуклого анализа.

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

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

Примеры выпуклых мн-ств: все пр-тво, гиперплоскость, -мерный куб, шар.

Невыпуклые множества: кривая поверхность, кривая линия, тор.

Свойства:

1) Пересечение любого числа выпуклых множеств, даже бесконечного, является снова выпуклым множеством. Для объединения это несправедливо.

2) Для любого невыпуклого подмножества можно ввести понятие его выпуклой оболочки как пересечение всевозможных выпуклых множеств, его содержащих.

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

Теорема. Пусть даны два подмножества и . Тогда, если они:

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

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

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

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

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

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

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

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

(2)

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

(3)

5) Если функция , и (4) , то строго выпукла.

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

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

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

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

2. Осн. З. Выпуклого программирования. Седловая точка и оптимал. План.

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

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

Опр. Пара , где (3)

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

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

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

Замеч.2. Условие эквивалентно условию

(5^*)

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