Оптимальная система автоматического управления (стр. 3 из 7)
(2.6)При единичной матрице Гессе сопряженность направлений означает их ограниченность:
Рис. 2.1
Дана функция:
с начальной точкой
. 
- точка безусловного экстремума.1) Найдем градиент функции в точке
: 
Выберем
,где
, имеем 
.1) Из начальной точки
мы должны шагнуть по направлению 
. Для этого найдем оптимальный шаг по формуле: 
Находим координаты
с помощью величины шага: 
Получили новую точку с координатами
2) Примем точку
за начальную. Определяем: 
Найдем координаты сопряженного вектора
: 
, тогда имеем: 
; 
, пусть 
, тогда 
Найдем оптимальный шаг:
Находим координаты
с помощью величины шага: 
Получили новую точку с координатами
- точка минимума.Значение функции в этой точке равно
.3. Анализ методов определения минимального, максимальногозначения функции при наличии ограничений
Напомним, что общая задача условной оптимизации выглядит так
f(x) min, x ,
где — собственное подмножество Rm. Подкласс задач с ограничениями типа равенств выделяется тем, что множество задается ограничениями вида
fi(x) = 0,
гдеfi: RmR (i = 1, ..., k).
Таким образом, = {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) = .
Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f0 над многообразием (см. рис. 3.1).
Рис. 3.1
Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f0 при ограничениях fi(x) = 0, i = 1, ..., k (или решением задачи (1)–(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, ) = (, F(x)) =
i fi(x) (x Rm, Rk+1).Координаты вектора , т. е. числа 0, 1, ..., k называются множителями Лагранжа или двойственными переменными. Оказывается, имеет место следующая теорема, часто именуемая правилом множителей Лагранжа:
Теорема. Пусть F C1 и x* — локальный условный минимум функции f0 при ограничениях fi(x) = 0 (i = 1, ..., k). Тогда найдется ненулевой вектор * такой, что x* является стационарной точкой функции x M(x, *):
Mx(x, *)|x=x*=
*if i(x*)= QПравило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки (x*, *) Rm+k+1, т. е. для нахождения m + k + 1 неизвестных, мы имеем m + k уравнений
f(x) = , Mx(x, )= .
Поскольку, очевидно, множители Лагранжа можно искать с точностью до постоянного множителя, то в общей ситуации этих уравнений хватает для отыскания x*.
Регулярные точки.
Допустимая точка x задачи (3.1)–(3.2) называется регулярной, если векторы {f i(x)}ki=1линейно независимы. Оказывается, что если x* — регулярная точка минимума, то в векторе * можно считать *0 ненулевым, а поскольку множители Лагранжа определяются с точностью до множителя, можно считать, что *0 = 1. Чтобы сформулировать это утверждение более точно, введем следующие обозначения. Пусть Rk, а функция Лагранжа в регулярном случае определяется равенством
L(x, ) = f0(x) + (, f(x)) = f0(x) +
i fi(x) (x Rm, Rk).Очевидно, L(x, ) = M(x, ), где = (1, ).
Теорема (правило множителей Лагранжа в регулярном случае).
Пусть F C1, а x* — регулярное локальное решение задачи (3.1)–(3.2). Тогда найдется ненулевой вектор * Rk такой, что
Lx(x*, *)= .
Одно достаточное условие локального минимума.
Говорят, что линейный оператор A положительно определен на подпространстве E, если (Ax, x) > 0 при всех x E. Касательным подпространством к многообразию в точке y называется множество Ty = {x Rm: (f (y), x) = 0, i = 1, ..., k}. Касательной гиперплоскостью к многообразию в точке y называется множество
y = {x Rm: fi(y) + (f (y), xy) = 0, i = 1, ..., k}.
Теорема (достаточное условие минимума).
Пусть F C2, а x* — регулярнаястационарная точкафункции Лагранжа, т. е., в частности, L(x*, *) = при некотором ненулевом * Rk. Тогда, если Lxx(x*, *)положительно определен на Tx*, то точка x* является локальным решением задачи(3.1)–(3.2).
Методы решения задач с ограничениями типа равенств.
Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)–(3.2) основывается на необходимом условии экстремума — правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)–(3.2) соответствует экстремум (x*, *) функции ЛагранжаL, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле, если в точке x ограничения не выполняются, то за счет выбора функцию L (поскольку по она линейна) можно сделать как сколь угодно большой положительной, так и сколь угодно большой отрицательной. Поэтому естественно искать решение x* как первые m координат стационарной точкифункции Лагранжа, например, методом Ньютона, мы приходим к методу Ньютона решения задач с ограничениями типа равенств — это просто метод Ньютона решения уравнения L(x, ) = (в регулярном случае):