ТЕОРИЯ ОПТИМИЗАЦИИ И Алгоритмов / Методы_оптимизации

11

f ′′(x(1)

= 1) =

2(1− 3)

= − 4

= −0,5 < 0.

(1+1)3

8

Следовательно, x=1 является точкой локального максиму-

ма ( I = {2

}).

Вычисляем значение

f ′′(x)

в точке x(2) :

f ′′(x(2)

= −1) = − 2(1− 3) =

4 =

0,5 >

0.

(1+1)3

8

Следовательно, x = −1 является точкой локального мини-

мума (I= ).

Вычисляем предельные значения f(x):

lim f (x) = lim

x

= lim

x

= lim

1

=

1

= 0,

+ x2

∞ 1

x→∞

x→∞ 1

x→∞ x2 (1+1 x2 )

x→∞ x(1+1 x2 )

lim

f (x) =

lim

x

= lim

1

=

1

= 0.

(−∞)1

x→−∞

x→−∞ 1+ x2

x→−∞ x(1+1 x2 )

Поскольку

V ≡ max{lim

f (x),

lim

f (x)} = 0 ≠ +∞ ,

x→∞

x→−∞

то f(x) имеет конечный глобальный максимум.

Поскольку

W ≡ min{lim f (x),

lim

f (x)} = 0 ≠ −∞ ,

x→∞

x→−∞

то f(x) имеет конечный глобальный минимум.

Вычисляем значения f(x) в точках локальных экстрему-

	мов:					1
	f (x = 1)	=					= 0,5;
				1		+12
	f (x = −1) =					−1		= −0,5.
			1+ (−1)2

Определяем точку глобального минимума f(x):

min f (x) = min{f (x = −1),W}= min{− 0,5; 0}= −0,5 = f (x = −1).

x R1

Таким образом, точка x = −1 является точкой глобального минимума f(x).

x R1

12

Определяем точку глобального максимума f(x):

max f (x) = max{f (x = 1), V}= max{0,5; 0}= 0,5 = f (x = 1).

Таким образом, точка x = 1 является точкой глобального максимума f(x).

Ответ: функция f (x) = x имеет в точке x = −1 гло- 1+ x2

бальный минимум, а в точке x = 1 − глобальный максимум.

1.2. ФУНКЦИЯ МНОГИХ ПЕРЕМЕННЫХ

Для функции f(x) многих переменных точка x представляет собой вектор, f ′(x) − вектор первых производных (градиент) функции f(x), f ′′(x) − симметричную матрицу вторых частных

производных (матрицу Гессе − гессиан) функции f(x).

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

Необходимое условие локальной оптимальности. Пусть

f(x) дифференцируема в точке x Rn . Если x − точка локального экстремума, то

f ′(x ) = 0.

(1.3)

Как и ранее, точки, являющиеся решениями системы уравнений (1.3), называются стационарными. Характер стацио-

нарной точки x связан со знакоопределенностью матрицы Гессе f ′′(x ) .

Знакоопределенность матрицы А зависит от знаков квадратичной формы Q(α) = αA,α при всех ненулевых α Rn .

Здесь и далее через x, y обозначается скалярное произведение векторов x и y. По определению,

n

x, y = ∑ x j y j .

j =1

Матрица A является положительно (неотрицательно) оп-

13

ределенной, если Q(α) > 0 (Q(α ) ≥ 0) при всех ненулевых α Rn ; отрицательно (неположительно) определенной, если

Q(α) < 0 (Q(α) ≤ 0)	при всех ненулевых α Rn ; неопределен-
ной, если Q(α) > 0	для некоторых ненулевых α Rn и Q(α) < 0
для остальных ненулевых α Rn .

Достаточное условие локальной оптимальности. Пусть

f(x) дважды	дифференцируема	в точке x Rn ,	причем
f ′(x ) = 0 , т.е.	x − стационарная	точка. Тогда, если	матрица

f ′′(x ) является положительно (отрицательно) определенной, то x − точка локального минимума (максимума); если матрица f ′′(x ) является неопределенной, то x − седловая точка.

Если матрица f ′′(x ) является неотрицательно (неположительно) определенной, то для определения характера стационарной точки x требуется исследование производных более высокого порядка.

Для проверки знакоопределенности матрицы, как правило, используется критерий Сильвестра. Согласно этому критерию, симметричная матрица А является положительно определенной в том и только том случае, если все ее угловые миноры положительны. При этом угловым минором матрицы А называется определитель матрицы, построенной из элементов матрицы А, стоящих на пересечении строк и столбцов с одинаковыми (причем первыми) номерами. Чтобы проверить симметричную матрицу А на отрицательную определенность, надо проверить матрицу (−А) на положительную определенность.

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

1. Находится f ′(x) .

2. Решается система

∂f (x) = =

∂x j

0, j 1,n .

14

В результате вычисляются стационарные точки x(i) , i = 1,N .

3.Находится f ′′(x) , полагается i=1.

4.Находится f ′′(x(i )) .

5.Вычисляются угловые миноры матрицы f ′′(x(i )) .

