26. Выпуклые множества и их свойства.

Опр.1 Множество наз. выпуклым, если выполняется .

Опр. 2 Множество наз. строго выпуклым, если.

Свойства выпуклых множеств:

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

2. Линейная комбинация выпуклых мн-в явл. выпуклым множеством.

3. Теорема о строгой отделимости. Пусть - выпуклые мн-ва, одно из которых ограничено и . Тогда сущ. n –вектор с и число , что выполняется нер-во:

(Т.е. сущ. гиперплоскость, проходящая между мн-вами ).

4. Теорема об отделимости. . Непересекающиеся выпуклые множества отделимы, т.е. –вектор, такой что .

28. Основная задача выпуклого программирования. Необходимое условие существования седловой точки.

(1)

Здесь , - выпуклые функции, - выпуклое множество .

Опр.1 Точка наз. допустимой, если она удовлетворяет ограничениям задачи: .

Тогда множество является выпуклым как пересечение выпуклых множеств и .

Определим мн-во как мн-во решений задачи (1) следующим образом . Оно является выпуклым как пересечение выпуклых множеств и .

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

Если строго выпуклая функция, то точка единственная. Док-м это от противного. Допустим, что сущ. 2 точки минимума: и , т.е.

.

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

Для задачи (1) выпишем классическую функцию Лагранжа .

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

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

Док-во. Из определения седловой точки ф-ции Лагранжа имеем .(4)

1. Покажем сначала, что - допустимая точка, т.е. для нее выполняется нер-во . Допустим, что это не так, т.е. .Тогда вектор определим следующим образом если Тогда из левой части нер-ва (4) получаем . Получили противоречие! Значит, не сущ. такого индекса , что , зн. , т.е. - допустимая точка.

2. Покажем, что выполняется условие дополняющей нежесткости (3). Т.к. и - допустимая точка. Тогда получаем Допустим, что . Тогда из левой части нер-ва (4) или . Это нер-во должно выполняться для любого , в том числе и для Получим противоречие! Зн., справедливо условие дополняющей нежесткости (3).

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

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