ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN - CƠ - TIN HỌC

Nguyễn Trường Giang

BÀI TOÁN QUY HOẠCH PHI TUYẾN
CÓ RÀNG BUỘC

LUẬN VĂN THẠC SĨ KHOA HỌC

Chuyên ngành: Toán - Giải tích
Mã số: 60.46.01.02

Người hướng dẫn: PGS.TS. Nguyễn Hữu Điển

Hà Nội - 2014


BẢNG KÝ HIỆU
Ký hiệu

Ý nghĩa

DFP

Davidon- Fletcher- Powell

QHPT

Quy hoạch phi tuyến


1


LỜI CẢM ƠN

Để hoàn thành bản luận văn này tôi đã nhận được sự giúp đỡ to lớn của Thầy,
Cô giáo, gia đình và bạn bè xung quanh.
Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS
Nguyễn Hữu Điển, Khoa Toán- Cơ- Tin học, Trường Đại học khoa học tự nhiên,
ĐHQG Hà Nội. Trong quá trình giảng dạy và hướng dẫn đã ân cần động viên, giúp
đỡ chỉ bảo tận tình cho tôi.
Tôi cũng gửi lời cảm ơn tới các thầy cô trong Khoa Toán- Cơ- Tin học, Phòng
sau đại học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội đã dạy dỗ và giúp
đỡ tôi rất nhiều trong suốt quá trình học tập và nghiên cứu luận văn. Đặc biệt là
các thầy cô trong Seminar của bộ môn Toán giải tích đã có những ý kiến đóng góp
quý báu giúp cho bản luận văn hoàn chỉnh hơn.
Cuối cùng tôi cũng xin gửi lời cảm ơn tới gia đình nơi đã sinh thành, nuôi nấng,
giúp đỡ, động viên tôi rất nhiều trong suốt thời gian qua.
Dù đã cố gắng hết sức nhưng luận văn không thể tránh khỏi những thiếu sót
và hạn chế. Mọi ý kiến đóng góp tôi xin được đón nhận với lòng biết ơn và trân
trọng sâu sắc.
Hà Nội, ngày 29 tháng 10 năm 2014
Học Viên

Nguyễn Trường Giang

2




29

2.1.1. Giới thiệu chung về QHPT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.1.2. Bài toán QHPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.1.3. Các vấn đề cần giải quyết khi giải bài toán QHPT . . . . . . . . . . . . . . . . . . . . . . .

31

2.2. Tuyến tính hóa ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.2.1. Bài toán và hướng giải quyết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.2.2. Thuật toán siêu phẳng cắt Kelley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.2.3. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

52

2.3.5. Chương trình giải ví dụ thuật toán Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . .

54

KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

4


LỜI MỞ ĐẦU
Tối ưu hóa là một trong những lĩnh vực kinh điển của toán học, có ảnh hưởng
đến hầu hết các lĩnh vực khoa học- công nghệ và kinh tế- xã hội. Trong thực tế, việc
tìm giải pháp tối ưu cho một vấn đề nào đó chiếm vai trò rất quan trọng. Phương
án tối ưu là phương án hợp lý nhất, tốt nhất, tiết kiệm chi phí, thời gian, tài nguyên,
nguồn nhân lực mà lại cho tiệu quả cao.
Những năm gần đây nhiều bài toán thực tế được giải quyết bằng phương pháp
mô hình hóa toán học rất thành công. Trong số các mô hình toán học được áp dụng
có nhiều mô hình tối ưu được giải quyết thông qua các bài toán tối ưu kinh điển.
Bài toán tối ưu được phát biểu như sau:
Cho D ∈ Rn , D = ∅ với Rn là không gian vector và hàm f : D → R tùy ý. Tìm
giá trị cực tiểu của hàm f ( x ) khi x ∈ D nghĩa là bài toán tìm vector w thuộc vào
tập D sao cho với mọi giá trị của x thuộc D thì

chọn được phương pháp phù hợp cho từng bài toán thực tế.
Đầu tiên, phương pháp hình học được coi là phương pháp đơn giản để tìm
nghiệm tối ưu cho bài toán cực trị cỡ nhỏ với thuật toán như sau
Bước 1. Vẽ miền chấp nhận được D của bài toán (1). Nếu miền D rỗng thì kết
luận bài toán (1) vô nghiệm.
Bước 2. Vẽ mặt mức f ( x1 , ..., xn ) = α với α ∈ R.
Bước 3. Giảm dẫn mức α (tăng dẫn mức α) để xác định mặt mức thấp nhất hay
xác lập bài toán không giải được do hàm mục tiêu f giảm vô hạn trện D.
6


