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

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

а) Уравнение Эйлера − dtd Lx& + Lx = 0 .

б) Находим общее решение уравнения Эйлера при λ0 = 0 и λ0 =1 (или другой ненулевой константе). Из условий на концах и из изопереметрических условий (1) находятся константы и получается экстремаль xˆ .

в) Проверяем все экстремали по определению экстремумов: будут ли они экстремумами, и какими, или нет.

1			1
&	2	dt	→ extr , ∫tx dt = 0 ,
Пример 1. I (x) = ∫x
0			0
x(0) = x − 4, x(1) = 4 .
&2	+ λ1tx .
Лагранжиан: L = λ0 x
		&&	+ λ1t = 0 .
Уравнение Эйлера: − 2λ0 x

λ0 = 0 λ1 = 0 λ0 ≠ 0 .

Пусть λ0 =12 . Тогда &x&= λ1t x = C1t3 + C2t + C3 .

x(0) = −4 C3		= −4 ,	x(1) = 4 C1 +C2 = 8 .
1
∫t(C1t3 + C2t − 4) dt = 0 C1 5 + C2 3 − 2 = 0 .
0
Это вместе с C1 + C2 = 8 дает C1					= 5, C2	= 3 .
Итак, xˆ = 5t3 + 3t − 4 .
			1		1	1
			&2	dt +	&&	&&
I = I (xˆ + h) − I (xˆ) = ∫h					2∫xˆh dt ≥ 2∫xˆh dt =
			0		0	0
1		1			1	1
&	&	1	&&
= 2∫xˆ dh	= 2xˆh |0 −2∫xˆh dt = −2∫15th dt = −30∫thdt = 0 .
0		0			0	0
&	1

Здесь 2xˆh |0 = 0 , так как h(0) = h(1) = 0

(x(0) = −4, (x + h)(0) =

1

= −4 h(0) = 0) и ∫th dt = 0 , так как

0

31

1		1									1
∫tx dt = ∫t(x + h)dt = 0 ∫th dt = 0 . Итак xˆ abs min .
0		0									0
					1						1		1
						&	2	dt → extr , ∫x dt =1,					∫tx dt = 0 ,
Пример 2. I (x) = ∫x
x(0) = x(1) = 0 .					0						0		0
					&	2	+		λ1 x + λ2tx
Лагранжиан: L = λ0 x
								&&		+ λ1 + λ2t = 0 .
Уравнение Эйлера: − 2λ0 x
				λ0 = 0 λ1 = λ2 = 0 λ0 ≠ 0 .
Пусть λ0		=1 2 . Тогда								+ C3t + C4 .
x = λ1 + λ2t x = C1t				3	+ C2t				2
&&
x(0) = 0 C4 = 0.								x(1) = 0 C1 + C2				+ C3		= 0 . (1)
1
∫x dt =1 C1				4 + C2					3 + C3		2 =1 ,			(2)
0
1
∫tx dt = 0 C1				5 + C2					4 + C3		3 = 0 ,			(3)
0
(1), (2), (3) C1 = 60, C2 = − 96, C3 =36.
xˆ = 60t3 − 96t2 + 36t .
			1						1
h C01[0, 1],			∫h dt = 0 , ∫th dt = 0 .
			0						0
1		1				1					1	&		1
&2	dt +	&	&					&	&		&		1	&&
I = ∫h		2 ∫xˆh dt		≥2 ∫xˆh dt = 2∫xˆ dh = 2xˆh |0										− ∫xˆh dt =
0		0				0					0			0
1		1									1		1
= −∫&xˆ&h dt = − ∫(360t −192)hdt = −360∫thdt +192∫hdt = 0 .
0		0									0		0

xˆ abs min .

32

10. Задача со старшими производными

Постановка задачи. Задачей со старшими производными называ-

ется следующая экстремальная задача в C n [t

0

, t ] :

1

t

&

&&

(n)

(t))dt → extr

(P)

