Bài giảng Toán tối ưu - Hoàng Quang Tuyến

n điều
kiện Slater. Lúc đó x∗ là lời giải của (P ) khi và chỉ khi tồn tại y∗ ≥ 0 để
(x∗, y∗) là điểm yên ngựa của L(hàm Lagrange) trên X ×Rm+ và y∗ là nghiệm
của bài toán đối ngẫu (D).
Chứng minh. ⇐) Suy ra từ định lý (2.9)
⇒) Giả sử x∗ ∈ argmin(P ). Do (P ) lồi, thỏa mãn điều kiện Slater (tức
∃x0 ∈ X : gj(x0) < 0,∀j = 1,m). Do đó, theo định lý (2.7) cặp (P ), (D) là đối
ngẫu chính xác:
f(x∗) = d(y∗) với y∗ ≥ 0
Theo định nghĩa của d(y∗):
f(x∗) = d(y∗) = inf
x∈X
L(x, y∗)
Nghĩa là x∗ là điểm cực tiểu của L(., y∗) (thỏa mãn điều kiện i) của định lý
(2.8))
Ngoài ra
f(x∗) ≤ f(x) + ⟨y∗, g(x)⟩ , ∀x ∈ X
⇒ g(x∗) = 0, ⟨y∗, g(x∗)⟩ = 0
⇒ ii), iii) của định lý (2.8) thỏa mãn. Thế thì (x∗, y∗) là điểm yên ngựa của
L(x, y) trên X × Rm+ .
Theo định lý (2.9) y∗ là nghiệm của (D).
2.3 Bài tập chương 2
Bài tập 2.1. Cho f tựa lồi trên tập lồi A, chứng minh rằng ∀x, y ∈ A và
z = tx+ (1− t)y, 0 ≤ t ≤ 1 ta có:
f(z) ≤ max{f(x), f(y)}.
21
Bài tập 2.2. Chứng minh rằng f đạt cực tiểu tuyệt đối trên D nếu
1. D đóng, D ̸= ∅.
2. f nửa liên tục dưới trên D.
3. ∃t ∈ R để tập mức {x ∈ D|f(x) ≤ t} ̸= ∅ và bị chặn.
Bài tập 2.3. Viết điều kiện Kuhn-Tucker tại x∗ = 1 của bài toán tối ưu .
min{−x2 : −1 ≤ x ≤ 1}.
Bài tập 2.4. Tìm điểm yên ngựa của hàm số
K(x, y) = x.y trên R× R.
Bài tập 2.5. Chứng minh rằng hàm Lagrange của bài toán tối ưu
min{−x2 : −1 ≤ x ≤ 1},
không có điểm yên ngựa trên R+ × R2+.
Bài tập 2.6. Viết bài toán đối ngẫu của quy hoạch toàn phương
min{1
2
xTQx+ qTx},
với ràng buộc:
Ax ≤ b, x ≥ 0
Trong đó Q và A là các ma trận n× n,m× n.
Chương 3
PHƯƠNG PHÁP CÓ THỂ VÀ
PHƯƠNG PHÁP TUYẾN
TÍNH HÓA
Phương pháp có thể là phương pháp rất hiệu quả để giải các bài toán tối
ưu phi tuyến.
3.1 Hướng chấp nhận tụt
Định nghĩa 3.1. Xét bài toán
min{f(x)|x ∈ D}. (3.1)
Ta nói rằng một vector d ̸= 0 là hướng chấp nhận tụt của bài toán (3.1)
tại điểm x ∈ D nếu:
d ∈ D(x) và theo hướng d, hàm f(x) giảm.
Xét bài toán
min f(x) (3.2)
với ràng buộc:
x ∈ D := {x ∈ Rn|g(x) ≤ 0},
trong đó g(x) lồi, xác định trên Rn.
Chú ý 3.1.1. g lồi ⇒ g liên tục tại mọi x ∈ int(D) và luôn giả thiết D là tập
compact.
Mệnh đề 3.1. Giả sử D được cho bởi (3.2), với g lồi, liên tục trên Rn. Giả
sử g(xk) = 0. Khi đó d là hướng chấp nhận được tại xk khi và chỉ khi bài toán
22
23
tối ưu một biến
min
0≤t≤
g(xk + td) (3.3)
có nghiệm tk > 0.
Chứng minh.
⇐) Nếu tk là nghiệm của (3.3) ⇒ g(xk + tkd) ≤ g(xk) = 0.
Do g lồi suy ra:
g(xk + tkd) ≤ 0,∀t ∈ [0, tk]⇒ d ∈ D(xk).
⇒) Vì d ∈ D(xk)⇒ ∃λ > 0 : g(xk + tkd) ≤ 0, ∀t ∈ [0, λ]
Và do g(xk) = 0 nên suy ra bài toán (3.3) có ít nhất một nghiệm tk > 0.
3.2 Phương pháp FRANK-WOLFE
(phương pháp hướng có thể)
Xét bài toán quy hoạch tuyến tính
min f(x) (3.4)
với ràng buộc:
x ∈ D := {x|Ax ≤ b, x ≥ 0}
trong đó f khả vi liên tục trên D, A là ma trận (aij)m×n, b ∈ Rm và D bị chặn.
* Thuật toán hướng chấp nhận tụt (Frank-Wolfe)
1. Bước 1: Dùng quy hoạch tuyến tính (nếu cần) tìm điểm xuất phát xk ∈
D, k = 0.
2. Bước 2: Tính ∇f(xk)
a. Nếu ∇f(xk) = 0 dừng.
b. Nếu ∇f(xk) ̸= 0, giải quy hoạch tuyến tính:
(L(xk)) min{⟨∇f(xk), x− xk⟩ |x ∈ D}
thu được lời giải là uk (một đỉnh của D).
i. Nếu
⟨∇f(xk), uk − xk⟩ ≥ 0⇒ dừng.
24
ii. Nếu
⟨∇f(xk), uk − xk⟩ < 0⇒ dk := uk−xk ̸= 0 là hướng chấp nhận
tụt (Bài tập: Áp dụng khai triển Taylor cho f).
Theo hướng dk tìm xk+1 ∈ D sao cho f(xk+1) < f(xk) thông qua
giải bài toán một biến
min{f(xk + tdk), 0 ≤ t ≤ 1}
được nghiệm tk > 0.
Khi đó lấy xk+1 = xk + tkd
k thế xk := xk+1, quay lại bước 2.
Thuật toán này hội tụ theo định lý sau:
Định lý 3.1. Thuật toán giải bài toán (3.4) cho kết quả:
i) f(xk+1) < f(xk), ∀k.
ii) Nếu thuật toán dừng ở xk thì xk là điểm dừng của f trên D. Nếu thuật
toán vô hạn thì mọi điểm tụ của dãy {xk} đều là điểm dừng.
iii) Nếu f lồi thì mọi điểm dừng đều là nghiệm của (3.4). Ngoài ra dãy
{f(xk)} hội tụ đến giá trị tối ưu của f ∗ và
0 ≤ f(xk)− f ∗ ≤ ⟨∇f(xk), xk − uk⟩ ,∀k
Chứng minh.
i) Dễ thấy vì theo cách xây dựng, thì dk là hướng chấp nhận tụt.
ii) Giả sử thuật toán kết thúc tại bước k, nghĩa là⟨∇f(xk), uk − xk⟩ ≥ 0
Do uk ∈ argminL(xk) nên⟨∇f(xk), x− xk⟩ ≥ min{⟨∇f(xk), x− xk⟩ : x ∈ D}
=
⟨∇f(xk), uk − xk⟩ ≥ 0, ∀x ∈ D
Từ đó suy ra xk là điểm dừng.
Giả sử thuật toán vô hạn.
Gọi x∗ là điểm tụ của dãy {xk}.
Do D compact nên tồn tại dãy con {xkj} → x∗.
Gọi {ukj} là nghiệm của L(xkj).
Do tập đỉnh của D hữu hạn ⇒ để cho gọn, ta coi ukj = u∗,∀j (nếu không ta
sẽ làm phép chứng minh dưới đây với nhiều nhất số lần bằng số đỉnh của D).
25
Theo tính đơn điệu của dãy {f(xk)} và cách xác định xkj , u∗ thì ∀t ∈ (0, 1) ta
có:
f(xkj+1) ≤ f(xkj+1) ≤ f(xkj + t(u∗ − xkj| {z }
h.ch.nh tụt
)).
Cho j → +∞, do f liên tục:
f(x∗) ≤ f(x∗ + t(u∗ − x∗)),∀t ∈ (0, 1).
Qua giới hạn (để ý f(x∗ + t(u∗ − x∗))− f(x∗) ≥ 0) ta có:
lim
t→0+
f(x∗ + t(u∗ − x∗))− f(x∗)
t
=
⟨∇f(xkj), x− x∗⟩ , ∀x ∈ D.
Vậy x∗ là điểm dừng.
iii) Nếu f lồi suy ra:
f(x)− f(x∗) ≥ ⟨∇f(x∗), x− x∗))⟩ ≥ 0, ∀x ∈ D
⇒ x∗ ∈ argmin(3.4)
3.3 Phương pháp cắt KELLEY
(phương pháp tuyến tính hóa)
Xét quy hoạch lồi:
min{cTx : x ∈ D}, (3.5)
trong đó c ∈ Rn, D là tập lồi compact cho dưới dạng
D := {x ∈ Rn|g(x) ≤ 0},
với g là hàm lồi trên Rn.
Chú ý 3.3.1. Trước đây D thường có dạng D := {x ∈ Rn|gj(x) ≤ 0, j = 1,m}
với gj lồi ∀j ∈ [1,m]. Bằng cách đặt:
g(x) = max
j
{gj(x)|j = 1,m} ⇒ g lồi .
Và tập:
{x ∈ Rn|gj(x) ≤ 0, j = 1,m} = {x ∈ Rn|g(x) ≤ 0}
Ta đều có thể đưa về biểu diễn D của (3.5) (Bài tập)
* Thuật toán cắt Kelley
26
1. Bước chuẩn bị: Xây dựng đa diện lồi D0 ⊃ D. Cho k = 0
2. Bước k(k = 0, 1, . . .): Giải quy hoạch tuyến tính
(Lk) min{cTx|x ∈ Dk}
Tìm được nghiệm xk.
a. Nếu xk ∈ D ⇒ xk ∈ argmin(3.5)⇒ dừng.
b. Nếu xk /∈ D, xây dựng siêu phẳng (hàm affine)
lk(x) :=
⟨
ak+1, x
⟩− bk+1 sao cho thỏa mãn :⟨
ak+1, xk
⟩− bk+1 ≤ 0, ∀x ∈ D⟨
ak+1, xk
⟩− bk+1 = g(xk) ≥ 0 (3.6)
Đặt Dk+1 := Dk
∩{x|lk(x) ≤ 0}, gán k := k + 1 rồi quay về bước k.
Chú ý 3.3.2. Để xây dựng được siêu phẳng lk(x) thỏa mãn (3.6) thông thường
lấy ak+1 ∈ ∂g(xk) và đặt
lk(x) =
⟨
ak+1, x− xk⟩+ g(xk).
Định nghĩa 3.2. Một dãy phiếm hàm affine {lk(x) :=
⟨
ak+1, x
⟩− bk+1} được
gọi là bị chặn đều nếu tồn tại một hằng số c sao cho :

