BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

NGUYỄN VĂN PHÚ

BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG LỒI
VỚI RÀNG BUỘC TUYẾN TÍNH

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

Hà Nội - 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

Nguyễn Văn Phú

BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG LỒI
VỚI RÀNG BUỘC TUYẾN TÍNH

Chuyên ngành: Toán giải tích
Mã số: 60 46 01 02

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

Người hướng dẫn khoa học:
PGS. TS. Nguyễn Năng Tâm

Hà Nội - 2015

ii


LỜI CẢM ƠN

Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2
dưới sự hướng dẫn của thầy giáo PGS. TS. Nguyễn Năng Tâm. Sự giúp
đỡ và hướng dẫn tận tình song rất nghiêm túc của thầy trong suốt quá
trình thực hiện luận văn này đã giúp tác giả trưởng thành hơn rất nhiều
trong cách tiếp cận một vấn đề mới. Tác giả xin bày tỏ lòng biết ơn,
lòng kính trọng sâu sắc nhất đối với thầy.
Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư
phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường
và các thầy cô giáo dạy cao học chuyên ngành Toán giải tích đã giúp đỡ,
tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập.
Tác giả xin chân thành cảm ơn .

Hà Nội, ngày 10 tháng 08 năm 2015
Tác giả

Nguyễn Văn Phú


LỜI CAM ĐOAN

Luận văn được hoàn thành tại trường Đại Học Sư phạm Hà Nội 2
dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm.
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi.
Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa
những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự

trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn
trong luận văn đã được chỉ rõ nguồn gốc.

Hà Nội, ngày 10 tháng 08 năm 2015
Tác giả

Nguyễn Văn Phú


Mục lục

Lời cảm ơn

iii

Lời cam đoan

iv

Bảng ký hiệu

vii

Mở đầu

1

1 Kiến thức chuẩn bị

3


1.1. Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.2. Nón lùi xa của một tập lồi . . . . . . . . . . . . .

5

1.1.3. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . .

6

1.2. Hệ bất phương trình tuyến tính và tập lồi đa diện . . . .

11

1.2.1. Hệ bất phương trình tuyến tính . . . . . . . . . .

11

1.2.2. Tập lồi đa diện . . . . . . . . . . . . . . . . . . .

13

1.3. Hàm toàn phương lồi . . . . . . . . . . . . . . . . . . . .


13

1.4. Bài toán tối ưu lồi . . . . . . . . . . . . . . . . . . . . .

15

2 Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính 20
2.1. Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . .
v

20


2.2. Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . .

22

2.3. Điều kiện cực trị . . . . . . . . . . . . . . . . . . . . . .

27

2.4. Tính ổn định của tập nghiệm . . . . . . . . . . . . . . .

41

2.4.1. Tính nửa liên tục dưới của ánh xạ nghiệm . . . .

42


2.4.2. Tính nửa liên tục trên của ánh xạ nghiệm . . . .

46

2.5. Hàm giá trị tối ưu của bài toán có tham số . . . . . . . .

52

Kết luận

58

Tài liệu tham khảo

59

vi


BẢNG KÝ HIỆU

N

Tập số tự nhiên

R

Tập số thực

R+


Tập số thực dương

∅

Tập hợp rỗng

Rn

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

x, y = xT y =
x =

n
2
j=1 xj

n
j=1 xj yj

Tích vô hướng của hai vectơ x và y
Chuẩn Euclide của vectơ x

B (x, δ)
¯ (x, δ)
B

Hình cầu mở tâm x, bán kính δ


[x, y]

Đoạn thẳng đóng nối x và y

0+ (C)
f¯

Nón lùi xa của tập lồi C

domf

Tập hữu dụng của hàm f

epi(f )

Trên đồ thị của hàm f

∂f (x)

Dưới vi phân của f tại x

∇f (x)

Vectơ gradient của f tại x

Sol (P )

Tập nghiệm của bài toán (P )

Sol (D, A, c, b)


Tập nghiệm của bài toán tối ưu toàn phương

(QP )

Bài toán tối ưu toàn phương

Rm×n

Không gian các ma trận m × n

Rn×n
S

Không gian các ma trận đối xứng n × n

AT

Ma trận chuyển vị của A

T∆ (¯
x)

Nón tiếp của ∆ tại x¯

Hình cầu đóng tâm x, bán kính δ

Hàm bao đóng của f

Kết thúc chứng minh.



MỞ ĐẦU
1. Lý do chọn đề tài
Quy hoạch toàn phương lồi là một bộ phận của quy hoạch toàn
phương đã được nghiên cứu nhiều và gần như đã mang tính hoàn thiện
một cách chuẩn mực. Tuy vậy, việc tìm hiểu những khía cạnh khác nhau
của quy hoạch toàn phương lồi một cách thấu đáo hơn vẫn luôn là một
việc làm có nhiều ý nghĩa (xem [2], [4] và những tài liệu tham khảo trong
đó).
Sau khi được học những kiến thức về Toán giải tích, với mong muốn tìm
hiểu sâu hơn về những kiến thức đã học, mối quan hệ và ứng dụng của
chúng, tôi đã chọn đề tài nghiên cứu:
“ Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính ”.