I (x( )) = ∫L(t, x(t), x(t), x(t),K, x

t0

x(k ) (t j ) = xkj ,

k =

j = 0,1.

0, n −1,

Функция n + 2 переменных L называется интегрантом.

Норма в пространстве C n [t

0

, t ] :

1

&

(n)

x(t)

n : = max max | x(t) |, max | x(t) |,K, max | x

(t) | .

t0 ≤t≤t1

t0 ≤t≤T1

t0 ≤t≤t1

Определение.

xˆ loc min P , если ε > 0 :

x( ) − xˆ( )

n < ε I (x( )) ≥ I (xˆ( )) .

Правило решения. 1. Пишем необходимые условия экстремума −

n	k
уравнение Эйлера-Пуассона: ∑(−1)k	d	Lx( k ) (t) = 0 .
	k
k =0	dt

2.Находим общее решение этого уравнения и с помощью начальных условий находим все константы и устанавливаем экстремали xˆ .

3.С помощью непосредственной проверки находим, что функции xˆ доставляют экстремумы или нет.

		1	&&2		= 0 ,
				&
Пример 1. I (x) = ∫(48x − x				) dt → extr , x(0) = x(0)
x(1) =1, x(1) = 4 .		0
&
&&2	, L&x&	&&2	, Lx	= 48 , Lx& = 0 .
L = 48x − x		= −2x

Уравнение Эйлера-Пуассона: 48 − 2x(4) = 0 x(4) = 24

x = t4 + C1t3 + C2t2 + C3t + C4 .

x(0) = 0 C4 = 0 , x&(0) = 0 C3 = 0 .

x(1) =1 C1 + C2 = 0 , x&(1) = 4 3C1 + 2C2 = 4

C1 = C2 = 0 xˆ = t4 .

33

1 1 1

I = I (xˆ + h) − I (xˆ) = 48∫h dt − ∫h&&2dt − 2∫&xˆ&h&&dt .

	0	0		0
1	1		1	1

− 2∫&xˆ&h&&dt = − 2∫&xˆ&dh& = − 2&xˆ&h&|10 + 2∫xˆ(3) h&dt = 2∫xˆ(3) h&dt =

0		0			0	0
1				1	1
= 2∫xˆ(3) dh = 2xˆ(3) h |10 − 2∫xˆ(n) h dt = − 2∫24h dt .
0				0	0
I = 48∫1	h dt − ∫1	h&&2 dt − 48∫1		h dt = −∫1	h&&2 dt ≤ 0 xˆ abs max .
0	0		0	0
Легко проверить, что Smin = −∞.
		1
		&&2	− 24tx) dt → extr ,
