Курсовая работа: Анализ методов определения минимального, максимального значения функции при наличии ограничений
Пусть F C1 , а x* — регулярное локальное решение задачи (3.1)–(3.2). Тогда найдется ненулевой вектор * Rk такой, что
L¢x (x*, l*)= Q.
Одно достаточное условие локального минимума
Говорят, что линейный оператор A положительно определен на подпространстве E, если (Ax, x) > 0 при всех x E. Касательным подпространством к многообразию в точке y называется множество Ty = {x Rm : (f (y), x) = 0, i = 1, ..., k}. Касательной гиперплоскостью к многообразию в точке y называется множество
W¢y = {xÎRm : fi (y) + (f¢(y), xy) = 0, i = 1, ..., k}.
Теорема (достаточное условие минимума)
Пусть F Î C2 , а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L¢(x*, *) = при некотором ненулевом * Rk . Тогда, если Lxx ¢¢(x*, l*)положительно определен на Tx* , то точка x* является локальным решением задачи (3.1)–(3.2).
Методы решения задач с ограничениями типа равенств
Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)–(3.2) основывается на необходимом условии экстремума — правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)–(3.2) соответствует экстремум (x*, *) функции Лагранжа L, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле, если в точке x ограничения не выполняются, то за счет выбора функцию L (поскольку по она линейна) можно сделать как сколь угодно большой положительной, так и сколь угодно большой отрицательной. Поэтому естественно искать решение x* как первые m координат стационарной точки функции Лагранжа, например, методом Ньютона, мы приходим к методу Ньютона решения задач с ограничениями типа равенств — это просто метод Ньютона решения уравнения L(x, ) = (в регулярном случае):
L¢(xn , ln ) + L¢¢(xn , ln )(xn +1 xn , ln +1 - ln ) = Q
в "координатной" форме
L¢x (xn ,ln ) + L¢¢xx (xn ,ln )(xn +1 - xn ) + L¢¢xl (xn ,ln )(ln+1 - ln ) = Q,
L¢l (xn ,ln ) + L¢¢xl (xn ,ln )(xn +1 - xn ) + L¢¢ll (xn ,ln )(ln+1 - ln ) = Q.
Остается подставить в эти уравнения явные выражения производных функции Лагранжа (учитывая, в частности, что L¢¢ll (xn ,ln ) = Q):
f¢0 (xn )+ [f ¢(xn )]*ln + (f ¢¢0 (xn )+ 
ln i f¢¢i (xn )) (xn +1 xn ) +[f ¢(xn )]*(ln +1 ln ) = Q,
f(xn ) + f ¢(xn )(xn +1 xn ) = Q
и мы получаем m+k линейных уравнений для нахождения m+k неизвестных (xn +1 , ln +1 ).
Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи (3.1)–(3.2). Поскольку, как сказано выше, точка (x*, *) - это седловая точка функции Лагранжа, то естественно пытаться с помощью градиентного метода минимизировать ее по x, одновременно максимизируя ее по :
xn +1 = xn aL¢x (xn ,ln ), ln +1 = ln + aL¢l (xn ,ln ),
или, что то же xn +1 = xn a(f ¢0 (xn )+ [f ¢(xn )]*ln ), ln +1 = ln + af(xn ).
Можно доказать, что этот метод (его обычно называют методом Эрроу — Гурвица ) при естественных ограничениях на гладкость и при условии положительной определенности оператора L¢¢xx (x*,l*) локально линейно сходится.
Описанные методы относятся к разряду двойственных методов , поскольку в итерационном процессе участвуют как прямые (x), так и двойственные (l) переменные.
Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xn +1 ищется как минимум функции x ® (f ¢0 (xn ),x xn ) + a||x xn ||2 на касательной гиперплоскости W¢xn . Здесь "штрафной член" ||x xn ||2 позволяет "минимизировать" линейную функцию x ® (f ¢0 (xn ),x xn ). Таким образом, мы приходим к прямому методу
xn +1 = argmin[(f¢0 (xn ),x xn ) + a||x xn ||2 ], (3.4)
fi (xn ) + (f ¢i (xn ),x xn ) = 0, i = 1, ..., k. (3.5)
Ограничения (3.5) в этом методе — это, очевидно, линеаризации ограничений (3.2) в точке xn : минимум ищется на касательной гиперплоскости W¢xn .
Один из распространенных методов решения задач с ограничениями, с которым мы еще столкнемся — так называемый метод штрафов . Он позволяет сводить задачу с ограничениями к задаче без ограничений и суть его заключается в наказании за невыполнение ограничений. Именно, вместо минимизации функции f0 с ограничениями (3.2) минимизируется функция fs (x) = f0 (x) + s||f(x)||2 без ограничений, в которой s — положительный параметр.
Теперь рассмотрим постановку задач с ограничениями типа неравенств gj (x) £ 0, j = 1, ..., l (3.6).
Рис. 3.2.