Если не все угловые миноры ненулевые, то для определения характера стационарной точки x(i) требуется исследование

производных более высокого порядка. При этом осуществляется переход к п.8.

В противном случае осуществляется переход к п.6. 6. Анализируются знаки угловых миноров f ′′(x(i )) .

Если f ′′(x(i )) является положительно определенной, то x(i) является точкой локального минимума. При этом осуществ-

ляется переход к п.8.

В противном случае осуществляется переход к п.7.

7. Вычисляются угловые миноры матрицы [− f ′′(x(i) )] и

анализируются их знаки.

Если [− f ′′(x(i) )] является положительно определенной, то f ′′(x(i )) является отрицательно определенной и x(i) является точ-

кой локального максимума.

В противном случае f ′′(x(i )) является неопределенной и x(i) является седловой точкой.

8. Проверяется условие определения характера всех стационарных точек

i = N .

Если оно выполняется, то вычисления завершаются.

Если условие не выполняется, то полагается i = i +1 и осуществляется переход к п.4.

Пример. Определить точки локальных экстремумов функции f (x) = x13 − 2x1x2 + x22 − 3x1 − 2x2 .

15

Решение.

Находим первые частные производные f(x):

	∂f	= 3x2 − 2x −			3,			∂f	= −2x + 2x − 2.
	∂x1		1	2			1			2
								∂x2
Решаем систему уравнений
			3x2	− 2x	2		− 3 = 0,			(1)
			1
			-2x	+ 2x			− 2 = 0.			(2)
						2
			1

Разрешаем уравнение (2) относительно x1:

2x1 = 2x2 − 2 → x1 = x2 −1.

Подставляя полученное выражение в уравнение (1), нахо-

дим x2:

3(x −1)2 − 2x

2

− 3

= 3x2

−

8x

2

= x

2

(3x

2

− 8) = 0 →

2

2

→ x

(1)2

=

0, x

= 8 .

(2)2

3

Соответственно

= 5 .

x

= −1,

x

(1)1

(2)1

3

Таким образом,

получили

две стационарные точки

( N = 2 ):

x = (5 , 8).

x

= (−1, 0),

(1)

(2)

3

3

Находим вторые частные производные f(x):

∂2 f

= 6x

,

∂2

f

= −2,

∂2 f

= 2.

∂x2

∂x ∂x

∂x2

1

2

1

1

2

Составляем матрицу Гессе

f ′′(x)

6x

− 2

=

1

.

− 2

2

Определяем характер стационарной точки x(1) . Находим f ′′(x(1) ) :

16

f ′′(x(1) ) =	−6
	−2
Вычисляем угловые миноры	f ′′(x(1)

2

2 . ) :

M1

=

− 6

= −6 < 0,

M 2 =

− 6

− 2

= (−6)2 − (−2)(−2) = −16 < 0.

− 2

2

Поскольку все угловые миноры ненулевые, то характер

x(1) определяется с помощью

f ′′(x).

Поскольку матрица

f ′′(x(1) )

не

является положительно

определенной, то рассматриваем матрицу [− f ′′(x(1) )]:

− f ′′(x(1) ) =

6

2

.

2

− 2

Вычисляем угловые миноры [− f ′′(x(1) )]:

M1 =

6

= 6 > 0,

6

2

= 6(−2) − 2 2 = −16 < 0.

M 2 =

2

− 2

Поскольку матрица [− f ′′(x(1) )] не является положительно

определенной, то матрица

f ′′(x(1) ) не является отрицательно оп-

ределенной. Следовательно, матрица

f ′′(x(1) ) является неопреде-

ленной и x(1) является седловой точкой.

Определяем характер стационарной точки x(2) . Находим

f ′′(x(2) ) :
10	− 2
f ′′(x(2) ) =	2	.
−2

Вычисляем угловые миноры f ′′(x(2) ) :

M1 = |10| = 10 > 0,

			17
M 2 =		10	− 2		= 10 2 −		(−2)(−2) = 16 >			0.
		− 2	2
Поскольку все угловые миноры ненулевые, то характер
x(2) определяется с помощью f ′′(x) .
Поскольку матрица f ′′(x(2) )						является положительно опре-
деленной, то x(2) является точкой локального минимума.
Ответ: функция			f (x) = x3 − 2x x				2	+ x2	− 3x − 2x	2	имеет в
			1			1		2	1
точке x = (5 3, 8 3) локальный минимум.

Задачи

1. Определить точки локальных и глобальных экстрему-

мов функции					f (x) = 1− x3 .
2.	Определить точки локальных и глобальных экстрему-
мов функции					f (x) = 1− x4 .
3.Определить точки локальных и глобальных экстремумов
функции f (x) = x4 − 4x3 + 4x2 −1.
4.		Определить							точки локальных								экстремумов				функции
f (x) = x2 x −				3x x − x + 2x +							5.
1	2					1	2	1	2
5.		Определить точки локальных экстремумов функции
f (x) = x3	+ x3			−3x x .
1			2				1	2				x (1) = (0, 3, 1) , x(2) = (0,1,−1) и
6.	Проверить,								что точки
x (3) = (1, 2,0)							являются			стационарными								точками			функции
f (x) = 2x x			2	x	3	+ x2 + x2 + x2					− 4x x		3	− 2x	2	x	3	− 2x − 4x	2	+ 4x		3	.
	1							1	2	3	1							1

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