Пример 2. I (x) = ∫(x
		0

2x(4)

x(0)

	x(0) = x(0) = 0,			x(1) =1 5,				x(1) =1 .
	&							&
	Лагранжиан:	d 2		L&& −	d	L& + L	x	= 0 .
		dt2			dt
				x		x

−24t = 0 x(4) =12t x = t5 10 + C1t3 + C2t2 + C3t + C4 .

=x&(0) = 0 C3 = C4 = 0 .

x(1) =1 5 C1 + C2 =1 10 , x&(1) =1 3C1 + 2C2 =12

C = 3 10 , C	2	= −1 5 xˆ	=1 10 (t5	+ 3t3 − 2t2 ) .
1
1		1

I = ∫(2&xˆ&h&&+ h&&2	− 24th) dt ≤ ∫(24&xˆ&h&&− 24th) dt = 0 xˆ abs min
0	0

11. Задача Лагранжа.

Постановка задачи. Задачей Лагранжа называется следующая экстремальная задача.

B0 (ξ) → min; Bi (ξ) ≤ 0, i =				,	B1 (ξ) = 0, i =
			1, m′				m′+1, m
(P)		,				(1)
xα (t) −ϕ(t, x(t)) = 0 t
&
ξ = (x( ), t	, t ) , x( ) C1 (	, Rn ) ,			t	, t , − отрезок.
0	1				0	1
	34

t1
Bi (ξ) = ∫	fi (t, x(t), x(t))dt + li (t0 , x(t0 ), t1 , x(t1 )), i =	0, m	.
	&

t0

Условие (1) может быть распространено лишь на некоторые координаты, пусть для определённости, на первые k координат.

	Обозначим x = (xα , xβ ) , xα			= (x1 ,K, xk ) , xβ = (xk +1 ,K, xn ) .
	Поставив ϕ(t, x)	&		в	&
fi =		вместо xα			fi (t, x, x) , можно считать, что
	fi (t, x, xβ ) .
	&
	Определение. ξˆ = (xˆ( ), tˆ		, tˆ		, ) loc min P , если ε > 0 :
		0		1

ξ D(P), x( ) − xˆ( )1 < ε ,

t0 − tˆ0 < ε, t1 − tˆ1 < ε B0 (ξ) ≥ B0 (ξˆ) .

Правило решения. 1. Привести задачу к виду (P).

2. Написать функцию Лагранжа с множителями Лагранжа

(λ, p) Rm+1 ×C1 ( , Rk ), λ ≠ 0 :

Λ(x( ), t0	t1		−ϕ(t, x))) dt +
	, t1 ) = ∫( f (t, x, xβ ) + p(t)(xα
	&	&
	t0
+ l(t0 , x(t0 ), t1 , x(t1 )), где			m
		f (t, x, xβ ) = ∑λi fi (t, x, xβ ) ,
		&	&

i=0

l= ∑λi li (t0 , x(t0 ), t1 , x(t1 )) − терминант.

i=0m

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

а) стационарности по x( )

− уравнение Эйлера для лагранжиана

L(t, x, x) = f (t, x, xβ ) + p(xα −ϕ(t, x)) :

&

&

&

d

ˆ

ˆ

−

dt

Lx&

(t) + Lx = 0

ˆ

− p&(t) − p(t)ϕˆxα

(t) +

(t) = 0

t

f xα

d

ˆ

ϕˆ

ˆ

;

−

f &

(t)

−

(t)

+

f

(t)

=

0

p(t)

xβ

dt

xβ

xβ

35

б) трансверсальности по x					ˆ
				ˆ
ˆ	ˆ				= lxα	(t0 )
				p(t0 )			;
Lx&	(tˆ0 ) = lx(t0 )
			fˆx&β (tˆ0 ) = lˆxβ (t0 )
ˆ	ˆ			ˆ		ˆ
				p(t1 ) = −lxα (t1 )				;
Lx&	(tˆ1 ) = −lx(t )
	1		fˆx&β (tˆ1 ) = −lˆxβ (t1 )

в) стационарности по подвижным концам (только для подвижных концов)

Λˆ t0 = 0 − fˆ (tˆ0 ) + lˆt0 + lˆx(t0 ) x&ˆ(tˆ0 ) = 0 , Λˆ t1 = 0 fˆ (tˆ1 ) + lˆt1 + lˆx(t1 ) x&ˆ(tˆ1 ) = 0 ;

г) дополняющей нежёсткости λi Bi (ξˆ) = 0, i =1, m′;

д) неотрицательности λi ≥ 0, i = 0, m′.

4.Находятся экстремали xˆ , удовлетворяющие условиям а) − д).

5.Непосредственной проверкой устанавливается, являются ли xˆ экстремумами или нет.

1

&&2		− 48x)dt → extr, x(0)	= x(1)	= 0 .
Пример 1. B(x) = ∫(x
0
				&
Приведём задачу к виду (P). Для этого положим x1 = x, x2 = x .
1
&2	− 48x1 )dt → min ,
Получаем B(x) = ∫(x2
0

x&1 = x1 , x1 (0) = x1 (1) = 0 .

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

1	(x2	− 48x1 ) + p(t)(x1 − x2 ))dt + λ1 x(0) + λ2 x(1) .
Λ = ∫(λ0
	&	&
0

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

а) система уравнений Эйлера для лагранжиана

L = λ0 (x&22 − 48x1 ) + p(t)(x&1 − x2 ) , 36

−

d

L&

+ L

&

λ 48 = 0 ,

dt

x1

x1

0

−

d

L&

+ L

&&

− p

= 0 ;

dt

x2

x2

0

2

б) условия трансверсальности по x для терминанта

l = λ1 x1 (0) + λ2 (x1 (1)) :

Lx&

(0) = lx (0) , Lx