Bước 4. Nếu bài toán giải được thì tìm một điểm thuộc D mà mặt mức thấp nhất
đi qua nó. Điểm tìm được chính là nghiệm tối ưu của bài toán (1) và tính giá
trị hàm mục tiều f tại điểm vừa tìm được ta có f min .
Nhóm phương pháp tiếp theo với ý tưởng đưa bài toán quy hoạch có ràng buộc
về bài toán quy hoạch không ràng buộc, bằng cách thay t hế hàm mục tiêu ban đầu
f ( x ) bởi hàm mục tiêu mở rộng F ( x, r ) chứa thông số r và có tính đến các ràng
buộc. Giá trị của hàm mục tiêu mở rộng phải trùng với giá trị hàm mục tiêu ban
đầu và khi ra ngoài miền ràng buộc thì giá trị hàm mục tiêu mở rộng khác với giá
trị hàm mục tiêu ban đầu. Khi x → w dẫn đến F (w, r ) → f (w). Với mỗi tập ràng
buộc khác nhau ta có hàm mục tiêu mở rộng F ( x, r ) được chọn khác nhau, do đó
ta cũng có các phương pháp khác nhau.
Phương pháp nhân tử Lagrange. Phương pháp này thường được dùng để tìm
cực trị của hàm với các ràng buộc đẳng thức và hàm mục tiêu mở rộng cũng
được xây dựng bởi hàm Lagrange như sau
m

L( x, r ) = f ( x ) + ∑ λ j g j ( x ),
j =1


∑ gj (x) ,

j =1

• dấu ” + ” khi tìm min f ( x )
• dấu ” − ” khi tìm max f ( x )
• rk nhân tử ở bước lặp thứ k
• w j trọng số.
Phương pháp Fiacco và Cormick. hàm mục tiêu f ( x ) → min(max) với ràng buộc
• gi ( x ) ≥ 0 với i = 1, n.
• h j ( x ) = 0 với j = 1, m.
Hàm mục tiêu mở rộng được xây dựng có dạng
n

F ( x, r ) = f ( x ) ± r ∑

i =1

−1
1
±r 2
gi ( x )

m

∑ h j 2 ( x ).

j =1

Phương pháp chọn r0 đối với F ( x, r ) → min .

Phương pháp Pietrzykoski. Hàm mục tiêu f ( x ) → min(max) với ràng buộc
• gi ( x ) ≥ 0 với i = 1.n,
8


• h j ( x ) = 0 với j = 1, m.
Hàm mục tiêu mở rộng
m

n

j =1

i =1

F ( x, r ) = r f ( x ) − ∑ h j 2 ( x ) − ∑ wi gi 2 ( x ).
Trong đó
• wi = 1 đối với gi ( x ) ≥ 0,
• wi = 0 đối với gi ( x ) < 0.
Tiếp theo là phương pháp Sai lệch linh hoạt. Ý tưởng cơ bản của phương pháp
này là mở rộng miền ràng buộc bằng cách đưa hàm T ( x ) là tổ hợp các ràng buộc.
Như vậy bài toán (1) được đưa về dạng
• Tìm cực tiểu của f ( x ) với x ∈ Rn .
• Thỏa mãn ràng buộc φ(k) − T ( x ) ≥ 0.
• Sai lệnh này so với ràng buộc ở bước lặp thứ k là

r +1

 φ(k) = min φ(k−1) , mr++11 ∑ xi (k) − xc (k)



1
2

.


Trong đó ui = 0 khi gi ( x ) ≤ 0, ngược lại ui = 1. Khi quá trình tìm kiếm gần điểm
cực tiểu thì φ(k) → 0 và T ( x ) = 0 hay hi ( x ) = 0 và gi ( x ) ≤ 0.

Nhóm phương pháp cuối cùng là phương pháp tuyến tính hóa. Bằng cách thay
đổi giả thiết của bài toán (1) thành bài toán tối ưu lồi với hàm mục tiêu tuyến tính.
f ( x ) → min với x ∈ D = x ∈ Rn : gi ( x ) ≤ 0, i = 1, m ,

(2)

