Методы оптимизации / volsu419

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра теории вероятностей и оптимального управления

В.Г. Шарапов

РУКОВОДСТВО ПО РЕШЕНИЮ ЗАДАЧ ПО КУРСУ

«ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ»

Методическое пособие

Волгоград 2004

Рецензент:

канд. физ.-мат. наук, доц., и.о. зав. каф. МАиТФ А.А. Клячин

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

(протокол № 3 от 04.06 2004 г.)

Печатается с готового оригинал-макета в авторской редакции

Шарапов В.Г.

Руководство по решению задач по курсу «Вариационное исчисление и методы оптимизации»: Методическое пособие. — Волгоград: Издательство Волгоградского государственного универси-

тета, 2004. — 52 с.

.

© В.Г. Шарапов, 2004 © Издательство Волгоградского

2

государственного университета, 2004

Введение

Методическое пособие предназначено для обучения студентов решению задач по курсу "Вариационное исчисление и методы оптимизации" (ВИМО).

Решение задач по ВИМО не простое дело, требующее не только знаний предмета, но и определённой интуиции и смекалки. Чтобы выработать в себе эти качества необходимо наработать опыт решения таких задач, т.е., попросту, решать их. Решение этих задач обычно требует больших затрат времени, но с каждой решённой задачей приходит удовлетворение и уверенность в себе.

Задачи усложняются постепенно, самые сложные − это задачи оптимального управления, они помещены в конце методического пособия.

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

Каждая задача (P) по ВИМО начинается с формализации типа: f(x) → extr (P),

и определения области D(P) допустимых решений x D(P) задачи (P). После этого обычно используются необходимые условия экстремума, по ним определяются экстремали xˆ , среди которых только и могут быть решения задачи. Затем по определению экстремумов (обычно даны определения локального минимума, остальные определяются по аналогии) устанавливаются, какими экстремумами являются xˆ или не являются вовсе. Достаточные условия привлекаются только в простейших случаях. В большинстве же случаев их привлечение очень сложно. Часто используется следствие из теоремы Вейерштрасса о достижении экстремума на компактном множестве:

Если функция f непрерывна на Rn и lim	f (x) = ∞ ( lim f (x) = −∞),
|x|→∞	|x|→∞

то f достигает абсолютный минимум (максимум) на любом замкнутом

подмножестве Rn.

Автор выражает благодарность А.Клячину за ценные замечания.

При подготовке пособия использовалась литература:

1.Алексеев В.М., Галеев Э.М., Тихомиров В.М., Сборник задач по оптимизации, Учебное пособие, М., Наука, 1979

2.Галеев Э.М., Тихомиров В.М., Краткий курс теории экстремальных задач, Издательство МГУ, 1989

3.Галеев Э.М., Тихомиров В.М., Оптимизация: теория, примеры,

3

задачи, М., Эдиториал УРСС, 2000

4

1. Конечномерные гладкие задачи без ограничений

Постановка задачи. Пусть f: Rn → R − функция n действительных переменных, обладающая некоторой гладкостью (дифференцируемо-

стью). f Dk (xˆ) означает, что функция f k раз дифференцируема в точке xˆ .

Гладкой конечномерной задачей называется задача f (x) → extr .

Точка xˆ Rn называется точкой локального минимума (максиму-

ма) функции f, если

| x − xˆ |< ε f (x) ≥ f (xˆ) ( f (x) ≤ f (xˆ)) .

Здесь | | − обозначение нормы в конечномерном пространстве. При

этом пишем xˆ loc min f (xˆ loc max f ) .

Необходимые условия экстремума первого порядка.

Если xˆ = (x1 ,K, xn ) loc extr f									и f D(xˆ) , то
′				∂f (xˆ)			∂f (xˆ)
f	(xˆ) = 0			∂x		=K	= ∂x	n		= 0 .
				1
Необходимые условия экстремума второго порядка.
Если		f D2	(xˆ) ,		xˆ loc min(max) f , то f ′(xˆ) = 0 ,
f ′′(xˆ)h, h ≥ 0 (				f ′′(xˆ)h, h ≤ 0) h Rn .
Достаточные условия экстремума второго порядка.
f ′(xˆ) = 0 .			f ′′(xˆ)h, h > 0 ( f ′′(xˆ)h, h < 0) h Rn , h ≠ 0.
Последовательными главными минорами матрицы A = (aij )in, j=1
называются определители
		a			K a
A1,...,k				11		1k
		= det K K K .
					K akk
		ak1
Главными минорами Ai Ki							матрицы A называются определители
						1 n
Ai		ai1i1			K ai1ik
	Ki	= det K K K , i1 < i2 < … < ik .
