ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

NGUYỄN VĂN MẠNH

MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP
BÀI TOÁN TỐI ƯU LỒI MẠNH

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

THÁI NGUYÊN - 2016


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

NGUYỄN VĂN MẠNH

MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP
BÀI TOÁN TỐI ƯU LỒI MẠNH
Chuyên ngành : Toán ứng dụng
Mã số
: 60 46 01 12

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

Người hướng dẫn khoa học:
GS.TSKH. Lê Dũng Mưu



12

1.3.1

Các khái niệm . . . . . . . . . . . . . . . . . . .

12

1.3.2

Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . .

13

1.3.3

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

15

1.4

Tối ưu có ràng buộc

. . . . . . . . . . . . . . . . . . .

16

1.4.1


. . . . . . . . .

30

2.2.1

Thuật toán chiếu dưới đạo hàm

2.2.2

Một thuật toán tách giải bài toán tối ưu lồi mạnh 35

Kết luận

42

Tài liệu tham khảo

43


DANH MỤC CÁC KÍ HIỆU
Kí hiệu

Ý nghĩa

Rn

Không gian Euclide n - chiều trên trường số thực;


ε - dưới vi phân của f theo x.


1

Mở đầu
Bài toán tối ưu hàm lồi mạnh với ràng buộc lồi là lớp bài toán
quan trọng của bài toán quy hoạch lồi. Bài toán này có nhiều ứng dụng
trong các vấn đề thực tế. Ngoài ra đây là bài toán xuất hiện như bài
toán phụ trong các phương pháp giải các bài toán tối ưu lồi tổng quát,
cũng như các bài toán khác như bài toán cân bằng, các mô hình kinh tế,
kĩ thuật. . . Chính vì thế bài toán cực tiểu hàm lồi mạnh là một trong
những vấn đề quan trọng được nhiều nhà toán học trong và ngoài nước
nghiên cứu, nhằm mục đích đưa ra những thuật toán hiệu quả để giải
lớp bài toán này. Trong các phương pháp giải, phương pháp tách có rất
nhiều ưu điểm, đặc biệt phương pháp này cho phép tách các ràng buộc
phức tạp thành các ràng buộc đơn giản dễ tính toán hơn. Vì vậy tôi
thực hiện đề tài Một phương pháp tách giải một lớp bài toán tối ưu lồi
mạnh.
Luận văn được chia làm 2 chương:
Chương 1: Bài toán tối ưu lồi
Chương này trình bày một số kiến thức cơ bản về giải tích lồi, phát
biểu bài toán tối ưu, sự tồn tại nghiệm và điều kiện tối ưu.
Chương 2: Một thuật toán tách giải bài toán tối ưu lồi mạnh.
Chương này trình bày chi tiết về toán tử chiếu lên tập lồi đóng và tính
chất của toán tử chiếu; thuật toán chiếu dưới đạo hàm. Cuối chương
là thuật toán chiếu tách để giải một số bài toán tối ưu lồi mạnh qua
m



3

Chương 1

Bài toán tối ưu lồi
Chương này trình bày một số kiến thức cơ bản về giải tích lồi,
giới thiệu bài toán tối ưu, sự tồn tại nghiệm tối ưu, điều kiện tối ưu như
tối ưu không ràng buộc, tối ưu có ràng buộc và điều kiện tối ưu Kuhn
- Tucker. Nội dung của chương được trích dẫn chủ yếu từ tài liệu tham
khảo [1]; [2]; [3] và [5].

1.1

Kiến thức chuẩn bị
Để thuận tiện cho người đọc, trong phần này ta xét một số khái

niệm và kết quả sẽ được sử dụng trong phần tiếp theo.
Định nghĩa 1.1. Cho hai điểm a, b ∈ Rn . Tập tất cả các điểm x ∈ Rn
có dạng

x = (1 − λ)a + λb , 0 ≤ λ ≤ 1
gọi là đoạn thẳng nối a và b được kí hiệu là [a, b].
Định nghĩa 1.2. Một tập D ⊆ Rn được gọi là tập affine nếu D chứa
trọn cả đường thẳng đi qua hai điểm bất kỳ x, y ∈ D, tức là