2. Mục đích nghiên cứu
Nghiên cứu chi tiết và toàn diện về những tính chất định tính của
bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính.

3. Nhiệm vụ nghiên cứu
Nghiên cứu bài toán tối ưu toàn phương lồi với ràng buộc tuyến
tính dựa trên những tài liệu đã có. Phân tích bài toán và sau đó nghiên
cứu các khía cạnh cơ bản của bài toán.


2

4. Đối tượng và phạm vi nghiên cứu
Hàm tối ưu toàn phương lồi.
Hệ bất phương trình tuyến tính.

Bài toán tối ưu lồi.
Điều kiện cực trị.
Sự tồn tại nghiệm và tính ổn định tập nghiệm của bài toán tối ưu
toàn phương lồi với ràng buộc tuyến tính.

5. Phương pháp nghiên cứu
Thu thập thông tin về bài toán tối ưu toàn phương lồi với ràng
buộc tuyến tính.
Sưu tầm, nghiên cứu các tài liệu liên quan.
Suy luận logic, phân tích, tổng hợp và sắp xếp và trình bày các
kiến thức thu thập được theo phương pháp của Giải tích.

6. Đóng góp mới của luận văn
Luận văn trình bày một tổng quan có hệ thống cùng với sự phân
tích sâu sắc, chi tiết về một số tính chất của bài toán tối ưu toàn phương
lồi với ràng buộc tuyến tính.


Chương 1
Kiến thức chuẩn bị
1.1.

Tập lồi và hàm lồi
Trong phần này chúng tôi trình bày một số khái niệm cơ bản liên

quan đến tập lồi và hàm lồi. Đây là những kiến thức cơ bản làm nền
tảng cho việc nghiên cứu bài toán tối ưu toàn phương lồi với ràng buộc
tuyến tính.
Nội dung của chương này được tham khảo dựa trên các tài liệu [1] - [3].
1.1.1.


Tập lồi

Định nghĩa 1.1.1. [1] Tập con C của Rn được gọi là tập lồi nếu
αx + (1 − α)y ∈ C, ∀x, y ∈ C, ∀α ∈ [0, 1].
Chú ý rằng, ta quy ước tập rỗng là tập lồi.
Mệnh đề 1.1.1. [1]
(a) Giao ∩i∈I Ci của họ các tập lồi {Ci |i ∈ I} là tập lồi.
(b) Tổng C1 + C2 của hai tập lồi C1 và C2 là tập lồi.
(c) Nếu tập C lồi thì tập λC lồi với mọi λ. Hơn nữa, nếu C là một tập

3


4

lồi và λ1 , λ2 là vô hướng dương, thì
(λ1 + λ2 )C = λ1 C + λ2 C.
(d) Bao đóng và phần trong của một tập lồi là tập lồi.
(e) Tạo ảnh và nghịch ảnh của một tập lồi qua một hàm afine là tập lồi.
Chứng minh. Để chứng minh phần (a), ta lấy 2 điểm x và y thuộc ∩i∈I Ci
và ta sử dụng tính lồi của Ci chỉ ra đoạn thẳng nối x và y thuộc Ci , do
đó nó thuộc ∩i∈I Ci .
Tương tự, để chứng minh phần (b), ta lấy 2 điểm của C1 + C2 , biểu
diễn là x1 +x2 và y1 +y2 , với x1 , y1 ∈ C1 và x2 , y2 ∈ C2 , với mọi α ∈ [0, 1],
ta có:
α (x1 + x2 ) + (1 − α) (y1 + y2 ) = (αx1 + (1 − α) y1 ) + (αx2 + (1 − α) y2 )
Từ tính lồi của C1 và C2 , vectơ trong 2 dấu ngoặc đơn bên vế phải
ở trên thuộc C1 và C2 , tương ứng tổng của chúng thuộc C1 + C2 . Do đó,
C1 + C2 là tập lồi. Phần (c) và (e) chứng minh tương tự phần (b).

