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í

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 TỐ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 tốn giải bài tốn Quy hoạch phi tuyến cĩ ràng buộc: Thuật tố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 tố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 tốn tối ưu hĩa phi tuyến giải bài tố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 tố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 tốn tối ưu hĩa tương ứng bị tắc lại ở đĩ. Cịn ở đây, quá trình tối ưu hố 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 tố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 tố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 tố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 tố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 tốn cực tiểu hĩa đơn giản, gọi là thuật tốn phân giác vượt khe. Thuật tố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 tốn gradient kiểu hạ nhanh nhất. 2. Phương pháp vượt khe giải bài tố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 tố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 tố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 ngồ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 tố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 tố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 tốn vượt khe hướng phân giác và tiêu chuẩn hội tụ 2.2.1. Thuật tố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 tố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 tố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 tố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 tố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 tố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 thố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 thố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 tố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 thố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 thố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 tố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 tốn tối ưu hĩa khơng điều kiện, Tạp chí Tố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 tốn học, Nxb Khoa học và Kỹ thuật, Hà Nội, 2001. [6]. Hồ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.