∀x, y ∈ D, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ D.
Mệnh đề 1.1. Tập D = ∅ là tập affine khi và chỉ khi nó có dạng

D = M + a, M ⊆ Rn , a ∈ Rn .


k

k

λj xj , λj ≥ 0 (j = 1, ..., k),

x=
j=1

λj = 1.
j=1

Mệnh đề 1.2. Tập hợp D là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi
của các điểm của nó. Tức là, D lồi khi và chỉ khi
k

∀k ∈ N, ∀λ1 , ..., λk ≥ 0 :

k

λj = 1,
j=1

∀x1 , ..., xk ∈ D ⇒

λj xj ∈ D.
j=1



nón pháp tuyến trong của D tại x0 .
(ii) Tập

NDε (x0 ) := {ω ∈ Rn : ω, x − x0 ≤ ε,

∀x ∈ D}

được gọi là nón pháp tuyến ε của D tại x0 .
Ta có 0 ∈ ND (x0 ) (hoặc thực hiện phép dời từ x0 → 0) và dùng định
nghĩa ta có ND (x0 ) là một nón lồi đóng.


6

Định nghĩa 1.14. Cho hai tập C và D, ta nói rằng siêu phẳng

H := {x : v, x = λ}
(i) Tách hai tập C và D nếu

v, a ≤ λ ≤ v, b ,

∀a ∈ C, ∀b ∈ D;

(ii) Tách chặt C và D nếu:

v, a < λ < v, b ,

∀a ∈ C, ∀b ∈ D;

(iii) Tách mạnh C và D nếu:

/ E . Theo Bổ đề 1.1, ta có

x0 ∈ E : t = 0 − x0 = 0 sao cho t, x − x0 ≤ 0,
⇒ t, z ≤ 0,

∀z ∈ E ⇒ sup t, z ≤ 0

⇒ t, x − y ≤ 0,

∀x ∈ C, ∀y ∈ D

∀x ∈ E


7

⇒ t, x ≤ sup t, x ≤ t, y ,

∀x ∈ C, y ∈ D

x∈C

⇒ t, x ≤ α ≤ t, y ,

∀x ∈ C, y ∈ D

với α = sup t, x . Suy ra α tách hai tập C, D.
x∈C

+ Nếu 0 ∈ E\riE . Lấy một điểm u ∈ riE và dãy ak =


, suy ra ta có:

tk , z − z k ≤ 0,

∀z ∈ E

⇒ t, z ≤ tk , z k ,
Do tk = 1 và hình cầu S = tk ∈ Rn

∀z ∈ E.
tk = 1 là compact, nên tồn

tại t0 ∈ S : t → t0 với tk = 1. Mà ak → 0 ⇒ z k → 0, nên

tk , z − z k → t0 , z
⇒ t0 , z ≤ 0,

∀z ∈ C − D ⊂ E

⇒ t0 , x − y ≤ 0,

∀x ∈ C, y ∈ D.

Tương tự, với β = sup t0 , x thì β tách hai tập C, D.
x∈C

Định lý 1.3. (Định lí tách 2). Cho C và D là hai tập lồi đóng khác
rỗng trong Rn sao cho C ∩D = ∅. Giả sử có ít nhất một tập là compact.
Khi đó hai tập C và D có thể tách mạnh được bởi một siêu phẳng.

C ∩ D = ∅, nhưng C và D không tách mạnh được.
Hệ quả 1.1. (Bổ đề Farkas). Cho a ∈ Rn và A là một ma trận m × n.
Khi đó a, x ≥ 0 với mọi x thỏa mãn Ax ≥ 0, khi và chỉ khi tồn tại

y ≥ 0 thuộc Rm sao cho a = AT y .
Ý nghĩa hình học của bổ đề Farkas: siêu phẳng đi qua gốc tọa độ

a, x = 0 để nón Ax ≥ 0 về một phía của nó khi và chỉ khi vectơ pháp
tuyến a của siêu phẳng nằm trong nón sinh bởi các hàng của ma trận

A.
1.2

Hàm lồi
Trong phần này ta chỉ xét hàm f xác định trên toàn không gian

Rn và không nhận giá trị −∞.
Định nghĩa 1.15. Một hàm số f xác định trên tập lồi D được gọi là
(i) lồi trên D nếu

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y),