Để chứng minh phần (d), ta lấy 2 điểm x và y từ bao đóng của tập
C, và dãy {xk } ⊂ C, {yk } ⊂ C, như vậy xk → x, yk → y với ∀α ∈ [0, 1],
dãy {αxk + (1 − α)yk }, thuộc C do tính lồi của C, hội tụ về αx+(1−α)y.
Vì thế, αx + (1 − α)y thuộc về bao đóng của C, cho thấy rằng bao đóng
của C là lồi. Tương tự, ta lấy hai điểm x và y từ phần trong của tập
C, và ta xem như hình cầu mở tâm tại x và y, và có bán kính r đủ nhỏ
để chúng chứa trong C. Với mọi α ∈ [0; 1], xét các hình cầu mở bán
kính r có tâm tại αx + (1 − α)y. Với bất kỳ điểm nào trong hình cầu,
αx + (1 − α)y + z, với z < r, thuộc về X, bởi vì nó biểu diễn sự kết
hợp lồi α (x + z) + (1 − α) (y + z) của vectơ x + z và y + z, thuộc X. Vì
thế, αx + (1 − α)y thuộc về phần trong của C, do đó phần trong của C
là lồi.
Tập C được cho là hình nón nếu với mọi x ∈ C và λ > 0, ta có


5

λx ∈ C. Một nón không cần lồi và không cần phải chứa gốc, mặc dù gốc
luôn nằm trong bao đóng của nón khác rỗng.
1.1.2.

Nón lùi xa của một tập lồi

Cho tập lồi khác rỗng C ⊂ X. Ta nói vectơ d là một phương lùi
xa của C nếu
x + λd ∈ C; ∀x ∈ C, ∀λ > 0.
Tập tất cả các phương lùi xa của C được gọi là nón lùi xa của C và được
ký hiệu là 0+ (C). Vậy
0+ (C) = {d ∈ X|x + λd ∈ C; ∀x ∈ C; ∀λ > 0} .
Mệnh đề 1.1.2. [1] 0+ (C) là nón lồi chứa gốc. Hơn nữa,

0+ (C) = {d ∈ X|C + d ⊂ C}
Ví dụ 1.1.1. Trong R2 cho các tập
C1 =

(x, y) |x > 0; y ≥

1
x

;

C2 = (x, y) |y ≥ x2 ;
C3 = (x, y) |x2 + y 2 ≤ 1 ;
√
C4 = (x, y) |y ≥ 1 + x2 ;
C5 = {(x, y) | (x > 0 ∧ y > 0) ∨ (x = y = 0)} .
Lúc đó,
0+ (C1 ) = {(u, v) |u ≥ 0; v ≥ 0} ;
0+ (C2 ) = {(0, v) |v ≥ 0} ;
0+ (C3 ) = {(0, 0)} ;
0+ (C4 ) = {(u, v) |v ≥ |u|} ;
0+ (C5 ) = C5 .
Ví dụ 1.1.2. Cho ai ∈ Rn , αi ∈ R; 1 ≤ i ≤ m. Xét tập hợp
C6 = x ∈ Rn | ai , x ≤ αi ; 1 ≤ i ≤ m = ∅.


6

Ta có
0+ (C6 ) = x ∈ Rn | ai , x ≤ 0; 1 ≤ i ≤ m .

Mệnh đề 1.1.3. [1] Cho C lồi đóng khác rỗng. Lúc đó, 0+ (C) là nón
lồi đóng và
a) d ∈ 0+ (C) ⇔ ∃x0 ∈ C, ∀λ > 0 : x0 + λd ∈ C.
b) 0+ (C) =

λ (C − x0 ); với mọi x0 ∈ C.
λ>0

Mệnh đề 1.1.4. [1] Cho tập lồi khác rỗng C ⊂ Rn . Lúc đó, C bị chặn
khi và chỉ khi 0+ (C) = ∅.
1.1.3.

Hàm lồi

Định nghĩa 1.1.2. [2] Cho C là một tập con lồi của Rn . Một hàm
f : C → R gọi là lồi nếu
f (αx + (1 − α) y) ≤ αf (x) + (1 − α) f (y) , ∀x, y ∈ C, ∀α ∈ [0; 1] .
(1.1)
Một hàm lồi f : C → R gọi là lồi ngặt nếu bất đẳng thức (1.1) đúng
cho mọi x, y ∈ C với x = y và với mọi α ∈ (0, 1). Một hàm f : C → R,
trong đó C là tập lồi, gọi là lõm nếu (−f ) là lồi.
Chú ý rằng, theo định nghĩa, tính lồi của miền định nghĩa C là
một điều kiện tiên quyết cho một hàm f : C → R lồi. Đôi khi ta sẽ làm
việc với những hàm f : X → R được định nghĩa trên một miền xác định
X (có thể không lồi) nhưng là lồi khi hạn chế trên một tập con lồi của
X.
Định nghĩa 1.1.3. [2] Cho C và X là tập hợp con của Rn , sao cho C
là khác rỗng và lồi, và C ⊂ X. Một hàm f : C → R được gọi là lồi trên
C nếu đẳng thức (1.1) đúng, tức là, khi miền xác định của f được hạn
chế trên C, f trở thành hàm lồi.



7