1	k
		aiki1			K aikik
							5

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

			∂2 f (xˆ) n			n
A = f	′′					= (aij )i, j=1 .
	(xˆ) =		∂x	∂x
			i		j i, j=1

Матрица A называется неотрицательно определенной (A ≥ 0), если

n

Ah, h ≥ 0 h Rn ∑aij hi h j ≥ 0 h = (h1 , K, hn ) Rn

i, j=1

.

Матрица A называется положительно определенной (A > 0), если

Ah, h > 0 h Rn , h ≠ 0 .

Аналогично определяются отрицательно определенная матрица и неположительно определенная матрица, для которых соответственно

A < 0, A ≤ 0.

Критерий Сильвестра.

Теорема. Пусть A − симметричная матрица. Тогда

1. A > 0 A1Kk > 0, k =1,K, n.

2. A < 0 (−1)k A1Kk > 0, k =1,K, n

3.	A ≥ 0 Ai Ki	≥ 0, 1 ≤ i1 ≤K≤ ik ≤ n, k =1,K, n
	1	k
4.	A ≤ 0 (−1)k A			≥ 0, 1 ≤ i ≤K≤ i	k	≤ n, k =1,K, n.
		i Ki	k	1
		1

Правило решения.

1. Выписать необходимые условия экстремума первого порядка

f ′(x) = 0 ∂f (x) =K= ∂f (x) = 0 ∂x1 ∂xn

Решения этой системы называются стационарными точками и обозначаются xˆ .

2. Проверить выполнение условий экстремума второго порядка. Для этого найти матрицу вторых производных

			∂2 f (xˆ) n				n
A =	′′						= (aij )i, j=1 .
	f (xˆ) =		∂x	∂x
					j
			i			i, j=1
				6

Найти Ai…k. Если все Ai…k > 0, то xˆ loc min f ; если все

(−1)kAi…k > 0, то xˆ loc max f .

Если предыдущие условия не выполняются, то надо проверить, бу-

дет ли Ai Ki	≥ 0 ; 1 ≤ i1	≤K≤ ik ≤ n, k =1,K, n (тогда A ≥ 0 ) и
1	k
(−1)k A	≥ 0 , 1 ≤ i	≤K≤ i	k	≤ n, k =1,K, n (тогда A ≤ 0 ). Если
i Ki	1
1 k

не выполняются оба условия A ≤ 0 и A ≥ 0 , то экстремума нет. Если вы-

полняется одно из условий A ≤ 0 или A ≥ 0 , то проверка на экстремум производится по определению экстремума.

Пример 1.

f (x1 , x2 ) = x1 x2 + 50 + 20 → extr . x1 x2

Необходимые условия экстремума первого порядка:

							50
f x1		= x2 − x2						= 0		x12 x2 = 50		50	=	20			x1 =		5	x2 .
							1
		= x1 −					20	=	0	x1 x22 = 20		x1			x2				2
f x2							2
							x2
		=		5	x
x				2			x1		=5, x2 = 2.
	1					2
		2		= 20
x1 x2
Стационарная точка xˆ = (5, 2) .
Вторые частные производные fx x =											100	,	f x x			= f x x =1,
										1 1	x3		1		2		2	1
											1
f	x2 x2		=		40 .
					x23
Матрица вторых частных производных в точке xˆ																		4 / 5	1
																A =				.
																		1
Последовательные главные миноры:																				5
A1	= 4			5	> 0, A1 2				= 4 5 1 = 3 > 0 xˆ loc min f .
									1	5

Минимальное и максимальное значения функции f(x1, x2):

7

