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

Trong bài báo này, dựa trên cơ sở nguyên lý vượt khe các tác giả xây dựng thuật toán 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ý hội tụ ñược nêu ra và chứng minh. Các ví dụ minh họa ñược trình bày.
Nội dung trích xuất từ tài liệu:
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ộcTẠP CHÍ KHOA HỌC, ðại học Huế, Số 65, 2011PHƯƠNG PHÁP VƯỢT KHE HƯỚNG PHÂN GIÁCGIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘCBùi Minh Trí, Trường ðại học Bách khoa Hà NộiNguyễn Vũ Tiến, ðại học HuếTÓM TẮTTrong 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ángiả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ýhội tụ ñược nêu ra và chứng minh. Các ví dụ minh họa ñược trình bày.1. Nguyên lý tối ưu hóa vượt khe và hướng tìm kiếm1.1. Nguyên lý tối ưu hóa vượt khe [3]Xét bài toán cực tiểu hóa có ràng buộc:min{J(x)│ gi(x) ≤ 0; i = 1, … ,m ; x ∈ Rn}(1.1)trong ñó: J(x) là hàm mục tiêu bị chặn dưới và thỏa mãn ñiều kiện:lim J ( x ) = ∞(1.2)x →∞các hàm gi (x) là các hàm lồi.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:xk+1 = xk + αk+1 Sk , k = 0, 1,…(1.3)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; Sklà vecto chỉ hướng thay ñổi các biến trong không gian Rn.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,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ểurằ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ñ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áchkhá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ó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ứctranh 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ủahàm mục tiêu.ðể 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ặpk+1:241h(α) = J(xk + αsk)(1.4)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ạimột giá trị α* > 0 bé nhất sao cho h(α) ñạt cực tiểu:α* = arg min h(α )(1.5)α >0Nếu h(α) khả vi liên tục, ta có ñịnh nghĩa bước vượt khe như sau:h (α )α =α v> 0,h (α v ) ≤ h ( 0 )(1.6)trong ñó, αv là bước vượt quá, tức là bước vượt khe.ðồ 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ñầ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ượtqua ñ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 theohướng sk theo quan hệ xk+1 = xk + αsk, thực hiện một ñộ dài bước α = αv ≥ α*. ðồ thị nàycũ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ảmtừ ñ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,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ị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á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ướckhi ñạ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á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:kαv > α* = arg min h(α ) , h(αv) – h* ≤ λ[h0 – h*]α >0(1.7)trong ñó, 0 < λ < 1 gọi là hệ số vượt; h* = h(α*); h0 = h(α0).h0h (αv)h*α*0αvαHình 1. Xác ñịnh bước vượt khe αv; h(α) = J(xk + αsk)Nếu thay h* trong (1.7) bởi ước lượng h ≈ h*, h > h* thì ta vẫn nhận ñược bướcvượ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ất242tí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ñị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.Thuật toán xác ñịnh bước vượt khe α (xem[3])Input: ñiểm x, hướng tìm kiếm s.Output: ñộ dài bước vượt khe α.Các tham số: a = 0.5, ñộ chính xác εBước 1: Giả sử β = a, tính h(β) = h(x + βs).Nếu h(β) ≥ h(0) thì α = 0, β = a, chuyển sang bước 2.Nếu không thì lặp α = β, β = 1.5β cho ñến khi h(α) ≤ h(β), rồi chuyểnsang bước 2.Bước2: Nếu |β – α| ≤ ε, ε > 0, thì chuyển sang bước 3.Nếu không, ñặt θ = α + γ (β – α), trong ñó tham số γ có thể ñặt là 0,1.Nếu h (θ) ≤ h (α) thì ñặt α = θ và quay lại bước 2.Nếu không thì ñặt β = θ và quay lại bước 2.Bước 3: Gán bước vượt khe là β.1.2. Hướng tìm kiếmHướ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àinhấ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êucầ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ềukiệ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ìnhtì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ìbất ñẳng thức sau ñược nghiệm ñúng:s , ∇J ( x ) < 0(1.8)ð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à gradiencủ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 ...