Nếu f : C → R là một hàm và γ là một vô hướng, các tập
{x ∈ C|f (x) ≤ γ} và {x ∈ C|f (x) < γ} được gọi là những tập mức của
f . Nếu f là một hàm lồi, thì tất cả những tập mức của nó là lồi. Chú
ý rằng nếu x, y ∈ C thỏa mãn f (x) ≤ γ và f (y) ≤ γ, khi đó với mọi
α ∈ [0, 1], ta có αx + (1 − α) y ∈ C, từ tính lồi của C, và ta có:
f (αx + (1 − α) y) ≤ αf (x) + (1 − α) f (y) ≤ γ.
Chứng minh tương tự ta có tập mức {x ∈ C|f (x) < γ} là lồi khi f là
hàm lồi. Tuy nhiên, tính lồi của những tập mức không suy ra tính lồi
của hàm; chẳng hạn: hàm vô hướng f (x) =

|x| có tập mức lồi nhưng

không phải là hàm lồi.
Định nghĩa 1.1.4. [2] Ta gọi trên đồ thị (epigraph) của hàm f : X →
[−∞, ∞], với mỗi X ⊂ Rn , là tập con của Rn+1 được cho bởi
epi (f ) = {(x, w) |x ∈ X, w ∈ R, f (x) ≤ w} .
Định nghĩa 1.1.5. [2] Ta gọi miền hữu hiệu (effective domain) của hàm
f là tập được cho bởi
dom (f ) = {x ∈ X|f (x) < ∞} .
Định nghĩa 1.1.6. [2] Hàm f được gọi là chính thường (proper), nếu
dom (f ) = ∅ và f (x) > −∞, ∀x ∈ X.
Sau đây chúng tôi xin trình bày các đặc trưng của hàm khả vi lồi.
Cho hàm khả vi, giả thiết thừa số liên quan của tính lồi đã cho trong
những Mệnh đề tiếp theo.
Mệnh đề 1.1.5. [4] Cho C là một tập con lồi của Rn và cho f : Rn → R
là khả vi trên Rn .

(a) f là lồi trên C khi và chỉ khi
f (z) ≥ f (x) + ∇f (x)T (z − x) , ∀x, z ∈ C.

(1.2)


8

(b) f là lồi ngặt trên C khi và chỉ khi bất đẳng thức trên là ngặt với mọi
x = z.
Chứng minh. Ta chứng minh phần (a) và (b) một cách đồng thời. Chỉ
ra rằng bất đẳng thức (1.2) đúng. Lấy x, y ∈ C bất kỳ và α ∈ [0, 1], và
đặt z = αx + (1 − α)y. Sử dụng bất đẳng thức (1.2) hai lần, ta thu được
f (x) ≥ f (z) + ∇f (z)T (x − z) ,
f (y) ≥ f (z) + ∇f (z)T (y − z) .
Ta nhân bất đẳng thức thứ nhất với α, thứ 2 với 1 − α và ta thu được
αf (x) + (1 − α) f (y) ≥ f (z) + ∇f (z)T (αx + (1 − α) y − z) = f (z) ,
chứng tỏ f là lồi. Nếu bất đẳng thức (1.2) là ngặt như trong phần (b),
khi đó nếu ta lấy x = y và α ∈ (0; 1) ở trên, ba bất đẳng thức trước trở
thành ngặt, do đó ta có tính lồi ngặt của f .
Ngược lại, giả sử rằng, f là lồi, lấy x và z là vectơ bất kỳ trong C
với x = z, và cho α ∈ (0, 1), xét hàm số
g (α) =

f (x + α (z − x)) − f (x)
, α ∈ (0; 1] .
α

Ta sẽ thấy rằng g(α) là dãy đơn điệu tăng với α, và là dãy đơn điệu tăng
ngặt nếu f là lồi ngặt. Điều này có nghĩa là

∇f (x)T (z − x) = lim g (α) ≤ g (1) = f (z) − f (x) ,
α↓0

với bất đẳng thức ngặt nếu g là dãy đơn điệu tăng ngặt, qua đó cho thấy
rằng đòi hỏi bất đẳng thức (1.2) cố định, và ngặt cố định nếu f là lồi
ngặt. Thực vậy, xét bất kỳ α1 , α2 , với 0 < α1 < α2 < 1, và cho
α=

α1
, z = x + α2 (z − x) .
α2

Ta có
f (x + α (z − x)) ≤ αf (z) + (1 − α) f (x) ,

(1.3)


9

hoặc
f (x + α (z − x)) − f (x)
≤ f (z) − f (x) ,
(1.4)
α
và trên bất đẳng thức là ngặt nếu f là lồi ngặt. Thế (1.3) vào (1.4), ta
thu được
f (x + α1 (z − x)) − f (x) f (x + α2 (z − x)) − f (x)
≤
,