= −lx (1) p(0) = λ1 , p(1) = −λ2 ,

1

1

1

1

2λ0 x2 (0) = 0, 2λ0 x2 (1) = 0 .

Lx&2

(0) = lx2 (0) , Lx&2

(1) = −lx2 (1)

&

&

в)неотрицательности λ0 ≥ 0 .

а)

б)

λ0 = 0 p

=

0 λ1

= λ2

= 0 λ0 ≠ 0 .

Пусть λ0

=1 2 . Тогда из а)

p = −24 p = −24t + C1 ,

&

+ C1t + C2

x2 = −p x = −p x = 24t + C x =12t

2

&&

&&&

&&&

&&

&

= 4t

3

+ C1t

2

+ C2t

+ C3

x = t

4

+ C1t

3

+ C2t

2

+ C3t + C4 ,

x

x(0) = 0 C4

= 0 . x(1) = 0 1 + C1 + C2

+ C3 0

(1)

Из б)

&

&&

= 0

&&

2

+ 6C1 (t) + 2C2

x2 (0) = x(0)

. x(t) =12t

x(0) = 0 C2

= 0 ,

&&

= 0 C1

= −2 .

x2 (1) = x(t) = 0 12 + 6C1

&

&&

Из (1) C3

=1 xˆ = t4

− 2t3 + t ,

1

1

1

B = B(xˆ + h) − B(xˆ) = ∫h&&2dt + 2∫&xˆ&h&&dt − ∫48hdt .

0

0

0

1

1

1

1

&&&&

=

&&

&

=

&&& 1

&

&&&

2∫xˆhdt

2∫xˆdh

2xˆh |0 −2∫&x&&hdt = −2∫xˆdh , так как

0

0

0

0

1

1

1

&&

&&

&&&

&&&

1

+2∫xˆ

(4)

hdt = 2∫xˆ

(4)

hdt ,

xˆ

(0)

= xˆ(1) = 0 . Далее − 2∫xˆdh = −xˆh |0

0

0

0

37

			1	1
так как h(0) = h(1) = 0 .		xˆ(4) = 24 2∫&xˆ&h&&dt = ∫48hdt . Поэтому
			0	0
1	1	1	1
B = ∫h&&2dt + ∫48hdt − ∫48hdt = ∫h&&2dt > 0 xˆ absmin ,
0	0	0	0
	1
Smin = ∫(&xˆ&2 − 48xˆ)dt = −24 5,			Smax = ∞ .
	0

12. Задачи оптимального управления.

Постановка задачи. Задачей оптимального управления (в понтрягинской форме) называется следующая задача:

B0 (ξ) → min,

Bi (ξ) ≤ 0,

i =

,

(P)

1, m′

Bi (ξ) = 0, i =

,

m′+1, m

(1)

x(t) −ϕ(t, x(t), u(t)) = 0 t T ,

&

u(t) U

t

,

(2)

где

, t ), x PC1 ( , Rn ), u PC( , Rr ), t

ξ = (x( ), u( ), t

0

0

, t ,

1

1

− конечный отрезок, U Rr , T

− множество точек непрерывно-

сти функций u(t) = (u1 (t),K, ur (t)) , называемых управлением.

t1

Bi (ξ) = ∫ fi (t, x(t), u(t))dt + l1 (t0 , x(t0 ), t1 , x(t1 )),

i =

0, m

.

t0

Здесь

PC(

, Rn ) − пространство кусочно-непрерывных вектор-

функций на

, а PC1 (

, Rr ) − пространство непрерывных функций на

с кусочно-непрерывной производной.

Ограничение (1) называется дифференциальным ограничением, ог-

раничение (2) называется ограничением включения.

Один или оба конца могут рассматриваться подвижными.

Элемент ξ, удовлетворяющий указанным условиям, называется до-

пустимым управляемым процессом (ДУП).

38

Определение. ДУП ξˆ = (xˆ( ), uˆ( ), tˆ0 , tˆ1 ) называется оптималь-

ным, если

ε > 0 : x( ) − xˆ( ) < ε, t0 − tˆ0 < ε, t1 − tˆ1 < ε B0 (ξ) ≥ B0 (ξˆ) .

Правило решения. 1. Для множителей Лагранжа

(λ, p) Rm+1 × PC1 ( , Rn ), λ ≠ 0

пишется функция Лагранжа:

t1

Λ(x( ), u( ), t0 , t1 ) = ∫( f (t, x, u) + p(t)(x −ϕ(t, x, u)))dt +

&

t0

+ l(t0 , x(t0 ), t1 , x(t1 )) ,

m

m

где f (t, x, u) = ∑λi

fi (t, x, u) ,

l = ∑λi li (t0 , x(t0 ), t1 , x(t1 )) .

i=0

i=0

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

а) стационарности по x − уравнений Эйлера для лагранжиана