trong đó D là một tập lồi compact, khác rỗng và gi ( x ) là các hàm lồi khả vi trên
Rn .
Để giải bài toán (2) thì năm 1960 Kelley đã đề xuất phương pháp với tên gọi là
phương pháp Siêu phẳng cắt Kelley với ý tưởng tuyến tính hóa ràng buộc.
Tương tự, thay đổi giả thiết của bài toán (1) thành bài toán tối ưu lồi với ràng buộc
tuyến tính như sau
f ( x ) → min với x ∈ D = { x ∈ Rn : Ax ≤ b, x ≥ 0} ,

(3)

trong đó
• f ( x ) là hàm lồi.
• A là ma trận cấp m × n.
• b ∈ Rm .

1.1.

Một số khái niệm cơ sở

Định nghĩa 1.1. [Tập lồi][9] Tập D ⊂ Rn được gọi là tập lồi nếu nó chứa trọn đoạn
thẳng nối hai điểm bất kỳ thuộc nó. Hay nói cách khác D lồi nếu (1 − λ) a + λb ∈ D
với mọi a, b ∈ D, 0 ≤ λ ≤ 1.
Định nghĩa 1.2. [Tổ hợp lồi][9] Cho x1 , ..., x m là các vector trong không gian vector
Rn , gọi
m

m

∑ λi x , ∑ λi = 1, λ ≥ 0,
i

i =1

là tổ hợp lồi của các vector

i =1

x1 , x2 , ..., x m .

Mệnh đề 1.1. Các tính chất của tập lồi
• Tổng đại số hữu hạn tập lồi là tập lồi.
• Giao của họ các tập lồi là tập lồi.
• Tích đề các của các tập lồi là tập lồi.
• Ảnh và nghịch ảnh của tập lồi qua ánh xạ tuyến tính cũng là lồi.
• D=

tập lồi chưa D hay nói cách khác bao lồi của D là tập lồi nhỏ nhất chưa D. Bao lồi
của D ký hiệu là co ( D ), hoặc conv( D ).
Định nghĩa 1.5. [Hàm lồi][9] Hàm f ( x ) xác định trên tập lồi D được gọi là hàm lồi
nếu

∀ x, y ∈ D, ∀λ ∈ [0, 1] : f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ) f (y) ,
nếu bất đẳng thức trên là thực sự thì với ∀λ ∈ [0, 1] thì hàm f được gọi là lồi chặt.
Hàm lồi có rất nhiều tính chất giải tích quan trọng, ta quan tâm đến các tính
chất tối ưu hóa sau
• Cực tiểu địa phương là cực tiểu toàn cục.
• Tập mức dưới L(α, f ) = { x ∈ D : f ( x ) ≤ a} là hàm lồi.
• Điểm dừng là điểm cực tiểu toàn cục.
• Nếu D là tập compact thì hạm đạt cực đại ít nhất một lần ở điểm cực biên.
Ví dụ 1.1 (Kiểm tra hàm lồi). Kiểm tra hàm f : D ≡→, x → f ( x ) = x2 là hàm lồi?
Thật vậy, dễ thấy D là tập lồi. ∀ x, y ∈ D, ∀λ ∈ [0, 1] thì f (λx + (1 − λ) y) ≤
λ f ( x ) + (1 − λ ) f ( y ) .
Định nghĩa 1.6. [Hàm khả vi][10] Giả sử hàm f xác định tại lân cận 0( x, ε) của
điểm x. Ta nói hàm f là khả vi tại điểm x nếu tìm được vector f ( x ) ∈ Rn sao cho
số gia của hàm số tại x
∆ f ( x ) = f ( x + ∆x ) − f ( x ), ∆x ≤ ε ,
13


có thể được viết lại
∆ f ( x ) = f ( x + ∆x ), f ( x ) + o ( x, ∆x ),
trong đó o ( x, ∆x ) là vô cùng bé bậc cao hơn ∆x ≤ ε nghĩa là
o ( x, ∆x )
=0
∆x
→0

• A được gọi là nửa xác định âm nếu x t Ax ≤ 0 với mọi vector x ∈ Rn .
• A được gọi là xác định âm nếu x t Ax 0 sao cho f (w) ≤ f ( x ) với x ∈ D và
x − w < ε.

1

f ( x + y) − f ( x ) = f ( x + αy), y =

f ( x + ty), y dt.
0

1.2.

Điều kiện tối ưu