α1
α2
Ta xấp xỉ tuyến tính f tại z = αx + (1 − α)y. Bất đẳng thức (1.2) ngụ
ý rằng
f (x) ≥ f (z) + ∇f (z)T (x − z) ,
f (y) ≥ f (z) + ∇f (z)T (y − z) .
Ta thấy αf (x) + (1 − α) f (y) nằm trên f (z), vì vậy f là lồi.
Giả sử rằng f là lồi. Ta có
f (x) +

f (x + α (z − x)) − f (x)
α

nằm dưới f (z), là dãy đơn điệu không tăng như α ↓ 0, và hội tụ tới
f (x) + ∇f (x)T (z − x). Do đó f (z) ≥ f (x) + ∇f (x)T (z − x).
hoặc
g (α1 ) ≤ g (α2 ) ,
với bất đẳng thức ngặt nếu f là lồi ngặt. Vì thế g là dãy đơn điệu tăng
với α, và ngặt nếu f là lồi ngặt.
Một hệ quả đơn giản của Mệnh đề 1.1.5(a): nếu f : Rn → R là
một hàm lồi và ∇f (x∗ ) = 0, sau khi x∗ cực tiểu f trên Rn . Đây là lớp
điều kiện đủ bài toán tối ưu không ràng buộc, được đề xuất bởi Fermat
năm 1637.
Đối với hàm lồi khả vi cấp 2, ta có đặc trưng khác của tính lồi
trong mệnh đề dưới đây.
Mệnh đề 1.1.6. [4] Cho C là một tập hợp con lồi của Rn và cho f :
Rn → R là khả vi cấp 2 liên tục trên Rn .


10


(a) Nếu ∇2 f (x) là hàm nửa xác định dương với mọi x ∈ C, thì f là
hàm lồi trên C.
(b) Nếu ∇2 f (x) là hàm xác định dương với mọi x ∈ C, thì f là hàm lồi
ngặt trên C.
(c) Nếu C là mở và f là hàm lồi trên C thì ∇2 f (x) là hàm nửa xác định
dương với mọi x ∈ C.
Chứng minh. (a) Với mọi x, y ∈ C ta có
1
f (y) = f (x) + ∇f (x)T (y − x) + (y − x)T ∇2 f (x + α (y − x)) (y − x)
2
với một vài α ∈ [0, 1]. Vì thế, khi sử dụng hàm xác định dương của ∇2 f ,
ta thu được
f (y) ≥ f (x) + ∇f (x)T (y − x) , ∀x, y ∈ C.
Từ mệnh đề 1.1.5(a), ta kết luận rằng f là lồi.
(b) Chứng minh tương tự phần (a), ta có
f (y) > f (x) + ∇f (x)T (y − x) , ∀x, y ∈ C
với x = y và kết quả tiếp theo dạng từ Mệnh đề 1.1.5(b).
(c) Giả sử, ta có điều ngược lại, tồn tại một vài x ∈ C và một vài
z ∈ Rn như vậy z T ∇2 f (x) z < 0. Từ C là mở và ∇2 f là liên tiếp, ta có
thể chọn z có mức đủ nhỏ để x + z ∈ C và z T ∇2 f (x + αz) z < 0 với
mỗi α ∈ [0, 1]. Sau đó, sử dụng một lần nữa ta thu được f (x + z) <
f (x) + ∇f (x)T z, mà theo quan điểm của Mệnh đề 1.1.5(a), mâu thuẫn
với tính lồi của f trên C
Ví dụ 1.1.3. Xét hàm toàn phương
f (x) = xT Qx + aT x,


11


ở đây Q là hàm ma trận đối xứng n × n và b là một vectơ trong Rn . Khi
∇2 f (x) = 2Q, sử dụng Mệnh đề 1.1.6, ta có f là lồi khi và chỉ khi Q là
hàm nửa xác định dương, và f là lồi ngặt khi và chỉ khi Q là hàm xác
định dương.

1.2.

Hệ bất phương trình tuyến tính và tập lồi đa
diện

1.2.1.

Hệ bất phương trình tuyến tính

Định nghĩa 1.2.1. [3]
1) Hệ bất phương trình tuyến tính n ẩn là hệ có dạng:



 a11 x1 + a12 x2 + ... + a1n xn ≤ b1

................................


 a x + a x + ... + a x ≤ b
m1 1
m2 2
mn n
m


(1.5)

trong đó x1 , x2 , ..., xn là các ẩn, aij , bi thuộc trường số thực R, với
i ∈ {1, 2, ..., m} , j ∈ {1, 2, ..., n} .
aij được gọi là hệ số của ẩn xj , bi được gọi là hạng tử tự do.
2) Một nghiệm của hệ (1.5) là một bộ n số (c1 , c2 , ..., cj , ..., cn ) thuộc
trường số thực R sao cho khi thay xj = cj thì mọi bất đẳng thức trong
hệ (1.5) đều là những bất đẳng thức đúng.
3) Ma trận


a
a12
 11
 a
 21 a22
A=
 ... ...

