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

Рассмотрим задачу поиска минимума функции f на допустимом множестве X.

X=xRⁿ,g_i(x)0,i=1...m,fи всеg_ii- выпуклы.

Утверждение:

Допустимое множество в задаче выпуклого программирования (ЗВП) выпукло.

Доказательство:

Пусть x₁,x₂X,0,1

Рассмотрим z=x₁+(1-)x₂X. Так какRⁿ– выпукло, тоzRⁿ. Надо проверитьg_i(z) 0.

Воспользуемся свойством выпуклости g_i :

g_i(x₁+(1-)x₂)  g_i (x₁) + (1-) g_i(x₂)0

тогда x₁+(1-)x₂X(см. определениеX), но рассматривается только отдельнаяg_i.

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

Определение :

Функцией Лагранжа в ЗВП называется функция

f(x)+f(x) + (,g(x)), где _i0.

Справедлива теорема Каруша-Джона:

f(x)+=0, _i g_i(x*) = 0,i=1..m

В случае выпуклости множества X условие линейной независимости векторов g_i(x), соответствующее активным ограничениям, можно заменить более просто проверяемыми, а именно, так называемыми условиями регулярности.

Существуют различные условия регулярности ограничений:

А) если для любого i (1 i m) существует такая точка x_iX : g_i (x_i) 0, то говорят, что множество X удовлетворяет

условию регулярности.

Б) условие регулярности Слейтера:

Существует точка xX такая, что для всех i=1...m g_i(x)0.

Легко доказать эквивалентность условий А и Б . Очевидно, что из Б следует А. Пусть теперь выполняется А. Выберем x =, =1, 0, i=1...mэто возможно, так как X выпукло. Тогда Б следует из неравенства Иенсена.

Замечание:

Условие регулярности означает, что допустимое множество имеет внутреннюю точку (то есть оно не вырождено в точку)

Определение:

Пусть существует функция (x,y), точка (x,y) называется седловой точкой функции, если выполняется следующее неравенство: (x,y)(x,y)(x,y)

Теорема (о седловой точке):

Пусть функция Лагранжа ЗВП имеет седловую точку, то есть

f(x)+ f(x)+ f (x)+

для любого xRⁿ, _i 0, i =1...m

тогда x*- оптимальная точка ЗВП.

Доказательство:

Из левого неравенства следует:

,_i* 0, g_i(x*)0 (см. определение X)

Так как -любое, то при =0 получится:

0(* , g(x*))=0.

Из правого неравенства имеем:

f(x*)+0 f(x)+ f(x) xX

Тогда по определению оптимальной точки x* оптимальна.

Теорема Куна-Таккера:

Пусть в ЗВП выполнено условие регулярности Слейтера. Тогда для того, чтобы x* была оптимальной точкой ЗВП, необходимо и достаточно, чтобы для некоторого вектора* с неотрицательными компонентами точка (x*,*) была седловой точкой функции Лагранжа, то есть

,где

Если на xналожены ограничения (x0), то :

Доказательство:

Достаточность следует из теоремы о седловой точке.

Необходимость - без доказательства.

2.3. Методы условной минимизации.

Рассматривается задача поиска минимума функции f на допустимом множестве X.

X=xRⁿ,g_i(x)0,i=1...m,fи всеg_ii- выпуклы.

2.3.1. Метод проекции градиента.

Этот метод является обобщением градиентного метода. Так как возможен выход за пределы допустимого множества, то вводится операция проектирования на X(поиск ближайшей точки наX).

x^k+1=p_x(x^k-f(x^k)), гдеp_xпроектор наX.

Пример:

Если X- круг, то проекция точки наXесть точка пересечения окружности и прямой, соединяющей центр и проектирующую точку. Чем сложнее областьX, тем сложнее операция проектирования.

Метод обладает теми же свойствами, что и градиентный метод с постоянным шагом.