∀x, y ∈ D, 0 < λ < 1.

(ii) lồi chặt nếu

f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y),

∀x, y ∈ D, 0 < λ < 1.


Định lý 1.6. Cho f : D → R là một hàm khả vi trên tập lồi mở D.
Điều kiện cần và đủ để f lồi trên D là

f (x) + ∇f (x), y − x ≤ f (y),

∀x, y ∈ D.

Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên D là với mọi

x ∈ D ma trận Hessian H(x) của f tại x xác định không âm, tức là
y T H(x)y ≥ 0,

∀x ∈ D, y ∈ Rn .

Như vậy, một dạng toàn phương xT Qx là một hàm lồi khi và chỉ khi

Q xác định không âm. Một dạng toàn phương là một hàm lồi chặt khi
và chỉ khi ma trận của nó xác định dương.


10

Tính khả vi của một hàm lồi giữ vai trò quan trọng trong các bài
toán tối ưu hóa. Lớp các hàm lồi có những tính chất khả vi rất đẹp mà
các lớp khác không có. Giả sử f : Rn → R ∪ {+∞} là hàm lồi. Ta có
khái niệm sau:
Định nghĩa 1.16. Cho ε > 0. Một véc tơ ω ∈ Rn được gọi là một ε−
dưới gradient của f tại x0 ∈ Rn nếu:

ω, x − x0 ≤ f (x) − f (x0 ) + ε,

0

khi x ∈ D;

+∞

khi x ∈
/ D.

Với mọi x0 ∈ D, ta có:

ω ∈ ∂δD (x) ⇔ δD (x) − δD (x0 ) ≥ ω, x − x0 ,
⇔ 0 ≥ ω, x − x0 ,

∀x ∈ D

∀x ∈ D ⇔ ω ∈ ND (x0 ).

Chứng tỏ

∂δD (x) = ND (x0 ),

∀x0 ∈ D.


11

Cũng có trường hợp tồn tại những điểm x∗ tại đó f không có dưới
vi phân, nghĩa là tập ∂f (x∗ ) có thể là một tập rỗng. Tuy nhiên, đối với
hàm lồi ta có định lý sau:

vi phân là một khái niệm mở rộng của đạo hàm trong trường hợp hàm
không khả vi. Trong trường hợp ∂f (x∗ ) chỉ gồm duy nhất một điểm thì

f khả vi tại x∗ .


12

1.3
1.3.1

Bài toán tối ưu lồi
Các khái niệm

Cho tập lồi D ⊆ Rn , hàm lồi f : Rn → R. Xét bài toán quy hoạch toán
học

min{f (x) : x ∈ D}

(P ).

Bài toán này được hiểu là hãy tìm một điểm x∗ ∈ D sao cho

f (x∗ ) ≤ f (x),

∀x ∈ D.

Mỗi điểm x∗ ∈ D dươc gọi là phương án chấp nhận được của bài
toán (P). Tập D được gọi là miền chấp nhận được, f được gọi là hàm
mục tiêu của bài toán (P). Thông thường, tập D được coi như là tập


∀x ∈ D.

Định lý 1.9. Đối với bài toán quy hoạch lồi (D là tập lồi và f là hàm
lồi trên D), mỗi nghiệm tối ưu địa phương đều là nghiệm tối ưu toàn
cục và tập nghiệm tối ưu là lồi (có thể rỗng).
Chứng minh
Giả sử x∗ ∈ D là một nghiệm tối ưu địa phương của bài toán

min{f (x)|x ∈ D}.
Theo định nghĩa, tồn tại một lân cận U của x∗ sao cho

f (x∗ ) ≤ f (x),

∀x ∈ U ∩ D.

Với bất kì x ∈ D, ta có:

xλ = λx + (1 − λ)x∗ = x∗ + λ(x − x∗ ) ∈ U ∩ D.
khi 0 < λ < 1 và λ đủ nhỏ.
Do x∗ là nghiệm tối ưu địa phương và f là hàm lồi nên

f (x∗ ) ≤ f (λx) ≤ λf (x) + (1 − λ)f (x∗ )
⇒ f (x∗ ) ≤ f (x),

∀x ∈ D.

Suy ra x∗ là nghiệm tối ưu toàn cục của bài toán đang xét.
1.3.2


thì bài toán (P) có nghiệm tối ưu.
Chứng minh
Đặt α := inf f (x). Theo định nghĩa có một dãy xk ⊂ D sao cho
x∈D

lim f (xk ) = α.

k→+∞

Do D compact nên có một dãy con hội tụ về x0 ∈ D, không giảm tính
tổng quát có thể coi xk → x0 . Vì f nửa liên tục dưới nên α > −∞.
Nhưng x0 ∈ D nên theo định nghĩa của α, ta phải có f (x0 ) ≥ α. Vậy

f (x0 ) ≥ α.
Định lý 1.12. Nếu f nửa liên tục dưới trên D và thỏa mãn điều kiện
bức sau:

f (x) → +∞ khi ||x|| → +∞,

∀x ∈ D

thì f có điểm cực tiểu trên D.
Chứng minh
Đặt D(a) := {x ∈ D : f (x) ≤ f (a)} với a ∈ D. Rõ ràng, D(a) đóng
và bị chặn nên f có điểm cực tiểu trên D(a) và điểm đó cũng chính là
điểm cực tiểu của f trên D.


15


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

Định lý 1.13. Giả sử D là tập lồi, và f khả dưới vi phân trên D. Khi
đó x∗ là nghiệm tối ưu của bài toán (P) nếu và chỉ nếu

0 ∈ ∂f (x∗ ) + ND (x∗ ),

(1.2)

trong đó ND (x∗ ) ký hiệu nón pháp tuyến của D tại x∗ .
Chứng minh
Xét hàm chỉ

δD (x) =

0

khi x ∈ D

+∞ khi x ∈
/ D.

Do D là tập lồi, suy ra δD (x) lồi và ∂δD (x∗ ) = ND (x∗ ). Bài toán (P)
được viết lại thành bài toán không ràng buộc:

min {f (x) + δD (x), x ∈ Rn } .

(UP)

Khi đó x∗ là nghiệm tối ưu của bài toán (UP) khi và chỉ khi

min {f (x) : x ∈ X, gj (x) ≤ 0, j = 1, ...m}

(P)

trong đó X ⊆ Rn là tập lồi khác rỗng.
Từ bài toán trên ta định nghĩa bài toán tối ưu khác có dạng

max {d(y) : y ∈ Y }

(D)

trong đó Y ⊆ Rm .
Định nghĩa 1.20. Bài toán (D) được gọi là đối ngẫu của bài toán (P )
nếu với mọi điểm chấp nhận được x của (P ) và mọi y chấp nhận được
của (D), ta có

f (x) ≥ d(y).
Bài toán (D) được gọi là đối ngẫu chính xác của bài toán (P ) nếu (D)
là bài toán đối ngẫu của (P ) và tồn tại x∗ là nghiệm của bài toán (P ), y ∗
là nghiệm của bài toán (D) sao cho

f (x∗ ) ≤ d(y ∗ ).


17

Từ Định nghĩa 1.20 ta thấy rằng, nếu bài toán (D) là đối ngẫu chính
xác của bài toán (P ) thì f (x∗ ) = d(y ∗ ).
Xét bài toán (P ), ta định nghĩa hàm Lagrange
m


yj gj (x) ≤ f (x),

∀x ∈ X, ∀y ∈ Y

j=1

Chứng tỏ (LD) là đối ngẫu của bài toán (P).
Nhận xét 1.4. Nhìn chung, một cặp đối ngẫu chưa chắc đã là đối ngẫu
chính xác như ví dụ sau đây sẽ chỉ ra.
Ví dụ 1.4. Xét bài toán

min f (x) = −x2 , x ∈ X = [0, 2] , x − 1 ≤ 0 .
Ta thấy min f (x) = f (1) = −1.
Hàm Lagrange của bài toán là

L(x, y) = −x2 + y(x − 1),

∀y ≥ 0,

∀x ∈ X = [0, 2].

Ta thấy

max d(y) = 0.
y≥0

Vậy cặp đối ngẫu là không chính xác.
Vậy cần thêm điều kiện gì để hai bài toán (P) và (LP) là cặp đối ngẫu
chính xác? Ta có định lí sau:

∀(t, z) ∈ A.

(1.3)

Do các hàm f , gj liên tục, bất đẳng thức trên đúng với mọi (t, z) ∈ A
(A là bao đóng của tập A). Mà (f (x), g(x)) ∈ A, nên ta có

αf (x) + y T g(x) ≥ αf (x∗ ),

∀x ∈ X.

(1.4)

Ta chỉ ra rằng (α, y) ≥ 0.
Thật vậy, giả sử có chỉ số j thỏa mãn yj < 0. Lấy (t0 , z0 ) ∈ A. Điểm

(t0 , z) ≡ ((t0 , z0 + ξej ) ∈ A,

∀ξ ≥ 0

(ej là véc tơ đơn vị thứ j ).
Thay (t, z) = (t0 , z) vào (1.3) và cho ξ → +∞. Ta có vế trái bằng −∞
mà vế phải hữu hạn. Mâu thuẫn này chứng tỏ y ≥ 0.


19

Chứng minh tương tự ta chỉ ra được α ≥ 0. Hơn nữa α > 0 vì nếu

α = 0 thì y = 0. Trong trường hợp này, từ (1.4) ta có:

+λ

j=1

Ta có

xj + λ = d(λ).
j=1



2x1 + λ





0



 

 =  ... 

 
2x10 + λ
0



20

là nghiệm tối ưu của bài toán và

f∗ = min {f (x1 , x2 , ..., x10 )} = 10(−
1.4.2

1
1 2
) = .
10
10

Điều kiện tối ưu có ràng buộc

Định lý 1.16. (Karush-Kuhn-Tucker) Giả sử (P) là bài toán tối
ưu lồi. Nếu x∗ là một nghiệm tối ưu của bài toán (P) thì tồn tại λ∗i ≥

0 (i = 0, 1, ..., m) và µ∗j (j = 1, 2, ..., k) không đồng thời bằng 0 sao cho
L(x∗ , λ∗ , µ∗ ) = min L(x, λ∗ , µ∗ ) (điều kiện đạo hàm triệt tiêu),
x∈X
∗

λ∗i gi (x ) = 0 (i = 1, ..., m) (điều kiện bù).
Hơn nữa, nếu int X = 0 và điều kiện Slater

∃x0 ∈ D : gi (x0 ) < 0 (i = 1, ..., m)
được thỏa mãn và các hàm affine hi (i = 1, ..., k) độc lập tuyến tính
trên X thì λ∗0 > 0 và các điều kiện đạo hàm triệt tiêu và điều kiện bù
là điều kiện đủ để điểm chấp nhận được x∗ là nghiệm tối ưu của bài



21

Nếu λ0 , ..., λm > 0 thì thay x = x∗ ta được:

(λ0 , ..., λm , 0, 0, ..., 0) ∈ C.
Vì thế có thể xem λ∗0 , ..., λ∗m ≥ 0. Hơn nữa, với ε > 0 và x ∈ X , ta lấy:

λ0 = f (x) − f (x∗ ) + ε, λi = gi (x)(i = 1, ..., m),
µj = hj (x)(j = 1, ..., k)
và thay vào vào (1.5), cho ε → 0 ta được:
m

λ∗0 f (x)

k

λ∗i gi (x)

+

µ∗i hi (x)

+

i=1

i=1
m

j . Nếu có chỉ số i sao cho gi (x∗ ) = ξ < 0, thì với mọi ε > 0, ta có
(ε, ..., ξ, ε, ..., ε, 0, ..., 0) ∈ C, (ξ ở vị trí i + 1).
Thay vào (1.5) và cho ε → 0, ta có λ∗i ξ ≥ 0 nhưng vì ξ < 0, nên λ∗i ≤ 0.
Thật vậy, nếu λ∗i = 0, do điều kiện triệt tiêu và điều kiện bù, ta có
m

k

λ∗j gj (x∗ )

0=

µ∗j hj (x∗ )

+

j=1
m

j=1
k

λ∗j gj (x) +

≤
j=1

µ∗j hj (x),

∀x ∈ X.