am1 am2

... a1n




... a2n 


... ... 


... amn


12

được gọi là ma trận các hệ số của hệ bất phương trình.
Hệ bất phương trình tuyến tính dạng: Ax ≤ b có ma trận








b
x
 1 
 1 
b 
x 
 2 
 2 
x=

; B = 
 ... 
 ... 





bm
xn
4) Hai hệ bất phương trình tuyến tính được gọi là tương đương nên chúng
có cùng một tập nghiệm.
Ta có thể viết gọn hệ bất phương trình (1.5) dưới dạng:
n

aij xj ≤ bi , i ∈ {1, 2, ..., m} .
j=1

Nếu coi mỗi cột của ma trận A như một vectơ trong không gian Rm ,
chẳng hạn:
→
−
→
−
αj = (a1j , a2j , ..., amj ) , β = (b1 , b2 , ..., bm )
thì có thể viết hệ (1.5) dưới dạng:
−
−
→x + −
→x + ... + −
→x ≤ →
α
α
α
β.

1 1
2 2
n n
và gọi đó là dạng vectơ của hệ (1.5). Như vậy, với ngôn ngữ không gian
vectơ giải hệ bất phương trình (1.5) là tìm các hệ số x để biểu diễn tuyến
→
−
→, −
→
−
→
tính β qua hệ vectơ {−
α
1 α2 , ..., αn } .
Nếu xét ánh xạ tuyến tính M xác định bởi hệ vectơ cột M =
→
−
→, −
→
−
→
{−
α
1 α2 , ..., αn } của ma trận A, và coi ξ = (x1 , x2 , ..., xn ) như một vectơ
ẩn thì hệ bất phương trình (1.5) có dạng:
M

→
−
→

−
ξ ≤ β


13

Đó là dạng ánh xạ tuyến tính của hệ (1.5). Giải hệ bất phương trình
−
(1.5) có nghĩa là tìm tập các vectơ có dạng →
γ = (c , c , ..., c ) ∈ K n sao
1

2

n

−
cho M (→
γ ) ≤ β.
1.2.2.

Tập lồi đa diện

Định nghĩa 1.2.2. [1] Một tập lồi đa diện trong Rn là một tập được
biểu diễn bằng giao của hữu hạn các nửa không gian đóng, nghĩa là tập
nghiệm của một hệ hữu hạn các bất phương trình có dạng
ai , x ≤ bi , i = 1, ..., m; ai ∈ Rn ; bi ∈ R.
Một tập lồi K được gọi là hữu hạn sinh nếu tồn tại một hệ hữu hạn các
vectơ z 1 , ..., z q sao cho
q


K=

tj z j : tj ≥ 0, ∀j = 1, ..., q

v=

.

j=1

Định nghĩa 1.2.3. [1] Tập lồi K là đa diện khi và chỉ khi K hữu hạn
sinh.

1.3.

Hàm toàn phương lồi

Định nghĩa 1.3.1. [2] Hàm toàn phương (còn gọi là hàm bậc hai) là
1
n
hàm có dạng f (x) = xT Dx + cT x + α mà D ∈ Rn×n
S , c ∈ R , α ∈ R.
2
Lưu ý: khi D = 0 (ma trận không) thì f (x) là hàm affine.
Định nghĩa 1.3.2.

(i) Một ma trận D ∈ Rn×n được gọi là xác định

dương nếu v T Dv > 0 với mỗi v ∈ Rn \ {0}. Nếu v T Dv ≥ 0 với mỗi

v ∈ Rn thì D được gọi là nửa xác định dương.
(ii) Một ma trận D ∈ Rn×n được gọi là xác định xác định âm nếu
v T Dv < 0 với mỗi v ∈ Rn \ {0}. Nếu v T Dv ≤ 0 với mỗi v ∈ Rn thì
D được gọi là nửa xác định âm.


14

1
Mệnh đề 1.3.7. [2] Cho f (x) = xT Dx + cT x + α mà D ∈ Rn×n
S , c ∈
2
Rn , α ∈ R. Nếu D là một ma trận nửa xác định dương thì f (x) là một
hàm toàn phương lồi.
Chứng minh. Từ x → cT x + α là một hàm lồi và tổng của hai hàm lồi
là một hàm lồi, nó cũng đủ cho thấy rằng f1 (x) := xT Dx là một hàm
lồi. Khi D là một ma trận nửa xác định dương, với mỗi u ∈ Rn , v ∈ Rn
ta có
0 ≤ (u − v)T D (u − v) = uT Du − 2v T Du + v T Dv.
Điều này suy ra rằng
v T Dv ≤ uT Du − 2v T D (u − v) .

(1.6)

Cho bất kì x ∈ Rn , y ∈ Rn và t ∈ (0, 1), ta đặt z = tx + (1 − t) y. Theo
(1.6) ta có
z T Dz ≤ y T Dy − 2z T D (y − z) ,
z T Dz ≤ xT Dx − 2z T D (x − z) .
Vì y − z = t (y − x) và x − z = (1 − t) (x − y), từ hai bất đẳng thức cuối
ta suy ra rằng

(1 − t) z T Dz + tz T Dz ≤ (1 − t) y T Dy + txT Dx,
vì thế
f1 (tx + (1 − t) y) = f1 (z) ≤ tf1 (x) + (1 − t) f1 (y) .
Như vậy f1 là một hàm lồi.
Nếu D là nửa xác định âm, thì hàm f cho như trên là lõm, tức là
f (tx + (1 − t) y) ≥ tf (x) + (1 − t) f (y)
với mỗi x ∈ Rn , y ∈ Rn và t ∈ (0, 1).


15

Ví dụ 1.3.1. Xét hàm toàn phương f (x) =

1 2
x1 − 2x1 x2 + 3x22 + x1 −
2

2x2 . Ta thấy
D=

1

−1

−1

3

,c=


1
−2

Do ma trận D xác định dương nên hàm f (x) đã cho là lồi chặt trên R2 .

1.4.

Bài toán tối ưu lồi
Xét một tập con lồi khác rỗng ∆ của Rn và một hàm số f : Rn →

(−∞, ∞]. Xét bài toán
(P ) : min f (x)
x∈∆

Khi đó, ta nói vectơ x∗ ∈ ∆ là một cực tiểu của f trên ∆ nếu f (x∗ ) =
inf x∈∆ f (x). Ta cũng có thể gọi x∗ là một cực tiểu hoặc cực tiểu toàn cục
trên ∆. Ngoài ra, ta nói f đạt cực tiểu trên ∆ tại x∗ , và ta viết
x∗ ∈ Sol (P ) := arg min f (x) .
x∈∆

Nếu x∗ là cực tiểu duy nhất của f trên ∆, thì ta viết
x∗ = arg min f (x) .
x∈∆

Tương tự cho bài toán cực đại, tức là, một vectơ x∗ ∈ ∆ sao cho f (x∗ ) =
supx∈∆ f (x) gọi là một cực đại của f trên ∆, và ta viết
x∗ ∈ arg max f (x) .
x∈∆

Nếu ∆ = Rn hoặc nếu miền của f là tập ∆ (thay cho Rn ), ta cũng có thể

gọi x∗ là một cực tiểu (toàn cục) hoặc cực đại (toàn cục) của f (không
có "trên ∆").
Một câu hỏi cơ bản trong bài toán tối ưu là có tồn tại nghiệm tối
ưu hay không. Ta có thể tìm được tập cực tiểu của f trên ∆ bằng giao


16

điểm của ∆ với các tập mức khác rỗng của f . Sử dụng điều này, ta có
thể chứng minh tập các cực tiểu là khác rỗng nếu tập có dạng
{x ∈ ∆|f (x) ≤ γ} ,
ở đây γ là một số thực, là đóng và ít nhất một trong số chúng là khác
rỗng và compact. Đây là nội dung của Định lý Weierstrass cổ điển, phát
biểu cho một hàm liên tục cực tiểu trên một tập compact.
Ta sẽ chứng minh một phiên bản mở rộng hơn của Định lý này. Ta nói
hàm f : Rn → (−∞, ∞] là bức trên một tập ∆ ⊂ Rn nếu với mỗi dãy
{xk } ⊂ ∆ sao cho xk → ∞, thì lim f (xk ) = ∞. Trong trường hợp
k→∞

n

∆ = R , ta nói f là bức. Chú ý một hệ quả của định nghĩa, mọi tập mức
khác rỗng của hàm bức f là bị chặn.
Định lý 1.4.1. [4] (Định lý Weierstrass). Xét một hàm lồi chính thường
đóng f : Rn → (−∞, ∞], và giả sử một trong ba điều kiện sau đây là
đúng:
(1) dom(f ) là bị chặn.
(2) Tồn tại một số thực γ sao cho tập mức
{x|f (x) ≤ γ}
là khác rỗng và bị chặn.

(3) f là hàm bức.
Khi đó tập cực tiểu của f trên Rn là khác rỗng và compact.
Chứng minh. Giả sử điều kiện (1) đúng. Chú ý rằng vì f là chính thường,
dom(f ) là khác rỗng. Xét dãy {xk } ⊂ dom (f ) sao cho
lim f (xk ) = infn f (x) .

k→∞

x∈R


17

Vì dom(f ) là bị chặn nên dãy có ít nhất một điểm giới hạn x∗ . Vì f đóng
nên f là nửa liên tục dưới tại x∗ , do đó f (x∗ ) ≤ lim f (xk ) = infn f (x),
k→∞

x∈R

∗

