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

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.