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

21

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

f (x) = 12 ax12 + 12 bx22 , a > 0, b > 0,

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

			x	3 + x3 = 1.
Решение.			1		2
Составляем функцию Лагранжа
L(x, λ) = 1 ax2				+ 1 bx2 + λ		(x3		+ x3		−1) .
	2		1	2	2		1	2
Находим L′
	(x, λ) :
x
∂L(x, λ) = ax + 3λx2 ,					∂L(x, λ) = bx				2	+ 3λx2 .
∂x1	1			1	∂x2					2
Решаем систему уравнений
ax +		3λx2		= x	(a + 3λx		) = 0,			(1)
	1		1	1		1
			2	= x2 (b + 3λx2 ) = 0,						(2)
bx2 +		3λx2
	3	3	−1	= 0.						(3)
x1 + x2

Для выполнения (1) должно выполняться условие x1 = 0 либо a + 3λx1 = 0 . Для выполнения (2) должно выполняться усло-

вие x2 = 0 либо b + 3λx2 = 0 . Однако в силу (3) одновременно не могут выполняться условия x1 = 0 и x2 = 0 . Следовательно, система имеет 3 решения.

1) Пусть x1 = 0 . Тогда из уравнения (3) получаем x2 = 1. Поскольку x2 ≠ 0, то для выполнения (2) должно выполняться

условие b + 3λx2 = 0 , откуда λ = −b3 .

Таким образом, получили первую стационарную точку

x(1) и λ(1) :

x(1) = (0, 1), λ(1) = −b3.

22

2) Пусть x2 = 0 . Тогда из уравнения (3) получаем x1 = 1. Поскольку x1 ≠ 0 , то для выполнения (1) должно выполняться

условие a + 3λx1 = 0 , откуда λ = − a3.

Таким образом, получили вторую стационарную точку x(2) и λ(2) :

x(2) = (1,	0), λ(2) = − a 3.
3) Пусть x1 ≠ 0 и x2 ≠	0 . Тогда для выполнения (1) долж-

но выполняться условие a + 3λx1 = 0 , откуда λ = − a3x1 ; для вы-

полнения (2)

должно выполняться условие b + 3λx2 = 0 ,

откуда

ë= − b 3x

. Приравнивая выражения для λ, получаем

x =

b

x .

2

2

a 1

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

дим x1 :

3

b

x1

3

3

a3 + b

3

= 1 →

x1

=

a

.

x1 +

−1 = 0 →

x1

a3

a

3 a3 + b3

Находим x2

и λ :

x

=

b

x =

b

, λ = −

a

= −

3

a3 + b3

a

3 a3 + b3

3x1

.

2

1

3

Таким образом, получили третью

стационарную

точку

x(3) и λ(3):

a

b

3

a

3

+ b

3

x(3)

=

3

a

3

+ b

3 ,

3

a

3

+ b

3

,

λ(3)

= −

3

.

Находим

g′(x),α :

∂g(x) = 3x2

,

∂g(x) = 3x2 ,

∂x1

1

∂x2

2

(3x2

,3x

2 ),(á ,á )

= 3x2á

+

3x2

á .

1

2

1

2

1

1

2

2

23

Находим

L′′

(x, λ) :

xx

∂2 L(x, λ)

= a + 6λx

,

∂2 L(x, λ)

= 0,

∂2L(x,

λ)

= b

+ 6λx

,

∂x2

∂x ∂x

∂x2

1

2

1

1

2

2

L′′

(x, λ) =

a + 6λx1

0

.

xx

0

b + 6λx2

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

L′′

(x

(1)

, λ

(1)

) :

xx

b

a

+

6 −

0

0

a

0

3

L′′

(x

, λ

) =

=

.

(1)

(1)

xx

b

0

− b

0

b + 6

−

1

3

Составляем квадратичную форму Q1(α) :

αL′′

(x

,

λ

(1)

)

= (α

1

,

α

2

) a

