Xem mẫu
- Lý thuyết điều khiển nâng cao
21 December 2009
Phụ lục
Nội dung Trang
Phụ lục 1
Bài 1Giới thiệu chung 3
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 4
3.1 Điều khiển tối ưu tĩnh 4
3.2 Điều khiển tối ưu động 5
Bài 2 Điều khiển tối ưu tĩnh 6
1 Mô tả toán học. 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. 7
3.2 Bài toán tối ưu có giới hạn. 8
Bài 3 Phương pháp không dùng đạo hàm riêng 10
1. Đặt vấn đề. 10
2. Phương pháp Gauss/Seidel. 10
3. Các phương pháp khác. 13
3.1 Phương pháp Rosenbrock. 13
3.2 Phương pháp đơn hình. 13
3.3 Phương pháp hướng tìm ngẫu nhiên. 14
Bài 4 Phương pháp đạo hàm riêng 15
1. Đặt vấn đề 15
2. Đạo hàm riêng theo nghĩa hẹp. 16
3. Phương pháp hạ nhanh nhất. 16
Bài 5 Phương pháp hướng liên hợp 17
1. Đặt vấn đề. 17
2. Thuật toán hướng liên hợp. 19
Bài 6 Phương pháp Newton/Raphson 21
1. Nội dung của phương pháp. 21
2. Thuật toán Newton-Raphson. 21
Bài 7 Cực tiểu hoá hàm một biến 24
1. Đặt vấn đề. 24
2. Phương pháp nhát cắt vàng. 25
3. Phương pháp Fibonaci. 26
Bài 8 Bài toán tối ưu có giới hạn 28
1. Bài toán tối ưu có giới hạn 28
2. Phương pháp đổi biến độc lập 28
3. Phương pháp sử dụng hàm phạt và hàm chặn. 29
3.1 Hàm phạt. 29
3.2 Hàm chặn. 29
Tài liệu tham khảo 31
Nguyễn Hoài Nam 1
- Bài 1 Giới thiệu chung
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
2
- Lý thuyết điều khiển nâng cao
21 December 2009
đị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
u = (u1 u2 . . . ur)T là các đầu vào
x = (x1 x2 . . . xn)T là các trạng thái
y = (y1 y2 . . . ym)T là các đầu ra
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.
Nguyễn Hoài Nam 3
- 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).
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
= f i ( x, u )
dt
Cho mô hình hệ thống như sau: xi = f i ( x1 , x 2 ..., x n , u1 , u 2 ..., u r ) 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 , y 2 ,..., y m ) .
T
Q = ∫ f 0 ( x, u )dt
Hàm mục tiêu được định nghĩa như sau: 0 , trontg đó T là thời
4
- Lý thuyết điều khiển nâng cao
21 December 2009
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
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 các đầu vào
y = (y1 y2 . . . ym)T 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 , u 2 ..., u ñ ) T u k min ≤ u k ≤ u k 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
Nguyễn Hoài Nam 5
- A Q B ???ng ??ng m?c
C u1
O
u* ∈ U , sao cho Q(u*) đạt giá trị nhỏ nhất. Khi đó,
*
ta có Q(u ) ≤ Q(u ) ∀u ∈ U (1)
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ộ.
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
*
*
Vậy điểm tối ưu u * = u 2 là điểm thuộc mặt phẳng (u ,u ), tại đó mặt
1 2
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
- u2 H?nh 1
Lý thuyết điều khiển nâng cao
21 December 2009
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
=0 k = 1,2..., r
điểm cực trị thoả mãn hệ phương trình vi phân ∂u k hay
∂Q ∂Q ∂Q ∂Q T
=( , ,..., ) =0
∂u ∂u1 ∂u 2 ∂u r
∂Q
- 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 ∂u , ký hiệu
∂Q
gradQ =
là ∂u , 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:
+ 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.
Nguyễn Hoài Nam 7
- + 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.
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:
8
- Lý thuyết điều khiển nâng cao
21 December 2009
Xác định hướng tìm và khoảng cách bước tìm thích hợp để cho u k ∈ 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à ε .
Bài 3 Phương pháp không dùng đạo hàm riêng
1. Đặt vấn đề.
Nguyễn Hoài Nam 9
- 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: s k = arg min Q(u k + s k h k )
*
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
- Lý thuyết điều khiển nâng cao
21 December 2009
0
0
.
h k = 1
.
0
- Xác định hướng tìm hk: , h là véc tơ có r hàng, chỉ có hàng thứ k +
k
1 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 = u1 + 2u 2 − 3 , tìm u* để cho Q → min
2 2
1
u0 =
Bước 1: Cho ε = 10 , chọn
−3
1
k = 0.
1
h0 =
Bước 2: Chọn 0
1 1 1 + s 0
u 1 = u 0 + s0 h 0 = + s0 =
1 0 1
∂Q(u 1 )
= 2(1 + s 0 ) = 0
(1 + s 0 ) + 2 − 3 , ta có ∂s 0
2
Q(u1) = , suy ra s0 = -1
Vậy s0* = argminQ(u1) = -1
Bước 3:
Nguyễn Hoài Nam 11
- 1 1 1 + s 0 0
u 1 = u 0 + s0 h 0 = + s0 = =
1 0 1 1
Bước 4:
||u1 - u0|| = 1 > ε quay về bước 2
k =1.
0
h0 =
Bước 2: Chọn 1
0 0 0
u 2 = u 1 + s1 h1 = + s1 =
1 1 1 + s1
∂Q(u 2 )
= 4(1 + s1 ) = 0
Q(u2) = 0 + 2(1 + s1 ) − 3 , ta có ∂s1
2
, 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 > ε quay về bước 2
k = 2.
Bước 2:
1
h2 =
Chọn 0
0 1 s
u 3 = u 2 + s2 h 2 = + s2 = 2
1 0 1
∂Q(u 3 )
= 2s 2 = 0
Q(u3) = s + 2.0 − 3 , ta có ∂s 2
2
2 , suy ra s2 = 0
Vậy s2* = argminQ(u3) = 0
Bước 3:
12
- Lý thuyết điều khiển nâng cao
21 December 2009
s 2 0
*
u2 = =
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.
ư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 ∆ . Trong đó r
là số biến đầu vào của hệ thống.
Sau đó đa diện ∆ được lấy đối xứng với một cạnh (hoặc mặt) của nó, sao
cho đ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.
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
Nguyễn Hoài Nam 13
- ∆.
Ví dụ:
Với hệ thống có hai đầu vào r = 2, đa
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
là chiều tìm nghiệm tối ưu.
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
- Lý thuyết điều khiển nâng cao
21 December 2009
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
1
∂Q
gradQ (u k ) = ∂u 2
:
∂Q
∂u r
u = uk
lấy đạo hàm riêng theo từng biến đầu vào ui, sau đó
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
Nguyễn Hoài Nam 15
- phương pháp tính gradQ như sau:
+ Phương pháp thứ nhất:
∂Q
∂u i
=
1
∆u i
[
Q( k u1 , k u 2 ,..., k u i + ∆u i ,..., k u r ) − Q( k u1 , k u 2 ,..., k u i ,..., k u r ) ]
u = uk
với i = 1, 2, ..., r.
+ Phương pháp thứ hai:
∂Q
∂u i
=
1
2∆u i
[
Q( k u1 , k u 2 ,..., k u i + ∆u i ,..., k u r ) − Q( k u1 , k u 2 ,..., k u i − ∆u i ,..., k u r ) ]
u = uk
với i = 1, 2, ..., r.
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.
16
- Lý thuyết điều khiển nâng cao
21 December 2009
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: s 0 = arg min Q(u 0 + s 0 h 0 )
*
suy ra u1 = u0 + s0*h0.
Với k = 1, 2, ...
Chọn hk sao cho hkThk-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)
s 0 = arg min Q(u 0 + s 0 h 0 )
*
u1 = u0 + s0*h0
Thực hiện các bước sau với k = 1, 2, 3, ...
Bước 2:
Tìm hướng hk sao cho: hkThk-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.
Nguyễn Hoài Nam 17
- 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à ε .
.
Bài 5 Phương pháp hướng liên hợp
1. Đặt vấn đề.
1 T T
Q= u Au + b u
Xét hàm mục tiêu có dạng chính phương: 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ả
18
- Lý thuyết điều khiển nâng cao
21 December 2009
∂Q
=0 *
mãn điều kiện ∂u ⇔ 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 ở vòng thứ k - 1, sao cho: hk-1Thk = 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:
T
k −1 p i Av k
pk = vk − ∑ T
pi
i =1 pi A pi
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)
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
Nguyễn Hoài Nam 19
- T
p k Ag k
ek = T
pk A pk
.
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
T
p k Ag k
ek = T
pk A pk
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
+ Nghiệm tối ưu u* thoả mãn hệ phương trình Au* + b = 0.
20
nguon tai.lieu . vn
