Lý thuyết điều khiển nâng cao - Nguyễn Hoài Nam

 phương pháp Gauss/Seidel, u* được tìm thấy sau đúng r bước. u* thoả mãn điều kiện .
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:
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 .
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
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 
+ piTgk = 0 với 
+ Nghiệm tối ưu u* thoả mãn hệ phương trình Au* + b = 0.
Phương pháp này thích hợp cho hàm mục tiêu có dạng: với A 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.
Hệ số đổi hưởng được tính từ Q có dạng tổng quát: 
Nghiệm tối ưu tìm được không phải là nghiệm đúng.
Bài 6 Phương pháp Newton-Raphson
1. Nội dung của phương pháp.
Phương pháp tìm nghiệm tối ưu sử dụng đạo hàm bậc nhất và bậc hai của hàm mục tiêu nên phải giả thiết hàm mục tiêu Q(u) khả vi hai lần. Để giải hệ phương trình (*) bằng phương pháp giải tích, trước tiên hệ (*) được khai triển thành chuỗi Taylor tại uk thuộc lân cận nghiệm tối ưu u* và là nghiệm của (*) như sau:
tiếp theo, bỏ qua các đạo hàm bậc cao. Khi đó u* sẽ không phải là nghiệm đúng nữa mà chỉ là nghiệm gần đúng. Gọi nghiệm gần đúng này là là uk+1 u* , thay vào hệ phương trình trên ta có: 
Đặt H(u) = , .
Suy ra uk+1 = uk - H-1(uk)gk
2. Thuật toán Newton-Raphson.
Bước 1:
Cho đủ bé, chọn u0 bất kỳ.
Thực hiện các bước sau với k = 0, 1, 2, ...
Bước 2:
Tính .
Tính H(uk)
Bước 3:
Tính uk+1 = uk - H-1(uk)gk
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.
Ưu điểm:
Nếu hàm mục tiêu có dạng , phương pháp này sẽ cho đúng giá trị u* chỉ sau đúng một vòng tính.
Ví dụ:
Cho hàm mục tiêu Q = 3u12 + 4u22 + u1u2 với 
Bước 1:
Bước 2:
, 
Bước 3:
Bước 4:
||u1 - u0|| = 1 > quay về bước 2
k = 1.
Bước 2:
, 
Bước 3:
Bước 4:
||u2 - u1|| = 0 < chuyển sang bước 5
Bước 5:
Nghiệm tối ưu là u* = 
Bài 7 Cực tiểu hoá hàm một biến
1. Đặt vấn đề.
Trong các phương pháp đã học, để tìm u* ta phải tìm sk* bằng cách giải bài toán tối ưu hàm mục tiêu theo một hướng đã chọn.
sk* = argminQ(uk + skhk)
Đi tìm sk*, ta đã sử dụng phương pháp đạo hàm, tức là phải giải phương trình: .
Để có thể cài đặt thành thuật toán, chúng ta sẽ sử dụng một số phương pháp cơ bản để tìm sk* mà không dùng đạo hàm.
Ta đã biết Q(uk + skhk) là hàm số một biến, chỉ phục thuộc vào sk, cho nên ta chỉ xét bài toán cực tiểu hoá hàm một biến.
- Xét hàm số một biến Q(s), giả thiết hàm số Q(s) thoả mãn các điều kiện sau:
+ Q(s) đơn điệu giảm khi 0 < s < s*
+ Q(s) đơn điệu tăng khi s* < s
+ s* là nghiệm tối ưu.
+ Biết một điểm s = s1.
Đồ thị của hàm mục tiêu Q(s) có dạng như hình 1.
x
f(x)
O
x*
1
s
Q(s)
O
s*
s1
Hình 2
Hình 1
Chuẩn hoá hàm Q(s) với s = xs1, suy ra , như vậy . Khi đó hàm Q(s) = Q(xs1) = f(x), f(x) có độ thị như hình 2.
f(x) có một điểm cực tiểu duy nhất x* trong khoảng (0 1), f(1) > f(0). [0 1] được gọi là khoảng nghiệm.
Nguyên tắc tìm nghiệm x* là thu nhỏ khoảng nghiệm qua từng bước.
Trong khoảng [0 1] chọn 2 giá trị bất kỳ x1 và x2 sao cho: 0 < x1 < x2 < 1. Xét các trường hợp sau:
+ Nếu f(x1) < f(x2), khoảng nghiệm mới được chọn là [0 x2].
+ Nếu f(x1) f(x2), khoảng nghiệm mới được chọn là [x1 1].
 Vấn đề còn lại là chọn x1 và x2 như thế nào để tốc độ hội tụ là cao nhất, tức là tốc độ tìm thấy x* nhanh nhất.
2. Phương pháp nhát cắt vàng.
Xác định x1, x2 sao cho sau mỗi lần chia cả hai phía đều có tỉ lệ giữa khoảng lớn và toàn bộ khoảng nghiệm bằng tỉ lệ khoảng nhỏ chia cho khoảng lớn.
Xét khoảng nghiệm bất kỳ [xmin xmax]. Gọi d là độ dài là khoảng nghiệm d = xmax - xmin. Lấy hai điểm x1 < x2 đối xứng nhau qua điểm giữa của khoảng nghiệm [xmin xmax].
Độ dài khoảng lớn là: x2 - xmin và xmax - x1
Độ dài khoảng nhỏ là: xmax - x2 và x1 - xmin
Ta có biểu thức sau: , suy ra 
Giải phương trình trên được: , đặt 
Sau mỗi lần chia, khoảng nghiệm mới sẽ là [xmin x2] hoặc [x1 xmax], vì x1 và x2 được lấy đối xứng cho nên: x2 - xmin = xmax- x1, do đó khoảng nghiệm mới thu được bao giờ cũng là ad = 0,618d. Sau n lần thu nhỏ khoảng nghiệm mới sẽ có độ rộng là and = (0,618)nd.
Thuật toán tìm x* gần đúng theo phương pháp nhát cắt vàng.
Bước 1:
Gán xmin = 0; xmax = 1; > 0 đủ bé. Tính f(xmin) và f(xmax). 
Chọn x2 = 0,618, tính f(x2).
Bước 2:
Xác định x1 sao cho x1 đối xứng qua trung điểm của đoạn [xmin xmax].
Bước 3:
Tính f(x1), f(x2)
+ Nếu f(x1) < f(x2), gán xmax = x2
+ Nếu f(x1) f(x2), gán xmin = x1
Bước 4: Kiểm tra
Nếu |xmax -xminh| < chuyển sang bước 5
Nếu |xmax -xminh| > quay về bước 2
Bước 5:
Nghiệm tối ưu gần đúng x* có thể được chọn là một điểm bất kỳ thuộc khoảng [xmin xmax]
3. Phương pháp Fibonaci.
Xét dãy Fibonaci {1, 1, 2, 3, 5, 8, ..., }.
Gọi Fi là phần tử thứ i của dãy Fibonaci. Fi được xác định theo công thức sau: 
Fi = Fi-1 + Fi-2. Trong đó, hai phần tử đầu tiên của dãy F1 và F2 được xác định như sau: F1 = F2 = 1.
Nội dung của phương pháp Fibonaci.
ở bước thu nhỏ khoảng nghiệm thứ k, tỉ lệ giữa khoảng nhỏ với khoảng lớn là , với n là số bước thu nhỏ khoảng nghiệm được chọn từ trước.
Ta có:
Hệ số thu nhỏ khoảng nghiệm thứ nhất là: 
Hệ số thu nhỏ khoảng nghiệm thứ hai là: 
Hệ số thu nhỏ khoảng nghiệm thứ k là: 
Hệ số thu nhỏ khoảng nghiệm thứ n là: 
Sau n lần thu nhỏ khoảng nghiệm, khoảng nghiệm mới có hệ số thu nhỏ khoảng nghiệm so khoảng nghiệm ban đầu là: .
Thuật toán tìm nghiệm x* gần đúng theo phương pháp Fibonaci.
Bước 1:
Gán xmin = 0; xmax = 1; > 0 đủ bé. Tính f(xmin) và f(xmax). 
Tìm n thoả mãn điều kiện: 
Thực hiện các bước sau với k = 1, 2, 3, ..., n.
Bước 2:
Tính 
Xác định x1, x2 thoả mãn điều kiện:
+ x1 < x2 đối xứng qua trung điểm của đoạn [xmin xmax].
+ 
Bước 3:
Tính f(x1), f(x2).
+ Nếu f(x1) < f(x2), gán xmax = x2
+ Nếu f(x1) f(x2), gán xmin = x1
Gán k = k + 1
Kiểm tra: k > n chuyển sang bước 4, ngược lại quay về bước 2.
Bước 4: 
Nghiệm tối ưu gần đúng x* có thể được chọn là một điểm bất kỳ thuộc khoảng [xmin xmax]
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.
Cho mô hình hệ thống có dạng như sau: y = f(u) với 
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: 
Thực chất của bài toán tối ưu có giới hạn là tìm nghiệm tối ưu u* trong điều kiện u bị giới hạn bởi miền thích hợp U. 
2. Phương pháp đổi biến độc lập.
Sử dụng các phương pháp tìm nghiệm tối ưu u* của bài toán không có giới hạn U bằng cách dùng phép chuyển vị u = (v). Phép chuyển vị có thể là phi tuyến, thoả mãn điều kiện: thì 
Khi đó bài toán tìm:
thành bài toán tìm: 
Sau khi tìm được v*, ta sẽ tìm được u* = (v*).
Tuỳ theo miền giới hạn U mà ta có thể chọn một trong các phương pháp chuyển vị sau:
+ : Thay 
+ : Thay 
+ : Thay 
+ : Thay 
3. Phương pháp sử dụng hàm phạt và hàm chặn.
3.1 Hàm phạt.
Trong quá trình tìm từng bước nghiệm tối ưu, hàm phạt có được sử dụng để thông báo rằng tại thời điểm hiện tại, giá trị uk đã ra ngoài miền U. 
Việc thông báo của hàm phạt thường là bằng những giá trị rất lớn (một cách không bình thường) tại những điểm gần biên, bên trong hoặc bên ngoài.
Cho hàm mục tiêu Q(u). Tìm .
Thay Q(u) = Q(u) + S(u), với điều kiện:
S(u) = 0 nếu 
S(u) > 0 nếu 
 là một số dương đủ lớn.
áp dụng các phương pháp giải bài toán tối ưu không ràng buộc để tìm nghiệm , nghiệm tối ưu u* được tìm theo công thức sau:
3.2 Hàm chặn.
Trong quá trình tìm từng bước nghiệm tối ưu, hàm chặn được sử dụng để ngăn cản việc giá trị uk hiện tại có thể sẽ vượt ra ngoài miền U. Việc ngăn cản của hàm chặn thường là bằng những giá trị rất lớn (một cách không bình thường) tại những điểm gần biên, bên trong hoặc bên ngoài 
Thay Q(u) = Q(u) + S(u), với điều kiện:
S(u) = 0 nếu u cách xa biên.
S(u) = nếu u ở gần biên.
 là một số dương đủ lớn.
áp dụng các phương pháp giải bài toán tối ưu không ràng buộc để tìm nghiệm , nghiệm tối ưu u* được tìm theo công thức sau:
Tài liệu tham khảo
1. Điều khiển tối ưu và bền vững, Nguyễn Doãn Phước, Phan Xuân Minh, KH&KT, 2000.
2. Lý thuyết điều khiển tự động hiện đại, Nguyễn Thương Ngô, KH&KT, 1999
3. Hệ mờ- Mạng nơron và ứng dụng, Bùi Công Cường, Nguyễn Doãn Phước, KH&KT, 2001.
4. Lý thuyết điều khiển mờ, Phan Xuân Minh, Nguyễn Doãn Phước, KH&KT, 1999.
5. Nhận dạng hệ thống điều khiển, Nguyễn Doãn Phước, Phan Xuân Minh, KH&KT, 2001.
6. Qui hoạch toán học, Bùi Minh Trí, KH&KT, 1999.