ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN ANH TUẤN
MỘT SỐ PHƯƠNG PHÁP CƠ BẢN
GIẢI QUY HOẠCH LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN ANH TUẤN
MỘT SỐ PHƯƠNG PHÁP CƠ BẢN
GIẢI QUY HOẠCH LỒI
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.36
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
Thái Nguyên - Năm 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
Mục lục
Trang phụ bìa
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Lời cảm ơn 1
Mở đầu 1
1 Kiến thức cơ bản về tập lồi và hàm lồi 3
1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Hàm lồi và hàm lõm . . . . . . . . . . . . . . . . . . 7
1.2.2 Hàm lồi liên tục . . . . . . . . . . . . . . . . . . . . 11

GS.TSKH Lê Dũng Mưu – người thầy đã trực tiếp hướng dẫn, động viên
và giúp đỡ tôi trong quá trình học tập và nghiên cứu để hoàn thành luận
văn này. Kính chúc thầy và gia đình luôn mạnh khỏe, hạnh phúc !
Tôi xin gửi lời cảm ơn tới các thầy cô giáo thuộc bộ môn Toán - Tin,
phòng Đào tạo và quan hệ Quốc tế, các cán bộ khoa Sau đại học trường
Đại học Khoa học – Đại học Thái Nguyên đã dạy dỗ, chỉ bảo tôi trong
suốt hai năm học vừa qua.
Tôi xin cảm ơn các bạn học viên Cao học Toán khóa 3 đã động viên,
giúp đỡ tôi trong quá trình học tập và rèn luyện tại trường, cũng như trong
quá trình nghiên cứu để hoàn thành luận văn.
Tôi xin được bày tỏ sự cảm ơn chân thành của mình tới bạn bè đồng
nghiệp, tới những người thân trong gia đình đã động viên, giúp đỡ tôi về
mọi mặt để tôi có thể hoàn thành khóa học và thực hiện luận văn này.
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
thiếu xót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của
các thầy cô và bạn đọc để luận văn được hoàn thiện hơn.
Xin trân trọng cảm ơn !
Thái Nguyên, 15 tháng 09 năm 2011.
Người thực hiện
Nguyễn Anh Tuấn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
Mở đầu
Quy hoạch toán học là một bộ môn quan trọng của toán học ứng dụng.
Lớp bài toán quan trọng của quy hoạch toán học là quy hoạch tuyến tính.
Tuy nhiên tính chất tuyến tính nhiều khi không thỏa mãn trong những
trường hợp thực tế. Một tính chất khá gần với tính chất tuyến tính là tính
lồi. Trong đó quy hoạch lồi là lớp bài toán tối ưu có cấu trúc lồi. Một tính

Cho hai điểm a, b ∈ R
n
. Tập tất cả các điểm x = (1 − λ)a + λb với
0  λ  1 gọi là đoạn thẳng (đóng) nối a và b, và được ký hiệu là [a, b].
Định nghĩa 1.1. Một tập C ⊆ R
n
được gọi là một 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ó. Tức là, nếu (1−λ)a+λb ∈ C
với mọi a, b ∈ C và mọi 0  λ  1.
Định nghĩa 1.2. Điểm x ∈ R
n
có dạng
x = λ
1
a
1
+ λ
2
a
2
+ + λ
k
a
k
=
k

i=1
λ
i

gọi là
có thứ nguyên đầy nếu dim C = n.
Định nghĩa 1.3. Điểm x ∈ R
n
có dạng
x = λ
1
a
1
+ λ
2
a
2
+ + λ
k
a
k
và
a
i
∈ R
n
,
k

i=1
λ
i
= 1
được gọi là tổ hợp afin của các điểm a

∈ C ⇒
k

j=1
λ
j
x
j
∈ C.
Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng
minh điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng
minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề
đúng với k - 1 điểm. Ta cần chứng minh với k điểm.
Giả sử x là tổ hợp lồi của k điểm x
1
, , x
k
∈ C. Tức là
x =
k

j=1
λ
j
x
j
, λ
j
> 0 ∀j = 1, , k,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn


j=1
λ
j
ξ
x
j
+ λ
k
x
k
.
Do
k−1

j=1
λ
j
ξ
= 1
và
λ
j
ξ
> 0 với mọi j = 1, , k -1 nên theo giả thiết quy nạp ta có điểm
y :=
k−1

j=1
λ

, C là lồi trong R
m
, thì
các tập sau là lồi:
A ∩ B := {x |x ∈ A, x ∈ B } ,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
λA + βB := {x |x = αa + βb, a ∈ A, b ∈ B; α, β ∈ R} ,
A × C :=

x ∈ R
n+m
|x = (a, c) : a ∈ A, c ∈ C

.
Ví dụ 1.1. Các tập sau đây đều là các tập lồi:
a) Các tập afin (nói riêng, các siêu phẳng);
b) Các nửa không gian đóng, các nửa không gian mở;
c) Hình cầu đóng B(a, r) = {x ∈ R
n
: x − a  r};
d) Hình cầu mở B(a, r) = {x ∈ R
n
: x − a < r} với a ∈ R
n
, r > 0.
Định nghĩa 1.4. Ta nói hai tập lồi khác rỗng C, D trong R
n
tách được bởi
siêu phẳng H = {x ∈ R

rỗng, không cắt nhau với ít nhất một trong hai tập này là compact, có thể
tách hẳn bởi một siêu phẳng, nghĩa là tồn tại một vectơ t ∈ R
n
(t = 0) và
một số α ∈ R sao cho (1.2) thỏa mãn.
Định nghĩa 1.6. Một tập được gọi là tập lồi đa diện, nếu nó là giao của
một số hữu hạn các nửa không gian đóng.
Như vậy, theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một
hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
tập lồi đa diện được cho như sau:
D :=

x ∈ R
n



a
j
, x

 b
j
, j = 1, , m

.
Hoặc nếu ta ký hiệu A là ma trận có m hàng là các vectơ a
j

+ λx
2

 (1 − λ)f(x
1
) + λf(x
2
).
+ Hàm f được gọi là hàm lồi chặt trên S nếu với mọi x
1
, x
2
∈ S, x
1
= x
2
và mọi λ ∈ (0, 1) ta có
f

(1 − λ)x
1
+ λx
2

< (1 − λ)f(x
1
) + λf(x
2
).
Hiển nhiên một hàm lồi chặt là lồi, nhưng điều ngược lại không đúng.

n
, các
tập
domf = {x ∈ S : f(x) < +∞}
và
epif = {(x, α) ∈ S × R : f(x)  α} ,
được gọi lần lượt là miền hữu dụng và tập trên đồ thị của hàm f. Nếu domf
khác rỗng (f không đồng nhất bằng +∞) và f(x) > −∞ với mọi x ∈ S thì
ta nói hàm f là chính thường. Nói cách khác, f chính thường nếu domf = ∅
và f hữu hạn trên domf.
Có thể chứng minh rằng hàm f lồi trên S khi và chỉ khi
a) Tập trên đồ thị epif là một tập lồi.
b)
f(
m

k=1
λ
k
x
k
) 
m

k=1
λ
k
f(x
k
)

Hàm chỉ của C : δ
C
(x) =

0 khi x ∈ C,
+∞ khi x = C.
Hàm tựa của C : s
c
(x) = sup
y∈C
y, x (cận trên của x
T
y trên tập C).
Hàm khoảng cách từ điểm x ∈ R
n
tới C : d
c
(x) = inf
y∈C
x − y .
Bốn phép toán cơ bản bảo toàn hàm lồi (suy trực tiếp từ định nghĩa)
a) Nếu f
i
: R
n
→ R (i = 1, , m) là hàm lồi thì α
1
f
1
+ + α

n
→ R là hàm lồi và h : R → R là hàm lồi không
giảm thì hàm hợp f(x) = h(g(x)) là hàm lồi.
Ví dụ 1.2. Theo d), hàm f (x) = c
1
e
g
1
(x)
+ + c
m
e
g
m
(x)
(x ∈ R
n
) lồi nếu
mọi c
i
> 0 và mọi hàm g
i
(x) lồi (chẳng hạn f(x
1
, x
2
) = e
x
1
+x

+ λx
2
]  max { f(x
1
), f(x
2
)} ∀x
1
, x
2
∈ R
n
, λ ∈ (0, 1).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
Từ đó suy ra các kết luận của định lý.
Tuy nhiên, mệnh đề đảo của định lý trên không đúng.
Một hàm f mà mọi tập mức dưới là tập lồi gọi là một hàm tựa lồi.
Ví dụ 1.3. f(x) = x
3
hay f(x) =

|x| trên R là hàm tựa lồi nhưng không
lồi.
Định lý 1.4. Cho C là một tập lồi, khác rỗng trong R
n
và f : R
n
→ R là
một hàm lồi. Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực

0
)
hay λf(x
0
)  λf(x). Do λ > 0 nên f(x
0
)  f(x). Vì x ∈ C được chọn
tùy ý nên x
0
là điểm cực tiểu toàn cục của f trên C. Nếu α = min{f(x) :
x ∈ C} thì Argmin
x∈C
f(x) trùng với tập C ∩ { x : f(x)  α} . Tập này
lồi do hàm f(x) lồi. (Xem Định lý 1.3)
Định lý 1.5. Một hàm lồi chặt f trên một tập lồi C có nhiều nhất một điểm
cực tiểu trên C, nghĩa là tập Argmin
x∈C
f(x)gồm nhiều nhất một phần tử.
Chứng minh. Nếu f có hai điểm cực tiểu khác nhau x
1
, x
2
∈ C thì
do tính lồi chặt của f nên f(
1
2
x
1
+
1

n
và đặt
d = y − x. Khi đó với mọi λ ∈ [0, 1] ta có
f((1 − λ)x + λy) = f(x + λd) = ϕ(λ) = ϕ((1 − λ).0 + λ.1)
 (1 − λ)ϕ(0) + λϕ(1) = (1 − λ)f(x) + λf(y).
1.2.2 Hàm lồi liên tục
Định lý 1.7. Hàm lồi chính thường f trên R
n
liên tục tại mọi điểm trong
của miền hữu dụng của nó (f liên tục trên int(domf)).
Chứng minh. Giả sử x
0
∈ int(domf). Với mọi i = 1, , n hàm thu
hẹp của f trên khoảng mở { t : x
0
+te
i
∈ int(dom f)} liên tục trên khoảng
này. Vì thế, với mọi ε > 0 cho trước và với mọi i = 1, , n ta có thể chọn
δ
i
> 0 đủ nhỏ sao cho


f(x
0
+ x) − f(x
0
)


, i = 1, , n. Khi đó, có thể thấy rằng
mọi x ∈ B có dạng x = λ
1
d
1
+ +λ
2n
d
2n
với λ
1
+ + λ
2n
= 1, λ
i
 0.
Từ đó
f(x
0
+ x)  λ
1
f(x
0
+ d
1
) + + λ
2n
f(x
0
+ d

0
+ x) - f(x
0
)


 λ
1


f(x
0
+ d
1
) − f(x
0
)


+ + λ
2n


f(x
0
+ d
2n
) - f(x
0
)

x
0
sao cho f(x) < f(x
0
) + 1 với mọi x ∈ U, tức là f(x) bị chặn trên trong
U.
b) ⇒ c) Nếu f(x)  M với mọi x trong tập mở U thì U×[M, + ∞) ⊂
epif, vì thế int(epif) = ∅.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
c) ⇒ d) Nếu int(epif) = ∅ thì tồn tại một tập mở U ⊂ R
n
và một
khoảng mở I ⊂ R sao cho U × I ⊂ epif, nên U ⊂ domf, nghĩa là
int(domf) = ∅. Theo Định lí 1.7 hàm f liên tục trên int(domf).
d) ⇒ a) là hiển nhiên.
Định lý 1.9. Cho một tập lồi C ⊂ R
n
và một hàm f : R
n
→ R khả vi
trên C.
a) Hàm f lồi trên C khi và chỉ khi
f(y)  f(x) + ∇f(x), y − x ∀x, y ∈ C.
b) Nếu f(y) > f(x) + ∇f(x), y − x ∀x, y ∈ C, x = y thì hàm f lồi
chặt trên C.
1.2.3 Dưới vi phân
Định nghĩa 1.9. Cho hàm lồi chính thường f trên R
n
, véctơ p ∈ R

rỗng tại mỗi điểm x
0
∈ int(domf) và ∂f(x
0
) là một tập lồi đóng.
Chứng minh. Do x
0
∈ int(domf) nên theo Định lí 1.8 int(epi f) = ∅.
Dĩ nhiên (x
0
, f(x
0
)) /∈ int(epi f). Nên theo Định lí 1.1 có một siêu phẳng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
tách điểm đó với int(epi f), tức là có một véctơ (t, t
n+1
) ∈ R
n+1
\{ 0} sao
cho

t, x
0

+ t
n+1
f(x
0
)  t, x + t

chỉ có thể xảy ra khi t = 0, mâu thuẫn với (t, t
n+1
) = 0. Vậy t
n+1
< 0.
Đặt p = −t/t
n+1
và α = f(x)ta sẽ nhận được bất đẳng thức (1.9).
Để chỉ rõ ∂f(x
0
) lồi ta lấy bất kỳ p
1
, p
2
∈ ∂f(x
0
), λ ∈ [0, 1]. Khi đó
với mọi x ∈ R
n
thì

λp
1
, x − x
0

 λ

f(x) − f(x
0

)
⇒ ∂f(x
0
) lồi.
Để chỉ rõ ∂f(x
0
) là tập đóng, lấy p
k
∈ ∂f(x
0
), p
k
→ p.Từ

p
k
, x − x
0

+ f(x
0
)  f(x) với mọi x ∈ R
n
.
Suy ra

p, x − x
0

+ f(x


p, x − x
0

 0 ∀x ∈ C

.
3) Nếu f(x) = x (chuẩn Euclid) thì
∂f(x
0
) =

{p : p  1} khi x
0
= 0,

x
0
/


x
0



khi x
0
= 0.
Liên hệ giữa dưới vi phân và đạo hàm: Theo định nghĩa, hàm f khả

), d

, ∀d ∈ R
n
.
Định lý 1.11. Nếu f là hàm lồi chính thường, khả vi tại điểm x
0
∈ dom f
thì ∂f(x
0
) =

∇f(x
0
)

tức là ∇f(x
0
) là véctơ dưới đạo hàm duy nhất của
f tại x
0
.
Chứng minh. Nếu p ∈ ∂f(x
0
) thì với mọi d ∈ R
n
, d = 0 và mọi
λ > 0 ta có

p, (x

) − p, d

 0 với mọi d ∈ R
n
. Từ đó suy ra p = ∇f(x
0
).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
Ngược lại có thể chứng minh rằng nếu f có tại x
0
một vectơ dưới đạo
hàm duy nhất thì f khả vi tại x
0
. Như vậy, khái niệm dưới đạo hàm là sự
mở rộng của khái niệm đạo hàm (tại những điểm đó hàm không khả vi).
Đạo hàm theo hướng. Cho f : R
n
→ (−∞, +∞] là một hàm bất kỳ và
x
0
là một điểm tại đó f hữu hạn (nghĩa là


f(x
0
)


< +∞).

, d).
Chứng minh. Do hàm f lồi nên hàm một biến ϕ(λ) = f(x
0
+ λd) lồi
và theo Định nghĩa 1.10 thì
f


x
0
, d

= lim
λ↓0
f

x
0
+ λd

− f

x
0

λ
= lim
λ↓0
ϕ (λ) − ϕ (0)
λ

λ
0
) × 0 và 0 <
λ
λ
0
< 1.
Do hàm ϕ lồi nên
ϕ(λ) 
λ
λ
0
ϕ(λ
0
) + (1 −
λ
λ
0
)ϕ(0).
Từ đó suy ra
ϕ(λ) − ϕ(0)
λ

ϕ(λ
0
) − ϕ(0)
λ
0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17

, d).
Cho λ = 1 ta có ϕ(1)−ϕ(0)  ϕ

+
(0), tức là f(x
0
+d)−f(x
0
)  f

(x
0
, d).
Định lý 1.13. Nếu f là một hàm lồi chính thường và x
0
∈ dom f thì
p ∈ ∂f(x
0
) khi và chỉ khi p, d  f

(x
0
, d) với mọi d ∈ R
n
\{0}.
Chứng minh. Bằng cách đặt x = x
0
+ λd và ϕ(λ) = f(x
0
+ λd) ta

∇
2
f(x)y  0 ∀x ∈ C ∀y;
Tức là ma trận ∇
2
f(x) xác định dương tại mọi x ∈ C.
1.2.4 Hàm lồi mạnh
Sau đây ta xét một lớp hàm luôn có cực tiểu trên mọi tập lồi đóng
khác ∅. Hơn nữa, giống như đối với hàm lồi chặt, cực tiểu này là duy nhất.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18
Định nghĩa 1.11. Hàm f(x) xác định trên một tập lồi C ⊂ R
n
được gọi
là lồi mạnh, nếu tồn tại hệ số ρ > 0 (hệ số lồi mạnh) sao cho với mọi
∀x, y ∈ C và mọi số λ ∈ [0, 1] ta có bất đẳng thức:
f [λx + (1 − λ)y]  λf(x) + (1 − λ)f(y) − λ(1 − λ)ρx − y
2
.
Có thể chứng minh rằng hàm f(x) lồi mạnh khi và chỉ khi hàm f(x) −
ρ.x
2
lồi. Rõ ràng một hàm số lồi mạnh thì lồi chặt, nhưng điều ngược
lại không chắc đúng. Chẳng hạn, hàm e
x
với mọi x ∈ R, lồi chặt nhưng
không lồi mạnh.
Các hàm lồi mạnh có vai trò đặc biệt quan trọng trong nghiên cứu các
bài toán tối ưu.
Ví dụ 1.7. Hàm f(x

x − y, Q(x − y)  ρx − y
2
trong đó ρ là giá trị riêng nhỏ nhất (dương) của ma trận Q.
Định lý 1.15. Nếu hàm f(x) lồi mạnh và khả vi trên tập lồi đóng C thì
a) ∇f(x) − ∇f(y), x − y  ρx − y
2
với mọi x, y ∈ C;
b) Với bất kỳ x
0
∈ C tập mức dưới C
0
=

x ∈ C : f(x)  f(x
0
)

bị
chặn;
c) Tồn tại duy nhất điểm x
∗
∈ C sao cho f(x
∗
) = min {f(x) : x ∈ C} .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
19
Chứng minh.
a) Do f lồi khả vi nên theo Định lí 1.9, với mọi x, y ∈ C thì
f(x) − f(y)  ∇f(x), x − y .
Hơn nữa, do f lồi mạnh nên với λ =

∇f(x), x − y +
1
4
∇f(y), y − x =
1
4
∇f(x) − ∇f(y), x − y .
b) Do
f(x) − f(y) =
1

0
∇f [y + λ(x − y)] , x − y dλ
= ∇f(y), x − y +
1

0
∇f[y + λ(x − y)] − ∇f(y), x − y dλ,
nên kết hợp với bất đẳng thức ở phần a) ta được
f(x) − f(y)  ∇f(y), x − y +
1
2
ρx − y
2
⇒
0  f(x) − f(x
0
) 

∇f(x

0
− x


2
ρ


∇f(x
0
)


×


x − x
0


.
Từ đó suy ra


x − x
0


2


∗
là duy nhất.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn