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

Пусть:

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

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

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

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

Ñg₁ Ñg₂

-Ñf

конус

Тогда -Ñf представляется так:

-Ñf = l₁Ñg₁+l₂Ñg₂, где l₁³0, l₂³0.(1)

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

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

Ñf + , где l_i - множители Лагранжа.

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

(l_i ³0). Пусть Ñf направлен иначе (-Ñf находится не в конусе), тогда иллюстрация.

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

S g₂(x) = 0

g₁(x) = 0

-Ñf

Ñg₁ конус Ñg₂

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

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

Таким образом, чтобы точка была экстремальной, антиградиент должен лежать в соответствующем конусе.

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

Ñf¹ g₂(x) = 0

Ñg₂

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

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

Лемма:

Ïóñòü - некоторый вектор, удовлетворяющий следующим свойствам:

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

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

Идея:

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

Пусть e>0

(1)

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

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

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

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

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

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

Пусть есть матрица А(m ´ n), тогда справедливо одно из следующих двух условий:

1)

2)