0

= (aα ,−bα

2

),

xx

(1)

1

0

− b

Q

(α)

= (aα

,−bα

2

), (α

,α

2

) = aα 2

− bα

2.

1

1

1

1

2

Решаем уравнение

g′(x(1) ),α = 0 :

3 0 α1 + 3 1 α2 = 0 → 3α2 = 0.

Решением являются точки α(r ) = (α1 ,0).

Вычисляем значения Q1 (α(r ) ) :

Q (α

(r)

) = aα 2

> 0

при

α

1

≠ 0 .

1

1

Поскольку

Q1(α(r) ) > 0

для всех ненулевых α(r ) , то x(1)

является точкой условного локального минимума.

Отметим,

′′

(x(1) ,λ(1) )

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

что матрица Lxx

тельно определенной.

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

L′xx′ (x(2) , λ(2) ):

24

																	a
									a		+ 6				−					1								0							− a
																	3
L′′	(x		, λ				) =																										=
		(2)			(2)
xx																														a						0
													0												b		+ 6	−			0
																													3
Составляем квадратичную форму Q2 (α) :
	αL′′			(x		(2)		,	λ	(2)	) = (α					1		,α				2	)	− a 0				= (−aα					1	,bα		2	),
		xx																							0
																											b
		Q		(α) = (−aα									1	,bα					2		),(α			1	,α	2	) = −aα 2					+ bα 2 .
			2																												1				2
Решаем уравнение															g′(x(2) ),α											= 0 :
							3 1 α1 + 3 0 α2 = 0 → 3α1 = 0.
Решением являются точки α(r) = (0,α2 ) .
Вычисляем значения Q2 (α(r) ) :
								Q		(α		(r)	)		= bα							2	>	0 при α				2	≠		0 .
									2												2
Поскольку Q2 (α(r) ) > 0																						для всех ненулевых α(r )

является точкой условного локального минимума.

Отметим, что матрица L′′ (x(2) , λ(2) ) не является

xx

0 b .

, то x(2)

положи-

тельно определенной.

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

L′′	(x	(3)	, λ	(3)	) :
xx

L′′	(x	,λ	) =
xx	(3)	(3)

		−
a + 6

3 a3 + b3						a
														0
3				a			+ b
			3			3				3
																		=
														3
								3			a	3	+ b				b
0		b +			6			−
												3					a3 + b3
															3
−a			0
=	0			.
		− b

																		25
	Составляем квадратичную форму Q3 (α) :
		αL′′			(x	(3)	,	λ	(3)		) = (α				,α		2	)	− a		0	= (−aα		,−bα	2	),
			xx											1						0			1
																					− b
Q	(α)		= (−aα					,−bα				2	), (α			,α		2	) = −aα 2			− bα 2 = −(aα 2 + bα 2 ).
(3)							1								1						1		2		1		2
	Поскольку Q3 (α) < 0															для всех ненулевых α (в том числе и
для α(r ) ,			являющихся решением уравнения																				g′(x(3) ),α = 0 ),					то
x(3) является точкой условного локального максимума.
	Ответ:					функция								f (x)				= 1 ax2			+ 1 bx2 ,		a > 0, b > 0,				в	до-
																			2	1	2	2
пустимой			области								X = {x R2 : x3 + x3											=1}	имеет			в	точках
x = (0, 1)			и x = (1,																	1	2
									0)		условные локальные минимумы, а в точке
		a			,					b
х =	a		+ b					a		+ b				− условный локальный максимум.
		3		3		3			3				3
3

Задачи

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

f (x) = x1 + x2

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

x12 + x22 = 1.

2. Определить точки локальных экстремумов функции f (x) = x12 + x22 + x32

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

4x1 + x22 + 2x3 = 14 .

3. Решить задачу условной максимизации

f (x) = x1x2 x3 → max, x1 + x2 + x3 = a .

26

3. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

Задачей квадратичного программирования (КП) называется задача оптимизации с квадратичной целевой функцией и линейными ограничениями. Задача КП, в которой целевая функция подлежит минимизации, имеет вид

f (x) =

n

x

n

n

x

x → min,

∑ c

j

j

+ ∑ ∑ d

j =1

j =1 k =1

jk

j k

n

x

≤ b

,

i =

1, m,

∑ a

ij

j =1

j

i

x j

≥ 0,

j =

.

1, n

Допустимое множество X является выпуклым, матрица D = [d jk ] предполагается симметричной неотрицательно опреде-

ленной. При этом f (x) является выпуклой на X и задача КП явля-

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

Для решения задачи КП используются необходимые условия Куна − Таккера, которые в силу выпуклости задачи КП оказываются также достаточными для установления наличия решения.

Предварительно составляется функция Лагранжа

m

L(x, λ) = f (x) + ∑ λi gi (x),

i =1

n

где g j (x) ≡ ∑ aij x j − bi .

j =1

Условия Куна − Таккера имеют следующий вид:

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

(3.1)

(3.2)

(3.3)

		27
	∂L(x, λ) ≤ 0,			i =							(3.4)
						1, m;
		∂λi
		λi ≥ 0,	i =				;				(3.5)
					1, m
λ		∂L(x, λ)	= 0,		i =						(3.6)
								1, m.
i		∂λi

Соотношения (3.3) и (3.6) определяют условия дополняющей нежесткости.

Непосредственное решение данной системы очень громоздко. Поэтому используется следующий прием. Неравенства (3.1) и (3.4) преобразуют в равенства, вводя соответственно две

группы дополнительных переменных v j , j = 1, n, и wi , i = 1, m,

удовлетворяющих требованиям неотрицательности. В результате от системы (3.1)−(3.6) переходят к следующей системе:

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

x j ≥ 0, v j ≥ 0, j =1, n; x jv j = 0, j = 1, n;

∂L(x, λ) + wi = 0, i =1, m;

∂λi

(3.8)

(3.9)

(3.10)

λi ≥ 0, wi ≥ 0, i =		1, m		;	(3.11)
					(3.12)
λi wi = 0, i =1, m.
Система уравнений (3.7) и (3.10) содержит (m + n)					линей-

ных уравнений с 2(m + n) неизвестными. Таким образом, исход-

ная задача эквивалентна задаче нахождения допустимого, т.е. удовлетворяющего требованиям неотрицательности (3.8) и (3.11), базисного решения системы линейных уравнений (3.7) и (3.10), удовлетворяющего также условиям дополняющей неже-

сткости (3.9) и (3.12). Так как задача КП является выпуклой задачей оптимизации, то допустимое решение, которое удовлетворяет всем этим условиям, является оптимальным.

28

Для нахождения допустимого базисного решения системы линейных уравнений может быть применен метод искусственных переменных, используемый в линейном программировании (ЛП) для определения начального базиса. При этом в уравнения системы (3.7), (3.10), в которых знаки дополнительных переменных v j

или wi совпадают со знаками свободных членов, вводятся неот-

рицательные			искусственные	переменные
			lmax ≤ m + n , знаки которых не совпадают со знака-
zl , l = 1,lmax		,

ми соответствующих свободных членов.

Затем решается вспомогательная задача ЛП

F(z) = ∑ zl → min

l

при ограничениях (3.7) − (3.12) с введенными неотрицательными искусственными переменными. Для решения этой задачи используется симплекс-метод. В процессе решения необходимо учитывать условия дополняющей нежесткости (3.9) и (3.12). Выполнение этих условий означает, что x j и v j , λi и wi не могут быть

положительными одновременно, т.е. переменную x j нельзя сделать базисной, если v j является базисной и принимает положительное значение, также и λi с wi .

В результате решения вспомогательной задачи могут быть два случая.

1. min F(z) = 0, т.е. все искусственные переменные выве-

z

