BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
—————————-

TRẦN NGỌC THĂNG

PHƯƠNG PHÁP GIẢI MỘT SỐ LỚP BÀI TOÁN
TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG DỤNG

LUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI - 2017


Lời mở đầu
1. Giới thiệu bài toán tối ưu đa mục tiêu
Trong những năm 50 của thế kỷ 20, Quy hoạch đa mục tiêu, hay còn được gọi là
Tối ưu đa mục tiêu hoặc Tối ưu véc tơ, đã trở thành một chuyên ngành toán học,
thu hút sự quan tâm của nhiều tác giả và được phát triển mạnh mẽ suốt gần 70
năm qua. Các thành tựu của Quy hoạch đa mục tiêu được ứng dụng rộng rãi trong
thực tế, đặc biệt là trong lý thuyết ra quyết định, kinh tế, tài chính, kỹ thuật, viễn
thông,... (xem [23], [64], [83], [93], [94],...).
Bài toán quy hoạch đa mục tiêu được phát biểu dưới dạng
Min f (x) = ( f1 (x), f2 (x), . . . , f p (x))

với điều kiện

x ∈ X,

(MOP)


f . Lý do chính cho hướng tiếp cận này là: i) Các bài toán tối ưu đa mục tiêu nảy
sinh trong thực tế thường có số hàm mục tiêu p nhỏ hơn rất nhiều so với số biến
n, hay thứ nguyên của không gian ảnh R p nhỏ hơn rất nhiều so với thứ nguyên của
không gian quyết định Rn ; ii) Nhiều điểm của tập nghiệm hữu hiệu (tương ứng1 ,
tập nghiệm hữu hiệu yếu) có thể có cùng một ảnh qua ánh xạ f nên tập ảnh hữu
hiệu YE (t.ư., tập ảnh hữu hiệu yếu YW E ) có cấu trúc đơn giản hơn XE (t.ư., XW E );
iii) Trong quá trình đưa ra quyết định, người ta thường lựa chọn phương án dựa
trên giá trị hữu hiệu hơn là dựa trên nghiệm hữu hiệu (xem [11]).
Trong tối ưu đa mục tiêu, việc nghiên cứu để giải bài toán quy hoạch đa mục
tiêu tuyến tính (LMOP) có thể xem gần như hoàn chỉnh. Đã có nhiều cuốn sách
chuyên khảo về bài toán (LMOP) (xem [57], [59], [92], [93],... và danh mục tài
liệu tham khảo kèm theo). Rất nhiều thuật toán đã được đề xuất theo cả hai hướng
tiếp cận trên không gian quyết định và không gian ảnh để giải bài toán này bằng
nhiều phương pháp khác nhau như phương pháp đơn hình đa mục tiêu, phương
pháp tham số, phương pháp vô hướng hóa, phương pháp nón pháp tuyến, phương
pháp xấp xỉ ngoài hoặc kết hợp của các phương pháp đó, chẳng hạn xem các công
trình của M. Zeleny [94], P. Armand and C. Malivert [7], R.E. Steuer [83], J.P.
Dauer và Y.H. Liu [27], H.P. Benson [11], N.T.B. Kim và D.T. Lục [44], [45], M.
Ehrgott, A. L¨ohne và L. Shao [29],...
1 Từ

sau đây đến hết luận án, cụm từ "tương ứng" sẽ được viết tắt là "t.ư.".

ix


Với bài toán quy hoạch đa mục tiêu lồi và không lồi, đã có một số thuật toán
được đề xuất. Hầu hết các thuật toán theo tiếp cận trên không gian quyết định được
thiết kế dựa trên các phương pháp trọng số [25], phương pháp ε−ràng buộc [36],
phương pháp hàm lợi ích [93], phương pháp lexicographic [20], phương pháp



loại theo hai hướng tiếp cận bao gồm tiếp cận trên không gian quyết định Rn (xem
H.P. Benson [10], J.P. Dauer và T.A. Fosnaugh [26, 1995], L.T.H. An, L.D. Mưu
và P.D. Tảo [4], L.T. Lực và L.D. Mưu [60], L.D. Mưu [67], N.T.B. Kim [42], N.V.
Thoại [87], L.D. Mưu và H.Q. Tuyến [70], N.V. Thoại, Y. Yamamoto và D. Zenke
[39], L.T.H. An, P.D. Tảo, N.C. Nam và L.D. Mưu [5], L.D. Mưu và L.Q. Thủy
[69],...) và tiếp cận trên không gian ảnh R p (xem R. Horst và N.V. Thoại [38], J.
Fulop and L.D. Mưu [31], Y. Yamamoto [91], N.T.B. Kim và L.D. Mưu [47], N.V.
Thoại [88], H.P. Benson [16],...). Ta cũng có thể phân loại các thuật toán dựa theo
phương pháp được dùng để xây dựng thuật toán, như thuật toán xấp xỉ ngoài, thuật
toán nhánh cận, thuật toán theo tiếp cận đối ngẫu, thuật toán tìm đỉnh kề, thuật
toán tìm đỉnh không kề,... (xem [92])
Bài toán quy hoạch tích và các dạng mở rộng của nó (gọi chung là bài toán quy
hoạch tích mở rộng) có nhiều ứng dụng quan trọng trong các lĩnh vực khác nhau
như kinh tế tài chính, tối ưu hóa quy trình sản xuất, tối ưu danh mục đầu tư, thiết
kế chip VLSI,... Đây cũng là lớp các bài toán tối ưu toàn cục khó và thú vị nên đã
thu hút sự quan tâm đặc biệt của nhiều tác giả. Bài toán quy hoạch tích được phát
biểu như sau

p

min ∏ f j (x),

v.đ.k.

x ∈ X,

(MP)


công sức.
Luận án này nghiên cứu và đề xuất các thuật toán mới để giải các bài toán sau:
1. Bài toán quy hoạch đa mục tiêu lồi suy rộng
Min f (x) = ( f1 (x), f2 (x), . . . , f p (x))

v.đ.k.

x ∈ X,

(GMOP)

trong đó tập chấp nhận được X ⊂ Rn là tập lồi compact khác rỗng và hàm
mục tiêu f là hàm véc tơ giả lồi vô hướng trên X.
2. Bài toán quy hoạch tích lồi suy rộng tương ứng với bài toán (GMOP)
m

min ∏ f j (x),

v.đ.k.

x ∈ X,

(GMP)

j=1

trong đó các hàm số f j : Rn → R, j = 1, . . . , m và tập chấp nhận được X được
giả thiết như trong phát biểu của bài toán (GMOP).
3. Bài toán quy hoạch tích lõm mở rộng, trong đó hàm mục tiêu có dạng tổng
của một hàm với tích các hàm và tập chấp nhận được là tập lồi compact khác


(QP)

trong đó ϕ : R2 → R là hàm tựa lõm trên tập ảnh Y và bài toán
max h(x) = ϕ( f (x)) v.đ.k. x ∈ XE ,

(DP)

với ϕ : R2 → R là hàm đơn điệu tăng trên tập ảnh Y . Dạng hàm mục tiêu
h(x) = ϕ( f (x)) với hàm số thực ϕ : Y → R xuất hiện nhiều trong các bài toán
nảy sinh từ thực tế và cũng đã được nhiều tác giả quan tâm nghiên cứu, chẳng
hạn [47], [87], [88], [91] và danh sách tài liệu tham khảo kèm theo.
Tất cả các thuật toán được đề xuất trong luận án đều được chứng minh là hội tụ,
đồng thời được tính toán thử nghiệm và so sánh với một số thuật toán đã có. Ngoài
các bài toán trên, chúng tôi đã nghiên cứu và đề xuất thuật toán giải bài toán cực
đại tổng một hàm lõm với các cặp tích hai hàm lõm trên tập lồi compact khác rỗng,

xiii


cụ thể là bài toán
s

max g(x) = f1 (x) + ∑ f2i (x)f2i+1 (x) v.đ.k. x ∈ X,

(GCMP)

i=1

trong đó X ⊂ Rn là tập lồi compact khác rỗng và f j , j = 1, . . . , 2s + 1, là các hàm

lồi suy rộng” đề xuất một thuật toán hướng pháp tuyến giải bài toán quy hoạch đa
mục tiêu lồi suy rộng (GMOP), trong đó sử dụng kỹ thuật xấp xỉ ngoài trên không
gian ảnh để xác định tập nghiệm hữu hiệu yếu θ −xấp xỉ của bài toán (GMOP).
Cách xác định điểm giá trị hữu hiệu yếu và hướng pháp tuyến tại mỗi bước lặp điển
hình được giới thiệu ở Mục 2.1. Thuật toán chi tiết được mô tả trong Mục 2.2. Tiếp
theo, Mục 2.3 sẽ trình bày chi tiết chứng minh tính hội tụ của thuật toán đề xuất.
Đây là một đóng góp chính và quan trọng về mặt lý thuyết cho các phương pháp
xấp xỉ ngoài giải bài toán quy hoạch đa mục tiêu. Các kết quả tính toán thử nghiệm
được giới thiệu trong Mục 2.4 chứng tỏ tính hiệu quả và những ưu điểm của thuật
toán so với một số thuật toán xấp xỉ ngoài giải bài toán quy hoạch đa mục tiêu lồi
trước đó.
Chương 3. “Thuật toán giải một số bài toán quy hoạch tích mở rộng” đưa ra
các thuật toán theo tiếp cận trên không gian ảnh để giải hai bài toán quy hoạch
tích: Bài toán quy hoạch tích lồi suy rộng (GMP) và Bài toán quy hoạch tích lõm
mở rộng (GIMP). Thuật toán giải bài toán (GMP) được giới thiệu trong Mục 3.1.
Thuật toán này được thiết lập dựa trên mối quan hệ của bài toán quy hoạch tích
lồi suy rộng (GMP) và bài toán quy hoạch đa mục tiêu (GMOP) tương ứng. Đây
cũng được xem như là một ứng dụng của thuật toán giải bài toán (GMOP) đã thiết
lập ở Chương 2. Mục 3.2 dành để trình bày thuật toán giải bài toán (GIMP). Bằng
các biến đổi thích hợp, việc giải bài toán này được đưa về việc giải bài toán cực
đại một hàm đơn điệu tăng trên tập các điểm hữu hiệu của một tập lồi đóng trong
R2 . Các tính toán thử nghiệm chứng tỏ tính hiệu quả của thuật toán đề xuất.
Chương 4. “Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu” đề xuất
các thuật toán trên không gian ảnh để giải hai bài toán (QP) và (DP) nhằm tối ưu
một hàm hợp trên tập nghiệm hữu hiệu của bài toán quy hoạch hai mục tiêu lồi,
tức bài toán (CMOP) với p = 2. Bằng cách biến đổi các bài toán gốc về bài toán
tương đương trên không gian ảnh và tận dụng cấu trúc đặc biệt của tập ảnh hữu
hiệu và tính chất đặc thù của các hàm mục tiêu, Mục 4.1 đề xuất một thuật toán
nhánh cận giải bài toán (QP) và Mục 4.2 đưa ra một thuật toán nhánh cận kết hợp
với lược đồ xấp xỉ ngoài giải bài toán (DP).

bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) và trường hợp riêng của nó
là bài toán quy hoạch đa mục tiêu lồi (CMOP). Để tiện theo dõi, chương này giới
thiệu mô hình toán học của bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP)
cùng một số khái niệm và kết quả cơ bản liên quan. Các khái niệm và kết quả được
trình bày ở đây là sự chuẩn bị để thiết lập cơ sở lý thuyết cho các thuật toán được
đề xuất trong các chương sau của luận án.
Một số hàm lồi suy rộng như hàm tựa lồi, hàm giả lồi, hàm véc tơ giả lồi vô
hướng cùng các tính chất hữu dụng của chúng được giới thiệu ở Mục 1.1. Mục này
cũng trình bày về định lý KKT về điều kiện tối ưu cho bài toán quy hoạch lồi suy
rộng một mục tiêu. Định lý này được dùng làm công cụ lý thuyết để xác định siêu
phẳng cắt trong thuật toán xấp xỉ ngoài được đề xuất trong Chương 2 để giải bài
toán (GMOP).
Như đã biết, khái niệm nền tảng của tối ưu véc tơ là điểm hữu hiệu và điểm hữu
yếu của một tập, nhờ đó, người ta mới có thể hiểu được thế nào là nghiệm của bài
toán quy hoạch đa mục tiêu. Các khái niệm điểm hữu hiệu, điểm hữu hiệu yếu của
một tập, điều kiện nhận biết thông qua khái niệm hướng pháp tuyến và các kết quả
về cấu trúc của các tập điểm này sẽ được trình bày ở Mục 1.2.
1


Cuối cùng, Mục 1.3 giới thiệu bài toán quy hoạch đa mục tiêu lồi suy rộng
(GMOP), cùng các khái niệm cơ bản như nghiệm hữu hiệu, nghiệm hữu hiệu yếu,
nghiệm hữu hiệu θ -xấp xỉ, nghiệm hữu hiệu yếu θ -xấp xỉ cũng như cấu trúc của
tập giá trị hữu hiệu và của tập giá trị hữu hiệu yếu của bài toán (GMOP).

