Nghiên cứu chiến lược tối ưu hóa trong điều khiển dự báo

Nguyễn Thị Mai Hương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 113(13): 115 - 121<br /> <br /> NGHIÊN CỨU CHIẾN LƯỢC TỐI ƯU HÓA TRONG ĐIỀU KHIỂN DỰ BÁO<br /> Nguyễn Thị Mai Hương, Mai Trung Thái,<br /> Lê Thị Huyền Linh, Lại Khắc Lãi*<br /> Trường ĐH Kỹ thuật Công nghiệp – ĐH Thái Nguyên; Đại học Thái Nguyên<br /> <br /> TÓM TẮT<br /> Tối ưu hóa trong điều khiển dự báo là một vấn đề khó đang được nhiều nhà khoa học trong và<br /> ngoài nước quan tâm nghiên cứu. Bài báo này, chúng tôi đưa ra những nghiên cứu tổng quan về<br /> các phương pháp tối ưu hóa phổ biến được sử dụng trong điều khiển dự báo đối với cả MPC tuyến<br /> tính và MPC phi tuyến.<br /> Từ khoá: Điều khiển dự báo,Tối ưu hóa, MPC tuyến tính, MPC phi tuyến.<br /> <br /> GIỚI THIỆU CHUNG*<br /> Lịch sử điều khiển tối ưu bắt đầu từ thập niên<br /> 60 khi xuất hiện 2 bài báo của Kalman. Hai<br /> bài báo này có tầm ảnh hưởng đáng kể đối với<br /> các nhà nghiên cứu về điều khiển tối ưu, là<br /> tiền đề cho sự phát triển của bộ điều khiển<br /> LQG (Linear Quadratic Gauss) mà sau này áp<br /> dụng lý trong thuyết điều khiển dự báo theo<br /> mô hình (MPC - Model Preditive Control).<br /> MPC về cơ bản là một dạng của bộ điều khiển<br /> LQG có bổ sung thêm các ràng buộc trong<br /> phạm vi dự báo hữu hạn. Có thể hiểu:<br /> MPC tuyến tính tầm vô hạn = LQG đơn giản<br /> Thập niên 70, MPC mới chỉ được sử dụng đối<br /> với các đối tượng biến đổi chậm, vì thủ tục tối<br /> ưu hóa sẽ được lặp đi lặp lại ở mọi bước. Cho<br /> tới thập niên 90, khi tốc độ tính toán của máy<br /> tính nhanh hơn thì MPC được áp dụng với<br /> nhiều loại đối tượng mà đặc tính động học<br /> nhanh như máy bay, robot, vệ tinh nhân tạo,<br /> máy móc tự động, … Khi áp dụng luật điều<br /> khiển rất nhiều vấn đề lý thuyết nảy sinh với<br /> MPC. Một trong các vấn đề chính là tìm ra<br /> thuật toán tối ưu thích hợp để giảm các sai số<br /> trong tương lai.<br /> Trong bài báo này, chúng tôi đưa ra những<br /> nghiên cứu tổng quát về các kỹ thuật tối ưu<br /> hóa phổ biến được sử dụng trong điều khiển<br /> dự báo. Các ứng dụng cho đối tượng cụ thể sẽ<br /> được công bố trong các bài báo tiếp sau.<br /> *<br /> <br /> Tel: 0913507464; Email: laikhaclai@gmail.com<br /> <br /> CHIẾN LƯỢC TỐI ƯU HÓA TRONG ĐIỀU<br /> KHIỂN DỰ BÁO<br /> Thuật toán điều khiển dự báo theo mô hình là<br /> sử dụng một mô hình quá trình rõ để dự báo<br /> đáp ứng tương lai của đối tượng. Bộ tối ưu<br /> hóa giải quyết một bài toán tối ưu, trong mỗi<br /> chu kì lấy mẫu của hệ thống điều khiển thông<br /> qua việc tính toán điều chỉnh chuỗi biến điều<br /> khiển tương lai, nhằm tối ưu hóa hoạt động<br /> của đối tượng ở mỗi một chu kì. Giá trị đầu<br /> tiên của chuỗi tối ưu được đưa tới điều khiển<br /> đối tượng, quá trình tính toán này sẽ được lặp<br /> lại trong mỗi chu kỳ tiếp theo. Hoạt động của<br /> MPC được biểu diễn như Hình 1.<br /> <br /> Hình 1. Hoạt động MPC<br /> <br /> Đặt Y là đầu ra của quá trình và u là đầu vào<br /> bộ điều khiển<br /> Ymongmuon (t ) = a1u (t − h ) + a 2 u ( t − 2 h ) + ...<br /> + b1 y (t − h ) + b2 y (t − 2 h ) + ....<br /> <br /> (1)<br /> <br /> YDubao (t ) = a1' u (t − h) + a 2' u (t − 2h) + ...<br /> +b1' y (t − h) + b2' y (t − 2h) + ....<br /> <br /> (2)<br /> <br /> 115<br /> <br /> Nguyễn Thị Mai Hương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> trong đó t = t – h là bước thời gian. Phương<br /> trình (1) miêu tả hoạt động vào/ra của hệ<br /> thống. Phương trình (2) biểu diễn hoạt động<br /> tương lai của hệ thống dự báo dựa trên đầu<br /> vào quá khứ của hệ thống u(t - h) và đầu ra y(t<br /> - h). Sai số giữa đầu ra dự báo và đầu ra mong<br /> muốn:<br /> <br /> e(t ) = YDubao (t ) − Ymongmuon (t )<br /> <br /> (3)<br /> <br /> U toiuu (t ) = ce(t )<br /> <br /> (4<br /> <br /> Phương trình (4) chỉ ra tỉ lệ sai số c và dự báo<br /> đầu vào tối ưu tính toán Utốiuu(t) dựa trên tính<br /> toán trước đó. Phương trình (1), (2), (3) và (4)<br /> miêu tả hoạt động của hệ thống đối với mỗi<br /> chu kì lấy mẫu ở tương lai. Thực hiện lặp 4<br /> phương trình trên tại các khoảng thời gian t +<br /> h, t + 2h, …để dự báo tín hiệu vào/ra tương<br /> lai của hệ thống có thể mô tả sơ lược như<br /> trong hình 1. Việc lặp các chu kì nhận được<br /> các sai số e(t), e(t + h), e(t + 2h) cho mỗi chu<br /> kì lấy mẫu. Để tối ưu hóa hệ thống (cực tiểu<br /> hóa sai số giữa đầu ra dự báo và tác động<br /> mong muốn) ta định nghĩa hàm số dư tương<br /> lai của hệ thống:<br /> Số dư = e2(t+ih), i=0, 1, …, n<br /> Mục tiêu là sử dụng các thuật toán tối ưu gần<br /> đúng và tìm các đầu vào tương lai sao cho cực<br /> tiểu hóa số dư, nghĩa là tìm cực tiểu (số dư).<br /> Tiến trình tối ưu hóa được miêu tả trong hình 2.<br /> Hệ thống tối ưu hóa<br /> <br /> Số dư cực tiểu (bằng việc lặp liên tục các phương<br /> trình (1), (2), (3) và (4))<br /> D(số dư)/dt<br /> C=Csốdư<br /> <br /> U to iu u ( t ) = c e ( t )<br /> Hình 2. Tiến trình tối ưu hóa MPC<br /> <br /> Sau đây trình bày ngắn gọn việc sử dụng các<br /> phương pháp tối ưu áp dụng cho MPC tuyến<br /> tính và MPC phi tuyến.<br /> 116<br /> <br /> 113(13): 115 - 121<br /> <br /> MPC tuyến tính<br /> Bài toán tối ưu hóa trong MPC tuyến tính<br /> Xét hệ thống thời gian bất biến và rời rạc sau:<br /> <br /> xt+1 = Axt + But<br /> <br /> (6)<br /> <br /> yt = Cxt<br /> <br /> (7)<br /> <br /> với các điều kiện ràng buộc:<br /> <br /> ymin ≤ yt ≤ ymax<br /> <br /> (8)<br /> <br /> umin ≤ ut ≤ umax<br /> <br /> (9)<br /> <br /> trong đó xt ∈ℜ , ut ∈ℜ và yt ∈ℜ là các<br /> véc tơ trạng thái, véc tơ đầu vào và vec tơ đầu<br /> ra. Chỉ số dưới min và max biểu thị giới hạn<br /> dưới và giới hạn trên. Nói chung, tối ưu hóa<br /> trong MPC tuyến tính là cực tiểu hóa phiếm<br /> hàm mục tiêu có dạng:<br /> n<br /> <br /> m<br /> <br /> J = x t Qx + u t Ru<br /> <br /> p<br /> <br /> (10)<br /> <br /> Đa số các ứng dụng MPC trong công nghiệp<br /> sử dụng các mô hình thực nghiệm tuyến tính,<br /> vì vậy hầu hết các sản phẩm MPC và các thuật<br /> toán tối ưu đều dựa trên loại mô hình này.<br /> Các phương pháp tối ưu hóa đối với MPC<br /> tuyến tính<br /> Khó khăn lớn nhất trong MPC là tìm ra cách<br /> nhanh nhất để tối ưu hóa khi thời gian yêu<br /> cầu để giải thuật toán tối ưu rất ngắn. Vì thế<br /> mà chúng ta cần sử dụng giải pháp tối ưu hóa<br /> thời gian thực. Đôi khi để giảm mức độ phức<br /> tạp chúng ta tìm kiếm bằng giải pháp cận tối<br /> ưu, với các điều kiện ràng buộc là tuyến tính.<br /> Đối với MPC tuyến tính giải pháp tối ưu<br /> thường được biểu diễn ở dạng toàn phương<br /> hoặc một chuẩn tuyến tính, vì vậy mà kết quả<br /> của bài toán tối ưu có thể được lập trình toàn<br /> phương (QP) hoặc lập trình tuyến tính (LP).<br /> Lập trình tuyến tính (LP): Một số tác giả đã<br /> nghiên cứu tối ưu hóa MPC dựa trên lập trình<br /> tuyến tính [1]. Xét hàm mục tiêu dạng:<br /> min J = min Px N<br /> <br /> N −1<br /> <br /> ∞<br /> <br /> + ∑ Qxk<br /> k =0<br /> <br /> + Ru k<br /> ∞<br /> <br /> ∞<br /> <br /> (11<br /> <br /> với điều kiện ràng buộc G z ≤ W + Sx ( t )<br /> Luật MPC được định nghĩa bởi giải pháp lập<br /> trình tuyến tính [2]. Schechter [2] đã chứng<br /> minh điều này đúng với bất kì tổng các giá trị<br /> hàm Afin (Affine) từng đoạn lồi.<br /> <br /> Nguyễn Thị Mai Hương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Phương pháp đại số: Xét hàm mục tiêu sau:<br /> Ny −1<br /> <br /> min J = xt'+Ny t Pxt +Ny t + ∑ xt' +Ny t Qxt +k t + xt'+k Rut +k<br /> k =0<br /> <br /> (12)<br /> <br /> các điều kiện ràng buộc<br /> <br /> ymin ≤ yt ≤ ymax , k =1,2,..., Nc<br /> umin ≤ ut ≤ umax , k = 0,1,..., Nc<br /> và động học hệ thống<br /> <br /> xt +k +1 = Axt +k t + But +k , k ≥ 0,<br /> yt +k t + Qxt +k t , k ≥ 0,<br /> ut +k = Kxt +k t , Nu ≤ k ≤ Ny ,<br /> trong đó các ma trận Q = Q' ≥ 0, R = R' ≥ 0 và<br /> P≥ 0. Nu, Ny, Nc là phạm vi đầu vào, phạm vi<br /> đầu ra và phạm vi điều kiện ràng buộc sao<br /> cho Ny ≥ Nu và Nc ≤ Ny −1. Giải bài toán (12),<br /> tiến hành lặp ở mỗi thời điểm t đối với giá trị<br /> đo được hiện thời xt và biến trạng thái dự báo,<br /> <br /> xt+1t ,..., xt+k t ở các bước thời gian t + 1, …,<br /> t + k và đạt được các hoạt động điều khiển tối<br /> ưu tương ứng U* ={ut*,...,ut*+k−1} . Đầu vào dự<br /> báo đầu tiên được đưa vào hệ thống cụ thể là<br /> ut = u*t , tiến hành lặp ở thời điểm t + 1 dựa<br /> trên trạng thái mới xt+1.<br /> Việc điều khiển ma trận hàm mục tiêu P và hệ<br /> số phản hồi trạng thái K thường được sử dụng<br /> để đảm bảo ổn định vòng kín của hệ thống<br /> (12). Giải pháp đại số của hệ thống phụ thuộc<br /> vào việc tìm kiếm các giá trị của ma trận P và<br /> Q. Để tìm P ta dùng giải pháp rời rạc hóa<br /> phương trình Lyapunov: P = A’PA + Q<br /> Giả sử bài toán không ràng buộc, tầm vô hạn,<br /> nghĩa là Nc = Nu = Ny =∞ chúng ta có thể tìm<br /> hệ số phản hồi trạng thái K bằng việc giải<br /> phương trình Ricatti:<br /> −1<br /> <br /> K = − ( R + B PB ) B PA,<br /> '<br /> <br /> '<br /> <br /> P = ( A + BK ) ' P ( A + BK ) + K ' RK + Q<br /> <br /> Giải phương trình Lyapunov và các phương<br /> trình Ricatti là phương pháp phổ biến nhất để<br /> <br /> 113(13): 115 - 121<br /> <br /> tìm các giá trị của ma trận K và P [4], thực<br /> hiện tương tự ta giải được bài toán đại số.<br /> Lập trình toàn phương (QP): Rawins và<br /> Morari [3] đã chứng minh rằng MPC tuyến<br /> tính có thể được gọi là bài toán lập trình toàn<br /> phương (QP). Nếu chúng ta đưa mối liên hệ<br /> dưới đây xt +1 t = A xt +<br /> k<br /> <br /> k −1<br /> <br /> ∑ A Bu<br /> j<br /> <br /> j =0<br /> <br /> t + k −1kj<br /> <br /> vào trong hệ thống được miêu tả bởi phương<br /> trình (12) sẽ được biểu thức tối ưu hóa lập<br /> trình toàn phương sau:<br /> 1<br /> 1<br /> J * ( xt ) = min U ' HU + xt' FU + xt'Yx(t ) (13)<br /> 2<br /> 2<br /> điều kiện ràng buộc là G z ≤ W + S x ( t )<br /> '<br /> <br /> trong đó U ≜ ut' ,...,ut'+Nu −1 ∈ℜs và s ≜ mN u là<br /> vectơ của các biến tối ưu, H = H' ≻ 0, các ma<br /> trận H, P, Y, G, W, E thu được từ ma trận<br /> ràng buộc trạng thái S và ma trận đầu vào R.<br /> MPC áp dụng được nhờ giải quyết bài toán<br /> QP (13), lặp tại mỗi thời điểm t ≥ 0 đối với<br /> giá trị trạng thái hiện thời xt. Mặc dù bộ giải<br /> phương trình QP là giải được nhưng việc tính<br /> toán đầu vào ut trực tuyến phụ thuộc rất nhiều<br /> vào tốc độ tính toán [5].<br /> Lập trình toàn phương đa tham số (Multi<br /> Parametric Quadratic Programming) (mp-QP)<br /> Mục đích của MPC là giảm thời gian tối ưu<br /> hóa trực tuyến bởi vì hệ thống hoạt động ở<br /> thời gian thực. Ngày nay, những nghiên cứu<br /> quan trọng đưa ra nhiều thuật toán tối ưu hóa<br /> hiệu quả. Tác giả Bemporad [4], [6] đã giải<br /> quyết bài toán (12) bằng cách lập trình toàn<br /> phương đa tham số. Bảng 1 dưới đây đưa ra<br /> các ưu, nhược điểm của các phương pháp<br /> điều khiển tối ưu trong MPC tuyến tính<br /> Bảng 1<br /> Độ khó<br /> TƯ hóa<br /> ĐK ràng<br /> buộc<br /> <br /> P. pháp<br /> đại số<br /> Nhỏ<br /> Không<br /> Không<br /> <br /> P. pháp P. pháp<br /> LP<br /> QP<br /> T. bình<br /> Lớn<br /> Có<br /> Tốt hơn<br /> Có<br /> <br /> Không<br /> <br /> PP. ràng<br /> buộc QP<br /> Lớn hơn<br /> Tốt hơn<br /> Có<br /> <br /> Lập trình toàn phương đa tham số (mp-QP)<br /> thì tránh được hiện tượng tối ưu hóa. Biến đổi<br /> 117<br /> <br /> Nguyễn Thị Mai Hương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> bài toán QP (13) bên trong bài toán tối ưu hóa<br /> đa tham số thông qua việc biến đổi tuyến tính<br /> sau:<br /> x ≜ U + H −1 F ' xt trong đó z∈ℜ là<br /> tham số biến tối ưu. Vấn đề QP (13) có thể<br /> được biểu diễn thành vấn đề mp-QP:<br /> 1<br /> Vz (xt ) = min z'Hz<br /> 2<br /> <br /> điều kiện ràng buộc<br /> <br /> (14<br /> <br /> G z ≤ W + Sx (t ) trong<br /> <br /> đó xt là vec tơ tham số và S = E +GH−1F' .<br /> Ưu điểm của công thức này là xt chỉ xuất hiện<br /> trong vế phải của điều kiện ràng buộc và<br /> không xuất hiện trong hàm mục tiêu. Khác<br /> với phương trình (13) véc tơ trạng thái xt xuất<br /> hiện ở vế phải của cả điều kiện ràng buộc và<br /> ở hàm mục tiêu. Vì vậy mà trong phương<br /> trình (14) z có thể đạt được như hàm Afin của<br /> x đối với không gian cho phép hoàn thiện của<br /> x [5]. Tác giả Vassilis đã chứng minh rằng<br /> tập hợp các tham số Xf ⊆ X lồi, giải pháp tối<br /> ưu z(x): X f →ℜ liên tục và affine từng đoạn,<br /> hàm mục tiêu tối ưu hóa Vz (x): X f →ℜ liên tục,<br /> lồi và toàn phương từng đoạn.<br /> Ưu điểm của phương pháp này là dễ cài đặt<br /> và thực hiện đánh giá trực tuyến nhanh hơn.<br /> Nhược điểm là trạng thái của hệ thống tăng,<br /> phạm vi điều khiển lớn hơn vì thế thực hiện<br /> cài đặt thuật toán khó khăn hơn.<br /> MPC phi tuyến<br /> Bài toán tối ưu hóa trong MPC phi tuyến<br /> MPC đã trở lên rất hấp dẫn với chiến lược<br /> điều khiển phản hồi, đặc biệt đối với các quá<br /> trình tuyến tính. Tuy nhiên, các mô hình<br /> tuyến tính không đủ tốt để miêu tả đặc tính<br /> động học quá trình khi yêu cầu sản phẩm chất<br /> lượng cao và tăng năng suất, các quy định<br /> môi trường chặt chẽ và yêu cầu về tính kinh<br /> tế trong các quá trình công nghiệp đòi hỏi các<br /> hệ thống phải hoạt động khép kín trong phạm<br /> vi cho phép, vì thế các mô hình phi tuyến<br /> được sử dụng.<br /> Cấu trúc cơ bản của NMPC được miêu tả như<br /> hình 3.<br /> Sơ đồ NMPC cơ bản làm việc như sau:<br /> 118<br /> <br /> 113(13): 115 - 121<br /> <br /> 1) Tính toán giá trị đặt/ước lượng trạng thái<br /> của hệ thống.<br /> 2) Tính toán tín hiệu đầu vào tối ưu thông qua<br /> việc cực tiểu hóa hàm mục tiêu đã cho trên<br /> phạm vi dự báo bền vững trong tương lai sử<br /> dụng một mô hình hệ thống.<br /> 3) Cài đặt tín hiệu đầu vào tối ưu đầu tiên cho<br /> đến khi đạt được giá trị đo mới/ ước lượng<br /> trạng thái mới của trạng thái có giá trị.<br /> 4) Tiếp tục với bước 1<br /> Bộ điều khiển NMPC<br /> u<br /> <br /> Tối ưu<br /> <br /> Hàm mục tiêu<br /> + các ràng<br /> buộc<br /> <br /> Mô hình hệ<br /> thống<br /> <br /> xsp<br /> <br /> xˆ<br /> <br /> Quá trình<br /> <br /> y<br /> <br /> Ước lượng<br /> trạng thái<br /> <br /> Tính toán giá<br /> trị đặt<br /> <br /> Hình 3. Cơ sở vòng lặp điều khiển NMPC<br /> <br /> * Xét hệ thống phi tuyến được miêu tả bởi các<br /> phương trình rời rạc:<br /> <br /> xk = f t x ( x k −1 , u k −1 )<br /> y k k −1 = g ( xk )<br /> Điều kiện ràng buộc<br /> U = u ∈ ℜ m umin ≤ u ≤ umax<br /> X = x ∈ ℜ n xmin ≤ x ≤ xmax<br /> <br /> trong đó xk là vec tơ trạng thái, uk là vec tơ<br /> đầu vào điều khiển, yk là vec tơ đầu ra, tx là<br /> thời gian lấy mẫu, k k −1 chỉ số dưới được<br /> dùng để chỉ ra giá trị dự báo ở bước thứ k dựa<br /> trên giá trị đo được ở bước thứ k-1. Ở đây<br /> umin, umax và xmin, xmax là các vec tơ hằng. Sai<br /> số mô hình được tính toán bởi phương trình:<br /> dk = yk − yk k−1<br /> Mục tiêu là cực tiểu hóa sai số sao cho nhận<br /> được đầu ra tối ưu như phương trình sau:<br /> <br /> xk +1 = f tx ( xk )uk<br /> yk +1 k = g ( xk +1 ) + d k<br /> Bài toán điều khiển tối ưu được mô tả trong<br /> miền thời gian rời rạc:<br /> <br /> Nguyễn Thị Mai Hương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> N −1<br /> <br /> min imize ∑ Li ( xi , zi , ui ) + E ( xN )<br /> x , z ,u<br /> <br /> (15)<br /> <br /> i=0<br /> <br /> Điều kiện ràng buộc<br /> <br /> x0 − x0 = 0<br /> <br /> (16)<br /> <br /> xi+1 − fi (xi , zi , ui ) = 0, i = 0,..., N −1<br /> <br /> (17)<br /> <br /> gi (xi , zi , ui ) = 0, i = 0,..., N −1<br /> <br /> (18)<br /> <br /> hi (xi , zi , ui ) ≤= 0, i = 0,..., N −1<br /> <br /> (19)<br /> <br /> r(xN ) ≤ 0<br /> <br /> (20)<br /> <br /> Các phương pháp tối ưu hóa đối với MPC<br /> phi tuyến<br /> Bài báo này chúng tôi đưa ra 2 phương pháp<br /> để giải bài toán NMPC<br /> + Tối ưu hóa kiểu Newton<br /> + Phương pháp số<br /> Tối ưu hóa kiểu Newton: Phương pháp<br /> Newton để giải phương trình phi tuyến<br /> R(W)=0 bắt đầu với ước đoán ban đầu W0 và<br /> tạo thành một chuỗi lặp Wk mà mỗi chuỗi lặp<br /> này giải quyết sự tuyến tính hóa của hệ thống<br /> ở các lần lặp trước đó, cụ thể là với Wk đã cho<br /> thì lần lặp tiếp theo Wk+1 sẽ thỏa mãn<br /> R (W k ) + ∇ (W k ) T (W<br /> <br /> k +1<br /> <br /> −W k) = 0<br /> <br /> Phương pháp Newton có tỉ lệ hội tụ toàn<br /> phương cục bộ mà khả năng hội tụ nhanh như<br /> khi thực hiện bất kì phương pháp số nào đã<br /> được phân tích trong [7]. Nếu Jacobi<br /> ∇R (W k )T không tính được hoặc nghịch đảo<br /> không chính xác, dẫn đến tỉ lệ hội tụ chậm<br /> hơn thì việc lặp vô giá trị và phải tăng số lớp<br /> “phương pháp kiểu Newton” rộng hơn.<br /> Phương pháp này được đề cập rất chi tiết<br /> trong tài liệu [8].<br /> Bài toán NMPC có cấu trúc đặc biệt của bài<br /> toán phi tuyến chung<br /> G ( X ) = 0<br /> min imize P ( X ) s.t <br /> x<br /> H ( X ) ≤ 0<br /> <br /> đối với giải pháp tối ưu X* phải thỏa mãn các<br /> điều kiện của Karush-Kuhn-Tucker (KKT) là:<br /> ∇z = ( X*, λ*µ*) = 0<br /> <br /> (21)<br /> <br /> G(X ) = 0<br /> <br /> (22)<br /> <br /> *<br /> <br /> 0 ≥ H(X ) ⊥ µ ≥ 0<br /> *<br /> <br /> *<br /> <br /> (23)<br /> <br /> 113(13): 115 - 121<br /> <br /> Ở đây chúng ta sử dụng định nghĩa Hàm<br /> Lagrange<br /> l ( X , λ , µ ) = F ( X ) + G ( X )T λ + H ( X ) T µ<br /> và biểu tượng ⊥ giữa hai vec tơ trong bất<br /> phương trình (23) biểu thị điều kiện bổ sung<br /> thêm cũng nên được duy trì.<br /> Tất cả các kiểu tối ưu hóa của Newton cố<br /> gắng tuyến tính hóa các hàm toán và sử dụng<br /> phương pháp lập trình toàn phương liên tiếp<br /> (SQP, Sequential Quadratic Programming).<br /> a1. Lập trình toàn phương liên tiếp<br /> Bước đầu tiên để giải hệ thống Karush-KuhnTucker (KKT) là tuyến tính hóa tất cả các<br /> hàm phi tuyến từ (21) đến (23) bằng cách sử<br /> dụng các điều kiện của lập trình toàn phương<br /> (QP).<br /> k<br /> GQP<br /> ( X k ) + ∇G( X k )T ( X − X k ) = 0<br /> k<br /> min imize PQP<br /> (X )  k<br /> k<br /> k T<br /> k<br /> X<br />  H QP ( X ) + ∇H ( X ) ( X − X ) ≤ 0<br /> <br /> với hàm mục tiêu<br /> 1<br /> k<br /> FQP<br /> ( X ) = ∇H ( X k )T ( X ) + ( X − X k )T<br /> 2<br /> ∇ 2x l ( X k , λ k , µ k )( X − X k )<br /> <br /> (24)<br /> <br /> ∇ 2x l ( X k , λ k , µ k ) được gọi là ma trận Hessian<br /> bán hữu hạn dương, QP lồi vì vậy giải pháp<br /> tổng thể có thể tìm được đáng tin cậy. Phương<br /> pháp xấp xỉ tổng quát áp dụng cho bài toán tối<br /> ưu hóa phi tuyến được gọi là lập trình toàn<br /> phương liên tiếp (SQR).<br /> a2. Phương pháp SQP kinh điển của Powell<br /> Một trong những người thành công nhất sử<br /> dụng biến thể SQP là Powell [10]. Ông đã sử<br /> dụng chính xác điều kiện ràng buộc Jacobi để<br /> lặp ma trận Hessian ∇ 2x l ( X k , λ k , µ k ) bằng<br /> <br /> việc xấp xỉ Ak. Mỗi lần xấp xỉ tiếp theo ma<br /> trận Hessian thu được là Ak+1 từ lần xấp xỉ<br /> trước đó Ak bằng một công thức cập nhật mà<br /> sử dụng Lagrange gradients.<br /> γ = ∇ z l ( X k +1 , λ k +1 , µ k +1 ) − ∇ z l ( X k , λ k +1 , µ k +1(25)<br /> )<br /> Mục tiêu của phương pháp Quasi-Newton<br /> hoặc phương pháp Variable-Metric là lựa<br /> chọn thông tin thứ 2 trong Ak+1 sao cho thỏa<br /> mãn phương trình cát tuyến Ak +1σ = γ<br /> Việc sử dụng rộng rãi phương pháp cập nhật<br /> là Broyden-Fletcher-Goldfarb-Shanno(BFGS)<br /> 119<br /> <br />