дены из базиса. Полученное оптимальное допустимое базисное решение вспомогательной задачи ЛП является допустимым базисным решением системы (3.7) − (3.12) и, следовательно, решением задачи КП.

2. min F(z) > 0, т.е. среди базисных остались искусствен-

z

ные переменные. Это означает, что система (3.7) − (3.12) не имеет допустимого базисного решения и, следовательно, задача КП не имеет решения.

Итак, алгоритм решения задачи КП заключается в сле-

29

дующем.

1. Ограничения задачи КП преобразуются к виду

gi (x) ≤ 0,

i =

.

1, m

2. Составляется функция Лагранжа

m

(x).

L(x, λ) = f (x) + ∑ λ g

i=1 i i

∂L

∂L

3. Находятся частные

производные

,

j =

;

,

1, n

∂x j

∂λi

i =

, и составляются условия Куна − Таккера (3.1) − (3.6).

1, m

4. Посредством введения

дополнительных

переменных

v j , j =

; wi , i =

, неравенства

1, n

1, m

∂L

≥

0,

∂L

≤ 0

∂x

j

∂λ

i

преобразуются в равенства

∂L

− v

j

= 0,

∂L

+ w = 0,

∂x j

i

∂λi

врезультате получается система (3.7) − (3.12).

5.Вводятся искусственные переменные z l , составляется

вспомогательная задача ЛП минимизации F(z) = ∑ zl при огра-

l

ничениях (3.7) − (3.12) с введенными неотрицательными искусственными переменными.

6. Решается вспомогательная задача ЛП симплексметодом с учетом условий дополняющей нежесткости.

Если в результате решения min F(z) = 0, то оптимальное

z

допустимое базисное решение вспомогательной задачи определя-

ет решение x* задачи КП.
Если min F(z) > 0,	то задача КП не имеет решения.
z
Пример. Решить следующую задачу КП:
f (x) = 2x2 + 2x x		2	+ 2x2	− 4x − 6x	2	→ min,
1	1		2	1

30

x1 + 2x2 ≤ 2,

Решение.

x1

≥ 0,

x2

≥ 0.

Преобразуем

ограничение

исходной

задачи

к виду

g(x) ≤ 0 :

g(x) = x1 + 2x2 − 2 ≤ 0 .

Составляем функцию Лагранжа

L(x, λ)

= 2x2

+

2x x +

2x2

− 4x − 6x + λ(x + 2x

2

−

2).

1

1

2

2

1

2

1

Находим частные производные и составляем условия Куна

− Таккера:

∂L

= 4x + 2x −

4 + λ ≥ 0,

x ≥

0,

x

∂L

=

0;

∂x

1

2

1

1 ∂x

1

1

∂L

= 2x + 4x − 6 + 2λ ≥ 0,

x ≥ 0,

x

∂L

= 0;

∂x

2

1

2

2

2 ∂x

2

∂L

= x + 2x

2

−

2 ≤ 0, λ ≥ 0, λ

∂L

= 0.

∂λ

1

∂λ

Вводим дополнительные переменные v1 , v2 и w , обращающие неравенства в равенства, в результате получаем

4x1 + 2x2 − 4 + λ − v1 = 0, x1 ≥ 0, v1 ≥ 0, x1v1 = 0; 2x1 + 4x2 − 6 + 2λ − v2 = 0, x2 ≥ 0, v2 ≥ 0, x2v2 = 0;

x1 + 2x2 − 2 + w = 0, λ ≥ 0, w ≥ 0, λw = 0.

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

Вводим в первое и второе уравнения соответственно искусственные переменные z1 и z2 :

4x1 + 2x2 − 4 + λ − v1 + z1 = 0, 2x1 + 4x2 − 6 + 2λ − v2 + z2 = 0.

Разрешая первое уравнение относительно z1 , а второе уравнение относительно z2 , находим целевую функцию F (z) вспомогательной задачи ЛП: