Курсовая работа: Анализ методов определения минимального, максимального значения функции при наличии ограничений

А теперь вектору  вектор  ортогонален т. е. сопряженность это не ортогональность векторов  и , а ортогональность повернутого вектора  т.е.  и .

Рис. 2.3. Блок-схема метода сопряженных направлений.

Реализация метода в программе: Метод сопряженных направлений.

Рис. 2.4. Реализация метода сопряженных направлений.

Рис. 2.5. График метода сопряженных направлений.

Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.

3. Анализ методов определения минимального, максимального значения функции при наличии ограничений

Напомним, что общая задача условной оптимизации выглядит так

f(x) ® min, x Î W,

где W — собственное подмножество Rm. Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида

fi(x) = 0, где fi: Rm ®R (i = 1, …, k).

Таким образом,W = {x Î Rm: fi(x) = 0, i = 1, …, k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде

f0(x) ® min, (3.1)

fi(x) = 0, i = 1, …, k. (3.2)

Если обозначить теперь через f функцию на Rm со значениями в Rk, координатная запись которой имеет вид f(x) = (f1(x), …, fk(x)), то (3.1)–(3.2) можно также записать в виде

f0(x) ® min, f(x) = Q.

Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f0 над многообразием  (см. рис. 3.1).

Рис. 3.1.

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f0 при ограничениях fi(x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точках x f0(x*)  f0(x). (3.3)

Если (3.3) выполняется только для допустимых x, лежащих в некоторой окрестности Vx* точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.

Правило множителей Лагранжа

Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим F: Rm ® Rk+1, положив F(x) = (f0(x), f1(x), ..., fk(x)). Заданная на Rm×Rk+1 скалярная функция Лагранжа M по определению принимает значения в R и задается равенством

M(x, m) = (m, F(x)) =  mi fi(x) (x Î Rm, m Î Rk+1).

Координаты вектора m, т. е. числа m0, m1, ..., mk называются множителями Лагранжа или двойственными переменными. Оказывается, имеет место следующая теорема, часто именуемая правилом множителей Лагранжа:

Теорема. Пусть F Î C1 и x* — локальный условный минимум функции f0 при ограничениях fi(x) = 0 (i = 1, ..., k). Тогда найдется ненулевой вектор m* такой, что x* является стационарной точкой функции x M(x, *):

M¢x(x, m*)|x=x*=m*i f ¢i(x*)= Q.

Правило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки (x*, m*) Î Rm+k+1, т. е. для нахождения m + k + 1 неизвестных, мы имеем m + k уравнений

f(x) = Q, M¢x(x, l)= Q.

Поскольку, очевидно, множители Лагранжа можно искать с точностью до постоянного множителя, то в общей ситуации этих уравнений хватает для отыскания x*.

Регулярные точки

Допустимая точка x задачи (3.1)–(3.2) называется регулярной, если векторы {f i(x)}ki=1линейно независимы. Оказывается, что если x* — регулярная точка минимума, то в векторе * можно считать *0 ненулевым, а поскольку множители Лагранжа определяются с точностью до множителя, можно считать, что *0 = 1. Чтобы сформулировать это утверждение более точно, введем следующие обозначения. Пусть   Rk, а функция Лагранжа в регулярном случае определяется равенством

L(x, l) = f0(x) + (l, f(x)) = f0(x) + li fi(x) (x Î Rm, l Î Rk).

Очевидно, L(x, l) = M(x, m), где m = (1, l).

Теорема (правило множителей Лагранжа в регулярном случае)

Пусть F  C1, а x* — регулярное локальное решение задачи (3.1)–(3.2). Тогда найдется ненулевой вектор *  Rk такой, что

L¢x(x*, l*)= Q.

Одно достаточное условие локального минимума

Говорят, что линейный оператор A положительно определен на подпространстве E, если (Ax, x) > 0 при всех x  E. Касательным подпространством к многообразию  в точке y называется множество Ty = {x  Rm: (f (y), x) = 0, i = 1, ..., k}. Касательной гиперплоскостью к многообразию  в точке y называется множество

W¢y = {x Î Rm: fi(y) + (f ¢(y), xy) = 0, i = 1, ..., k}.

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

Пусть F Î C2, а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L¢(x*, *) =  при некотором ненулевом *  Rk. Тогда, если Lxx¢¢(x*, l*)положительно определен на 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¢(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)+ lnif ¢¢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) переменные.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8