Smin = −∞, Smax = +∞.

						Smin = −∞, Smax = +∞.
	( Для последовательностей {(−1 n , −1 n)}и {(1 4 ,1 n)}соответ-
ственно).
	Пример 2.								) = x2	+ x2 + 2x2 + x x
	f (x , x				2	, x		3									2	+ 2x x				3	+ 3x				2	x	3	− x → extr
			1						1			2		3		1				1										1
	Необходимые условия экстремума первого порядка:
	f x		= 2x1 + x2 + 2x3 −1 = 0
		1		= 2x2 + x1 + 3x3 = 0 .
	f x2
	f		= 4x					3	+ 2x	+ 3x			2	= 0
		x3							1
	Решив эту систему, находим стационарную точку
xˆ = (1 2 , −1,1 2) .
	Вторые частные производные fx x															= 2,		f x x		2	= f x			x			=1,
														1	1				1				2		1
	fx x		3	= fx			x		= 2, f x		x	2	= 2, fx		x	= f x x			= 3, f x						x	3		= 4.
	1					3		1		2				2	3			3	2				3
	Матрица вторых частных производных в точке xˆ
	2	1		2
	1	2		3
A =						.
	2	3		4

Последовательные главные миноры: A1 = 2, A12 = 3, A123 = −2. Так как условия A ≥ 0 и A ≤ 0 не выполняются, то xˆ loc extr f .

Минимальное и максимальное значения функции f(x1, x2, x3):

(Соответствующие последовательности

легко построить).

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

Постановка задачи. Пусть fi: Rn → R, i = 0, m − функции, об-

ладающие определенной гладкостью.

Гладкой конечномерной задачей с ограничениями типа равенств называется задача:

f0 (x) → extr , fi (x) = 0 , i =	1, m	.	(P)
8

Необходимые условия экстремума первого порядка.

Пусть xˆ loc extr P , функции fi , i = 0, m , непрерывно дифференцируемы в некоторой окрестности точки xˆ .

Тогда λ = (λ , λ ,K, λ						m	) Rm+1 , λ ≠ 0 , такие что для функции
			0	1
			m
Лагранжа Λ(x) = ∑λi fi (x) выполняется условие стационарности:
		i=0		∂Λ(xˆ) = 0, j =
	Λx (xˆ) = 0								.
								1, n
				∂x j
Точки, удовлетворяющие условию стационарности, называются
стационарными.
Необходимые условия экстремума второго порядка.
Пусть xˆ loc min P ,					fi	D2 (xˆ), i =					, размерность оболоч-
										0, m
′	′
ки {f1 (xˆ),K, fm (xˆ)}равна m. Тогда
λ = (1, λ ,K, λ		m	) Rm+1		(λ	=1) , такие что для функции Лагранжа
	1				0

m

Λ(x) = f0 (x) + ∑λi fi (x) выполняется условие стационарности

i=1

Λx (xˆ) = 0 и условие неотрицательной определённости матрицы вторых

Λ′′(xˆ)h, h

≥ 0 h : fi′(xˆ), h

= 0, i =

.

производных:

1, m

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

Пусть f

D2 (xˆ), i =

, dim lim{f ′(xˆ),K, f ′(xˆ)}= m,

i

0, m

1

m

λ = (1, λ ,K, λ

m

) Rm+1 такие, что для функции Лагранжа

1

m

Λ(x) = f0 (x) + ∑λi fi (x) задачи (P) выполняется условие стационар-

k =1

′

′

m

ности: Λ

(xˆ)

′

= 0 f1 (xˆ) + ∑λi fi (xˆ) = 0 и условие положительной

i=1

определённости матрицы вторых производных:

Λ′′(xˆ)h, h > 0 h ≠ 0

такого, что fi′(xˆ), h = 0,

i =

. Тогда xˆ loc min P .

1, m

9

Условие максимума аналогично, если

m

Λ(x) = − f0 (x) + ∑λi fi (x) .

k =1

Правило решения. Для решения задачи (P) нужно:

m

1. Составить функцию Лагранжа Λ(x) = ∑λi fi (x) .

i=0

2. Написать необходимое условие экстремума первого порядка − условие стационарности:

′	m
	′	(1)
Λx (xˆ) = 0	∑λi fi (xˆ) = 0

i=0

3.Решение системы (1) даёт стационарные точки. При этом сначала

рассматривается случай λ0 = 0, а затем λ0 = 1 или любое другое положительное число. Обычно этого достаточно, чтобы установить, являются ли стационарные точки точками локального или абсолютного максимума или минимума по их определению. Можно воспользоваться достаточными условиями экстремума второго порядка. При этом для максимума удобно

брать λ0 = −1 или любое другое отрицательное число.

Пример 1. f (x, y, z) = xyz → extr ; x2 + y2 + z2 =1, x + y + z = 0 .

Функция Лагранжа

Λ(x) = λ0 xyz + λ1 (x2 + y2 + z2 −1) + λ2 (x + y + z) .

Условия стационарности:

Λx = 0 λ0 yz + 2λ1 x + λ2 = 0 ,

Λy = 0 λ0 xz + 2λ1 y + λ2 = 0 ,

Λz = 0 λ0 xy + 2λ1z + λ2 = 0 .

Пусть λ0 = 0. Тогда 2λ1 x + λ2 = 0 , 2λ1 y + λ2 = 0 ,

2λ1 z + λ2 = 0 .

Если эти три равенства сложить и принять во внимание, что x + y + z = 0 , получаем λ2 = 0, а значит, и λ1 = 0. Отсюда λ0 ≠ 0.

Принимаем λ0 = 1. Получаем:

yz + 2λ1x + λ2 = 0 xz +2λ1y + λ2 = 0 xy +2λ1z + λ2 = 0

10