1.1

Hàm lồi suy rộng

Cho tập lồi khác rỗng S ⊆ Rn và hàm số h : Rn → R. Ta nói h là hàm lồi xác định

lại, nếu ϕ là hàm lồi thì 1/ϕ chưa chắc là hàm lõm trên S.
Dễ thấy, hàm ϕ(x) = ex với x ∈ R là hàm lồi trên R nhưng hàm 1/ϕ(x) = e−x
không phải làm hàm lõm trên R.
Khẳng định sau chỉ ra điều kiện đủ để một hàm phân thức là tựa lồi (xem Bảng
5.4 [8, tr. 165] và Bài tập 9.6.3 [66, tr. 149]).
Mệnh đề 1.2. Cho hai hàm số ϕ1 , ϕ2 xác định trên tập lồi khác rỗng S ⊆ Rn .
i) Nếu ϕ1 là hàm lồi, ϕ2 là hàm lõm trên S thỏa mãn ϕ1 (x) ≥ 0 và ϕ2 (x) > 0
với mọi x ∈ S thì hàm phân thức h = ϕ1 /ϕ2 là hàm tựa lồi trên S;
ii) Nếu ϕ1 , ϕ2 là hai hàm afin và ϕ2 (x) = 0 với mọi x ∈ S thì hàm phân thức
h = ϕ1 /ϕ2 là hàm vừa tựa lồi, vừa tựa lõm trên S.
Ví dụ 1.1. Cho các hàm lõm φi , i = 1, . . . , m, trong đó m ≥ 2, nhận giá trị dương
trên tập lồi S ⊆ Rn và các số thực αi > 0, i = 1, . . . , m. Khi đó,
m

h(x) = ∏ φiαi (x)
i=1

là hàm tựa lõm trên S (Định lý 5.15 [8, tr. 161]). Đặc biệt, Mệnh đề 1.3 sau đây
khẳng định rằng, nếu αi = 1 với mọi i = 1, . . . , m, thì trung bình nhân của h lại là
hàm lõm. Tính chất này sẽ được sử dụng trong Chương 3 của luận án để phân tích
và giải bài toán quy hoạch tích mở rộng (GIMP).
Mệnh đề 1.3. (Mệnh đề 2.7 [89, tr. 47]) Nếu φi (x), i = 1, . . . , m, là các hàm lõm

3


nhận giá trị dương trên tập lồi S ⊆ Rn thì hàm
m

h(x) =

Mệnh đề 1.4. (xem [8, tr. 165]) Cho hai hàm số ϕ1 , ϕ2 xác định trên tập lồi khác
rỗng S ⊆ Rn . Nếu ϕ1 là hàm lồi khả vi và ϕ2 là hàm afin nhận giá trị dương trên S
thì hàm phân thức h = ϕ1 /ϕ2 là hàm giả lồi trên S.
4


Định lý 1.1. (Xem Định lý 9.3.3 [66, tr. 142]) Cho h là hàm giả lồi trên tập lồi S
và x∗ là một điểm dừng của bài toán (PS ), tức ∇h(x∗ ), x − x∗ ≥ 0 với mọi x ∈ S.
Khi đó, x∗ là nghiệm tối ưu toàn cục của bài toán (PS ).
Các định lý sau chỉ ra rằng lớp các hàm lồi được chứa trong lớp các hàm giả lồi,
và lớp các hàm giả lồi được chứa trong lớp các hàm tựa lồi.
Định lý 1.2. (Định lý 9.3.6 [66, tr. 144]) Cho S là tập lồi trong Rn và hàm h xác
định, khả vi trên một tập mở chứa S. Nếu h là hàm lồi (t.ư., lõm) trên S thì h là giả
lồi (t.ư., giả lõm) trên S. Điều ngược lại chưa chắc đúng.
Định lý 1.3. (Định lý 9.3.5 [66, tr. 143]) Cho S là tập lồi trong Rn và hàm h xác
định trên một tập mở chứa S. Nếu h là hàm giả lồi trên S thì h là tựa lồi trên S.
Điều ngược lại chưa chắc đúng.
Ví dụ 1.3. Xét hàm h(x) = 1 − x3 xác định trên R. Theo định nghĩa, h là hàm tựa
lồi trên R. Tuy nhiên, điểm x = 0 là điểm dừng nhưng nó không phải nghiệm tối
ưu của bài toán min{h(x) | x ∈ R}. Vì vậy, theo Định lý 1.1, h không phải là hàm
giả lồi trên S.
Khác với lớp các hàm lồi, tính giả lồi và tựa lồi của hàm số không được bảo
toàn qua phép cộng, tức tổng của hai hàm giả lồi chưa chắc đã là hàm giả lồi.
Ví dụ 1.4. Cho hai hàm h1 (x) = tan x và h2 (x) = −x xác định trên S = − π2 , π2 .
Theo Ví dụ 1.2, h1 là hàm giả lồi trên S. Vì h2 là hàm tuyến tính trên S nên h2 cũng
là hàm giả lồi trên S. Tuy nhiên, hàm h(x) = h1 (x) + h2 (x) = tan x − x không phải
là hàm giả lồi trên S. Thật vậy, điểm x = 0 là điểm dừng của hàm h do h (0) = 0.
Mặt khác, x = 0 không phải là nghiệm tối ưu của bài toán min{h(x) | x ∈ S} vì
h(0) > h(−π/4). Theo Định lý 1.1, h không phải là hàm giả lồi trên S.
Mệnh đề sau khẳng định lớp các hàm giả lồi và tựa lồi vẫn đóng đối với phép

ii) Nếu f là hàm véc tơ lồi trên S thì f cũng là hàm véc tơ giả lồi vô hướng trên
S. Thật vậy, nếu f là hàm véc tơ lồi trên S thì các hàm thành phần f1 , . . . , f p cũng
p
là các hàm lồi. Do đó, với mọi λ = (λ1 , . . . , λ p ) ≥ 0, hàm ∑i=1
λi fi cũng là hàm lồi
p
trên S. Theo Định lý 1.2, ta suy ra ∑i=1 λi fi là hàm giả lồi trên S với mọi λ ≥ 0,

tức f là hàm véc tơ giả lồi vô hướng trên S.

6


Ví dụ 1.5. Cho hàm véc tơ f (x) = ( f1 (x), f2 (x)), trong đó
5x12 + 10x2
5x1 − 5x22
f1 (x) =
và f2 (x) =
x1 − x2
x2 − x1
là hai hàm số xác định trên tập S = {x ∈ R2 | Ax ≥ b, x ≥ 0} và




1 1
3




7


Theo Mệnh đề 1.4, hàm λ1 f1 (x) + λ2 f2 (x) = ϕ1 (x)/ϕ2 (x) là giả lồi trên S. Suy ra
f là hàm giả lồi vô hướng trên S.
Cho hàm giả lồi h và các hàm tựa lồi g1 , . . . , gm xác định trên Rn . Xét bài toán
min h(x) v.đ.k. x ∈ S,

(SOP)

trong đó S = {x ∈ Rn | gi (x) ≤ 0, i = 1, . . . , m}. Do mọi tập mức dưới của hàm tựa
lồi là tập lồi nên tập chấp nhận được S là tập lồi.
Như thường lệ, với mỗi điểm x¯ ∈ S, ta ký hiệu
I(x)
¯ = {i ∈ {1, . . . , m} | gi (x)
¯ = 0}
là tập chỉ số của các ràng buộc thỏa mãn chặt tại x.
¯ Số phần tử của tập I(x)
¯ được
ký hiệu là |I(x)|.
¯ Định lý KKT sau đây đóng vai trò quan trọng trong việc thiết
lập cơ sở lý thuyết của thuật toán giải bài toán quy hoạch đa mục tiêu lồi suy rộng
được trình bày trong Chương 2. Kết quả này có thể xem là sự kết hợp của Định lý
10.2.7 [66, tr. 156] và Định lý 10.1.2 [66, tr. 151].
Định lý 1.4. Cho hàm giả lồi h và hàm véc tơ tựa lồi g = (g1 , . . . , gm ) khả vi liên
tục trên một tập mở chứa S. Giả sử điều kiện Slater được thỏa mãn, tức
∃ x∗ ∈ S : gi (x∗ ) < 0 với mọi i = 1, . . . , m.
Khi đó, x¯ là nghiệm tối ưu của bài toán (SOP) khi và chỉ khi tồn tại một véc tơ
u¯ ∈ Rq , trong đó q = |I(x)|
¯ , sao cho

p
p
điểm bất kỳ a, b ∈ R p , ta viết a ≥ b nếu a − b ∈ R+
và a > b nếu a − b ∈ intR+
.

Cho tập khác rỗng Q ⊂ R p . Ta nói q∗ ∈ Q là điểm hữu hiệu theo nghĩa cực tiểu
của tập Q nếu
p
∃q ∈ Q sao cho q∗ ≥ q và q∗ = q ⇔ (q∗ − R+
) ∩ Q = {q∗ }.

Điểm q∗ được gọi là điểm hữu hiệu theo nghĩa cực đại của tập Q nếu
p
∃q ∈ Q sao cho q ≥ q∗ và q∗ = q ⇔ (q∗ + R+
) ∩ Q = {q∗ }.

Tập tất cả các điểm hữu hiệu theo nghĩa cực tiểu và cực đại của Q được ký hiệu
tương ứng là MinQ và MaxQ. Tương tự, ký hiệu WMinQ và WMaxQ lần lượt là
tập tất cả các điểm hữu hiệu yếu theo nghĩa cực tiểu và cực đại của Q và được định
nghĩa là
WMinQ = {q∗ ∈ Q | ∃q ∈ Q sao cho q∗ > q}
p
= {q∗ ∈ Q | (q∗ − intR+
) ∩ Q = 0};
/