ak

 ≤ c, ∀k.
Định lý 3.2.
i) Nếu thuật toán Kelley dừng lại ở bước thứ k thì xk là nghiệm tối ưu của
bài toán (3.5).
ii) Nếu thuật toán vô hạn, các siêu phẳng cắt bị chặn đều thì mọi điểm tụ
của dãy {xk} đều là nghiệm tối ưu của bài toán (3.5) và dãy {f(xk)} đơn
điệu tăng đến trị tối ưu f∗ của bài toán (3.5).
Chứng minh.
i) Theo cách xây dựng siêu phẳng ta có
D ⊂ Dk, Dk+1 ⊂ Dk, ∀k.
Giả sử thuật toán dừng tại bước thứ k ta suy ra
27
xk ∈ D,D ⊂ Dk và xk là nghiệm của bài toán (Lk)
Do đó xk ∈ argmin(3.5).
ii) Giả sử thuật toán vô hạn. Do xk ∈ D0, ∀k, và D0 compact
⇒ {xk} có dãy con {xkj} hội tụ đến x∗. Để dễ ký hiệu, ta gọi dãy con
hội tụ đó là {xk}.
Với k > j, theo (3.6) ta có:⟨
aj+1, xk
⟩− bj+1 ≤ 0
⇒ ⟨aj+1, xk − xj⟩+ g(xj) ≤ 0
⇒ g(xj) ≤ 

⟨aj+1, xk − xj⟩

 ≤ 

aj+1

 .

xk − xj


≤ c. 

xk − xj

 .
Do g(xj) > 0, ∀j và 

xk − xj

→ 0 khi k, j → +∞
⇒ g(xj)→ 0.
Tức là g(x∗) = 0⇒ x∗ ∈ D. (*)
Mặt khác : f(xk) ≤ f∗,∀k,
do f liên tục suy ra f(x∗) ≤ f∗. Kết hợp điều này với (*) ta đi đến kết
quả x∗ ∈ argmin(3.5).
Hơn nữa f(xk+1) ≥ f(xk),∀k ⇒ f(xk)↗ f∗
3.4 Bài tập chương 3
Bài tập 3.1. Cho D := {x : g(x) ≤ 0} với g lồi trên Rn. Giả sử g(u0) < 0 và
g(xk) > 0. Cho uk là điểm trên đoạn (uO, xk) sao cho g(uk) = 0. Lấy ak+1 là
dưới vi phân của g tại uk và xây dựng siêu phẳng:
lk(x) :=
⟨
ak+1, x− uk⟩ .
Chứng tỏ rằng siêu phẳng lk(x) thỏa mãn các tính chất trong thuật toán Kelley:
1. lk(x) ≤ 0,∀x ∈ D,
2. lk(x
k) > 0,
3. lk(x
k) ≤ g(xk),
4. Dãy {lk} bị chặn đều nếu D bị chặn.
28
Biết rằng: Ảnh của tập compact qua ánh xạ dưới vi phân của một hàm lồi trên
Rn cũng là một tập compact.
Bài tập 3.2. Cho x0 = (0, 0, 4)T . Tính 2 bước đầu tiên của thuật toán Frank-
Wolfe cho bài toán
min{0, 5x21 + 2x1x2 + 2, 5x22 + x2x3 + x23 − 2x1 − 4x2 − 6x3},
với ràng buộc 
x1 + x2 + x3 ≤ 5
2x1 + x3 ≤ 6
x1, x2, x3 ≥ 0
Chương 4
PHƯƠNG PHÁP HÀM PHẠT
ĐIỂM TRONG, ĐIỂM NGOÀI
4.1 Phương pháp hàm phạt điểm trong
Xét bài toán
min f(x), (4.1)
s.t
D := {x|gj(x) ≤ 0, j = 1,m, gj liên tục trên Rn}
Giả sử D compact.
Định nghĩa 4.1. Hàm p : Rn → R được gọi là hàm phạt điểm trong trên miền
D nếu thỏa mãn:
a) p liên tục trên tập hợp
D0 := {x ∈ Rn|gj(x) < 0,∀j = 1,m}.
b) ∀{xk} ⊂ D0, xk k→+∞−−−−→ x /∈ D0 ta có
lim
k→+∞
p(xk) = +∞.
Hai hàm phạt điểm trong nổi tiếng (Fiacco, McCormick):
p(x) = −
m∑
j=1
log(−gj(x) hoặc p(x) = −
m∑
j=1
1
gj(x)
.
Xây dựng bài toán phụ (Bt)
1. Xây dựng hàm tham số một biến s(t) : R+ \ {0} → R+ \ {0} sao cho :
29
30
i) s(t) liên tục ∀t > 0 và s(t)→ 0 khi t→ +∞.
ii) s(t) đơn điệu giảm (s(t) > s(t′), ∀t′ > t > 0).
Ví dụ: s(t) = 1/t, s(t) = 1/t2.
2. Xây dựng bài toán phụ
Đặt hàm
F (x, t) := f(x) + s(t)p(x), (4.2)
với miền t > 0 xây dựng bài toán phụ không ràng buộc
(Bt) min
x
{F (x, t) | x ∈ Rn}.
Mệnh đề 4.1. Giả sử các điều kiện a, b, i, ii thỏa mãn và bài toán (Bt) có
nghiệm ∀t > 0. Khi đó, nếu 0 < t1 < t2 và xi là nghiệm của Bti(i = 1, 2). Ta
có :
1. p(x1) ≤ p(x2),
2. f(x1) ≥ f(x2).
Chứng minh. Để đơn giản ký hiệu, đặt s(ti) = si, p(x
i) = pi, f(x
i) = fi, i =
1, 2. Khi đó :
f1 + s1p1 ≤ f2 + s1p2 vì x1 là argmin(Bt1), (4.3)
f2 + s2p2 ≤ f1 + s2p1 vì x2 là argmin(Bt2). (4.4)
Cộng 2 vế và ước lược:
s1p1 + s2p2 ≤ s1p2 + s2p1
⇒ (s1 − s2)(p1 − p2) ≤ 0.
Do t1 s2 (đđ giảm) ⇒ p(x1) ≤ p(x2)
⇒ (theo (4.4)) f(x1) ≥ f(x2).
Định lý 4.1. Nếu dãy {tk} đơn điệu tăng đến +∞ và xk là nghiệm của (Btk)
thì dãy {f(xk)} hội tụ giảm đến trị tối ưu f∗ của bài toán (4.1). Ngoài ra mọi
điểm tụ của dãy xk đều là nghiệm của bài toán (4.1).
Chứng minh. Theo mệnh đề (4.1) thì dãy {f(xk)} đơn điệu giảm, do đó dãy
{f(xk)} hội tụ. (vì sao ?)
31
1) Xét trường hợp nghiệm của (4.1) x∗ ∈ D0:
Do xk là nghiệm của (Btk) (để ý x
k ∈ D0, nếu xk /∈ D0 thì F = +∞)
nên:
f(xk) + s(tk)p(x
k) ≤ f(x∗) + s(tk)p(x∗). (4.5)
Do D compact nên {xk} hội tụ đến u∗ nào đó.
1.a) Nếu u∗ ∈ D0 qua giới hạn (s(tk)→ 0, p(x∗), p(u∗) hữu hạn) suy ra:
f(u∗) ≤ f(x∗)⇒ u∗ ∈ argmin(4.1).
1.b) Nếu u∗ /∈ D0 thì p(xk) k→+∞−−−−→ +∞ nên ∃K1 sao cho s(tk)p(xk) ≥
0,∀k ≥ K1. Khi đó, từ 4.5 ta có:
f(xk) ≤ f(x∗) + s(tk)p(x∗), ∀k ≥ K1.
Qua giới hạn ta được
lim
k→+∞
f(xk) ≤ f(x∗).
Mặt khác do xk ∈ D ⇒ f(xk) ≥ f(x∗),∀k ≥ K1 nên ta có
lim
k→+∞
f(xk) ≥ f(x∗).
Từ đó suy ra
lim
k→+∞
f(xk) = f(x∗).
2) Trường hợp nghiệm tối ưu của bài toán (4.1)x∗ /∈ D0
Đặt β = limk→+∞ f(xk). Ta suy ra f∗ ≤ β (do f(xk) ≥ f(x∗), ∀k)
Nếu thật sự f ∗ < β thì do f liên tục trên D,
nên suy ra ∃u ∈ D0 : f ∗ < f(u) < β. Từ bất đẳng thức:
f(xk) + s(tk)p(x
k) ≤ f(u)s(tk)p(u),
tương tự 1.b) ta suy ra: f(xk) ≤ f(u), ∀k ≥ K1. Điều này mâu thuẫn
với
f(xk) ≥ β > f(u),∀k.
Vậy β = f(x∗).
32
4.2 Phương pháp hàm phạt điểm ngoài
Định nghĩa 4.2. Hàm số p : Rn → R được gọi là hàm phạt điểm ngoài miền
D của bài toán (4.1) nếu thỏa mãn:
a) p liên tục trên Rn.
b) p(x) = 0,∀x ∈ D, p(x) > 0,∀x /∈ D.
Ví dụ 4.2.1. Với gj của bài toán (4.1), ta có 2 hàm phạt điểm ngoài
p(x) =
m∑
j=1
max(0, gj(x)), (4.6)
p(x) =
m∑
j=1
[max(0, gj(x))]
2. (4.7)
* Xây dựng bài toán phụ (Pt)
1) Xây dựng hàm r : R+ \ {0} → R+ \ {0}.
i) r(t) liên tục tại ∀t > 0, r(t)→ 0 khi t→ +∞.
ii) r(t) đơn điệu tăng: t > t′ > 0→ r(t) > r(t′) > 0.
2) Với mỗi t cố định xây dựng bài toán phụ (Pt):
(Pt) min{F (x, t) := f(x) + r(t)p(x) | x ∈ Rn}.
Ta có mệnh đề và cách chứng minh tương tự mệnh đề (4.1).
Mệnh đề 4.2. Giả sử (Pt) có nghiệm ∀t > 0. Khi đó nếu x là nghiệm của
(Pti), (i = 1, 2) và 0 < t1 < t2 thì
1) p(x1) ≥ p(x2).
2) f(x1) ≤ f(x2).
Định lý 4.2. Nếu dãy {tk} đơn điệu tăng đến +∞ và xk là nghiệm của (Ptk),
thì dãy số {f(xk)} hội tụ tăng đến giá trị tối ưu f∗ của (4.1). Ngoài ra mọi
điểm tụ của dãy {xk} đều là nghiệm của (4.1).
Chứng minh. Gọi x∗ ∈ argmin(4.1), xk ∈ argmin(Ptk) suy ra p(x∗) = 0 và
f(xk) + r(tk)p(x
k) ≤ f(x∗) + r(tk)p(x∗) = f∗. (4.8)
33
Ta sẽ chứng minh mọi điểm tụ u∗ của dãy {xk} phải thuộc D.
Thật vậy, giả sử u∗ /∈ D ⇒ p(u∗) > 0. Cho r(tk)→ +∞ khi đó, ∃k đủ lớn để:
f(u∗) + r(tk)p(u∗) > f∗ ⇒ mâu thuẫn với (4.8).
Do đó, u∗ ∈ D.
Bây giờ ta chứng minh u∗ ∈ argmin(4.1):
Từ (4.8) ta suy ra f(xk) ≤ f∗,∀k.
Vì f liên tục, qua giới hạn ta được: f(u∗) ≤ f∗.
Vì u∗ ∈ D ⇒ f(u∗) = f∗ ⇒ u∗ ∈ argmin(4.1)
Cuối cùng, ta chứng minh f(xk)↗ f∗
Ta có: f(xk) ≤ f∗, ∀k và theo mệnh đề (4.2)⇒ f(xk)↗ f∗ khi tk → +∞
Chú ý 4.2.1.
1. Nếu tập {x | f(x) + r(t0)p(x) ≤ c} compact với mọi hằng số C thì bài toán
không ràng buộc (Pt) có nghiệm.
2. Nếu gj, j = 1,m lồi thì (4.6), (4.7) lồi.
4.3 Bài tập chương 4
Bài tập 4.1. Cho bài toán
(P ) min{f(x) | x ∈ S, g(x) ≤ 0},
trong đó, f, g hàm lõm trên S, S là đa diện lồi bị chặn và g(x) ≥ 0,∀x /∈ S.
Chứng minh rằng ∃t∗ ∈ (0,+∞) sao cho mọi nghiệm của bài toán
(Pt) min{f(x) + tg(x) | x ∈ S},
đều là nghiệm của (P ),∀t ≥ t∗.
(Gợi ý: Cực tiểu của hàm lõm đạt trên đỉnh của S.)
Chương 5
TỐI ƯU ĐA MỤC TIÊU
5.1 Điểm hữu hiệu và bài toán tối ưu đa mục
tiêu
5.1.1 Điểm hữu hiệu
Định nghĩa 5.1. Cho nón lồi Rp := {x ∈ Rp | x ≤ 0}, x, y ∈ Rp, ta nói :
x nhỏ hơn hoặc bằng y (x ≤ y) khi và chỉ khi x− y ∈ Rp−.
(Tức là : xi ≤ yi ∀i = 1, p)
Định nghĩa 5.2. Cho Y ⊆ Rp, ta nói : y∗ ∈ Y là điểm hữu hiệu hay điểm
Pareto của Y nếu :
̸ ∃ y ∈ Y để y ≤ y∗ và y ̸= y∗
Nhận xét 10. Về mặt hình học nếu y∗ là điểm Pareto của Y thì nón có đỉnh
tại y∗ và có phương của các cạnh trùng với phương của các cạnh của nón Rp−
không chứa một điểm y ∈ Y, y ̸= y∗ nào.
5.1.2 Bài toán tối ưu đa mục tiêu
Cho Rn ⊃ D ̸= ∅, f : Rn → Rn, Y := f(D) là ảnh của D qua f .
Bài toán tối ưu đa mục tiêu được viết như sau:
Min{f(x) | x ∈ D}. (5.1)
Bài toán này được hiểu là : hãy tìm một tập (có thể là một điểm) các điểm
x∗ ∈ D sao cho y∗ := f(x∗) là điểm Pareto của Y . Khi đó x∗ được gọi là
nghiệm tối ưu của bài toán (5.1) hay điểm hữu hiệu của f trên D.
34
35
Chú ý 5.1.1.
1. Khi p = 1 thì x∗ là điểm làm cực tiểu tuyệt đối f trên D.
2. Nếu D là khúc lồi, f affine trên D (mỗi fi là affine) thì (5.1) được gọi
là bài toán tuyến tính đa mục tiêu.
5.2 Sự tồn tại và tính chất của nghiệm tối ưu
của bài toán tối ưu đa mục tiêu
Mệnh đề 5.1. Cho λ ∈ Rp là vector dương λ > 0. Khi đó mọi nghiệm tối ưu
của bài toán một mục tiêu
min{λTf(x) | x ∈ D} (5.2)
đều là điểm hữu hiệu của f trên D.
Chứng minh. Gọi x∗ ∈ argmin(5.2). Giả sử x∗ /∈ argmin(5.1) (tức x∗ không
phải là điểm hữu hiệu của f trên D). Suy ra :
∃x′ ∈ D : f(x′) ≤ f(x∗) và f(x′) ̸= f(x).
Kết hợp với λ > 0 (tức là λi > 0,∀i = 1, p), ta có:
λTf(x′) < λTf(x∗).
Điều này mâu thuẫn với x∗ ∈ argmin(5.2).
Vậy, x∗ ∈ argmin(5.1)
Hệ quả 5.1.1. Nếu D compact và f(x) nửa liên tục dưới thì bài toán tối ưu
đa mục tiêu (5.1) có nghiệm tối ưu.
Định lý 5.1. Giả sử (5.1) là bài toán quy hoạch lồi. Khi đó mọi u ∈ argmin
(5.1) đều tồn tại λ = (λ1, λ2, . . . , λp) ≥ 0 sao cho u ∈ argmin của bài toán
min{λTf(x) | x ∈ D}.
Chứng minh.
Đặt C := cov (K := {y ∈ Rp | y = f(x)− f(u), x ∈ D}) .
1) Ta chứng minh C ∩Rp = {0}:
Trước hết, C ̸= ∅ vì {0} ∈ K (lấy x ≡ u).
Lấy bất kỳ y ∈ C, vì C là bao lồi của K nên suy ra :
∃y1, y2 ∈ K : y = ty1 + (1− t)y2, 0 ≤ t ≤ 1.
36
Và ∃x1, x2 ∈ D:
yi = f(xi)− f(u), i = 1, 2. (5.3)
Lấy x = tx1 + (1− t)x2 ⇒ x ∈ D (D lồi).
Do f lồi và kết hợp với (5.3) có:
f(x)− f(u) ≤ tf(x1) + (1− t)f(x2)− f(u)
= t(f(x1)− f(u)) + (1− t)(f(x2)− f(u))
= ty1 + (1− t)y2 = y
Tức là f(x)− f(u) ≤ y
Giả sử y ∈ C ∩Rp− và y < 0, ta suy ra
f(x)− f(u) ≤ 0 và f(x) ̸= f(u)
Do đó u không phải là điểm hữu hiệu của f trên D. Điều này mâu thuẫn
với giả thiết u là điểm hữu hiệu của f trên D.
Vậy: C ∩Rp− = {0}.
2) Bây giờ ta sẽ chứng minh u ∈ argmin{λTf(x) | x ∈ D}:
Do C lồi, Rp− lồi và C ∩ Rp− = {0} nên theo định lý tách ∃λ ̸= 0 (λ =
λ1, λ2, . . . , λp):
λTy ≤ 0 ∀y ∈ Rp− (5.4)
λTy ≥ 0 ∀y ∈ K (5.5)
Bằng cách chia cho
∑p
i=1 λi ta coi
∑p
i=1 λi = 1.
Từ (5.4) ⇒ λT ≥ 0.
Từ (5.5) và định nghĩa của K suy ra λTy = λT (f(x)−f(u)) ≥ 0,∀x ∈ D.
Do đó, u là nghiệm tối ưu của bài toán (5.2):
min{λTf(x) | x ∈ D}.
Bây giờ, ta xét bài toán sau:
Bài Toán 5.2.1. Cho quy hoạch lồi
Minf(x) (5.6)
x ∈ D = {x ∈ Rn | g(x) ≤ 0}
trong đó f : Rn → Rp, g : Rn → Rm lồi.
37
Định lý 5.2. Giả sử quy hoạch lồi (5.6) thỏa mãn điều kiện Slater. Khi đó
x0 là điểm hữu hiệu của (5.6) khi và chỉ khi tồn tại (x0, v0) sao cho (x0, v0) là
điểm yên ngựa của hàm
F (u0, x, v) :=
⟨
u0, f(x)
⟩
+ ⟨v, g(x)⟩ trên Rn × Rm+
Chứng minh.
⇒) Giả sử x0 là điểm hữu hiệu của quy hoạch lồi (5.6).
Theo định lý (5.1), ∃u0 ≥ 0 : x0 ∈ argmin{minx ⟨u0, f(x)⟩ | g(x) ≤ 0}
Áp dụng định lý điểm yên ngựa cho hàm Lagrange của bài toán này, ta
suy ra tồn tại v0 ≥ 0 sao cho (x0, v0) là điểm yên ngựa của hàm
F (u0, x, v) =
⟨
u0, f(x)
⟩
+ ⟨v, g(x)⟩ trên Rn × Rm+
Tức là:
F (u0, x0, v) ≤ F (u0, x0, v0) ≤ F (u0, x, v0) ∀(x, v) ∈ Rn × Rm+ (5.7)
⇐) (x0, u0) là điểm yên ngựa của F (u0, x, v) trên Rn × Rm+ .
Từ điều kiện Slater, lặp lại chứng minh của định lý điểm yên ngựa (ở
chương 2), ta có u0 > 0. Áp dụng (5.7) với v = 0 ta có⟨
u0, f(x0)
⟩ ≤ ⟨u0, f(x)⟩+ ⟨v, g(x)⟩ = ⟨x0, f(x)⟩ ∀x ∈ D
⇒ x0 ∈ argmin{⟨u0, f(x)⟩ | x ∈ D}
Theo mệnh đề (5.1), x0 là điểm hữu hiệu của f trên D.
5.3 Bài tập chương 5
Bài tập 5.1. Điểm x∗ ∈ D gọi là hữu hiệu yếu của hàm vector f(x) trên D
nếu ̸ ∃x ∈ D : f(x) < f(x∗).
Chứng minh rằng nếu λ > 0 thì mọi nghiệm của bài toán
minλTf(x)|x ∈ D
đều là điểm hữu hiệu yếu của f trên D.
38
Bài tập 5.2. Cho bài toán tối ưu đa mục tiêu
Minx∈Df(x), f : Rn → Rp.
Chứng minh x0 là điểm hữu hiệu (điểm Pareto) khi và chỉ khi x0 là nghiệm tối
ưu của bài toán một mục tiêu
minh(x) := eTf(x)|x ∈ D, f(x) ≤ f(x0),
trong đó : e = (1, 1, . . . , 1) ∈ Rp.
Bài tập 5.3. Tìm một điểm hữu hiệu của bài toán đa mục tiêu
Min{f(x) = (f1(x), f2(x)) |x ∈ D},
trong đó:
f1(x) = x1 + x2; f2(x) = x1 − 2x2;D := {x |x1 ≥ x2, 0 ≤ x1 ≤ 2, x2 ≥ 0}
Mục lục
1 CƠ BẢN VỀ GIẢI TÍCH LỒI 1
1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Tính chất cực trị . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 ĐIỀU KIỆN TỐI ƯU 9
2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Điều kiện tối ưu và đối ngẫu Lagrange . . . . . . . . . . . . . . 12
2.2.1 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Điểm yên ngựa . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Bài tập chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 PHƯƠNG PHÁP CÓ THỂ VÀ PHƯƠNG PHÁP TUYẾN
TÍNH HÓA 22
3.1 Hướng chấp nhận tụt . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Phương pháp FRANK-WOLFE
(phương pháp hướng có thể) . . . . . . . . . . . . . . . . . . . . 23
3.3 Phương pháp cắt KELLEY
(phương pháp tuyến tính hóa) . . . . . . . . . . . . . . . . . . . 25
3.4 Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 PHƯƠNG PHÁPHÀMPHẠTĐIỂM TRONG, ĐIỂMNGOÀI 29
4.1 Phương pháp hàm phạt điểm trong . . . . . . . . . . . . . . . . 29
4.2 Phương pháp hàm phạt điểm ngoài . . . . . . . . . . . . . . . . 32
4.3 Bài tập chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 33
39
40
5 TỐI ƯU ĐA MỤC TIÊU 34
5.1 Điểm hữu hiệu và bài toán tối ưu đa mục tiêu . . . . . . . . . . 34
5.1.1 Điểm hữu hiệu . . . . . . . . . . . . . . . . . . . . . . . 34
5.1.2 Bài toán tối ưu đa mục tiêu . . . . . . . . . . . . . . . . 34
5.2 Sự tồn tại và tính chất của nghiệm tối ưu của bài toán tối ưu
đa mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3 Bài tập chương 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 37