5. УСЛОВНАЯ ОПТИМИЗАЦИЯ

Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой ищется оптимум. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Однако, напротив, процесс оптимизации становится более сложным, поскольку при наличии ограничений даже нельзя использовать применяемые нами выше условия оптимальности. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом.

Например, безусловный минимум функции f (x)= (x − 2)2 имеет место в стаци-

онарной точке x = 2. Но если задача минимизации решается с учетом ограничения x ≥ 4, то будет найден условный минимум, которому соответствует точка x = 4. Эта точка не является стационарной точкой функции f(х), так как

f ′(4)= 4 . Поэтому нужно изучить необходимые и достаточные условия опти-

мума в задачах с ограничениями, которые иначе называют задачами условной оптимизации.

5.1. Задачи с ограничениями в виде равенств

Рассмотрим задачу: f (x)→ min, x Rn

при ограничениях

hk (x)= 0, k =1,2,..., K .

Одним из методов ее решения является метод множителей Лагранжа.

5.1.1.Множители Лагранжа

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

Рассмотрим задачу с одним ограничением-равенством:

f (x)→ min, x Rn ,	(5.1)
h1 (x)= 0 .	(5.2)

Всоответствии с методом множителей Лагранжа эта задача преобразуется

вследующую задачу безусловной минимизации:

33

L(x;λ)= f (x)−λh (x)→ min, x Rn .	(5.3)
1
Функция L(x;λ) называется функцией Лагранжа. Здесь λ – множитель
Лагранжа.
Пусть при заданном значении λ = λ0	безусловный минимум функции

L(x;λ) по переменной х достигается в точке x = x0 и x0 удовлетворяет уравнению

h1 (x0 )= 0 .

Тогда, как не трудно видеть, x0 минимизирует (5.1) с учетом (5.2), поскольку для всех значений х, удовлетворяющих (5.2), h1 (x)= 0 и

min L(x;λ)= min f (x).

Разумеется, нужно подобрать значение λ = λ0 таким образом, чтобы коор-

дината точки безусловного минимума x0 удовлетворяла равенству (5.2). Это можно сделать, если, рассматривая λ как переменную, найти безусловный минимум функции Лагранжа (5.3) в виде функции λ, а затем выбрать значение λ, при котором выполняется равенство (5.2).

Пример. Решить задачу

f (x)= x12 + x22 → min

при ограничении

h1 (x)= 2x1 + x2 − 2 = 0.

Построим функцию Лагранжа:

L(x;λ)= x12 + x22 −λ(2x1 + x2 − 2)

и определим ее безусловный минимум. Найдем стационарную точку функции Лагранжа, приравняв нулю компоненты ее градиента:

∂L		= 2x − 2λ = 0 x0			= λ,
1				1
∂x1
∂L		= 2x	−λ = 0	x0	= λ .
2				2	2
∂x2

Для того чтобы проверить, соответствует ли стационарная точка x0 минимуму, вычислим матрицу Гессе функции Лагранжа, рассматриваемой как функция от x :

HL (x;λ)= 2	0	.
0	2

Эта матрица положительно определена, так как для любого ненулевого вектора uT = (a,b)

34

2

0

a

a

= 2a2 + 2b2 > 0.

uT HLu = (a,b)

0

2

= (2a,2b)

b

b

Это означает, что L(x;λ)

в точке x0

= λ

и x0

= λ

имеет точку минимума.

1

2

2

Оптимальное значение

λ

находится путем подстановки значений x0

и

x0

в

1

2

уравнение 2x1 + x2 = 2, откуда

2λ + λ2 = 2 и λ0 = 54 .

Таким образом, условный минимум достигается при

x10 = 54 , x20 = 52 ,

а минимальное значение f (x0;λ0 ) есть 54 .

Очень часто оказывается, что решение системы

∂L = 0, j =1,2,...,n

∂x j

в виде явной функции переменной λ получить нельзя. Тогда значения x и λ находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:

∂L = 0, j =1,2,...,n,

∂x j

h1 (x)= 0.

Решить такую систему можно каким-либо численным методом.

Для каждого из решений (x0;λ0 ) вычисляется матрица Гессе функции Ла-

гранжа, рассматриваемой как функция от x . Если она положительно определена, то решение – точка минимума.

Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств:

f (x)→ min, x Rn ,

hk (x)= 0, k =1,2,..., K .

Функция Лагранжа принимает вид

K

L(x;λ)= f (x)−∑λk hk .

k=1

35