- 6 1.4 Điều kiện tối ƣu bài toán không ràng buộc. - 17 2.1 Phƣơng pháp không gian hạt nhân (Null Space) giải bài toán quy hoạch toàn phƣơng với ràng buộc đẳng thức tuyến tính. - 17 2.1.1 Phát biểu bài toán. - 21 2.2 Phƣơng pháp tập hoạt động (Active Set) giải bài toán quy hoạch toàn phƣơng với ràng buộc bất đẳng thức tuyến tính. - 23 2.2.1 Phát biểu bài toán. - 57 4.2 Kết quả của một số bài toán cụ thể. - Bài toán quy hoạch phi tuyến đóng vai trò quan trọng trong lý thuyết điều khiển tối ƣu. - Phƣơng pháp SQP (Sequential Quadratic Programming) là một trong những phƣơng pháp thông dụng, hiệu quả để giải bài toán quy hoạch phi tuyến và không thể thiếu trong các thƣ viện tối ƣu lớn nhƣ NAG, LANCELOT… Ý tƣởng của phƣơng pháp là tách bài toán phi tuyến ban đầu thành một dãy các bài toán quy hoạch toàn phƣơng, các bài toán con này đƣợc giải quyết bằng phƣơng pháp Không gian hạt nhân (cho bài toán có ràng buộc đẳng thức) hoặc bằng phƣơng pháp Tập hoạt động (cho bài toán có ràng buộc bất đẳng thức). - Chƣơng II: Tìm hiểu phƣơng pháp giải quyết bài toán con là bài toán quy hoạch toàn phƣơng với các ràng buộc tuyến tính, cụ thể là phƣơng pháp Không gian hạt nhân (Null space) giải các bài toán với ràng buộc đẳng thức và Tập hoạt động (Active set) giải quyết các bài toán với ràng buộc bất đẳng thức. - Chƣơng IV: Trình bày các kết quả số đạt đƣợc bao gồm: lập trình thuật toán SQP, lập trình các bài toán con sử dụng các phƣơng pháp Không gian hạt nhân và phƣơng pháp Tập hoạt động. - Điều kiện tối ưu của bài toán không ràng buộc Xét bài toán tối ƣu sau: trong đó là một hàm số trong lớp . - Định lý Karush-Kuhn-Tucker (KKT) Xét bài toán quy hoạch phi tuyến: với điều kiện. - Giả sử là điểm cực tiểu địa phƣơng của bài toán. - Phương pháp hướng giảm Xét bài toán quy hoạch không ràng buộc trong đó là hàm phi tuyến, khả vi trên . - Ý tƣởng cơ bản của phƣơng pháp hƣớng giảm để giải bài toán với hàm mục tiêu là: Xuất phát từ một điểm bất kỳ , ta xây dựng một dãy điểm. - Nếu là hàm lồi, thì điểm chính là nghiệm cực tiểu toàn cục của bài toán. - Ta xét bài toán tối ƣu không ràng buộc: Theo giả thiết, tại mọi điểm x k cho trƣớc thì giá trị của và véc tơ gradient là hoàn toàn xác định. - Vậy với đủ bé, ta có thể xấp xỉ theo công thức Taylor: Ta tìm là nghiệm của bài toán xấp xỉ sau: 13 Áp dụng điều kiện tối ƣu bậc 1 đối với hàm số theo biến ta có. - Chƣơng 1 trình bày các kiến thức cơ sở là nền tảng cần thiết để tìm hiểu các phƣơng pháp tối ƣu phi tuyến nhƣ các điều kiện tối ƣu cho bài toán toán tối ƣu có ràng buộc và bài toán tối ƣu không có ràng buộc, phƣơng pháp hƣớng giảm, phƣơng pháp Newton, phƣơng pháp quasi-Newton. - Các phương pháp giải bài toán quy hoạch toàn phương có ràng buộc Chƣơng 2 trình bày phƣơng pháp Không gian hạt nhân giải bài toán quy hoạch toàn phƣơng với ràng buộc đẳng thức và phƣơng pháp Tập hoạt động giải bài toán quy hoạch toàn phƣơng với ràng buộc bất đẳng thức. - 2.1 Phương pháp Không gian hạt nhân (Null Space) giải bài toán quy hoạch toàn phương với ràng buộc đẳng thức tuyến tính 2.1.1 Phát biểu bài toán Xét bài toán quy hoạch toàn phƣơng: trong đó G là ma trận đối xứng xác định không âm,A là ma trận cấp mn(mn), ran k Am. - Ta tìm thuật toán xác định nghiệm tối ƣu của bài toán (Q). - 2.1.2 Ý tưởng Hàm Lagrange tƣơng ứng với bài toán (Q) là: 1( ).2T T TL x G x c x A x b Vì bài toán (Q) có hàm mục tiêu là hàm lồi với ràng buộc afin nên x là nghiệm của bài toán (Q) khi và chỉ khi là điểm KKT, tức là tồn tại thoả mãn điều kiện KKT: 18 00,TxL G x c AL A x b hay 0.TG x c AA x b (2.1) Giả sử x là điểm gần với của bài toán (Q). - Đặt ,d x x khi đó bài toán (Q) trở thành: với g G x c và .b b A x Thật vậy, thay thế x d x vào bài toán (Q) ta có: 1m in. - )2 ( )TTd x G d x c d xA d x b 1 1 1 1m in 2 2 2 2 T T T T Td G d x G d d G x x G x c d c xA d A x b 1m in 2 .TTd G d g dA d b 19 2.1.3 Phương pháp giải Sau đây ta sẽ giải bài toán (QD). - )2T T TL d d G d g d A d b là hàm Lagrange tƣơng ứng với bài toán (QD). - Khi đó điều kiện KKT của bài toán (QD) là: 00TdL G d g AL A d b 0TG d g AA d b 0TG d A gA d b .0TgG A dbA (2.2) Ta thấy rằng, nếu d x x thì hệ (2.2) chính là điều kiện KKT của bài toán (QD) tƣơng ứng với bài toán gốc (Q). - Do vậy, nếu d là nghiệm của bài toán (QD) với nhân tử Largrange thì x d x là nghiệm của bài toán (Q) với nhân tử Largrange . - Đặc biệt, bài toán (Q) có nghiệm duy nhất. - Ma trận của hệ (2.2) có tồn tại ma trận nghịch đảo, do đó, hệ (2.2) có nghiệm duy nhất là và bài toán (Q) có nghiệm duy nhất là . - Do đó, ta sẽ tìm đƣợc nghiệm tối ƣu của bài toán (Q) là . - 2.1.4 Ví dụ 22 Xét bài toán quy hoạch toàn phƣơng m in f(x. - kx x x x x x x x x x x xxxxx Nhƣ vậy ta có bài toán (Q) với . - 1112G c A b Chọn 000Tx , giả sử gần nghiệm tối ƣu của bài toán là . - 23 2.2 Phương pháp Tập hoạt động (Active Set) giải bài toán quy hoạch toàn phương với ràng buộc bất đẳng thức tuyến tính 2.2.1 Phát biểu bài toán Xét bài toán: với G là ma trận đối xứng, xác định dƣơng, và Giả sử là một điểm chấp nhận đƣợc của bài toán . - Ta trình bày phƣơng pháp tập hoạt động (active set method) xác định nghiệm tối ƣu của bài toán . - 2.2.2 Ý tưởng Cho x là nghiệm của bài toán . - Nếu ta biết các ràng buộc active tại x, thì x là nghiệm của bài toán ràng buộc đẳng thức: Do chúng ta không biết trƣớc đƣợc nên phƣơng pháp Tập hoạt động sẽ cập nhật từ tập chỉ số . - 24 2.2.3 Phương pháp Active Set Hàm Lagrange tƣơng ứng với bài toán là. - (2.8) Giả sử là điểm KKT bài toán . - và G là ma trận nửa xác định dƣơng, thì là một nghiệm toàn cục của bài toán . - suy ra là điểm cực tiểu toàn cục của bài toán . - Sau đây, chúng ta sẽ mô tả phƣơng pháp Tập hoạt động để tìm nghiệm của bài toán quy hoạch dạng toàn phƣơng với ràng buộc bất đẳng thức qua các bước dƣới đây. - Giả sử là một điểm chấp nhận đƣợc của bài toán và giả sử là tập con của . - Kiểm tra xem có phải là nghiệm của bài toán: (kQ) v.đ . - Áp dụng phƣơng pháp Null Space để giải bài toán: (kQD) v.đ . - Nếu 0kd thì kx là nghiệm của bài toán (kQ. - Nếu không thì kx không là nghiệm của bài toán (kQ). - Vì là điểm chấp nhận đƣợc của bài toán , nên giá trị tối ƣu của bài toán là không dƣơng. - Tính k là giá trị lớn nhất trong [0,1] để kkkxd là chấp nhận đƣợc của bài toán . - Giả sử 0kd: Giả sử là nhân tử Lagrange tƣơng ứng với bài toán (kQ). - Ta có: 27 Nếu với kiW thì kx là nghiệm của bài toán vì kx là điểm chấp nhận đƣợc của bài toán . - Sau đây là thuật toán Active Set để giải bài toán quy hoạch lồi toàn phƣơng . - Giải bài toán để tìm . - 28 2.2.5 Ví dụ Xét bài toán quy hoạch toàn phƣơng: 12121212v.đ . - Bước khởi đầu: Chọn là điểm chấp nhận đƣợc của bài toán . - Giải bài toán con sau theo phƣơng pháp Không gian hạt nhân: 0QD 0121m in 2 - 0 - 0,TTd G d g ddd sẽ suy ra nghiệm là. - Giải bài toán con sau theo phƣơng pháp Không gian hạt nhân: (1QD) 121m in 2 - 0,TTd G d g dd tìm đƣợc nghiệm . - Giải bài toán con sau theo phƣơng pháp Không gian hạt nhân: (2QD)21221m in 2 3 0 - 0,TTd G d g dddd tìm đƣợc nghiệm . - 31 Giải bài toán con sau theo phƣơng pháp Không gian hạt nhân: (3QD) 1321m in 2 3d + 0,TTd G d g dd tìm đƣợc nghiệm . - Giải bài toán con sau: (4QD)4121m in 2 3 0.TTd G d g ddd Hàm mục tiêu: 32 . - Vì , ta sẽ tìm các nhân tử Lagrange theo công thức sau: Do với mọi , Dừng thuật toán và nghiệm tối ƣu của bài toán là . - Giả sử ˆx là nghiệm của bài toán: (ˆQ)v.đ . - Giả sử d là nghiệm của bài toán: (ˆdQ) v.đ . - Thật vậy, do 0kd, kx là cực tiểu toàn cục của bài toán: 35 (kQ) v.đ . - Nếu 1k thì 1k k kx x d và 10kd vì 1kx là nghiệm của bài toán (kQ). - Phương pháp SQP giải bài toán quy hoạch phi tuyến Chƣơng 3 trình bày các phƣơng pháp SQP là phƣơng pháp Newton-Lagrange và phƣơng pháp Wilson-Han-Powell cũng nhƣ tổng hợp các tính chất và kết quả hội tụ của các phƣơng pháp. - 3.1 Phương pháp Newton-Lagrange Xét bài toán quy hoạch phi tuyến với ràng buộc đẳng thức: (3.1) với và là các hàm thuộc lớp . - Nếu ma trận (3.6) bị chặn đều, thì bất kì điểm tụ của dãy đƣợc sinh bởi thuật toán 1 đều là điểm KKT của bài toán (3.1). - Ngƣời ta nhận thấy rằng nhìn chung phƣơng pháp SQP là một phƣơng pháp tốt để giải các bài toán tối ƣu phi tuyến có số chiều nhỏ hoặc trung bình. - Dễ thấy, (3.15) là điều kiện KKT của bài toán con : (3.16) ở đây và . - Như vậy, phương pháp Lagrange-Newton có thể được xem như một phương pháp giải một dãy các bài toán con (3.16). - 3.2 Phương pháp Wilson-Han-Powell Chúng ta xét bài toán con (3.16) trong dạng tổng quát (cả ràng buộc đẳng thức và ràng buộc bất đẳng thức. - Đặt là nhân tử Lagrange của bài toán (3.17), ta có: (3.18) Ngƣời ta có thể chứng minh rằng là hƣớng giảm của nhiều hàm phạt. - Thuật toán sau đây đƣợc đƣa ra bởi Han: Thuật toán 2 (Wilson-Han-Powell) Bƣớc 1: Cho Bƣớc 2: Giải bài toán con (3.17) ta đƣợc . - 46 nếu thì với bất kỳ điểm tụ của dãy đƣợc sinh ra từ thuật toán 2 là một điểm KKT của bài toán (3.17). - Để đơn giản, ta xét trƣờng hợp bài toán tối ƣu không có ràng buộc, chúng ta có thể áp dụng kỹ thuật quasi-Newton chuẩn: Thêm vào đó 48 sẽ luôn luôn đúng với bài toán tối ƣu không ràng buộc. - 50 3.4 Hiệu ứng Maratos Với bài toán tối ƣu không có ràng buộc, nếu là một điểm dừng thỏa mãn điều kiện đủ bậc hai, tức là ma trận xác định dƣơng, thì với , và nếu là một bƣớc di chuyển hội tụ siêu tuyến tính thì với lớn. - Do đó, với các bài toán tối ƣu không có ràng buộc thì các bƣớc hội tụ siêu tuyến tính là chấp nhận đƣợc, nhƣng điều này chƣa chắc đã đúng với bài toán tối ƣu có ràng buộc. - Ví dụ: Xét bài toán tối ƣu có ràng buộc đẳng thức sau: v.đ.k . - Dễ thấy là nghiệm tối ƣu của bài toán và là điểm KKT của bài toán. - Đặt thì bài toán con Wilson-Han-Powell (3.17) là: Dễ dàng tìm đƣợc nghiệm của bài toán trên là . - 52 3.5 Bước hiệu chỉnh bậc 2 Để cải thiện hiệu ứng Maratos, ngƣời ta giải thêm một bài toán con nhƣ sau. - Gọi là nghiệm của bài toán (3.17). - Định nghĩa là nghiệm của bài toán toàn phƣơng: (3.28) Để đơn giản hóa, giả sử tất cả các ràng buộc là ràng buộc đẳng thức. - Do đó, với việc giải thêm bài toán (3.27) chúng ta sẽ có một bƣớc hội tụ siêu tuyến tính, và phƣơng pháp Wilson-Han-Power sẽ tìm đƣợc một hƣớng chấp nhận đƣợc, là điều kiện để tìm ra nghiệm tối ƣu. - Kết quả số 4.1 Công cụ sử dụng Trong khuôn khổ của luận văn này, ta sử dụng phần mềm Matlab 7.5 để lập trình và tiến hành khảo sát một vài bài toán tối ƣu phi tuyến dựa vào phƣơng pháp SQP. - Hàm nullspace() dùng để giải bài toán quy hoạch dạng toàn phƣơng với ràng buộc dạng đẳng thức dùng phƣơng pháp Không gian hạt nhân (mục 2.1 phần 2) 58 . - Hàm activeset() dùng để giải bài toán quy hoạch toàn phƣơng với điều kiện bất đẳng thức dùng phƣơng pháp Tập hoạt động (mục 2.2 phần 2. - Kết hợp phƣơng pháp Lagrange-Newton và phƣơng pháp Wilson-Han-Powell, chúng ta đƣa ra thuật toán SQP (để đơn giản, ta giả sử bài toán chỉ có ràng buộc bất đẳng thức. - Bƣớc Giải bài toán sau theo biến : Nghiệm trả về của bài toán trên gồm 2 giá trị là . - 4.2 Kết quả của một số bài toán cụ thể Sau đây là kết quả của một số bài toán quy hoạch toàn phƣơng và quy hoạch phi tuyến với ràng buộc đẳng thức và bất đẳng thức . - Ví dụ 1: Giải bài toán quy hoạch toàn phƣơng : 61 Sử dụng hàm nullspace() với điểm ban đầu là (0;0) ta có kết quả sau: Ví dụ 2: Giải bài toán dạng toàn phƣơng: Sử dụng hàm activeset() với điểm ban đầu (0;0) ta có kết quả sau: 62 Ví dụ 3: Giải bài toán Dùng hàm sqp. - Ví dụ 4: Giải bài toán Dùng hàm sqp. - nếu chọn điểm ban đầu là (0;3) thì sau 4 bƣớc lặp, ta có nghiệm của bài toán : 64 65 KẾT LUẬN Luận văn trình bày phƣơng pháp SQP giải bài toán quy hoạch phi tuyến có ràng buộc. - Phƣơng pháp này tách bài toán phi tuyến ban đầu thành một dãy các bài toán quy hoạch toàn phƣơng. - Các bài toán con này đƣợc giải quyết bằng phƣơng pháp không gian hạt nhân (cho bài toán có ràng buộc đẳng thức) hoặc phƣơng pháp tập hoạt động (cho bài toán có ràng buộc bất đẳng thức). - Các phƣơng pháp SQP giải bài toán quy hoạch phi tuyến đƣợc đề cập đến là phƣơng pháp Newton- Lagrange, phƣơng pháp Wilson-Han-Powell. - Luận văn trình bày phƣơng pháp hiệu chỉnh bậc hai để có các bƣớc lặp hữu hạn cũng nhƣ kết quả hội tụ của bài toán. - Trong thời gian tới, tôi mong có cơ hội nghiên cứu sâu hơn về vấn đề này, để có thể ứng dụng cho các bài toán điều khiển tối ƣu trong thực tế
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt