Теорема (достаточное условие минимума).

Пусть F  C², а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L(x*, *) =  при некотором ненулевом *  R^k. Тогда, если L_xx(x*, *)положительно определен на T_x*, то точка x* является локальным решением задачи (3.1)–(3.2).

Методы решения задач с ограничениями типа равенств.

Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)–(3.2) основывается на необходимом условии экстремума — правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)–(3.2) соответствует экстремум (x*, *) функции Лагранжа L, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле, если в точке x ограничения не выполняются, то за счет выбора  функцию L (поскольку по  она линейна) можно сделать как сколь угодно большой положительной, так и сколь угодно большой отрицательной. Поэтому естественно искать решение x* как первые m координат стационарной точки функции Лагранжа, например, методом Ньютона, мы приходим к методу Ньютона решения задач с ограничениями типа равенств — это просто метод Ньютона решения уравнения L(x, ) =  (в регулярном случае):

L(xⁿ, ⁿ) + L(xⁿ, ⁿ)(xⁿ⁺¹  xⁿ, ⁿ⁺¹  ⁿ) = 

в "координатной" форме

L_x(xⁿ,ⁿ) + L_xx(xⁿ,ⁿ)(xⁿ⁺¹  xⁿ) + L_x(xⁿ,ⁿ)(ⁿ⁺¹  ⁿ) = ,

L_(xⁿ,ⁿ) + L_x(xⁿ,ⁿ)(xⁿ⁺¹  xⁿ) + L_(xⁿ,ⁿ)(ⁿ⁺¹  ⁿ) = .

Остается подставить в эти уравнения явные выражения производных функции Лагранжа (учитывая, в частности, что L_(xⁿ,ⁿ) = ):

f ₀(xⁿ)+ [f (xⁿ)]*ⁿ + (f ₀(xⁿ)+ ⁿ_if _i(xⁿ)) (xⁿ⁺¹  xⁿ) + [f (xⁿ)]*(ⁿ⁺¹  ⁿ) = ,f(xⁿ) + f (xⁿ)(xⁿ⁺¹  xⁿ) = 

и мы получаем m+k линейных уравнений для нахождения m+k неизвестных (xⁿ⁺¹, ⁿ⁺¹).

Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи (3.1)–(3.2). Поскольку, как сказано выше, точка (x*, *) - это седловая точка функции Лагранжа, то естественно пытаться с помощью градиентного метода минимизировать ее по x, одновременно максимизируя ее по :

xⁿ⁺¹ = xⁿ  L_x(xⁿ,ⁿ), ⁿ⁺¹ = ⁿ + L_(xⁿ,ⁿ),

или, что то же xⁿ⁺¹ = xⁿ  (f ₀(xⁿ)+ [f (xⁿ)]*ⁿ), ⁿ⁺¹ = ⁿ + f(xⁿ).

Можно доказать, что этот метод (его обычно называют методом Эрроу — Гурвица) при естественных ограничениях на гладкость и при условии положительной определенности оператора L_xx(x*,*) локально линейно сходится.

Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные () переменные.

Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xⁿ⁺¹ ищется как минимум функции x  (f ₀(xⁿ),x  xⁿ) + ||x  xⁿ||² на касательной гиперплоскости _xn. Здесь "штрафной член" ||x  xⁿ||² позволяет "минимизировать" линейную функцию x  (f ₀(xⁿ),x  xⁿ). Таким образом, мы приходим к прямому методу

xⁿ⁺¹ = argmin [(f ₀(xⁿ),x  xⁿ) + ||x  xⁿ||²], (3.4)

f_i(xⁿ) + (f _i(xⁿ),x  xⁿ) = 0, i = 1, ..., k. (3.5)

Ограничения (3.5) в этом методе — это, очевидно, линеаризации ограничений (3.2) в точке xⁿ: минимум ищется на касательной гиперплоскости _xn.

Один из распространенных методов решения задач с ограничениями, с которым мы еще столкнемся — так называемый метод штрафов. Он позволяет сводить задачу с ограничениями к задаче без ограничений и суть его заключается в наказании за невыполнение ограничений. Именно, вместо минимизации функции f₀ с ограничениями (3.2) минимизируется функция f^s(x) = f₀(x) + s||f(x)||² без ограничений, в которой s — положительный параметр.

Теперь рассмотрим постановку задач с ограничениями типа неравенств g_j(x)  , j = 1, ..., l (6).

Рис. 3.2

Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из R^m в R^k и R^l, соответственно, определяемые координатами f_i и g_j. Поэтому задачу (3.1)- (3.3), (3.6) можно записывать в виде

f(x) = , g(x)  .

(напомним, что неравенство g(x)   означает покоординатные неравенства).

f₀(x)  min, f(x) = , g(x)  .

Через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j  {1, ..., l}: g_j(x) = 0} — это номера ограничений, которые в данной точке существенны.