Задачи на условный экстремум. Необходимые условия оптимальности

Рассмотрим теперь задачу на условный экстремум, состоящую в минимизации функции f ( x ) с учетом ограничения g ( x ) = 0

(4.1)

Здесь g – вектор-функция размерности m, x – вектор размерности n. Предполагается, что n > m.

Частный случай. Получим сначала необходимые условия оптимальности для частного случая, рассматривая задачу с двумя переменными и одним ограничением

(4.2)

Пусть условный экстремум достигается в точке x ^* =( x ₁ ^*, x ₂ ^*). Предположим, что в этой точке существуют частные производные первого порядка для функций f ( x ) и g ( x ). Тогда в e-окрестности ограничение может быть заменено его линейным приближением

.

Предположим, что хотя бы одна из производных (например, ) не равна нулю. Тогда, можно записать

где                .

Теперь целевую функцию f ( x ₁, x ₂ ) можно представить в виде сложной функции f[x ₁ ( x ₂ ), x ₂] одного аргумента x ₂, по которому и необходимо минимизировать, но уже без учёта ограничения. Таким образом, задача на условный экстремум функции двух переменных свелась к задаче на безусловный экстремум функции одного переменного. Необходимые условия оптимальности при этом примут вид

.

Учитывая, что в данном случае имеет место соотношение

,

получим

.

Введём обозначение

.

Тогда условия оптимальности можно представить в виде

,

где одно из условий определяет собственно l ^*. Таким образом, если точка (x ₁ ^*, x ₂ ^*) является точкой условного экстремума, то она должна удовлетворять соотношениям

 

,	(4.3)
g(x 1 *, x 2 *) = 0.

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

F ( x 1, x 2, l ) = f ( x 1, x 2 ) + l g ( x 1, x 2 ),

(4.4)

где l - множитель Лагранжа.

Рассмотрим частные производные функции Лагранжа по x ₁, x ₂ и l,

;
;
.

Поэтому необходимые условия оптимальности (4.3) могут быть представлены в следующем виде

.

или в векторной форме:

.

(4.5)

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

Рассмотрим геометрическую интерпретацию задачи на условный экстремум для функции двух переменных x ₁ и x ₂. На рис. 4.1 представлены линии уровня f ( x )= C, причем C ₁ < C ₂ < C ₃ < C ₄.

Рис.	4.1	Геометрическая интерпретация задачи на условный экстремум

Из рисунка видно, что точки касания кривой g ( x ₁, x ₂ ) линий уровня, а именно точки 1, 2, 3, 4, являются стационарными, то есть удовлетворяют необходимым условиям оптимальности. При этом точка 1 является точкой абсолютного минимума, точка 2не является ни минимумом, ни максимумом- это точка перегиба, в точке 3 функция достигает относительного максимума, а точка 4 является точкой относительного минимума. Для отыскания точки абсолютного условного минимума, необходимо вычислить значения функции во всех стационарных точках и выбрать наименьшее из них.

Общий случай. Рассмотрим теперь задачу в общем случае n переменных и m ограничений, полагая n > m.

(4.6)

Здесь x – вектор размерности n, g – вектор-функция размерности m. Пусть условный экстремум достигается в точке x ^*, а функции f ( x ) и g ( x ) в точке x ^* имеют частные производные первого порядка. В e-окрестности точки x ^* ограничение может быть заменено его первым приближением

.

Здесь  - якобиан функции g ( x ) в точке x ^*, матрица размерности n ´ m. Представим вектор x и матрицу  в блочном виде

Здесь через x ₁ обозначен вектор, составленный из m компонент вектора x, т.е. вектор размерности m, а через x ₂ вектор, составленный из оставшихся n – т компонент вектора x, т.е. вектор размерности n – т;

 - якобиан функции g по x ₁, квадратная матрица размерности m ´ m;

, - якобиан функции g по x ₂, матрица размерности (n - m ) ´ m. ( в формуле – производная по х_{1-исправить})

Перепишем выражение для ограничения в следующем виде

.

Полагая, что  - неособенная матрица, получим выражение для x ₁

.

Подставляя x ₁ в выражение для целевой функции, мы сводим задачу на условный экстремум функции n переменных (по вектору x) к задаче на безусловный экстремум функции f[x ₁ ( x ₂ ), x ₂] n - m переменных (по вектору x ₂).

Воспользуемся необходимым условием оптимальности

.

Матрицу  определим, дифференцируя по х₂ выражение для

.

Учитывая это, необходимое условие оптимальности примет вид

.

Введём в рассмотрение вектор l ^* размерности m

.

Можно считать, что вектор l ^* есть  решение уравнения

.

Само условие оптимальности при этом примет вид

.

Формально последние два соотношения можно объединить в одно

.

Именно оно совместно с условием g ( x *) = 0 и представляет собой необходимое условие оптимальности в задаче на условный экстремум.

Аналогично двумерному случаю, введем в рассмотрение функцию Лагранжа следующего вида

(4.7)

где l - вектор множителей Лагранжа размерности m.

Так как имеют место соотношения

,

то необходимые условия оптимальности могут быть представлены в следующей компактной форме

(4.8)

или в развернутом виде

(4.9)

Упражнение 1. Показать, что необходимые условия оптимальности (4.8) имеют силу и при , но при условии .

Упражнение 2. Вывести необходимое условие оптимальности (4.8) для задачи на условный экстремум в общем случае.( в каком? )

Упражнение 3. Показать, используя условия (4.9), что имеют место равенства

,

где через x_{n+ i} обозначена компонента, численно равная i-му ограничению   x_{n+ i} = g_i( x^*), т.е. каждый множитель Лагранжа  характеризует скорость изменения целевой функции на оптимальном решении при изменении соответствующего ограничения.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: