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

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

L¢(xⁿ, lⁿ) + L¢¢(xⁿ, lⁿ)(xⁿ⁺¹  xⁿ, lⁿ⁺¹ - lⁿ) = Q

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

L¢_x(xⁿ,lⁿ) + L¢¢_xx(xⁿ,lⁿ)(xⁿ⁺¹ - xⁿ) + L¢¢_xl(xⁿ,lⁿ)(lⁿ⁺¹ - lⁿ) = Q,

L¢_l(xⁿ,lⁿ) + L¢¢_xl(xⁿ,lⁿ)(xⁿ⁺¹ - xⁿ) + L¢¢_ll(xⁿ,lⁿ)(lⁿ⁺¹ - lⁿ) = Q.

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

f ¢₀(xⁿ)+ [f ¢(xⁿ)]*lⁿ + (f ¢¢₀(xⁿ)+ lⁿ_if ¢¢_i(xⁿ)) (xⁿ⁺¹  xⁿ) + [f ¢(xⁿ)]*(lⁿ⁺¹  lⁿ) = Q,

f(xⁿ) + f ¢(xⁿ)(xⁿ⁺¹  xⁿ) = Q

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

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

xⁿ⁺¹ = xⁿ  aL¢_x(xⁿ,lⁿ), lⁿ⁺¹ = lⁿ + aL¢_l(xⁿ,lⁿ),

или, что то же xⁿ⁺¹ = xⁿ  a(f ¢₀(xⁿ)+ [f ¢(xⁿ)]*lⁿ), lⁿ⁺¹ = lⁿ + af(xⁿ).

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

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

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

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

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

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

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

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

Рис. 3.2.

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

f(x) = Q, g(x) £ Q.

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

f₀(x) ® min, f(x) = Q, g(x) £ Q.

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

Теорема (обобщенное правило множителей Лагранжа)

Пусть f₀, f, g Î C¹, а x* — локальное решение задачи f₀(x) ® min, f(x) = Q, g(x) £ Q. Тогда найдутся такие l*₀ Î R, l* Î R^k, m* Î R^l, не равные одновременно нулю, такие, что m*_j ³ 0 при j Î J(x*) и

l*₀ f ¢₀(x*)+ l*_i f ¢_i(x*)+ m*_j g¢_j(x*) = Q. (3.7)

Регулярный случай

Так же, как и в случае ограничений-равенств, в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если l*₀¹ 0. В этой ситуации можно разделить (3.7) на l*₀ и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: R^m×R^k×R^k ® R (в регулярном случае) равенством

(x, l, m) = f₀(x) + (l, f(x)) + (m, g(x)).

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ¢₁(x),..., f ¢_k(x) линейно независимы и для некоторого ненулевого вектора

hÎR^m (f ¢_i(x),h) = 0 при i = 1, ..., k и (g¢_j(x),h) < 0 при j Î J(x).

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ¢_i(x)), и, во-вторых, он образует с градиентами g¢_j(x) активных ограничений (указывающими, очевидно, вовне множества W) тупой угол.

Рис. 3.3.