2.1.2. Ограничения типа неравенств.

Не формальное введение.

Решаем задачу: найти.

Пусть:

область, которая разрешена ограничениями

g₁(x)=0 f g₂(x)=0

точка минимума

f = const (линия уровня)

g₁ g₂

-f

конус

Пусть x* точка минимума, тогда из рисунка видно, что -f представляется так:

-f = ₁g₁+₂g₂, где ₁0, ₂0. (1)

-f расположен в конусе, образованном g₁ и g₂.

1. переписывается так:

f + , где _i - множители Лагранжа.

По рисунку _i g_i (x) = 0 (мы попадаем на границу). Тогда можно рассматривать функцию Лагранжа f + и считать стационарную точку так, будто нет ограничений. Переход от равенств к неравенствам накладывает ограничения на _i (_i 0). Пусть f направлен иначе (-f находится не в конусе), тогда иллюстрация принимает вид:

Иллюстрация:

S g₂(x) = 0

g₁(x) = 0

-f

g₁ конус g₂

В этом случае есть вектор S, который составляет острый угол с -f и тупой с g₁ иg₂.

То есть, для векторов x()=x* + S, (при малых ) наши ограничения будут выполняться (в тоже время функция будет убывать), и точка x* не будет точкой локального минимума.

Таким образом, чтобы точка была экстремальной, антиградиент должен лежать в выпуклом конусе, определенном векторами g₁ иg₂.

Рассмотрим другую точку на g₂(x) = 0.

f¹ g₂(x) = 0

g₂

Если f¹ направлен так, как показано на рисунке, то точка x* будет подозрительной на точку локального минимума. Необходимое условие записывается также, но в этом случае ₁=0 (то есть не рассматривается g₁).

Таким образом, наша цель получить необходимые условия экстремума функции в допустимой точке.

Пусть x*- экстремальная точка, свяжем с x* множество индексов активных ограничений :

Лемма:

Пусть - некоторый вектор, удовлетворяющий следующим свойствам:

(*),тогда точкаx* - не экстремальная. i  I(x*)

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

Идея:

Показать, что на луче с вершиной x* и направлением S будут лежать вблизи вершины некоторые точки, которые будут допустимыми и в них целевая функция строго меньше чем в точке x*

Пусть >0

(1)

(разложение в полином Тейлора)

тогда (см. определение I(x*)).

Тогда (см.(1) и (*)).

Если , то . Отсюда(- достаточно мало).

Таким образом, при достаточно малых , точка x* + S- допустима, кроме этого функция f на этом луче убывает. Таким образом точка x* не является экстремальной. Для экстремальной точки x* система неравенств (*) - несовместна.

Лемма Фаркаша:

Для любой m  n-матрицы А справедливо ровно одно из следующих двух условий :

1. либо

2. либо

Без доказательства.

Теорема Каруша-Джона:

Пусть x* - экстремальная точка задачи нелинейного программирования.

Пусть в точке x* градиенты функций, соответствующие активным ограничениям, линейно- независимы, тогда существуют ₁,...,_m 0 (не все нулевые), для которых выполняются следующее условия:

- условие дополняющей нежесткости.

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

Как показано выше, не существует такого S, для которого выполнялись бы следующие неравенства:

, для любого iI(x*).

Воспользуемся леммой Фаркаша, составим матрицу:

, iI(x*).

Не существует S такого, что AS<0. Следовательно, существуют такие, что (по лемме Фаркаша) выполняются условия:

( *) (_i: = 0, если iI(x*)).

Для активных ограничений g_i = 0, для неактивных _i = 0. Тогда

 _i g_i (x*) = 0, .

так как если бы он был равен 0 ,то градиенты, соответствующих активных ограничений, были бы линейно-зависимы, что противоречит условию. Разделим (*) на  ₀ и получим требуемое утверждение. Условие линейной независимости градиентов функций активных ограничений иногда называют условием регулярности.

Упражнение. Найти минимум функции f(x₁, x₂) при ограничении x₁²+x₂²1.