L(t, x, x, u) = f (t, x, u) + p(x −ϕ(t, x, u)) :

&

&

d

ˆ

ˆ

ˆ

−

dt

Lx&

(t) + Lx (t) = 0 t

T −p&(t) + f x (t) − p(t)ϕˆ x (t)

= 0 ;

б) трансверсальности по x

ˆ

ˆ

ˆ

ˆ

ˆ

,

L&

(t

0

) = l

x(t0 )

p(t

0

) = l

x(t0 )

x

ˆ

ˆ

ˆ

ˆ

= −l

;

L&

(t ) = −l

x(t1 )

p(t )

x(t1 )

x

1

1

в) оптимальности по u:

&

&

min L(t, xˆ(t), xˆ(t), u(t))

= L(t, xˆ(t), xˆ(t), uˆ(t))

u U

min{f (t, xˆ(t), u) − p(t)ϕ(t, xˆ(t), u)}= fˆ (t) − p(t)ϕˆ(t) t T ;

u U

г) стационарности по подвижным концам (только для подвижных

ˆ

ˆ

ˆ

ˆ

ˆ

& ˆ

концов): Λt

0

= 0 − f (t0 ) + lt

+ lx(t ) xˆ(t0 ) = 0 ,

ˆ

ˆ ˆ

ˆ

ˆ

0

0

=

&

ˆ

Λ

t

0 f (t ) + l

t

+ l

x(t )

xˆ(t ) = 0 ;

1

1

1

1

1

д) дополняющей нежёсткости: λi Bi (ξˆ) = 0, i =

0, m′;

е) неотрицательности: λi ≥ 0,

i =

0, m′.

39

3. Найти ДУП, для которых выполняются необходимые условия экстремума. При этом удобно рассмотреть отдельно случаи λ0 = 0 и λ0 ≠

0. В последнем случае можно положить λ0 = 1 (или другой положительной константе).

4. Отыскать решение среди найденных ДУП или показать, что решений нет.

π

Пример 1. ∫x	2	sintdt → extr,			&		≤1, x(±π) = 0 .
					x
−π
Приводим задачу к виду (P):
π
		&	u [−1,1], x(±π) = 0 .
B(x) = ∫x sin t dt → extr, x = u,
−π

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

π

Λ = ∫(λ0 x sin t + p(x − u)) dt + λ1 x(−π) + λ2 x(π) .
&
−π
Необходимые условия:
			&
а) уравнение Эйлера для лагранжиана L = λ0 x sin t + p(x − u) ,
− p + λ0 sin t = 0 ;
&
б) условие трансверсальности L&	= (−1) j l	x(t j )	, j = 0,1,
x

p(−π) = λ1, p(π) = −λ2 ;

в) min{− pu}= −puˆ ;

u ≤1

г) λ0 ≥ 0 для min, λ0 ≤ 0 для max.

	а)			в)
λ0	= 0 p = const ≠ 0 (если 0, то λ1	= λ2	= 0 )	uˆ = ±1 = x& −
	− противоречие с x(±π) = 0 λ0	≠ 0 .
	а)		+ C .
	Пусть λ0 =1 p = sin t p = −cos t
	&
	Из в) следует, что uˆ = sgn p, т.е. x& = ±1 .
ние xˆ	Из центральной симметричности условий задачи следует, что реше-
	должно быть центрально симметричным. Это возможно только при
xˆ симметричной относительно оси y1. Следовательно,				p = −cos t и по-
этому
	40