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 chúng tôi 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.
Bạn đang xem 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ộc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung 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ộc
![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 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](https://s1.tailieubachkhoa.net/rl6k7x3q9zfh00j8/thumb/2024/01/09/phuong-phap-vuot-khe-huong-phan-giac-giai-bai-toan-quy-hoach_KRfggNBKcc.jpg)
241 TẠP CHÍ KHOA HỌC, ðại học Huế, Số 65, 2011 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 Bùi Minh Trí, Trường ðại học Bách khoa Hà Nội Nguyễn Vũ Tiến, ðại học Huế TÓM TẮT 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 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. 1. Nguyên lý tối ưu hóa vượt khe và hướng tìm kiếm 1.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 x J x →∞ = ∞ (1.2) 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 S k , 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; Sk là 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ểu 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 ñ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 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ó 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 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 hà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ặp k+1: 242 h(α) = 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ại một giá trị α* > 0 bé nhất sao cho h(α) ñạt cực tiểu: α* = 0 min ( )arg h α α > (1.5) Nếu h(α) khả vi liên tục, ta có ñịnh nghĩa bước vượt khe như sau: ( ) ( ) ( )' 0, 0= > ≤v vh h hα αα α (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 xk ñế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 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 hướng sk theo quan hệ xk+1 = xk + αsk, thực hiện một ñộ dài bước α = αv ≥ α*. ðồ thị này 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 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, 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ước 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á 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: αv > α* = 0 min ( )arg h α α > , h(αv) – h* ≤ λ[h0 – h*] (1.7) trong ñó, 0 < λ < 1 gọi là hệ số vượt; h* = h(α*); h0 = h(α0). h0 h (α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ước 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 243 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 ñị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ển sang 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ếm 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 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 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 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 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ì 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à gradien 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 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 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 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ì 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 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 chuyển ñộng cơ bản ñược sử dụng trong thuật toán vượt khe. 244 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: a b d a b = + (1.9) trong ñó, àa v b là ñộ dài của véc tơ a, b. 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. 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ơ 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 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 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 trường hợp nhanh hơn hẳn thuật toán gradient kiểu hạ nhanh nhất. 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 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 toán tối ưu phi tuyến có ràng buộc min { J ( x ) | gi ( x ) ≤ 0; i = 1,, m; x∈ Rn } trong ñó , J(x) là hàm mục tiêu bị chặn dưới và thoả mãn ñiều kiện: lim ( ) x J x →∞ = ∞ các hàm gi ( x ) là các hàm lồi. 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 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 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 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 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 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 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 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ó ràng buộc. Với các thông số khởi tạo như sau: γ = 0,1, a = 0,5 Bước lặp thứ 1: S0 = − ∇ J ( x0 ). Xác ñịnh bước vượt khe λ0 theo hướng di chuyển S0. 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 chính: Giai ñoạn 1. Tính gradient ∇ J (xk) và xác ñịnh hướng cải tiến ñược Sk (theo 245 hướng ñó hàm mục tiêu cực tiểu hóa giảm ). Ở ñây có hai khả năng: + 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 giác; + 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 - Kuhn - Tucker không ñược thỏa mãn nên hệ sau chắc chắn có nghiệm: ( ) ( ) ( ) , 0 , 0, k k k k k i J x S g x S i I x ∇ 〈 ∇ 〈 ∈ I ( xk ) = { i ∈{ 1,, m }| gi ( xk ) = 0 } (xem [3, 4]) Bằng việc giải hệ trên ta sẽ có hướng di chuyển cải tiến ñược Sk. 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 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 ñộ 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 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 nhận ñược phương án mới: xk+1 = xk + αk+1S k 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. 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 Karush - Kuhn - Tucker: ( ) ( ) ( )1 2 3, ,+ +∇ ≤ − ≤ − ≤k k n k k n kJ x x x J x J xε ε ε 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 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 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 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 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ó 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ệ thống thời gian thực. 2.2. Thuật toán vượt khe hướng phân giác và tiêu chuẩn hội tụ 2.2.1. Thuật toán Gọi C = { x | gi ( x ) ≤ 0 }, int C ≠ ∅ . Giả sử ñã chọn ñược ñiểm x0 ∈ C, dãy ñ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: xk+1 = xk + αk+1S k, k = 0,1, Trong ñó, αk+1 là bước vượt khe có ñiều chỉnh, Sk là véc tơ hướng chuyển ñộng 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: 246 Hình 2. Sơ ñồ của các phương pháp vượt khe có ràng buộc Bắt ñầu 0),(, 00 =∈ kxJCx Kiểm tra ñiều kiện tối ưu Dừng Thỏa mãn Xác ñịnh hướng di chuyển Sk Hướng cải tiến ñược Xác ñịnh bước vượt khe vkk αα =−1 Kiểm tra các ràng buộc Thỏa mãn ðiều chỉnh bước di chuyển ñạt tới biên của miền ràng buộc Chuyển tới phương án mới kkkk S11 ++ += ααα Vi phạm 247 + Nếu xk+1 là một ñiểm trong của C, thì: k k kk SxJS 1 11 )( + ++ +−∇= β k ∈ I1 ∨ ( )( 1k kS J xγ += ∇ ; γ > 0 ) k ∈ I2 ∧ ( )( )1 , 0k kJ x S+∇ ≤ (2.1) k ∈ I2 ∧ ( )( 1 ,k kJ x S+∇ > 0 ) trong ñó, I1 là tập các chỉ số k = 0, r, 2r,, với r là số nguyên dương cho trước, gọi là chu kỳ khôi phục; I2 = { 0, 1, 2,} \ I1. + Nếu xk là một ñiểm trên biên của C, thì Sk ñược xác ñịnh từ các hệ thức: ( ) ( ) ( ) ( ) { } ( ){ } , 0 , 0, 1,..., 0 k k k k k i k k i J x S g x S i I x I x i m g x ∇ < ∇ < ∈ = ∈ = (2.2) Vì xk chưa là ñiểm tối ưu nên theo ñiều kiện Karush – Kuhn – Tucker hệ có nghiệm. ðể tăng ñộ bám khe của hàm mục tiêu, qua mỗi chu kì nhất ñịnh hướng chuyển ñộng ñược khởi tạo lại bằng cách cho hệ số lái bằng βk = 0. 2.2.2. Tiêu chuẩn hội tụ của thuật toán. Bổ ñề 1. (Hướng giảm) Giả sử ( ) 0kJ x∇ > khi ñó ta có: ( )0 à , 0> ∇ <k k kS v J x S . Chứng minh: 1. Nếu xk ∈ int C, giả sử ( ) 0kJ x∇ ≠ , ta cần chứng minh rằng Sk ≠ 0. Ta nhận thấy: a. Nếu 1,k I∈ hoặc ( )1k kS J xγ += ∇ thì ( )k kS J x= −∇ . Khi ñó: ( ) 2 , 0k k kS S J x= ∇ 〉 . Vậy Sk ≠ 0. ( ) ( ) ( ) 1 1 21 1 0 2 , + + + + ∇ = ∇ 〈∇ 〉 k k k k k k J x S J x J x S β 248 b. Trong trường hợp 2.k I∈ TH1: Nếu ( ) 1, 0k kJ x S −∇ ≤ , khi ñó, nếu Sk = 0, theo ñịnh nghĩa thuật toán, ta có: ( ) ( ) ( ) ( ) ( ) 2 1 10 , , , 0k k k k k k k kk kJ x S J x J x S J x J x Sβ β − −=− ∇ =− ∇ − + = ∇ − ∇ 〉 Mâu thuẫn, vậy 0kS ≠ . TH2: Nếu ( ) 1, 0k kJ x S −∇ 〉 , giả sử Sk = 0. Khi ñó: ( ) ( ) ( ) ( ) ( ) 2 1 10 , , ,k k k k k k k kk kJ x S J x J x S J x J x Sβ β − −=− ∇ =− ∇ −∇ + = ∇ − ∇ ( ) ( ) ( ) 22 2 1 1 ( ) , 0 22 , , − − ∇∇ = ∇ − ∇ = 〉 ∇ kk k k k k k J xJ x J x J x S J x S Mâu thuẫn, vậy 0kS ≠ . Từ các công thức trên, ta cũng luôn thấy rằng ( ) , 0k kJ x S∇ 〈 . Hay nói cách khác Sk luôn là hướng giảm của hàm ( )J x . 2. Nếu kx C∈∂ , thao ñịnh nghĩa của hướng Sk trong trường hợp này ta có: ( ), 0k kJ x S∇ < ( ), 0, ( )k k kig x S i I x∇ < ∈ { }{ }( ) 1,..., ( ) 0k kiI x i m g x= ∈ = Vậy hiển nhiên ta có ñiều phải chứng minh. Bổ ñề 2. (ðiều kiện vượt khe) Giả sử J(x) có ñạo hàm liên tục và bị chặn dưới và tập hợp M(x0) = { }0( ) ( )x j x j x≤ giới nội. Khi ñó ñiều kiện: ( ) 0 k k kd J x S d α α α α = + > (2.3) luôn luôn ñược thực hiện trong M(x0), M(x0) ⊃ { }( ) 0x J x∇ = . Chứng minh: Theo ñiều kiện của bổ ñề thì J(x), do ñó gk(α ) = J(xk+α Sk) bị chặn dưới và có ñạo hàm liên tục trong En, nên sẽ có ñiểm dừng thuộc M(x0). Giả sử ñiểm dừng ñó là α d. Ta giả thiết phản chứng rằng không tồn tại ñiều kiện (2.3) với α >α d tức là với dα α∀ ≥ ta ñều có bất ñẳng thức: 249 ( ) 0 dk d g d α α α α ≥ ≤ Có nghĩa là gk(α ) không tăng với dα α∀ ≥ . ðiều này dẫn ñến kêt quả là trên khoảng ( ,dα ∞ ) hàm số gk(α ) = J( k kx Sα+ )≤ J(xk)≤ J(x0). Như vậy, nửa ñường thẳng [ ,dα ∞ ) cũng phải thuộc tập hợp M(x 0). Vậy (2.3) tồn tại. Bổ ñề 3. (Tồn tại bước vượt khe) Nếu hàm J(x) có ñạo hàm liên tục, bị chặn dưới thì tồn tại ít nhất một giá trị α > 0 thỏa mãn: ( ) 0k k d J x S d α α + ≥ J( k kx Sα+ )≤ J( 1 k kx Sε+ ) với 1ε > 0 Chứng minh: Kí hiệu gk(α ) = J( k kx Sα+ ), theo yêu cầu của bổ ñề ta phải chứng minh: ( ) 0k d g d α α ≥ ; 1( ) ( )k kg gα ε≥ Do J(x) bị chặn dưới ta giả sử *kα là ñiểm dừng gần nhất của hàm một biến ( )kg α . Chọn 1ε ñủ bé *(0, )kα∈ sao cho: * 1(0) ( ) ( )k k k kg g gε α> > Ta có thể chọn ñược 1ε như vậy vì rằng: 2 1 1 1 1(0) ( ) ( ) ( ) ( ), 0( ) k k k k k k kg g J x J x S J x Sε ε ε ε− = − + = − ∇ + > 0 Do *kα là ñiểm dừng nên tồn tại ñoạn [ * kα , ** kα ] sao cho: * ** 1( ) ( ) ( )k k k k kg g gα α ε≤ ≤ Như vậy, trong ñoạn [ *kα , ** kα ] tồn tại ít nhất một ñoạn [ ],β γ ⊂ [ *kα , **kα ] mà trên ñó hàm ( )kg α không giảm. Vậy, trên ñoạn ñó ta có: ( ) 0k d g d α α ≥ ** 1( ) ( ) ( )k k k kg g gα α ε≤ ≤ ðịnh lý. (Hội tụ) Giả sử J(u) là hàm trơn bị chặn dưới trên C và ( )J u∇ thỏa mãn ñiều kiện Lipshits với hằng số L. Cho x0 C∈ là ñiểm tùy ý ñã chọn, khi ñó tồn tại dãy con của dãy ñiểm {xk} xây dựng theo thuật toán tựa phân giác, hội tụ tới ñiểm tối ưu ñịa phương của J(x), và ( )1lim ( ) ( ) 0k k k J x J x + →∞ − = . 250 Chứng minh: Theo thuật toán TPG và ñiều kiện chọn bước ta có: J(xk ) – J(xk+1 ) = 1 0 ( ),− ∇ +∫ k k kk kJ x t S S dtα α ðặt ( ) ( )k kg J x Sα α= + , theo hệ thức trong giải tích cổ ñiển 1 ' ' 0 ( ) (0) ( ) ( )− = = ∫g g g g t dtα θα α α ). Tiếp tục khảo sát vế phải ra có: 1 0 ( ),k k kk kJ x t S S dtα α− ∇ + =∫ 1 0 , ( ) , ( ) ( ),k k k k k k kk k k kS J x S J x J x t S S dtα α α α= − ∇ + ∇ − ∇ +∫ 1 0 , ( ) ( ) ( ),k k k k k kk k kS J x J x t S J x S dtα α α= − ∇ − ∇ + −∇∫ 1 0 , ( )k k k kk k kS J x L t S S dtα α α≥ − ∇ − ∫ 221 22 0 , ( ) , ( ) 2 k kk k k k k k k k L S S J x L S tdt S J x α α α α= − ∇ − =− ∇ −∫ 2 , ( ) 1 2 , ( ) k k k k k k k SL S J x S J x α α = − ∇ + ∇ sử dụng hệ thức ở TH2 Bổ ñề 1 ta có ( ), ( ) 1 2 , ( ) 1 2 = − ∇ − = − ∇ − k k k kk k k k L S J x S J x L α α α α 1 2 , ( ) 1k k L S J x L ε ε ≥ − ∇ − = + (vì 0 < 1ε ≤ α k≤ 21 ( )Lε + ), (xem [1]) 1 2 2 , ( ) 0k kS J x L ε ε ε = − ∇ > + Từ ñây, kết hợp với Bổ ñề 1 suy ra dãy số { ( )kJ x }, k →∞ ñơn ñiệu giảm. Nhưng vì inf ( ) k n k u E J x ∈ > −∞ nên theo ñịnh lý Bolzano - Weierstrass dãy { ( )kJ x } phải có một giới hạn J* nào ñó và tồn tại một dãy con của {xk} hội tụ ( )1lim ( ) ( ) 0k k k J x J x + →∞ − = . 251 2.2.3. Các ví dụ minh họa Ví dụ 1: 2 2 1 2 2 2 1 2 1 2 ( ) min ( 3) ( 2) 1 , 0 J x x x x x x x = + → − + − ≤ ≥ Phương án tối ưu là * 3( 13 1) 2( 13 1) , (2.167949,1.445299) 13 13 x − − = ≈ J(x*) = ( 13 1)− 2 6.78889≈ Phương án xuất phát: x0 = (3,1.1); J(x0) = 10.21 Bước lặp 1: Hướng di chuyển thoát biên S0 = 0 1.877753 ( ) 0.688509 J x − −∇ = − Bước vượt khe: 1 1.68834375λ = Bước di chuyển ñiều chỉnh : 1 0.112117α = Phương án mới: x1 = 2.7894728 1.0228067 , J(x1)=8.827292 Bước lặp 2: Hướng di chuyển thoát biên: S1 = 0.398322 0.597484 − Bước vượt khe: 2 1.1255625λ = Bước di chuyển ñiều chỉnh : 2 2 1.1255625α λ= = Phương án mới: x2 = 2.341135 1.6953128 , J(x2)=8.355000 Bước lặp 12 thì dừng và kết quả là x2 = 2.168201 1.445554 , J(x2)=6.7907219. Ví dụ 2: Xét bài toán tìm cực tiểu hàm Rosenbrock 2 2 2 1 2 1 2 2 1 2 2 ( ) (1 ) ( ) min 2 0 J x x x x x x x = − + − → + ≤ ≥ 252 ( ) 0.005kJ x∇ ≤ Phương án tối ưu là x* = (1,1) ; J(x*) = 0. Phương án xuất phát: x0 = (-1, 1) ; J(x0) = 4. Giả sử ñiều kiện dừng bước là : ( ) 0.005kJ x∇ ≤ Bước lặp 1: Hướng di chuyển thoát biên S0 = 0.25 0.25 − Bước vượt khe : 1 5.695597λ = Bước di chuyển ñiều chỉnh : 1 3.99915α = Phương án mới : x1 = 0.0002113 0.0002113 − , J(x1)=1.000423 Bước lặp 2: Hướng di chuyển thoát biên S1 = 0.500105 1 Bước vượt khe : 2 0.586139λ = Bước di chuyển ñiều chỉnh : 2 2 0.586139α λ= = Phương án mới : x2 = 0.292920 0.586350 , J(x2)=0.750510 Bước lặp 324: ta có 324 324 0.000965 ( ) 0.000550 ( ) 0.001 0.005 J x J x − −∇ = ∇ = ≤ Do ñó thuật toán dừng và kết quả là x324 = 0.999842 0.99967 , J(x324)=2.4910289E-8. 253 TÀI LIỆU THAM KHẢO [1]. Nguyễn Văn Mạnh, Bùi Minh Trí, Phương pháp tựa phân giác giải bài toán tối ưu hóa không ñiều kiện, Tạp chí Toán học, tập XV, số 4 (12/1987). [2]. Nguyễn Văn Mạnh, Bùi Minh Trí, Method of "clef-overstep" by perpendicular for solving the unconstraines nonlinear optimization problem, Acta Mathematica Vietnamica, vol. 15, N0 2/1990. [3]. Poliak B.T, Nhập môn Tối ưu hóa, Nxb Khoa học, Moskva, 1983 (Tiếng Nga). [4]. Stephen G. Nash, Ariela Sofer, The Linear and Non-linear Programming, The McGraw-Hill Companies, Inc. 1996. [5]. Bùi Minh Trí, Quy hoạch toán học, Nxb Khoa học và Kỹ thuật, Hà Nội, 2001. [6]. Hoàng Tụy, Lý thuyết tối ưu, Nxb Khoa học và Kỹ thuật, Hà Nội, 2003. THE ALGORITHM OF CLEFT OVERSTEP BY BISECTOR DIRECTION FOR SOLVING THE PROBLEM OF NON-LINEAR MATHEMATICAL PROGRAMMING WITH CONSTRAINS Bui Minh Tri Hanoi University of Science and Technology Nguyen Vu Tien, Hue University SUMMARY In this paper, based on the principe of “cleft – overstep” we establish an algorithm for solving the problem of non-linear mathematical programming with constrains: The algorithm of “cleft overstep” by bisector direction. The theorem of convergence is presented and proved. The illustrative examples are presented.
File đính kèm:
phuong_phap_vuot_khe_huong_phan_giac_giai_bai_toan_quy_hoach.pdf