Bài giảng Lý thuyết điều khiển nâng cao - Nguyễn Hoài Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
`Phô lôc
Néi dung
Trang
1
Phô lôc
3
Bµi 1Giíi thiÖu chung
1 §Þnh nghÜa
3
2 §iÒu kiÖn h¹n chÕ
3
3 Bµi to¸n ®iÒu khiÓn tèi -u
3.1 §iÒu khiÓn tèi -u tÜnh
3.2 §iÒu khiÓn tèi -u ®éng
Bµi 2 §iÒu khiÓn tèi -u tÜnh
1 M« t¶ to¸n häc.
4
4
5
6
6
2 BiÓu diÔn h×nh häc.
6
3 Gi¶ thiÕt cho lêi gi¶i.
7
3.1 Bµi to¸n tèi -u kh«ng cã giíi h¹n.
3.2 Bµi to¸n tèi -u cã giíi h¹n.
Bµi 3 Ph-¬ng ph¸p kh«ng dïng ®¹o hµm riªng
1. §Æt vÊn ®Ò.
7
8
10
10
10
13
13
13
14
15
15
16
16
17
17
19
2. Ph-¬ng ph¸p Gauss/Seidel.
3. C¸c ph-¬ng ph¸p kh¸c.
3.1 Ph-¬ng ph¸p Rosenbrock.
3.2 Ph-¬ng ph¸p ®¬n h×nh.
3.3 Ph-¬ng ph¸p h-íng t×m ngÉu nhiªn.
Bµi 4 Ph-¬ng ph¸p ®¹o hµm riªng
1. §Æt vÊn ®Ò
2. §¹o hµm riªng theo nghÜa hÑp.
3. Ph-¬ng ph¸p h¹ nhanh nhÊt.
Bµi 5 Ph-¬ng ph¸p h-íng liªn hîp
1. §Æt vÊn ®Ò.
2. ThuËt to¸n h-íng liªn hîp.
1
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
21
21
21
24
24
25
26
28
28
28
29
29
29
31
Bµi 6 Ph-¬ng ph¸p Newton/Raphson
1. Néi dung cña ph-¬ng ph¸p.
2. ThuËt to¸n Newton-Raphson.
Bµi 7 Cùc tiÓu ho¸ hµm mét biÕn
1. §Æt vÊn ®Ò.
2. Ph-¬ng ph¸p nh¸t c¾t vµng.
3. Ph-¬ng ph¸p Fibonaci.
Bµi 8 Bµi to¸n tèi -u cã giíi h¹n
1. Bµi to¸n tèi -u cã giíi h¹n
2. Ph-¬ng ph¸p ®æi biÕn ®éc lËp
3. Ph-¬ng ph¸p sö dông hµm ph¹t vµ hµm chÆn.
3.1 Hµm ph¹t.
3.2 Hµm chÆn.
Tµi liÖu tham kh¶o
Bµi 1 Giíi thiÖu chung
2
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
1. §Þnh nghÜa.
§iÒu khiÓn tèi -u lµ mét chuyªn ngµnh c¬ b¶n trong ®iÒu khiÓn tù ®éng, nã cã
vai trß x¸c ®Þnh vµ t¹o lËp nh÷ng luËt ®iÒu khiÓn cho hÖ thèng ®Ó hÖ thèng ®¹t
®-îc chØ tiªu vÒ tÝnh hiÖu qu¶ ®· ®-îc ®Þnh tr-íc d-íi d¹ng hµm môc tiªu Q.
Trong thùc tÕ tån t¹i c¸c bµi to¸n ®iÒu khiÓn tèi -u nh- sau:
- Bµi to¸n tèi -u cùc tiÓu:
+ X¸c ®Þnh tham sè cña m« h×nh sao cho b×nh ph-¬ng sai lÖch trung b×nh
gi÷a m« h×nh vµ ®èi t-îng ®¹t gi¸ trÞ nhá nhÊt, vÝ dô nh- huÊn luyÖn m¹ng n¬-
ron, nhËn d¹ng ®èi t-îng, ...
+ §iÒu khiÓn mét qu¸ tr×nh ®¹t chØ tiªu chÊt l-îng, kü thuËt cho tr-íc sao cho
tæn hao n¨ng l-îng lµ nhá nhÊt.
+ T¹o ra mét s¶n phÈm ®¹t chØ tiªu chÊt l-îng cho tr-íc nh-ng chi phÝ lµ nhá
nhÊt.
+ Bµi to¸n t×m ®-êng ®i ng¾n nhÊt gi÷a hai ®iÓm bÊt kú, vÝ dô nh- x¸c ®Þnh
quÜ ®¹o chuyÓn ®éng cña c¸nh tay r« bèt, ®-êng ®i thu r¸c, thu tiÒn ®iÖn, thu tiÒn
n-íc, ®i chµo hµng ...
- Bµi to¸n tèi -u cùc ®¹i.
+ T¹o ra s¶n phÈm víi chi phÝ cho tr-íc, nh-ng cã chÊt l-îng cao nhÊt.
+ Bµi to¸n t×m ®-êng c¨ng.
- Bµi to¸n tèi -u t¸c ®éng nhanh: Thêi gian x¶y ra qu¸ tr×nh lµ ng¾n nhÊt, vÝ dô
nh- ®iÒu khiÓn tªn löa.
2. §iÒu kiÖn h¹n chÕ.
Cho hÖ thèng nhiÒu ®Çu vµo vµ nhiÒu ®Çu ra, ®-îc m« t¶ bëi hÖ c¸c ph-¬ng
tr×nh nh- sau:
y = f(x,u)
®-îc gäi lµ m« h×nh to¸n häc
lµ c¸c ®Çu vµo
u = (u1 u2 . . . ur)T
x = (x1 x2 . . . xn)T
y = (y1 y2 . . . ym)T
lµ c¸c tr¹ng th¸i
lµ c¸c ®Çu ra
3
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Do bµi to¸n tèi -u ®-îc thùc hiÖn trªn m« h×nh hÖ thèng, cho nªn lêi gi¶i cña
bµi to¸n tèi -u phô thuéc vµo ®é chÝnh x¸c cña m« h×nh hÖ thèng.
Nh÷ng tÝn hiÖu kh«ng thÓ m« t¶ ®-îc trong c¸c ph-¬ng tr×nh trªn sÏ ®-îc coi
lµ nhiÔu t¸c ®éng.
3. Bµi to¸n ®iÒu khiÓn tèi -u.
Bµi to¸n tèi -u ®-îc x©y dùng dùa trªn c¸c gi¶ thiÕt sau:
+ Cã mét m« h×nh to¸n häc.
+ Kh«ng cã nhiÔu t¸c ®éng.
+ BiÕt c¸c ®iÒu kiÖn biªn cña m« h×nh nh- ®iÓm lµm viÖc, thêi gian lµm viÖc
cña hÖ thèng.
+ BiÕt miÒn gi¸ trÞ cho phÐp cña c¸c ®Çu vµo u.
+ BiÕt hµm môc tiªu Q m« t¶ tÝnh hiÖu qu¶ mµ hÖ thèng cÇn ®¹t ®-îc.
Môc ®Ých cña ®iÒu khiÓn tèi -u lµ t×m tÝn hiÖu tèi -u u* ®Ó hµm môc tiªu Q ®¹t
gi¸ trÞ cùc ®¹i hoÆc cùc tiÓu.
Víi nh÷ng gi¶ thiÕt nµy cã rÊt nhiÒu ph-¬ng ph¸p gi¶i bµi to¸n ®iÒu khiÓn tèi
-u kh¸c nhau. Trong ch-¬ng tr×nh cña m«n häc nµy, chóng ta sÏ nghiªn cøu c¸c
ph-¬ng ph¸p c¬ b¶n nhÊt cña lÜnh vùc ®iÒu khiÓn tèi -u, ®-îc chia thµnh hai
nhãm chÝnh nh- sau:
+ §iÒu khiÓn tèi -u tÜnh.
+ §iÒu khiÓn tèi -u ®éng.
3.1. §iÒu khiÓn tèi -u tÜnh.
Bµi to¸n ®iÒu khiÓn tèi -u tÜnh lµ bµi to¸n trong ®ã quan hÖ vµo, ra vµ biÕn
tr¹ng th¸i cña m« h×nh kh«ng phô thuéc vµo thêi gian. Gi¸ trÞ ®Çu ra t¹i mét thêi
®iÓm chØ phô thuéc vµo c¸c ®Çu ®Çu vµo vµ tr¹ng th¸i t¹i thêi ®iÓm ®ã.
M« h×nh hÖ thèng ®-îc cho nh- sau:
yk = fk(u1, u2, . . .ur), víi k = 1, 2, . . ., m, viÕt gän l¹i thµnh y = f(u). Hµm môc
tiªu nh- sau: Q = Q(u,y).
4
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Thay y = f(u) vµo hµm môc tiªu ®-îc: Q = Q(u,y) = Q(u,f(u)) = Q(u), nh-
vËy Q chØ phô thuéc vµo c¸c ®Çu vµo vµ ®Çu ra.
3.2. §iÒu khiÓn tèi -u ®éng.
Bµi to¸n ®iÒu khiÓn tèi -u ®éng lµ bµi to¸n trong ®ã m« h×nh to¸n häc cã Ýt
nhÊt mét ph-¬ng tr×nh vi ph©n.
dxi
fi (x,u)
dt
Cho m« h×nh hÖ thèng nh- sau: xi fi (x1, x2 ..., xn ,u1,u2 ...,ur ) víi i 1 n , viÕt
gän l¹i thµnh: x f (x,u) .
C¸c ®Çu ra cña hÖ thèng lµ y g(x,u) víi y (y1, y2 ,..., ym ) .
T
Hµm môc tiªu ®-îc ®Þnh nghÜa nh- sau: Q f (x,u)dt , trontg ®ã T lµ thêi
0
0
gian x¶y ra qu¸ tr×nh tèi -u.
Víi bµi to¸n ®iÒu khiÓn tèi -u tÜnh, ®©y chÝnh lµ bµi to¸n cùc trÞ víi nh÷ng
®iÒu kiÖn rµng buéc. Cã nhiÒu ph-¬ng ph¸p gi¶i bµi to¸n cùc trÞ, ë ®©y chóng ta
chØ nghiªn cøu c¸c ph-¬ng ph¸p phi tuyÕn:
+ C¸c ph-¬ng ph¸p kh«ng dïng ®¹o hµm riªng.
+ C¸c ph-¬ng ph¸p ®¹o hµm riªng.
+ Ph-¬ng ph¸p h-íng liªn hîp.
+ Ph-¬ng ph¸p Newton-Raphson.
Víi bµi to¸n ®iÒu khiÓn tèi -u ®éng, chØ nghiªn cøu c¸c ph-¬ng ph¸p sau:
+ Ph-¬ng ph¸p biÕn ph©n kinh ®iÓn.
+ Ph-¬ng ph¸p cùc ®¹i cña Pontrjagin
+ Ph-¬ng ph¸p qui ho¹ch ®éng cña Bellman
5
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Bµi 2 §iÒu khiÓn tèi -u tÜnh
1. M« t¶ to¸n häc.
M« h×nh hÖ thèng cã d¹ng nh- sau: y = f(u) víi u U
u = (u1 u2 . . . ur)T
y = (y1 y2 . . . ym)T
c¸c ®Çu vµo
c¸c ®Çu ra
U lµ miÒn thÝch hîp cña c¸c biÕn ®Çu vµo, ®-îc ®Þnh nghÜa nh- sau:
U
u (u1,u2 ...,uñ )T uk min uk uk max ;k 1 r
Hµm môc tiªu cã d¹ng nh- sau: Q = Q(u,y) = Q(u,f(u)) = Q(u)
Kh«ng mÊt tÝnh tæng qu¸t nÕu gi¶ thiÕt tiªu chuÈn tèi -u lµ: Q(u) min
Bµi to¸n ®iÒu khiÓn tèi -u tÜnh ®-îc ph¸t biÓu nh- sau: T×m tÝn hiÖu tèi -u u*
U , sao cho Q(u*) ®¹t gi¸ trÞ nhá nhÊt. Khi ®ã, ta cã Q(u* ) Q(u) u U
NÕu u* tho¶ m·n (1) víi mäi u thuéc U, th× u* ®-îc gäi lµ vÐc t¬ tèi -u toµn
côc.
NÕu u* tho¶ m·n (1) víi mäi u thuéc l©n cËn u*, th× u* ®-îc gäi lµ vÐc t¬ tèi -u
côc bé.
(1)
2. BiÓu diÔn h×nh häc.
XÐt hÖ thèng cã hai tÝn hiÖu ®Çu vµo u1 vµ u2. Hµm môc tiªu Q chØ phô thuéc
vµo u1 vµ u2, Q = Q(u1,u2).
Gi¶ thiÕt hµm môc tiªu Q cã ®å thÞ nh- h×nh 1.
*
u1
u2*
VËy ®iÓm tèi -u u* =
lµ ®iÓm thuéc mÆt ph¼ng (u1,u2), t¹i ®ã mÆt cong Q
ë ®iÓm thÊp nhÊt.
§iÓm A lµ ®iÓm tèi -u côc bé, ®iÓm B lµ ®iÓm yªn ngùa vµ ®iÓm C lµ ®iÓm tèi
-u toµn côc.
TËp hîp c¸c ®iÓm n»m trong mÆt ph¼ng (u1,u2), t¹i c¸c ®iÓm ®ã hµm môc tiªu
Q cã cïng gi¸ trÞ ®-îc gäi lµ ®-êng ®ång møc.
6
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Q
B
A
C
u1
O
®-êng ®ång møc
u2
H×nh 1
3. Gi¶ thiÕt cho lêi gi¶i.
3.1. Bµi to¸n tèi -u kh«ng cã giíi h¹n.
- NghiÖm u* cña bµi to¸n tèi -u kh«ng cã giíi h¹n lµ mét ®iÓm cùc trÞ. C¸c
Q
uk
®iÓm cùc trÞ tho¶ m·n hÖ ph-¬ng tr×nh vi ph©n
0
k 1,2...,r
hay
Q
u
Q Q
u1 u2
Q
ur
(
,
,...,
)T 0
Q
u
- T¹i mçi ®iÓm u cña mÆt cong Q tån t¹i vÐc t¬ ®¹o hµm riªng
, ký hiÖu lµ
Q
u
gradQ
, vÐc t¬ ®¹o hµm riªng gradQ cã c¸c tÝnh chÊt sau:
+ Cã ph-¬ng vu«ng gãc víi mÆt cong Q.
+ Cã h-íng chØ chiÒu t¨ng gi¸ trÞ cña c¸c ®-êng ®ång møc.
+ Cã ®é lín thÓ hiÖn tèc ®é t¨ng hay gi¶m gi¸ trÞ cña Q. Do ®ã t¹i ®iÓm cùc trÞ
cña mÆt cong Q ph¶i cã gradQ = 0 (*). HÖ ph-¬ng tr×nh nµy chØ lµ ®iÒu kiÖn cÇn
®Ó t×m nghiÖm tèi -u u*.
§Ó gi¶i hÖ ph-¬ng tr×nh (*) sÏ gÆp nh÷ng vÊn ®Ò sau:
7
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
+ HÖ ph-¬ng tr×nh (*) lµ hÖ phi tuyÕn, dÉn ®Õn viÖc gi¶i trùc tiÕp khã thùc
hiÖn ®-îc.
+ Cã nhiÒu ®iÓm u* tho¶ m·n hÖ ph-¬ng tr×nh (*) nh-ng kh«ng ph¶i lµ nghiÖm
tèi -u.
Thùc tÕ, c¸c ph-¬ng ph¸p gÇn ®óng ®-îc sö dông nhiÒu h¬n, theo thuËt to¸n
t×m nghiÖm tõng b-íc.
ThuËt to¸n t×m nghiÖm tõng b-íc.
+ B-íc 1:
Cho 0 bÐ tuú ý, chän u0 bÊt kú.
Thùc hiÖn c¸c b-íc sau víi k = 1, 2 ...
+ B-íc 2:
X¸c ®Þnh h-íng t×m vµ kho¶ng c¸ch b-íc t×m.
+ B-íc 3:
T×m uk theo h-íng t×m vµ kho¶ng c¸ch b-íc t×m.
+ B-íc 4:
KiÓm tra ®iÒu kiÖn.
NÕu || uk - uk-1 ||
chuyÓn sang b-íc 5.
NÕu || uk - uk-1 || >
quay vÒ b-íc 2.
+ B-íc 5:
NghiÖm tèi -u gÇn ®óng lµ u* = uk víi ®é chÝnh x¸c lµ
.
3.2. Bµi to¸n tèi -u cã giíi h¹n.
B¶n chÊt lµ t×m nghiÖm tèi -u u* gÇn ®óng cho bµi to¸n mµ u bÞ giíi h¹n bëi
miÒn thÝch hîp U. ThuËt to¸n t×m nghiÖm tõng b-íc vÒ c¬ b¶n còng gièng nh-
trªn, nh-ng cÇn ph¶i chó ý c¸c tr-êng hîp sau:
+ NÕu nghiÖm tèi -u u* kh«ng n»m trªn biªn cña U th× gradQ = 0 vÉn lµ ®iÒu
kiÖn cÇn ®Ó t×m u*.
+ NÕu trong miÒn thÝch hîp U kh«ng tån t¹i nghiÖm u* tho¶ m·n ®iÒu kiÖn
gradQ = 0, khi ®ã nghiÖm tèi -u u* n»m trªn biªn cña U vµ t¹i ®iÓm u* vÐc t¬ ®¹o
hµm riªng gradQ ph¶i cã h-íng vµo trong miÒn U.
8
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
ThuËt to¸n t×m nghiÖm tèi -u u* cho bµi to¸n tèi -u cã giíi h¹n.
+ B-íc 1:
Cho 0 bÐ tuú ý, chän u0 bÊt kú.
Thùc hiÖn c¸c b-íc sau víi k = 1, 2 ...
+ B-íc 2:
X¸c ®Þnh h-íng t×m vµ kho¶ng c¸ch b-íc t×m thÝch hîp ®Ó cho uk U
.
+ B-íc 3:
T×m uk theo h-íng t×m vµ kho¶ng c¸ch b-íc t×m.
+ B-íc 4:
KiÓm tra ®iÒu kiÖn.
NÕu || uk - uk-1 ||
chuyÓn sang b-íc 5.
NÕu || uk - uk-1 || >
quay vÒ b-íc 2.
+ B-íc 5:
NghiÖm tèi -u gÇn ®óng lµ u* = uk víi ®é chÝnh x¸c lµ
.
9
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Bµi 3 Ph-¬ng ph¸p kh«ng dïng ®¹o hµm riªng
1. §Æt vÊn ®Ò.
ViÖc t×m u* th«ng qua hÖ ph-¬ng tr×nh vi ph©n gradQ = 0 (*) kh«ng ph¶i lµ tèt
nhÊt cho mäi tr-êng hîp v× nh÷ng lý do sau:
+ HÖ ph-¬ng tr×nh (*) cã thÓ rÊt phøc t¹p.
+ Hµm môc tiªu Q cã thÓ tån t¹i nhiÒu ®iÓm cùc trÞ t¹i ®iÓm ®ã lu«n tho¶ m·n
hÖ ph-¬ng tr×nh (*).
+ Kh«ng ph¶i hµm môc tiªu nµo còng kh¶ vi.
ChÝnh v× nh÷ng lý do nµy, mµ cÇn ph¶i cã c¸c ph-¬ng ph¸p t×m nghiÖm tèi -u
u* mµ kh«ng dïng vÐc t¬ ®¹o hµm riªng (gradient).
2. Ph-¬ng ph¸p Gauss/ Seidel.
Cho m« h×nh hÖ thèng y = f(u).
Hµm môc tiªu ®-îc ®Þnh nghÜa lµ Q = Q(u).
T×m u* ®Ó cho Q ®¹t gi¸ trÞ nhá nhÊt, tøc lµ Q min
.
Gi¶ sö u* nghiÖm tèi -u tho¶ m·n Q min , ký hiÖu u* = argminQ.
Néi dung cña ph-¬ng ph¸p Gauss/Seidel.
+ H-íng t×m ®-îc chän song song víi c¸c trôc to¹ ®é ui víi i = 1, 2, ..., r. KÝ
hiÖu h-íng t×m ë b-íc thø k lµ hk.
+ Kho¶ng c¸ch b-íc t×m ë b-íc thø k ®-îc ký hiÖu lµ sk. sk ®-îc x¸c ®Þnh nh-
sau: sk* argminQ(uk sk hk )
ThuËt to¸n t×m nghiÖm cña Gauss/Seidel.
+ B-íc 1:
Cho 0 bÐ tuú ý, chän u0 bÊt kú.
Thùc hiÖn c¸c b-íc sau víi k = 0, 1, 2 ...
+ B-íc 2:
10
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
0
0
.
- X¸c ®Þnh h-íng t×m hk: hk
, hk lµ vÐc t¬ cã r hµng, chØ cã hµng thø k + 1
1
.
0
cã gi¸ trÞ b»ng 1, c¸c hµng kh¸c ®Òu b»ng kh«ng.
- X¸c ®Þnh kho¶ng c¸ch b-íc t×m sk: sk ®-îc x¸c ®Þnh sao cho hµm môc tiªu
*
®¹t gi¸ trÞ nhá nhÊt trªn h-íng t×m hk. sk = argminQ(uk + skhk)
+ B-íc 3:
*
uk+1 = uk + sk hk
+ B-íc 4: KiÓm tra ®iÒu kiÖn.
NÕu || uk+1 - uk ||
chuyÓn sang b-íc 5.
NÕu || uk+1 - uk || >
quay vÒ b-íc 2.
+ B-íc 5:
NghiÖm tèi -u gÇn ®óng lµ u* = uk+1
VÝ dô: Cho hµm môc tiªu Q = u12 2u22 3, t×m u* ®Ó cho Q min
1
B-íc 1: Cho 103 , chän u0
1
k = 0.
1
B-íc 2: Chän h0
0
1
1
1 s
0
u1 u0 s0 h0
s0
1
0
1
Q(u1 )
s0
Q(u1) = (1 s0 )2 2 3 , ta cã
2(1 s0 ) 0 , suy ra s0 = -1
*
VËy s0 = argminQ(u1) = -1
B-íc 3:
1
1
1 s 0
0
u1 u0 s0 h0
s0
1
0
1
1
B-íc 4:
||u1 - u0|| = 1 >
quay vÒ b-íc 2
11
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
k =1.
0
B-íc 2: Chän h0
1
0
0
0
u2 u1 s1 h1
s1
1
1
1 s1
Q(u2 )
s1
Q(u2) = 0 2(1 s1 )2 3, ta cã
4(1 s1 ) 0, suy ra s1 = -1
*
VËy s1 = argminQ(u2) = -1
B-íc 3:
0
0
u2
1 s1*
0
B-íc 4:
||u2 - u1|| = 1 >
k = 2.
quay vÒ b-íc 2
B-íc 2:
1
Chän h2
0
0
1
s
2
u3 u2 s2 h2
s2
1
0
1
Q(u3 )
s2
Q(u3) = s22 2.0 3, ta cã
2s2 0 , suy ra s2 = 0
*
VËy s2 = argminQ(u3) = 0
B-íc 3:
*
0
s2
u
2
0
0
B-íc 4:
||u3 - u2|| = 0 <
chuyÓn sang b-íc 5
B-íc 5:
0
u* = u3 =
0
Sau hai vßng tÝnh ta ®· t×m ®-îc nghiÖm tèi -u u* = u2.
12
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
-u ®iÓm cña ph-¬ng ph¸p lµ: nÕu hÖ thèng cã r ®Çu vµo, hµm môc tiªu cã
d¹ng chÝnh ph-¬ng th× nghiÖm tèi -u u* sÏ ®-îc t×m thÊy sau ®óng r vßng.
3. C¸c ph-¬ng ph¸p kh¸c.
3.1 Ph-¬ng ph¸p Rosenbrock.
HÖ trôc to¹ ®é ®-îc xoay sau mçi lÇn t×m ®-îc nghiÖm uk tõ uk-1 sao cho mét
trôc to¹ ®é cña hÖ míi trïng víi h-íng cña vÐc t¬ uk - uk-1.
¦u ®iÓm cña ph-¬ng ph¸p lµ tèc ®é héi tô cao h¬n ph-¬ng ph¸p Gauss/Seidel
khi hµm môc tiªu phøc t¹p (c¸c ®-êng ®ång møc kh«ng ®èi xøng, hµm môc tiªu
kh«ng cã d¹ng chÝnh ph-¬ng).
3.2 Ph-¬ng ph¸p ®¬n h×nh.
TÝnh gi¸ trÞ hµm môc tiªu t¹i r +1 ®Ønh cña mét h×nh ®a diÖn
sè biÕn ®Çu vµo cña hÖ thèng.
. Trong ®ã r lµ
Sau ®ã ®a diÖn
®a diÖn míi ' thu ®-îc cã gi¸ trÞ hµm môc tiªu t¹i c¸c ®Ønh kh«ng lín h¬n c¸c
gi¸ trÞ cña hµm môc tiªu t¹i c¸c ®Ønh cña t-¬ng øng.
®-îc lÊy ®èi xøng víi mét c¹nh (hoÆc mÆt) cña nã, sao cho
PhÐp lÊy ®èi xøng vµ tÝnh gi¸ trÞ hµm môc tiªu Q sÏ ®-îc tiÕp tôc nÕu ®a diÖn
míi ' vÉn n»m trong miÒn thÝch hîp U vµ gi¸ trÞ hµm môc tiªu Q t¹i c¸c ®Ønh
cña ' kh«ng lín h¬n so víi gi¸ trÞ hµm môc tiªu Q t¹i c¸c ®Ønh cña
.
VÝ dô:
Víi hÖ thèng cã hai ®Çu vµo r = 2, ®a
u2
diÖn
lµ mét tam gi¸c. Qu¸ tr×nh t×m
nghiÖm tèi -u ®-îc minh ho¹ nh- h×nh 2.
ë ®©y ®Ó ®¬n gi¶n ta chän tam gi¸c
lµ mét tam gi¸ vu«ng c©n. ChiÒu mòi tªn
c¸c ®-êng ®ång møc
lµ chiÒu t×m nghiÖm tèi -u.
u1
O
H×nh 2
13
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
3.3 Ph-¬ng ph¸p h-íng t×m ngÉu nhiªn.
H-íng t×m ngÉu nhiªn ®-îc lÊy tõ tËp ngÉu nhiªn cã ph©n bè chuÈn, ®Òu c¸c
h-íng trong kh«ng gian.
uk ®-îc t×m theo h-íng ®· ®-îc chän ngÉu nhiªn ë b-íc k.
NÕu Q(uk) < Q(uk-1) th× h-íng t×m ®ã vÉn ®-îc dïng ®Ó t×m uk+1 tiÕp theo, nÕu
kh«ng th× chän theo h-íng ng-îc l¹i.
14
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Bµi 4 Ph-¬ng ph¸p ®¹o hµm riªng
1. §Æt vÊn ®Ò.
Theo ph-¬ng ph¸p nµy, h-íng t×m ®-îc x¸c ®Þnh theo vÐc t¬ ®¹o hµm riªng
cña hµm môc tiªu Q theo c¸c biÕn ®Çu vµo gradQ.
VÊn ®Ò ®Æt ra lµ tÝnh vÐc t¬ ®¹o hµm riªng gradQ nh- thÕ nµo? Tuú thuéc vµo
hµm môc tiªu Q ®-îc cho d-íi d¹ng c«ng thøc, b¶ng tra hay thuËt to¸n mµ ta cã
ph-¬ng ph¸p tÝnh gradQ kh¸c nhau.
Khi hµm gradQ cho d-íi d¹ng c«ng thøc, tÝnh gradQ theo ph-¬ng ph¸p gi¶i
tÝch.
Q
u
Q
1
gradQ(u )
lÊy ®¹o hµm riªng theo tõng biÕn ®Çu vµo ui, sau ®ã
k
u
2
:
Q
u
r
u uk
thay gi¸ trÞ u = uk vµo.
NÕu hµm môc tiªu Q cho d-íi d¹ng b¶ng tra hoÆc thuËt to¸n th× cã c¸c
ph-¬ng ph¸p tÝnh gradQ nh- sau:
+ Ph-¬ng ph¸p thø nhÊt:
Q
ui
1
Q(k u1,k u2 ,...,k ui ui ,...,k ur ) Q(k u1,k u2 ,...,k ui ,...,k ur )
ui
u uk
víi i = 1, 2, ..., r.
+ Ph-¬ng ph¸p thø hai:
Q
ui
1
Q(k u1,k u2 ,...,k ui ui ,...,k ur ) Q(k u1,k u2 ,...,k ui ui ,...,k ur )
2ui
u uk
víi i = 1, 2, ..., r.
15
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
2. Ph-¬ng ph¸p ®¹o hµm riªng theo nghÜa hÑp.
H-íng t×m cã h-íng ng-îc l¹i so víi h-íng cña vÐc t¬ ®¹o hµm riªng gradQ
hk = - gradQ(uk).
Kho¶ng c¸ch b-íc t×m tØ lÖ víi ®é lín cña gradQ(uk). Gi¸ trÞ uk+1 ®-îc tÝnh
theo c«ng thøc sau: uk+1 = uk - s.gradQ(uk)
Kho¶ng c¸ch b-íc t×m s cã ¶nh h-ëng rÊt lín ®Õn tèc ®é héi tô cña ph-¬ng
ph¸p.
+ NÕu s nhá, sè b-íc tÝnh lín, sè lÇn tÝnh gradQ nhiÒu.
+ NÕu s lín, chuçi gi¸ trÞ {uk} ph©n kú.
V× t¹i ®iÓm cùc trÞ gradQ(u) = 0 nªn ph-¬ng ph¸p sÏ cho mét d·y {uk} héi tô
®Õn mét ®iÓm cùc trÞ. Khi Q kh«ng cã ®iÓm yªn ngùa, ®iÓm cùc trÞ ®ã cã thÓ lµ
côc bé hoÆc toµn côc.
Muèn t×m nghiÖm tèi -u u* toµn côc, nªn ¸p dông ph-¬ng ph¸p cho nhiÒu
®iÓm ban ®Çu u0 kh¸c nhau.
3. Ph-¬ng ph¸p h¹ nhanh nhÊt.
B¶n chÊt cña ph-¬ng ph¸p lµ ph-¬ng ph¸p dïng vÐc t¬ ®¹o hµm riªng cã
h-íng t×m kh«ng cè ®Þnh theo gradQ tõ ®Çu ®Õn cuèi. H-íng t×m ®-îc x¸c ®Þnh
nh- sau: h0 = -gradQ(u0).
Kho¶ng c¸ch b-íc t×m ®-îc x¸c ®Þnh nh- sau: s0* argminQ(u0 s0 h0 )
*
suy ra u1 = u0 + s0 h0.
Víi k = 1, 2, ...
T
Chän hk sao cho hk hk-1 = 0.
*
Chuçi gi¸ trÞ {uk } cã tèc ®é héi tô lín khi c¸ch xa u*, cµng gÇn u* th× ®é héi
tô cµng gi¶m.
ThuËt to¸n h¹ nhanh nhÊt.
B-íc 1:
Cho 0 ®ñ bÐ, chän u0 bÊt kú.
h0 = -gradQ(u0)
16
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
s0* argminQ(u0 s0 h0 )
*
u1 = u0 + s0 h0
Thùc hiÖn c¸c b-íc sau víi k = 1, 2, 3, ...
B-íc 2:
T
T×m h-íng hk sao cho: hk hk-1 = 0
*
*
T×m sk nh- sau: sk = argminQ(uk + skhk)
B-íc 3:
*
TÝnh uk+1 = uk + sk hk.
B-íc 4: KiÓm tra ®iÒu kiÖn.
NÕu || uk+1 - uk ||
chuyÓn sang b-íc 5.
NÕu || uk+1 - uk || >
quay vÒ b-íc 2.
B-íc 5: KÕt thóc
NghiÖm tèi -u gÇn ®óng u* = uk+1 víi ®é chÝnh x¸c lµ
.
.
17
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
Bµi 5 Ph-¬ng ph¸p h-íng liªn hîp
1. §Æt vÊn ®Ò.
1
XÐt hµm môc tiªu cã d¹ng chÝnh ph-¬ng: Q uT Au bT u
2
A lµ ma trËn ®¬n vÞ.
u = (u1 u2 . . . ur)T
b = (b1 b2 . . . br)T
Theo ph-¬ng ph¸p Gauss/Seidel, u* ®-îc t×m thÊy sau ®óng r b-íc. u* tho¶
Q
u
m·n ®iÒu kiÖn
0 Au b 0 u* Ab
.
Theo ph-¬ng ph¸p Gauss/Seidel, c¸c h-íng t×m song song víi c¸c trôc to¹ ®é,
xuÊt ph¸t tõ ®©y ®Ó ®i tíi ph-¬ng ph¸p h-íng liªn hîp.
ý t-ëng cña ph-¬ng ph¸p lµ: h-íng t×m ë vßng thø k ®-îc t×m theo h-íng t×m
T
ë vßng thø k - 1, sao cho: hk-1 hk = 0.
XÐt hµm môc tiªu bÊy kú, trong ®ã ma trËn A kh«ng ph¶i lµ ma trËn ®¬n vÞ.
Nh- vËy ta ph¶i chuyÓn hÖ trôc to¹ ®é ®Ó ®-a A vÒ d¹ng ma trËn ®¬n vÞ. Khi ®ã
h-íng t×m hk sÏ chuyÓn thµnh pk. Coi A lµ mét to¸n tö tuyÕn tÝnh biÕn ®æi hÖ trôc
to¹ ®é, qua phÐp biÕn ®æi nµy hk chuyÓn thµnh pk. Khi ®ã pk ph¶i cã tÝnh chÊt
sau:
pk-1Apk = 0
C¸c h-íng t×m pk víi k = 1, 2, ...,r ®-îc x¸c ®Þnh nhê c«ng thøc sau:
pT Avk
k1
i
p v
p
i
pT Ap
k
k
i1
i
i
vi víi i = 1, 2, ...,r lµ mét c¬ së cña kh«ng gian Rr, cã nghÜa lµ c¸c vÐc t¬ v1, v2,
... vr ®éc lËp tuyÕn tÝnh víi nhau.
H-íng t×m ban ®Çu p0 cã thÓ ®-îc x¸c ®Þnh nhê vÐc t¬ gradQ hoÆc ®-îc x¸c
®Þnh ngÉu nhiªn. Däc theo h-íng t×m pk, uk ®-îc t×m sao cho Q(uk) ®¹t gi¸ trÞ
nhá nhÊt.
*
sk = argminQ(uk-1 + skpk)
18
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
*
uk = uk-1 + sk pk
2. ThuËt to¸n h-íng liªn hîp.
Chän c¸c vÐc t¬ c¬ së vi nh- sau: vk = -gk-1 víi k = 1, 2, ..., r. Trong ®ã gk =
gradQ(uk) = Auk + b.
pk+1 = -gk + ekpk víi k = 0, 1, ..., r-1. Trong ®ã p0 = -g0, hÖ sè ®æi h-íng
pT Ag
k
k
k
ek
.
pT Ap
k
Däc theo h-íng t×m pk+1, uk+1 ®-îc t×m theo tõ uk theo nguyªn t¾c hµm Q ®¹t
gi¸ trÞ nhá nhÊt.
sk+1* = argminQ(uk + sk+1pk+1)
*
uk+1 = uk + sk+1 pk+1
ThuËt to¸n.
B-íc 1:
Chän u0, e0 = 0.
p0 = -g0 = -(Au0 + b)
Thùc hiÖn c¸c b-íc sau víi k = 1, 2, ..., r-1.
B-íc 2:
gk = gradQ(uk) = Auk + b
pT Ag
k
k
k
ek
pT Ap
k
pk+1 = -gk + ekpk
sk+1* = argminQ(uk + sk+1pk+1)
B-íc 3:
*
uk+1 = uk + sk+1 pk+1
B-íc 4:
u* = ur
Ph-¬ng ph¸p h-íng liªn hîp cã nh÷ng tÝnh chÊt sau:
+ giTgj = 0 víi i j
+ piTgk = 0 víi i k
19
NguyÔn Hoµi Nam
Lý thuyÕt ®iÒu khiÓn n©ng cao
10 May 2022
+ NghiÖm tèi -u u* tho¶ m·n hÖ ph-¬ng tr×nh Au* + b = 0.
1
Ph-¬ng ph¸p nµy thÝch hîp cho hµm môc tiªu cã d¹ng: Q uT Au bT u víi A
2
lµ ma trËn x¸c ®Þnh d-¬ng.
Khi hµm môc tiªu cã d¹ng bÊt kú, kh«ng gièng víi d¹ng ë trªn ta cã thÓ dung
ph-¬ng ph¸p nµy ®Ó t×m u*, tuy nhiªn cÇn ph¶i thay ®æi.
2
g
k
HÖ sè ®æi h-ëng ®-îc tÝnh tõ Q cã d¹ng tæng qu¸t: ek
2
g
k1
NghiÖm tèi -u t×m ®-îc kh«ng ph¶i lµ nghiÖm ®óng.
20
NguyÔn Hoµi Nam
Tải về để xem bản đầy đủ
31 trang
24400
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết điều khiển nâng cao - Nguyễn Hoài Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_ly_thuyet_dieu_khien_nang_cao_nguyen_hoai_nam.doc