Như chúng ta đã biết thì đối với một bài toán qui hoạch nói chung và bài toán
qui hoạch phi tuyến có ràng buộc hiển nói riêng thì việc xét điều kiện để tìm xem
bài toán đó có nghiệm hay không được coi là việc đầu tiên trong quá trình giải
quyết bài toán đó. Vì thế, việc tìm hiểu về những điều kiện để có nghiệm tối ưu
cho bài toán QHPT có ràng buộc là rất quan trọng. Ta xét bài toán sau.
Cho không gian vector Rn cho f : D → R là một hàm tùy ý xét bài toán tối ưu
ràng buộc hiển sau đây
f ( x ) → min,

(1.1)

gồm các điều kiện


 gi ( x ) ≤ 0 với i = 1, m,

 h j ( x ) = 0 với j = 1, p.
Trước khi xét về các điều kiện tối ưu cho bài toán trên ta có các định nghĩa được bổ
sung dưới đây.


∇hi (w0 )d = 0, j = 1, p,




 I ( x 0 ) = i : g ( w0 ) = 0 .
i

(1.2)

Khi đó, ký hiệu S(w0 ) gọi là nón chấp nhận được tuyến tính hóa.
Bổ đề 1.1. Cho tập D là tập con không thực sự trong không gian vector Rn .Lấy điểm
w0 ∈ D. Nếu mọi hàm gi và h j khả vi tại x0 và S(w0 ) là nón chấp nhận được tuyến tính
hóa thì
FD (w0 ) ⊆ TD (w0 ) ⊆ S(w0 ).
17


Chứng minh. Lấy bất kỳ d ∈ TD (w0 ). Nếu d = 0 rõ ràng d ∈ S(w0 ). Giả sử d = 0.
Theo định nghĩa (1.2.2) ta có dãy wk
dk =

( w k − w0 )
tk

∈ D, wk → w0 và dãy tk

0 sao cho


sao cho gi (v) < 0 với mọi i mà gi không phải là hàm afin.
Bổ đề 1.2. (Bổ đề Farkas) [10] Trong không gian vector Rn cho trước vector p và A là
ma trận cấp m × n. Muốn cho py ≥ 0 với mọi y nghiệm đúng Ay ≥ 0 khi và chỉ khi tồn
tại vector v ∈ Rm sao cho v ≥ 0 và p = A T v (p biểu diễn được dưới dạng tổ hợp tuyến
tính không âm các vector hàng của A).
Chứng minh. Ta sẽ lần lượt chúng minh chiều xuôi (điều kiện cần) và chiều ngược
(điều kiện đủ).
• (Chiều xuôi) Giả sử trong không gian vectorRn cho trước vector p được định
nghĩa p = A T v và v ≥ 0. Khi đó, với mọi y thỏa mãn Ay ≥ 0 ta sẽ có
py = A T vy = vAy ≥ 0.
• (Chiều ngược) Đặt G =

z ∈ Rn : ∃v ≥ 0, z = A T v , ta thấy rằng G là một

nón lồi đa diện (z ∈ G ⇒ λz ∈ G, z1 , z2 ∈ G ⇒ z1 + z2 ∈ G ). Giả sử p ∈
/G
ta sẽ chỉ ra tồn tại r thỏa mãn Ar ≥ 0 nhưng pr < 0. Thật vậy, nếu gọi q là
hình chiếu của p trên G thì q = infc∈G c − p (q là điểm thuộc C gần p nhất).
Điểm q tồn tại do G lồi đóng. Đặt r = q − p(r = 0 do p = q) hay p = q − r. ta
thấy hai điều như sau
Điều 1. r (z − q) ≥ 0. Vì nếu ngược lại thì trên đoạn nối liền z với q sẽ tìm
được một điểm nằm gần p hơn q và do điểm này thuộc G nên điều này
trái với q là hình chiếu của p (q là điểm thuộc G gần p nhất).
Điều 2. r (z − q) = 0, vì nếu ngược lại thì trên đường thẳng nối q với gôc tọa
độ tìm được một điểm nằm gần p hơn q và do điểm này thuộc G nên
điều này trái với giả thiết q là hình chiếu của p (q là điểm thuộc G gần p
nhất).
19



λi ∇ gi (w) = 0; λi ∗ ≥ 0, i = 1, m,



g (w) ≤ 0, i = 1, 2, ..., m,


 i



 h j (w) = 0, j = 1, p.

(KKT)

Chứng minh. Do w là điểm cực tiểu địa phương nên ta có f (w)d ≥ 0 với mọi
d ∈ TD (w). Lại do w là điểm chính qui ( tức là TD (w) = S(w)) nên bất đẳng thức
này đúng với mọi d ∈ S(w), nghĩa là với mọi d ∈ Rn là nghiệm đúng hệ phương
trình (1.2) với w thay cho w0 .
Áp dụng bổ đề Farkas cho ma trận A và ma trận chuyển vị A T có các cột là