WMaxQ = {q∗ ∈ Q | ∃q ∈ Q sao cho q > q∗ }
p
= {q∗ ∈ Q | (q∗ + intR+

(q∗ − θ ) − intR+
∩ Q = 0,
/

thì q∗ được gọi là điểm hữu hiệu yếu θ -xấp xỉ của Q. Tập tất cả các điểm hữu hiệu
θ -xấp xỉ và tập tất cả các điểm hữu hiệu yếu θ -xấp xỉ của tập Q được ký hiệu tương
ứng là Min(Q, θ ) và WMin(Q, θ ).
Cho một tập đóng khác rỗng Q ⊂ R p và một điểm q∗ ∈ Q. Véc tơ v ∈ R p được
gọi là một hướng pháp tuyến (trong) của Q tại q∗ nếu
v, q − q∗ ≥ 0 với mọi q ∈ Q.
Nói cách khác, véc tơ v là một hướng pháp tuyến của Q tại q∗ ∈ Q nếu q∗ là nghiệm
của bài toán min { v, q | q ∈ Q} . Dễ thấy, véc tơ v ∈ R p \ {0} là hướng pháp tuyến
10


của tập Q tại q∗ khi và chỉ khi v là véc tơ pháp tuyến của siêu phẳng tựa
H = {q ∈ R p | v, q = v, q∗ }
của tập Q tại điểm q∗ . Tập {q ∈ R p | v, q ≥ v, q∗ } được gọi là nửa không gian
tựa của Q tại q∗ . Nếu Q là tập lồi đóng khác rỗng thì luôn tồn tại ít nhất một siêu
phẳng tựa của Q tại mỗi điểm biên q∗ của nó (xem Định lý 2.3 [2, tr. 31]).
Tập tất cả các hướng pháp tuyến của Q tại q∗ được gọi là nón pháp tuyến của
tập Q tại q∗ và ký hiệu là NQ (q∗ ) (xem Định nghĩa 6.3 [77, tr. 199]). Nếu Q là tập
lồi đóng khác rỗng thì NQ (q∗ ) là một nón lồi đóng. Dễ thấy rằng NQ (q∗ ) = {0} khi
và chỉ khi q∗ là điểm trong của Q. Hình 1.3 minh họa các nón pháp tuyến NQ (q1 )
và NQ (q2 ) của tập Q tại các điểm q1 , q2 ∈ Q, tương ứng.
Như đã biết, nón pháp tuyến đóng vai trò quan trọng trong việc thiết lập điều
kiện tối ưu của bài toán tối ưu. Các kết quả về nón pháp tuyến của một tập và ứng
dụng của nó có thể được tham khảo chi tiết trong các cuốn sách chuyên khảo [76]
của Rockafellar và [77] của Rockafellar và Wets.


Khẳng định (i) của Định lý 1.5 chỉ là điều kiện đủ, tức không phải tại điểm
hữu hiệu nào của Q cũng tồn tại một hướng pháp tuyến dương. Chẳng hạn, xét
Q = {q ∈ R2 | q ≤ 1}. Dễ thấy, điểm q∗ = (−1, 0) là điểm hữu hiệu của Q
nhưng rõ ràng không có ξ ∈ intR2+ để ξ , q − q∗ ≥ 0 với mọi q ∈ Q.
Mệnh đề 1.6. (Xem Mệnh đề 5.24 [58]) Nếu tập Q ⊂ R p là đóng thì tập điểm hữu
hiệu yếu WMinQ là tập đóng. Nếu Q là tập compact thì WMinQ là tập compact.
12


Lưu ý rằng, tập điểm hữu hiệu MinQ chưa chắc là tập đóng, kể cả khi Q là tập
compact. Chẳng hạn, xét tập
Q = {q ∈ R2 | q1 + q2 ≥ 1, q1 ≤ 1, q2 ≤ 1} ∪ {(−1, 1)}.
Dễ thấy Q là tập compact nhưng MinQ không phải là tập đóng. Cụ thể, ta có
MinQ = {(−1, 1)} ∪ {q ∈ R2 | q1 + q2 = 1, q1 ≤ 1, q2 < 1}.
Như đã biết, ngay trong trường hợp đơn giản nhất, khi Q ⊂ R p là tập lồi đa diện,
tập điểm hữu hiệu và tập điểm hữu hiệu yếu của Q tuy là tập liên thông đường gấp
khúc, bao gồm một số diện đóng của Q, nhưng nói chung, chúng là các tập không
lồi và có cấu trúc phức tạp (xem Định lý 2.2 [57, trang 137]).
Trường hợp đặc biệt, khi Q là tập lồi đóng khác rỗng trong R2 thì tập điểm hữu
hiệu của Q có tính chất rất đặc sắc như được mô tả trong kết quả sau. Tính chất này
là công cụ hữu ích trong việc xây dựng các thuật toán để giải bài toán tối ưu trên
tập nghiệm hữu hiệu của bài toán quy hoạch hai mục tiêu lồi, được trình bày trong
Chương 4 của luận án.
Định lý 1.6. (Xem Định lý 1.2 [40] và Định lý 3 [74]) Cho Q ⊂ R2 là một tập lồi
đóng khác rỗng và có điểm hữu hiệu. Khi đó, tập điểm hữu hiệu MinQ đồng phôi
với một đoạn đóng khác rỗng trong R.
p
p
Xét một tập đóng khác rỗng Q ⊂ R p . Dễ thấy Q + R+
và Q − R+

Hình 1.5: Minh họa tập Q và Q+

Theo Mệnh đề 1.7(i), để thuận tiện, ta gọi Q+ và Q− là các tập tương đương
hữu hiệu của Q theo nghĩa cực tiểu và theo nghĩa cực đại, tương ứng. Khái niệm
này đã được sử dụng trong [47].
Tập các điểm hữu hiệu yếu WMinQ+ (t.ư., WMaxQ− ) có mối liên hệ với biên
∂ Q+ của tập Q+ (t.ư., biên ∂ Q− của tập Q− ) như mô tả ở mệnh đề sau.
Mệnh đề 1.8.

∂ Q+ = WMinQ+ và ∂ Q− = WMaxQ− .

Chứng minh. Do tính tương tự, ta chỉ cần chứng minh ∂ Q+ = WMinQ+ . Thật vậy,
lấy tùy ý một điểm y¯ trên biên của Q+ . Ta sẽ chứng minh y¯ là một điểm hữu hiệu
yếu của Q+ . Thật vậy, giả sử phản chứng y¯ không phải là một điểm hữu hiệu yếu
của Q+ . Theo định nghĩa, tồn tại một điểm y ∈ Q+ thỏa mãn y¯ > y. Khi đó
p
p
y¯ ∈ y + intR+
⊆ Q+ + intR+
⊆ intQ+ .

14


Điều này trái với giả thiết y¯ ∈ ∂ Q+ . Vậy y¯ ∈ WMinQ+ , tức ∂ Q+ ⊆ WMinQ+ . Hơn
nữa, như đã biết, mọi điểm hữu hiệu yếu của một tập đều thuộc biên của nó, tức là
WMinQ+ ⊆ ∂ Q+ . Suy ra điều phải chứng minh.
m
M
M

hiệu yếu của tập Q+ nằm trên tia xuất phát từ yO và đi qua v (xem Hình vẽ 1.6).

Hình 1.6: Cách xác định một điểm hữu hiệu yếu của tập Q+

15