7.

Определить,

являются

ли точки

x(1) = (0, −1)

и

x

(2)

= (2, 1)

точками

экстремумов

функции

f (x) = x3

+ x3

−

1

2

− 3x 2

− 3x x

2

+ 3x + 3x

2

−1.

1

1

1

18

2. ЗАДАЧА УСЛОВНОЙ ОПТИМИЗАЦИИ

Задача оптимизации (минимизации) f (x) → min,

x X

называется задачей условной оптимизации, если X − собственное подмножество пространства Rn (X Rn , X ≠ Rn ).

На практическом занятии рассматривается так называемая классическая задача на условный экстремум. Это задача оптимизации с допустимым множеством X, заданным системой конечного числа уравнений:

X = {x Rn : gi (x) = 0, i = 1, m}.

Здесь предполагается, что m < n .

Обычно эта задача записывается в виде f (x) → min,

gi (x) = 0, i = 1,m .

(2.1)

Для решения задачи (2.1) используется метод множителей Лагранжа. Основная идея метода заключается в переходе от задачи на условный экстремум исходной функции f (x) к задаче на

безусловный экстремум некоторой специально построенной функции Лагранжа L(x, λ)

											m
						L(x, λ) = f (x) + ∑λi gi (x),
											i =1
где	x Rn , λ = ( λ , λ							2	,..., λ	m	) Rm .
					1
	Необходимое							условие локальной оптимальности. Пусть
f(x),	g (x), g		2	(x),..., g			m		(x) дифференцируемы в точке x Rn . Ес-
	1
ли	x −	точка			локального						экстремума, то существует вектор
λ = ( λ , λ ,...,					λ ) ,	компоненты которого не равны нулю одно-
	1	2			m

временно, такой, что

						19
					L′	(x , λ ) = 0,
					x	(x , λ ) = 0,	(2.2)
					L′
	L′	(x, λ),	L′	(x, λ) −	λ
где					соответственно векторы первых частных
	x		λ

производных функции Лагранжа по x j , j = 1,n, и ëi , i = 1,m . При этом должны выполняться условия регулярности: гра-

диенты g1′( x ), g′2 (x ),..., g′m (x ) должны быть линейно независимы. Это означает, что ранг матрицы G′ , строками которой являются градиенты gi′(x ) , должен быть равен m.

Любая точка x , удовлетворяющая при некотором ненулевом λ условиям (2.2), называется стационарной точкой задачи

(2.1).

Для определения характера стационарных точек используется достаточное условие оптимальности с привлечением матрицы L′xx′ (x, λ) вторых частных производных функции Лагранжа по

x j , j = 1,n .

Достаточное условие локальной оптимальности. Пусть f(x), g1(x), g2 (x),..., gm (x) дважды дифференцируемы в точке

x Rn , причем при некотором	λ ≠ 0 выполняются условия
(2.2), т.е. x − стационарная точка. Тогда, если
α L′′ (x ,λ ),α > 0 (	α L′′ (x ,λ ),α < 0)
xx	xx

при всех ненулевых α Rn таких, что

gi′(x ),α = 0, i = 1,m,

то x − точка локального минимума (максимума) f(x) на множестве X.

Алгоритм определения точек условных локальных экстремумов заключается в следующем.

1. Составляется функция Лагранжа L(x, λ).

20

2.Находится L′x (x, λ).

3.Решается система

∂L(x,λ) = 0, j = 1,n;

∂x j

∂L(x, λ) = gi (x) = 0, i = 1,m .

∂λi

В результате вычисляются стационарные точки x(l) , l = 1, N, и соответствующие им λ(l ) , l = 1, N.

4.Находятся gi′(x),α , i = 1,m .

5.Находится L′xx′ (x, λ) , полагается l = 1.

6.Находится L′xx′ (x(l) , λ(l ) ) . Составляется квадратичная

форма Ql (α) , задаваемая матрицей L′xx′ (x(l) , λ(l ) ) :

Ql (α) = αL′xx′ (x(l ), λ(l )),α . 7. Решается система

gi′(x(l) ),α = 0, i = 1,m .

В результате вычисляются точки α(r ) .

8. Вычисляются значения Ql (α(r) ) и анализируются их

знаки.

Если Ql (α(r) ) > 0 для всех ненулевых α(r ) , то x(l ) − точка условного локального минимума.

Если Ql (α(r) ) < 0 для всех ненулевых α(r ) , то x(l) − точка

условного локального максимума.

9. Проверяется условие определения характера всех стационарных точек

l = N .

Если оно выполняется, то вычисления завершаются.

Если условие не выполняется, то полагается l = l +1 и осуществляется переход к п.6.