và x là một cực tiểu của f . Như vậy, Sol(P ), tập các cực tiểu của f trên
Rn , là khác rỗng. Vì Sol(P ) ⊂ dom (f ) và dom(f ) là bị chặn, Sol(P ) là
bị chặn. Tuy nhiên Sol(P ) là giao của tất cả các tập mức {x|f (x) ≤ γ}
trong đó γ > infn f (x). Các tập mức là đóng vì f đóng, bởi vậy Sol(P )
x∈R

là đóng, và vì thế compact.
Giả sử điều kiện (2) đúng. Thay f bởi hàm số
f˜ (x) =


f (x) khi f (x) ≤ γ,
∞

khi f (x) > γ

Miền xác định của f˜ là tập {x|f (x) ≤ γ}. Nó bị chặn bởi giả thiết và
đóng bởi tính đóng của f . Vì thế, sử dụng tính đóng của f , suy ra hàm
f˜ là đóng. Hơn nữa, tập cực tiểu của f˜ bằng tập cực tiểu của f . Áp dụng
điều kiện (1) ta có điều phải chứng minh.
Giả sử điều kiện (3) đúng. Vì f là chính thường, nên có một vài
tập mức khác rỗng. Vì f là bức, nên các tập mức khác rỗng bị chặn, do
đó điều kiện (2) là thỏa mãn.
Thường thì bài toán tối ưu chúng ta phải đề cập đến dạng yếu hơn
của cực tiểu, tức là chỉ khi so sánh giá trị ở các điểm "lân cận" với nhau.
Đặc biệt, cho một tập con ∆ của Rn và một hàm số f : Rn → (−∞, ∞],
ta nói vectơ x∗ ∈ ∆ là cực tiểu địa phương của f trên ∆ nếu tồn tại
ε > 0 sao cho
f (x∗ ) ≤ f (x) , ∀x ∈ ∆ : x − x∗ ≤ ε.
Nếu ∆ = Rn hoặc miền xác định của f là tập ∆ (thay cho Rn ), ta có thể
gọi x∗ là một cực tiểu địa phương của f (không có "trên ∆"). Một cực
tiểu địa phương x∗ được gọi là ngặt nếu không có cực tiểu địa phương
khác ở trong cùng một lân cận của x∗ . Cực đại địa phương được định
nghĩa tương tự.


18

Trong các ứng dụng thực tế ta thường quan tâm đến cực tiểu toàn
cục, nhưng ta phải làm việc với cực tiểu địa phương vì không có nhiều

điều kiện tối ưu và các thuật toán để phân biệt giữa hai loại cực tiểu
này. Đây có thể là khó khăn lớn, nhưng một ý nghĩa quan trọng của tính
lồi của f và ∆ là tất cả cực tiểu địa phương đều là cực tiểu toàn cục
được thể hiện trong mệnh đề sau.
Mệnh đề 1.4.8. [4] Nếu ∆ là tập con lồi của Rn và f : Rn → (−∞, ∞]
là một hàm lồi chính thường, thì cực tiểu địa phương của f trên ∆ cũng
là cực tiểu toàn cục của f trên ∆. Ngoài ra, nếu f là lồi ngặt, thì tồn
tại nhiều nhất là một cực đại toàn cục của f trên ∆.
Chứng minh. Cho f lồi, và giả thiết ngược lại, rằng x∗ là cực tiểu địa
phương của f trên ∆ sao cho nó không toàn cục. Khi đó, tồn tại x¯ ∈ ∆
sao cho f (¯
x) < f (x∗ ). Theo tính lồi, với mọi α ∈ (0, 1),
f (αx∗ + (1 − α) x¯) ≤ αf (x∗ ) + (1 − α) f (¯
x) < f (x∗ ) .
Như vậy, f là giá trị nhỏ hơn f (x∗ ) tại mỗi điểm trên đoạn thẳng nối x∗
với x¯, ngoại trừ x∗ . Khi ∆ là lồi, đoạn thẳng thuộc ∆, do đó mâu thuẫn
với x∗ là cực tiểu địa phương.
Cho f lồi ngặt, và giả thiết ngược lại, rằng tồn tại hai cực tiểu
toàn cục x và y phân biệt của f trên ∆. Khi đó, trung điểm (x + y) /2
có thể thuộc ∆, từ đó ∆ là lồi. Hơn nữa, vì tính lồi ngặt của f nên giá
trị của f có thể nhỏ hơn tại trung điểm của x và y. Từ đó x và y là cực
tiểu toàn cục. Dẫn tới mâu thuẫn.
Kết luận chương 1
Chương này nhằm trình bày những khái niệm cơ bản nhất và
những tính chất đặc trưng về tập lồi, hàm lồi, nón lùi xa của một tập
lùi, tập lồi đa diện, hệ bất phương trình tuyến tính, hàm toàn phương
lồi và bài toán tối ưu lồi, ... sẽ được sử dụng cho chương sau.