Phương pháp vượt khe hướng phân giác giải bài toán quy hoạch phi tuyến có ràng buộc

TẠP CHÍ KHOA HỌC, ðại học Huế, Số 65, 2011<br /> <br /> PHƯƠNG PHÁP VƯỢT KHE HƯỚNG PHÂN GIÁC<br /> GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC<br /> Bùi Minh Trí, Trường ðại học Bách khoa Hà Nội<br /> Nguyễn Vũ Tiến, ðại học Huế<br /> <br /> TÓM TẮT<br /> Trong bài báo này, dựa trên cơ sở nguyên lý vượt khe chúng tôi xây dựng thuật toán<br /> giải bài toán Quy hoạch phi tuyến có ràng buộc: Thuật toán vượt khe hướng phân giác. ðịnh lý<br /> hội tụ ñược nêu ra và chứng minh. Các ví dụ minh họa ñược trình bày.<br /> <br /> 1. Nguyên lý tối ưu hóa vượt khe và hướng tìm kiếm<br /> 1.1. Nguyên lý tối ưu hóa vượt khe [3]<br /> Xét bài toán cực tiểu hóa có ràng buộc:<br /> min{J(x)│ gi(x) ≤ 0; i = 1, … ,m ; x ∈ Rn}<br /> <br /> (1.1)<br /> <br /> trong ñó: J(x) là hàm mục tiêu bị chặn dưới và thỏa mãn ñiều kiện:<br /> <br /> lim J ( x ) = ∞<br /> <br /> (1.2)<br /> <br /> x →∞<br /> <br /> các hàm gi (x) là các hàm lồi.<br /> Thuật toán tối ưu hóa phi tuyến giải bài toán (1.1) có phương trình lặp như sau:<br /> xk+1 = xk + αk+1 Sk , k = 0, 1,…<br /> <br /> (1.3)<br /> <br /> trong ñó: xk, xk+1 là ñiểm ñầu và ñiểm cuối của bước lặp thứ k+1; αk+1 là ñộ dài bước; Sk<br /> là vecto chỉ hướng thay ñổi các biến trong không gian Rn.<br /> Nếu αk+1 ñược xác ñịnh theo nguyên lý vượt khe thì ñược gọi là bước vượt khe,<br /> còn phương trình (1.3) gọi là thuật toán vượt khe [3]. Nguyên lý vượt khe phát biểu<br /> rằng ñiểm ñầu và ñiểm cuối của mỗi bước lặp tối ưu hóa luôn luôn nằm về hai phía<br /> ñiểm cực tiểu của hàm mục tiêu xét dọc theo hướng chuyển ñộng tại bước ñó. Nói cách<br /> khác, nếu tại ñiểm ñầu hàm mục tiêu thay ñổi theo chiều giảm, thì ñến ñiểm cuối nó<br /> phải có xu hướng tăng. Quỹ ñạo tìm kiếm tối ưu theo nguyên lý vượt khe tạo ra bức<br /> tranh hình học, tựa như ñiểm tìm kiếm tại mỗi lần lặp ñều bước vượt qua lòng khe của<br /> hàm mục tiêu.<br /> ðể cụ thể hóa nguyên lý vượt khe, ta xét hàm một biến sau ñối với mỗi bước lặp<br /> k+1:<br /> 241<br /> <br /> h(α) = J(xk + αsk)<br /> <br /> (1.4)<br /> <br /> Giả sử sk là hướng giảm hàm mục tiêu tại ñiểm xk. Theo ñiều kiện (1.2) tồn tại<br /> một giá trị α* > 0 bé nhất sao cho h(α) ñạt cực tiểu:<br /> α* = arg min h(α )<br /> <br /> (1.5)<br /> <br /> α >0<br /> <br /> Nếu h(α) khả vi liên tục, ta có ñịnh nghĩa bước vượt khe như sau:<br /> <br /> h ' (α )<br /> <br /> α =α v<br /> <br /> > 0,<br /> <br /> h (α v ) ≤ h ( 0 )<br /> <br /> (1.6)<br /> <br /> trong ñó, αv là bước vượt quá, tức là bước vượt khe.<br /> ðồ thị biến thiên của hàm h(α), khi quỹ ñạo tìm kiếm ñiểm tối ưu thay ñổi tử ñiểm<br /> ñầu x ñến ñiểm cuối xk+1 thể hiện ở hình 1. Ta thấy rằng, khi giá trị α tăng dần từ 0 vượt<br /> qua ñiểm cực tiểu α* của h(α) tới giá trị αv, quỹ ñạo tối ưu hóa tương ứng tiến dọc theo<br /> hướng sk theo quan hệ xk+1 = xk + αsk, thực hiện một ñộ dài bước α = αv ≥ α*. ðồ thị này<br /> cũng chỉ ra rằng, xét theo hướng chuyển ñộng, thì hàm mục tiêu thay ñổi theo chiều giảm<br /> từ ñiểm xk, còn khi ñạt tới ñiểm xk+1 thì nó ñã chuyển sang xu hướng tăng. Trước ñây,<br /> người ta dùng phổ biến bước xác ñịnh theo ñiều kiện (1.5), nên ñiểm tìm kiếm thường bị<br /> rơi ngay vào lòng khe và thuật toán tối ưu hóa tương ứng bị tắc lại ở ñó. Còn ở ñây, quá<br /> trình tối ưu hoá theo ñiều kiện (1.6) không cho phép ñiểm tìm kiếm rơi vào lòng khe trước<br /> khi ñạt lời giải tối ưu, ñồng thời nó vẽ ra một quy ñạo luôn luôn vượt lòng khe. ðể quá<br /> trình lặp có hiệu quả hội tụ cao và ổn ñịnh, ñiều kiện (1.6) ñược thay bởi:<br /> k<br /> <br /> αv > α* = arg min h(α ) , h(αv) – h* ≤ λ[h0 – h*]<br /> α >0<br /> <br /> (1.7)<br /> <br /> trong ñó, 0 < λ < 1 gọi là hệ số vượt; h* = h(α*); h0 = h(α0).<br /> h0<br /> <br /> h (αv)<br /> <br /> h*<br /> <br /> α*<br /> <br /> 0<br /> <br /> αv<br /> <br /> α<br /> <br /> Hình 1. Xác ñịnh bước vượt khe αv; h(α) = J(xk + αsk)<br /> <br /> Nếu thay h* trong (1.7) bởi ước lượng h ≈ h*, h > h* thì ta vẫn nhận ñược bước<br /> vượt khe theo ñịnh nghĩa. Vì vậy, ñể ñơn giản hóa việc lập trình nên lấy giá trị bé nhất<br /> 242<br /> <br /> tính ñược của h một cách ñơn giản trong mỗi bước lặp tương ứng, mà không cần xác<br /> ñịnh chính xác h* . ðiều ñó ñồng thời làm giảm ñáng kể số lần tính giá trị hàm mục tiêu.<br /> Thuật toán xác ñịnh bước vượt khe α (xem[3])<br /> Input: ñiểm x, hướng tìm kiếm s.<br /> Output: ñộ dài bước vượt khe α.<br /> Các tham số: a = 0.5, ñộ chính xác ε<br /> Bước 1: Giả sử β = a, tính h(β) = h(x + βs).<br /> Nếu h(β) ≥ h(0) thì α = 0, β = a, chuyển sang bước 2.<br /> Nếu không thì lặp α = β, β = 1.5β cho ñến khi h(α) ≤ h(β), rồi chuyển<br /> sang bước 2.<br /> Bước2: Nếu |β – α| ≤ ε, ε > 0, thì chuyển sang bước 3.<br /> Nếu không, ñặt θ = α + γ (β – α), trong ñó tham số γ có thể ñặt là 0,1.<br /> Nếu h (θ) ≤ h (α) thì ñặt α = θ và quay lại bước 2.<br /> Nếu không thì ñặt β = θ và quay lại bước 2.<br /> Bước 3: Gán bước vượt khe là β.<br /> 1.2. Hướng tìm kiếm<br /> Hướng tìm kiếm gọi là cải tiến ñược nếu chuyển dịch theo hướng ñó với ñộ dài<br /> nhất ñịnh dẫn ñến giảm giá trị hàm mục tiêu cần cực tiểu hóa (hay tăng hàm mục tiêu<br /> cần cực ñại hóa). Hầu hết các thuật toán tối ưu hóa hàm trơn xây dựng trên cơ sở ñiều<br /> kiện này, nghĩa là quá trình chuyển dịch luôn thỏa mãn ñiều kiện ñơn ñiệu của quá trình<br /> tìm kiếm tối ưu. Khi || ∇ J(x)|| ≠ 0, nếu véc tơ s ∈ Rn thoả mãn ñiều kiện ñơn ñiệu thì<br /> bất ñẳng thức sau ñược nghiệm ñúng:<br /> <br /> s , ∇J ( x ) < 0<br /> <br /> (1.8)<br /> <br /> ðiều kiện âm của tích vô hướng (1.8) giữa hai véc tơ chuyển ñộng s và gradien<br /> của hàm mục tiêu cho thấy rằng góc tạo bởi chúng là một góc tù (>900) hay nói cách<br /> khác, véc tơ hướng tìm kiếm luôn tạo với ñối gradient (anti-gradient) một góc nhọn khi<br /> xét bài toán cực tiểu hóa. Mặt khác ta biết rằng véc tơ gradient của hàm trơn tại ñiểm<br /> bất kỳ trong không gian biến số luôn luôn vuông góc với bề mặt mức tại ñiểm ñó. Vì<br /> vậy, hướng cải tiến ñược luôn luôn hướng vào phía trong của mặt mức này. ðó là hướng<br /> trên mỗi bước lặp cực tiểu hóa mà ñiểm tìm kiếm trượt theo. Sau ñây ta sẽ xét hướng<br /> chuyển ñộng cơ bản ñược sử dụng trong thuật toán vượt khe.<br /> <br /> 243<br /> <br /> Hướng phân giác: giữa hai véc tơ a và b là hướng của véc tơ d cho bởi công thức:<br /> d=<br /> <br /> a<br /> b<br /> +<br /> a<br /> b<br /> <br /> (1.9)<br /> <br /> trong ñó, a và b là ñộ dài của véc tơ a, b.<br /> Nhận xét: Nếu a, b không cùng phương thì véc tơ d tạo với a, b một góc nhọn.<br /> Do ñó nếu thay a, b bởi các véc tơ ñối gradient của hàm mục tiêu cực tiểu hóa thì véc tơ<br /> d sẽ luôn luôn là hướng cải tiến ñược. Trên cơ sở khái niệm hướng này ta có thể xây<br /> dựng thuật toán cực tiểu hóa ñơn giản, gọi là thuật toán phân giác vượt khe. Thuật toán<br /> này ñặc biệt thích hợp trong những hàm mục tiêu có dạng lòng khe dài. Trong nhiều<br /> trường hợp nhanh hơn hẳn thuật toán gradient kiểu hạ nhanh nhất.<br /> 2. Phương pháp vượt khe giải bài toán tối ưu phi tuyến có ràng buộc<br /> Sau ñây trình bày biến thể của các phương pháp vượt khe trong [1, 2] ñể giải bài<br /> toán tối ưu phi tuyến có ràng buộc<br /> min { J ( x ) | gi ( x ) ≤ 0; i = 1,…, m; x ∈ Rn }<br /> trong ñó , J(x) là hàm mục tiêu bị chặn dưới và thoả mãn ñiều kiện:<br /> <br /> lim J ( x) = ∞<br /> x →∞<br /> <br /> các hàm gi ( x ) là các hàm lồi.<br /> 2.1. Sơ ñồ của phương pháp vượt khe cho bài toán tối ưu có ràng buộc<br /> Sự kết hợp qui tắc ñiều chỉnh bước theo nguyên lý vượt khe với hướng di<br /> chuyển phù hợp với ñặc trưng của hàm mục tiêu dạng lòng khe tạo thành phương pháp<br /> tối ưu hóa vượt khe. Trong trường hợp có ràng buộc, tại mỗi bước lặp nếu bước vượt<br /> khe ra khỏi miền ràng buộc thì ta ñiều chỉnh lại bước di chuyển sao cho phương án mới<br /> không vượt ra ngoài miền ràng buộc gọi là bước vượt khe hiệu chỉnh. Sự kết hợp quy<br /> tắc ñiều chỉnh bước theo nguyên lý vượt khe hiệu chỉnh và hướng di chuyển phù hợp<br /> với các hàm có dạng lòng khe tạo thành phương pháp vượt khe giải bài toán tối ưu có<br /> ràng buộc. Với các thông số khởi tạo như sau:<br /> γ = 0,1, a = 0,5<br /> <br /> Bước lặp thứ 1: S0 = − ∇ J ( x0 ).<br /> Xác ñịnh bước vượt khe λ0 theo hướng di chuyển S0.<br /> Quá trình tối ưu lặp theo phương pháp vượt khe ở bước thứ k+1 gồm 2 giai ñoạn<br /> chính:<br /> Giai ñoạn 1. Tính gradient ∇ J (xk) và xác ñịnh hướng cải tiến ñược Sk (theo<br /> 244<br /> <br /> hướng ñó hàm mục tiêu cực tiểu hóa giảm ). Ở ñây có hai khả năng:<br /> + Nếu xk là một ñiểm trong của miền ràng buộc thì ta di chuyển theo hướng phân<br /> giác;<br /> + Nếu xk là một ñiểm nằm trên biên của miền ràng buộc thì do ñiều kiện Karush<br /> - Kuhn - Tucker không ñược thỏa mãn nên hệ sau chắc chắn có nghiệm:<br /> <br />  ∇J ( x k ) , S k 〈 0<br /> <br /> <br /> k<br /> k<br /> k<br />  ∇g i ( x ) , S 〈0, i ∈ I ( x )<br /> <br /> ∈ { 1,…, m }| gi<br /> <br /> I ( xk ) = { i<br /> <br /> ( xk ) = 0 }<br /> <br /> (xem [3, 4])<br /> <br /> Bằng việc giải hệ trên ta sẽ có hướng di chuyển cải tiến ñược Sk.<br /> Giai ñoạn 2. Thực hiện di chuyển ñiểm tìm kiếm theo hướng Sk cho ñến khi ñạt<br /> tới sườn dốc lên của khe. Khi ñó ñộ dài bước thoả mãn ñiều kiện (1.5) và (1.6). Nếu ñộ<br /> dài bước vượt khe vượt ra khỏi miền ràng buộc thì ñiều chỉnh về một ñiểm trên biên<br /> của miền ràng buộc với bước di chuyển ñiều chỉnh là αk+1. Kết thúc bước lặp k+1 ta<br /> nhận ñược phương án mới:<br /> xk+1 = xk + αk+1Sk<br /> <br /> Quá trình lặp tiếp diễn cho ñến khi thoả mãn các ñiều kiện dừng ñã ñịnh trước.<br /> Với hàm mục tiêu trên ta có thể dùng một trong các ñiều kiện sau ñây: ðiều kiện<br /> Karush - Kuhn - Tucker:<br /> <br /> ∇J ( x k ) ≤ ε 1 ,<br /> <br /> x k +n − xk ≤ ε 2 ,<br /> <br /> J ( xk +n ) − J ( xk ) ≤ ε 3<br /> <br /> Cần nhấn mạnh rằng chiến lược tìm kiếm tối ưu theo nguyên lý vượt khe tạo ra<br /> khả năng lớn cho các phương pháp vượt khe nghiên cứu tính chất hàm mục tiêu tại vùng<br /> khe của nó. Thuật toán tương ứng có ñược khả năng thích nghi xác ñịnh chiến lược hiệu<br /> quả nhất tiến nhanh ñến ñiểm tối ưu mà không bị rơi vào khe ở các bước trung gian. Qui<br /> tắc tìm bước vượt khe theo ñiều kiện (1.8) rất ñơn giản về mặt thực hiện, thậm chí có<br /> thể tính bằng tay và cho phép dễ dàng áp dụng cho quá trình tối ưu hóa tự ñộng trên hệ<br /> thống thời gian thực.<br /> 2.2. Thuật toán vượt khe hướng phân giác và tiêu chuẩn hội tụ<br /> 2.2.1. Thuật toán<br /> <br /> Gọi C = { x | gi ( x ) ≤ 0 }, int C ≠ ∅ . Giả sử ñã chọn ñược ñiểm x0 ∈ C, dãy<br /> ñiểm cực tiểu hóa xây dựng theo thuật toán vượt khe phân giác có dạng:<br /> xk+1 = xk + αk+1Sk, k = 0,1,…<br /> <br /> Trong ñó, αk+1 là bước vượt khe có ñiều chỉnh, Sk là véc tơ hướng chuyển ñộng<br /> của ñiểm tìm kiếm trên bước thứ k + 1. Hướng này ñược xác ñịnh theo qui tắc sau:<br /> 245<br /> <br />