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

А теперь вектору

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

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

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

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

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

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

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

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

f(x) ® min, x Î W,

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

f_i(x) = 0, гдеf_i: R^m®R (i = 1, …, k).

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

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

f₀(x) ® min, (3.1)

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

Если обозначить теперь через f функцию на R^m со значениями в R^k, координатная запись которой имеет вид f(x) = (f₁(x), …, f_k(x)), то (3.1)–(3.2) можно также записать в виде

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

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

Рис. 3.1.

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

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

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

Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим F: R^m® R^k+1, положив F(x) = (f₀(x), f₁(x), ..., f_k(x)). Заданная на R^m×R^k+1 скалярная функция Лагранжа M по определению принимает значения в R и задается равенством

M(x, m) = (m, F(x)) =

m_if_i(x) (xÎR^m, m ÎR^k+1).

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

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

M¢_x(x, m*)|_x=x*=

m*_if¢_i(x*)= Q.

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

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

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

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

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

L(x, l) = f₀(x) + (l, f(x)) = f₀(x) +

l_if_i(x) (x Î R^m, l Î R^k).

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

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

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

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

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

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

W¢_y = {xÎR^m: f_i(y) + (f¢(y), xy) = 0, i = 1, ..., k}.

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

Пусть F Î C², а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L¢(x*, *) =  при некотором ненулевом *  R^k. Тогда, если L_xx¢¢(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¢(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*) локально линейно сходится.