−∇ gi (w), i ∈ I (w), −∇h j (w), −∇h j (w), j = 1, m,
20


ta tìm được các số thực λi∗ ≥ 0(i ∈ I (w)), α j ≥ 0, β ≥ 0( j = 1, p) sao cho

∇ f (w) = −

∑

∇ f ( w ) + ∑ λ i ∇ gi ( w ) + ∑ µ j ∗ ∇ h j ( w ) = 0
∗

i =1

j =1

được gọi là điều kiện dừng, bởi ∇ x L( x, λ, µ) = 0, điều kiện tiếp theo là điều
kiện bù và hai điều kiện cuối là điều kiện chấp nhận được.
2. Trường hợp D có thêm ràng buộc xk ≥ 0 với k ∈ K ⊂ {1, 2, ..., n} , tức là
D = x ∈ Rn : gi ( x ) ≤ 0, i = 1, 2, ..., m; h j ( x ) = 0, j = 1, 2, ..., p; xk ≥ 0, k ∈ K ,
thì điều kiện dừng của (KKT ) được đổi thành một trong ba điều kiện sau
p

m
∂h j ( x ∗ )
∂g ( x ∗ )
∂ f (x∗ )
+ ∑ λi i
+ ∑ µj
= 0, ∀k ∈
/ K,
∂xk
∂xk
∂xk
i =1
j =1

21


∂xk
∂xk
i =1
j =1

= 0, ∀k ∈ K,

còn hai điều kiện đủ và chấp nhận được là không thay đổi.
Tiếp sau điều kiện cần cấp 1 đó là điều kiện đủ hay còn được goị là điều kiện
đủ cho bài toán qui hoạch lồi.
Định lý 1.3. (Điều kiện đủ cấp 1) [10]Trong không gian vector Rn cho một tập mở
chứa D. Giả sử f , gi , i = 1, m là các hàm lồi, khả vi liên tục trên D và h j , j = 1, p là các
hàm afin. Ta xét bài toán qui hoạch lồi
f ( x ) → min,
có điều kiện



 gi ( x ) ≤ 0 với i = 1, m,

 h j ( x ) = 0 với j = 1, p.

Giả sử w là một điểm chấp nhận được của bài toán trên (tức là thỏa mãn điều kiện chấp
nhận được trong (KKT )).Lúc này, nếu tồn tại vector λ∗ = (λ1∗ , λ2∗ , ..., λ∗m ) T ≥ 0 và µ∗ =

(µ1∗ , µ2∗ , ..., µ∗p )T thỏa mãn điều kiện dừng và điều kiện đủ của (KKT ) thì w là nghiệm cực
tiểu của bài toán qui hoạch lồi trên.
Chứng minh. Ta chứng minh phản chứng bằng cách giả sử ngược lại là w không
phải là nghiệm cực tiểu thì có x ∈ D sao cho f ( x ) < f (w). Đặt d = x − w = 0. Từ
giả thiêt hàm f lồi nên ta có


p
m

∗

∇
f
(
w
)
+
λ
∇
g
(
w
)
+
µ j ∗ ∇h j (w) = 0,
∑
∑

i
i


i =1
j =1



(*)

∃d ∈ TD (w) sao cho ∇ f (w)d < 0,

(**)

Còn nếu

thì w không thể là cực tiểu địa phương của bài toán. Các kết quả này cho biết khi
một trong hai điều kiện (∗) hoặc (∗∗) được thỏa mãn thì có thể dùng điều kiện tối
ưu cấp một để xác định xem tính cực tiểu của điểm w. Chính vì vậy nếu cả hai điều
kiện trên cùng không thỏa mãn thì trong trường hợp này ta cần dùng đến thông
tin đạo hàm cấp hai.
Giả sử w là một điểm thỏa mãn điều kiện Karush- Kuhn- Tucker của bài toán

(1.1) (tức là x ∗ thỏa mãn (KKT )) và λ∗ và µ∗ là vector nhân tử Lagrange tương
ứng. Ký hiệu P(w) là tập xác định theo điều kiên (1.2). Ta xây dụng tập con P0 ( x ∗ )
của P(w) như sau



∇h j (w)d = 0, j = 1, p,



d ∈ P0 (w) ⇔
∇ gi (w)d = 0, gi (w) = 0, λi ∗ > 0,

