BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ LÊ
PHƯƠNG PHÁP HÀM PHẠT
CHO BÀI TOÁN TỐI ƯU
LUẬN VĂN THẠC SỸ
Chuyên ngành : TOÁN ỨNG DỤNG
Mã số : 60 46 36
Người hướng dẫn khoa học:
GS- TSKH LÊ DŨNG MƯU
THÁI NGUYÊN, 2012
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
Mục lục
Lời cảm ơn
4
Mở đầu
5
1 Các kiến thức cơ bản về tập lồi và hàm lồi
1.1 Tập lồi . . . . . . . . . . . . . . . . . . . .
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . .
1.2.1 Định nghĩa và tính chất . . . . . . .
1.2.2 Tính liên tục . . . . . . . . . . . . .
1.2.3 Dưới vi phân . . . . . . . . . . . . .
1.2.4 Tính chất cực trị . . . . . . . . . .
2 Phương pháp hàm phạt
2.1 Bài toán tối ưu . . . . . . . . .
2.1.1 Phát biểu bài toán . . . .
2.1.2 Các điều kiện tối ưu . . .
2.2 Phương pháp hàm phạt . . . . .
2.2.1 Hàm phạt điểm ngoài . .
2.2.2 Hàm phạt điểm trong . .
2.2.3 Hàm phạt kiểu Lagrange
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Hàm phạt chính xác và áp dụng
3.1 Hàm phạt chính xác cho bài toán tối ưu lồi. . . . . . . . .
3.2 Hàm phạt chính xác cho bài toán tối ưu trên tập Pareto .
3.2.1 Bài toán tối ưu vecto tuyến tính . . . . . . . . . .
3.2.2 Hàm phạt chính xác cho bài toán tối ưu trên tập
Pareto . . . . . . . . . . . . . . . . . . . . . . . .
2
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
7
11
11
13
14
15
.
.
.
.
.
.
.
17
17
17
19
23
24
26
31
42
. 42
. 49
. 49
. 53
Tài liệu tham khảo
58
3
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
Lời cảm ơn
Trước khi trình bày nội dung chính của luận văn, em xin bày tỏ lòng
biết ơn sâu sắc tới GS.TSKH Lê Dũng Mưu người đã tận tình hướng dẫn
và giúp đỡ em trong suốt quá trình học tập và nghiên cứu để em có thể
hoàn thành khóa luận này.
Em cũng xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường
Đại học Khoa học- Đại học Thái Nguyên và Viện Toán học - Viện Khoa
học và Công nghệ Việt Nam đã giảng dạy và giúp đỡ em hoàn thành khóa
học.
Nhân dịp này em cũng xin chân thành cảm ơn Ban Giám hiệu, các bạn
đồng nghiệp Trường Cao đẳng Công nghệ và Kinh tế công nghiệp, gia đình
và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt
trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp.
Mặc dù đã có nhiều cố gắng nhưng Luận văn khó tránh khỏi những
thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của quý 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, ngày 20 tháng 07 năm 2012
Tác giả
Nguyễn Thị Lê
4
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
Mở đầu
Bài toán tối ưu là bài toán tìm một phương án chấp nhận được để
làm cực trị một hàm số hoặc một hàm vecto. Đây là bài toán có nhiều ứng
dụng trong thực tế. Khó khăn chính trong việc nghiên cứu và giải quyết
bài toán này là phải tìm được một phương án tối ưu trong miền chấp nhận
được. Để giải quyết khó khăn này, phương pháp hàm phạt là một cách
tiếp cận cơ bản để giải quyết bài toán tối ưu có ràng buộc. Ý tưởng chính
của phương pháp này là chuyển bài toán có ràng buộc về một dãy các bài
toán không ràng buộc hoặc có ràng buộc đơn giản hơn. Các loại hàm phạt
thường được dùng là hàm phạt điểm ngoài, hàm phạt điểm trong và hàm
phạt kiểu Lagrange (thưởng- phạt). Đối với phương pháp hàm phạt điểm
ngoài, hàm phạt được xác định cả bên ngoài miền chấp nhận được và có
tính chất là lượng phạt p(x) > 0 nếu x không thuộc miền chấp nhận được
D, trái lại, nếu x ∈ D thì p(x) = 0. Một hàm phạt khác là hàm phạt kiểu
Lagrange, hàm này cũng xác định cả bên ngoài miền ràng buộc như hàm
phạt điểm ngoài, nhưng bên trong miền chấp nhận được, lượng phạt có
thể nhận giá trị âm, tức là được thưởng tùy theo mức độ thỏa mãn miền
ràng buộc. Phương pháp có hiệu quả hơn cả là phương pháp hàm phạt
điểm trong, khác với hàm phạt điểm ngoài và hàm phạt kiểu Lagrange,
hàm phạt này chỉ xác định tại miền trong của tập chấp nhận được, còn
tại các điểm gần biên của miền chấp nhận được thì p(x) = +∞.
Thông thường, người ta chỉ có thể chuyển việc một bài toán có ràng
buộc về việc giải một dãy vô hạn các bài toán không có ràng buộc hoặc có
ràng buộc đơn giản hơn. Tuy nhiên trong một số trường hợp cụ thể, với
những điều kiện nhất định thì ta có thể chuyển về việc giải chỉ duy nhất
một bài toán không ràng buộc. Hàm phạt cho tính chất này được gọi là
hàm phạt chính xác.
Bản luận văn này nhằm mục đích chủ yếu là hệ thống các kiến thức cơ
bản về các loại phương pháp hàm phạt đã kể trên. Cụ thể, luận văn đã đề
5
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
cập đến các vấn đề sau:
1. Giới thiệu các kiến thức cơ bản về phương pháp hàm phạt điểm
ngoài, phương pháp hàm phạt điểm trong và phương pháp hàm phạt kiểu
Lagrange.
2. Trình bày một kết quả tương đối mới về hàm phạt chính xác cho bài
toán tối ưu lồi. Ngoài ra, luận văn còn trình bày phương pháp hàm phạt
chính xác cho bài toán tối ưu không lồi, đó là bài toán tối ưu một hàm
tuyến tính trên tập nghiệm của một bài toán tối ưu vecto affin.
Luận văn gồm 3 chương:
Chương 1. Giới thiệu một số khái niệm và kiến thức cơ bản của giải
tích lồi thường được dùng trong tối ưu hoá (tập afin, tập lồi, nón lồi, hàm
lồi và các tính chất cơ bản của chúng).
Chương 2. Trình bày ba phương pháp hàm phạt là: Phương pháp
hàm phạt điểm trong, phương pháp hàm phạt điểm ngoài và hàm phạt
kiểu Lagrange (thưởng- phạt).
Chương 3. Trình bày khái niệm về hàm phạt chính xác, điều kiện đủ
để tồn tại hàm phạt chính xác cho bài toán tối ưu lồi, bài toán tối ưu
trên tập Pareto của một bài toán tối ưu vecto affine và áp dụng hàm phạt
chính xác vào bài toán tối ưu trên tập này.
6
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
Chương 1
Các kiến thức cơ bản về tập lồi và
hàm lồi
Chương này nhằm giới thiệu một số khái niệm và kiến thức cơ bản của
giải tích lồi thường được dùng trong tối ưu hoá (tập afin, tập lồi, nón lồi,
hàm lồi và các tính chất cơ bản của chúng). Các khái niệm và kết quả
trong chương này hầu hết được lấy từ các tài liệu: [1],[2], [3].
1.1
Tập lồi
Định nghĩa 1.1.
Một đường thẳng nối hai điểm (hai vecto) trong không gian Rn là tập
hợp tất cả các vecto x ∈ Rn có dạng
{x ∈ Rn |x = αa + βb, α + β = 1} .
Đoạn thẳng nối hai điểm trong không gian Rn là tập hợp tất cả các
vecto x ∈ Rn có dạng
{x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} .
Một tập M được gọi là tập affine (đa tạp affine) nếu nó chứa đường
thẳng đi qua hai điểm bất kỳ của nó, tức là
∀x, y ∈ M, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ M.
Ví dụ 1.1. Các không gian con của Rn là các tập affine.
Nhận xét 1.1.
7
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
• Nếu M là tập affine thì
a + M = {a + x | x ∈ M }
cũng là một tập affine với ∀a ∈ Rn .
• M là tập affine chứa gốc khi và chỉ khi M là không gian con.
Định nghĩa 1.2.
Thứ nguyên của một đa tạp affine được cho bởi thứ nguyên của không
gian con song song với nó.
Siêu phẳng H trong Rn là một tập affine có số chiều bằng (n-1), hay
chính là tập có dạng:
H = {x ∈ Rn | aT x =α},
trong đó 0 6= a ∈ Rn và α ∈ R.
Ví dụ 1.2. Trong không gian hai chiều, siêu phẳng là đường thẳng. Trong
không gian 3 chiều, siêu phẳng là mặt phẳng.
Định nghĩa 1.3.
Trong Rn , siêu phẳng
H = {x ∈ Rn | aT x =α},
với 0 6= a ∈ Rn và α ∈ R chia Rn thành hai nửa không gian đóng :
H − = {x ∈ Rn | aT x ≤ α} và H + = {x ∈ Rn | aT x ≥ α},
mỗi nửa không gian này nằm về một phía của siêu phẳng và phần chung
của chúng chính là siêu phẳng H .
Tương tự, H cũng chia Rn thành hai nửa không gian mở:
{x ∈ Rn | aT x < α} và {x ∈ Rn | aT x > α}.
Một tập C trong Rn được gọi là tập lồi nếu C chứa mọi đoạn thẳng nối
hai điểm thuộc nó, tức là tập C lồi khi và chỉ khi:
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
Bao lồi của tập A là tập lồi nhỏ nhất chứa A, ký hiệu là CoA, đây
chính là giao của tât cả các tập lồi chứa A.
Cho hai tập A, B bất kỳ trong Rn , tổ hợp lồi của các tập A và B là
tập các điểm thuộc Rn có dạng:
x = λa + (1 − λ)b, a ∈ A, b ∈ B, 0 ≤ λ ≤ 1.
8
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
Lớp các tập lồi là đóng đối với phép giao, phép cộng đại số và phép
nhân tích Decartes, cụ thể ta có định lý sau:
Định lý 1.1. Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các
tập sau là tập lồi:
1. A ∩ B := {x |x ∈ A, x ∈ B };
2. αA + βB := {x |x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R};
3. A × C := {x ∈ Rn+m |x = (a, c), a ∈ A, c ∈ C }.
Định nghĩa 1.4. Cho A là tập lồi, tập affine nhỏ nhất chứa A được gọi
là bao affine của A, ký hiệu là af f A.
Thứ nguyên của tập lồi A ký hiệu là dimA được cho bởi thứ nguyên
của bao affin của A.
Một điểm a ∈ A được gọi là điểm trong của A nếu tồn tại một lân cận
mở U của a sao cho U ⊂ A, tập hợp các điểm trong của A ký hiệu là
intA. Một tập lồi A trong Rn có thể không có điểm trong (khi xét trong
Rn ), nhưng nó luôn có điểm trong khi xét trong af f A, điểm trong này gọi
là điểm trong tương đối. Nếu ký hiệu riA là tập các điểm trong tương đối
của A thì
riA := {x ∈ affA |∃ U, U ∩ affA ⊂ A},
trong đó U là một lân cận mở của x. nếu A là tập lồi khác rỗng thì riA 6= ∅.
Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được
gọi là tập lồi đa diện ( khúc lồi). Như vậy dạng tường minh của một tập
lồi đa diện D được cho như sau:
D = {x ∈ Rn < aj , x >≤ bj , j = 1, 2, .., m}.
Một tập con A0 của A được gọi là một diện của A nếu hễ nó chứa một
điểm trong của một đoạn thẳng thì nó chứa cả đoạn thẳng đó, tức là:
∀a, b ∈ A, nếu x = λa + (1 − λ)b, 0 < λ < 1, x ∈ A0 ⇒ a, b ∈ A0 .
Một diện có thứ nguyên bằng 0 được gọi là đỉnh hay điểm cực biên.
Cạnh là một diện có thứ nguyên bằng 1.
Đối với một tập C bất kỳ, một điểm x ∈ C được gọi là điểm biên của
C nếu không tồn tại a, b ∈ C, 0 < λ < 1 sao cho:
9
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
x = λa + (1 − λ)b và đoạn thẳng [a, b] ⊂ C .
Với một tập lồi đa diện, một đỉnh của diện cũng chính là đỉnh của tập
đó.
Một tập C được gọi là nón lồi nếu
∀x, y ∈ C thì x + y ∈ C và tx ∈ C với mọi t ≥ 0.
Ví dụ 1.3. Rn+ là một nón lồi.
Cho C là một tập trong Rn , một vecto y 6= 0 được gọi là hướng lùi xa của
C nếu mọi tia xuất phát từ một điểm bất kỳ của C theo hướng y đều nằm
trọn trong C , tức là y 6= 0 là hướng lùi xa khi và chỉ khi
x + λy ∈ C, ∀x ∈ C, ∀λ ≥ 0.
Tập tất cả các hướng lùi xa của C cùng với điểm gốc được gọi là nón
lùi xa của C , ký hiệu là reC .
Cho C là một tập lồi trong Rn và x ∈ C , tập hợp:
NC (x) = {w |hw, y − xi ≤ 0,∀y ∈ C}
được gọi là nón pháp tuyến ngoài của C tại x, tập hợp
−NC (x) = {w |hw, y − xi ≥ 0,∀y ∈ C}
được gọi là nón pháp tuyến trong của C tại x, tập hợp
C ∗ = {w |h w, xi ≤ 0, ∀x ∈ C}
được gọi là nón đối cực của C .
Cho C là một tập lồi khác rỗng và x thuộc C . Ta nói d ∈ Rn là một
hướng chấp nhận được của C nếu tồn tại t0 > 0 sao cho x + td ∈ C với
mọi 0 ≤ t ≤ t0 . Tập tất cả các hướng chấp nhận được của C tại x ký hiệu
là C(x) và gọi là nón chấp nhận được của C tại x.
Định lý tách các tập lồi dưới đây là những định lý cơ bản nhất của giải
tích lồi, được dùng nhiều trong lý thuyết tối ưu.
Cho hai tập C và D khác rỗng, ta nói siêu phẳng aT x = α tách C và
D nếu
aT x ≤ α ≤ aT y, ∀x ∈ C, ∀y ∈ D.
10
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
Ta nói siêu phẳng aT x = α tách chặt C và D nếu
aT x < α < aT y, ∀x ∈ C, ∀y ∈ D.
Ta nói siêu phẳng aT x = α tách mạnh C và D nếu
sup aT x < α < inf aT y.
y∈D
x∈C
Bổ đề 1.1. : Cho C ⊂ Rn là một tập lồi khác rỗng. Giả sử x0 ∈
/ C . Khi
n
0
đó tồn tại t ∈ R , t 6= 0 thỏa mãn ht, xi ≥ ht, x i, ∀x ∈ C.
Định lý 1.2. (Định lý tách 1): Cho C và D là hai tập lồi đóng khác rỗng
trong Rn và C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D.
Định lý sau đây nói về việc tách mạnh hai tập lồi:
Đị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 và C ∩ D = ∅. Giả sử có it nhất một tập compac. Khi đó hai tập
này có thể được tách mạnh bởi một siêu phẳng.
Một hệ quả rất quan trọng của định lý tách là bổ đề Farkas. Bổ đề này
rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu, điều khiển,..
Bổ đề 1.2. (Farkas)
Cho a ∈ Rn và A là ma trận cỡ m × n. Khi đó ha, xi ≥ 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ổ đề này rất rõ: nó có nghĩa rằng siêu phẳng đi
qua gốc tọa độ ha, xi = 0 để nón Ax ≥ 0 nằm 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
1.2.1
Hàm lồi
Định nghĩa và tính chất
Cho C ⊆ Rn là tập lồi và
f : C → R ( R = R ∪ { ± ∞})
11
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
Ta ký hiệu domf := {x ∈ C | f (x) < +∞} và gọi là miền hữu dụng
của f . Nếu domf 6= ∅ và f (x) > −∞ thì f được gọi là hàm lồi chính
thường.
Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là trên đồ thị của
hàm f f : Rn → R ∪ { + ∞}
Định nghĩa 1.5. Cho ∅ =
6 C ⊆ Rn là một tập lồi và f : C → R
Ta nói f là hàm lồi trên C nếu epif là một tập lồi trong Rn+1 .
Từ đây ta luôn xét f : Rn → R ∪ { + ∞}.Khi đó định nghĩa trên tương
đương với
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1).
Hàm f được gọi là lồi chặt trên C nếu
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1)
Hàm f được gọi là hàm lõm (lõm chặt) trên C nếu −f là hàm lồi (lồi chặt)
trên C.
Hàm f được gọi là tựa lồi trên C nếu với mọi λ ∈ R, tập mức
{ x ∈ C |f (x) ≤ λ }
là tập lồi.
Hàm f được gọi là hàm tựa lõm trên C nếu −f là hàm tựa lồi trên C.
Ta định nghĩa các hàm sau:
(λf )(x) := λf (x);
(f + g)(x) := f (x) + g(x).
Lớp các hàm lồi là đóng đối với phép lấy tổ hợp tuyến tính không âm và
phép lấy max, cụ thể:
Định lý 1.4. Cho f là hàm lồi trên tập A và g là hàm lồi trên tập B . Khi
đó các hàm sau là lồi trên tập A ∩ B :
1. αf + βg, ∀α, β > 0;
2. max{f, g}.
12
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
Định lý sau đây cho phép kiểm tra tính lồi của một hàm số:
Định lý 1.5. Cho f : C → R là một hàm khả vi trên tập lồi mở C . Điều
kiện cần và đủ để f lồi trên C là:
f (x) + h∇f (x), y − xi ≤ f (y), ∀x, y ∈ C,
trong đó ký hiệu f 0 (a) hoặc ∇f (a) là đạo hàm của f tại a.
Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên C là với mọi
x thuộc C , 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 ∈ C, 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.
Tính khả vi của hàm lồi giữ vai trò quan trọng bậc nhất trong các
phương pháp tối ưu hóa.
1.2.2
Tính liên tục
Một hàm f xác định trên Rn được gọi là nửa liên tục dưới tại điểm x0
nếu với
mọi ε
> 0, tồn tại δ > 0, sao cho f (x) ≥ f (x0 ) − ε, với mọi x thỏa
mãn
x − x0
< δ.
Hàm f được gọi là nửa liên tục trên tại x0 nếu−f nửa liên tục dưới tại
x0 .
Hàm f được gọi là liên tục tại điểm x0 nếu f vừa nửa liên tục trên vừa
nửa liên tục dưới tại điểm này
Hàm f được gọi là liên tục (nửa liên tục) trên X , nếu nó liên tục (nửa
liên tục) tại mọi điểm trên X .
Định lý 1.6. Đối với một hàm lồi chính thường trên Rn và x0 ∈ int(domf ),
các khẳng định sau đây là tương đương:
(i) f liên tục tại điểm x0 ;
(ii) f bị chặn trong một lân cận của x0 ;
(iii) int(epif ) 6= ∅;
(iv) int(domf ) 6= ∅ và f liên tục trên tập int(domf ).
Một hàm lồi có thể không liên tục trên biên miền xác định của nó nhưng
liên tục tại mọi điểm trong của tập đó theo định lý sau:
Định lý 1.7. Một hàm lồi liên tục trên C thì liên tục tại mọi điểm trong
của C.
13
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.2.3
Dưới vi phân
Cho một hàm n biến, khi cố định một hướng và xét hàm nhiều biến
trên hướng đó thì ta có hàm một biến. Giả sử y 6= 0 là một hướng cho
trước xuất phát từ điểm x0 . Khi đó mọi điểm thuộc đường thẳng đi qua
x0 và có hướng y đều có dạng:
x = x0 + λy,
với λ ∈ R.
Cho f : Rn → R ∪ { + ∞} và x0 ∈ R sao cho f (x0 < +∞). nếu với
một vecto y ∈ Rn mà giới hạn:
f (x0 + λy) − f (x0 )
lim
λ→0
λ
tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại
điểm x0 , ký hiệu giới hạn này là f 0 (x0 , y).
Ta biết rằng nếu hàm lồi khả vi tại một điểm nào đó thì tiếp tuyến của
đồ thị tại điểm đó sẽ nằm dưới đồ thị hàm số. Nhưng hàm lồi có thể không
khả vi tại một điểm nào đó, trong trường hợp này ta mở rộng khái niệm
đạo hàm bằng dưới đạo hàm, sao cho vẫn giữ được tính chất cơ bản trên
của đạo hàm của hàm lồi khả vi.
Định nghĩa 1.6. Cho f : Rn → R ∪ { + ∞}. Ta nói x∗ ∈ Rn là dưới đạo
hàm của f tại x nếu:
hx∗ , z − xi + f (x) ≤ f (z), ∀z
Tập hợp tất cả các dưới đạo hàm của f tại x được gọi là dưới vi phân của
f tại x, ký hiệu là ∂f (x). Khi ∂f (x) 6= ∅ ta nói hàm f khả dưới vi phân
tại x. Trong trường hợp tập ∂f (x) chỉ gồm duy nhất một điểm thì hàm f
khả vi tại x.
Cũng có trường hợp tập ∂f (x) là tập rỗng, tức là tại điểm x hàm số f
không có dưới vi phân. Tuy nhiên đối với hàm lồi thì điều đó chỉ có thể
xảy ra theo định lý sau:
Định lý 1.8. Cho f : Rn → R ∪ { + ∞} là một hàm lồi, khi đó ∂f (x) 6= ∅
với mọi x thuộc ri(domf )
14
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
Từ định lý này suy ra rằng nếu hàm f là hàm lồi hữu hạn trên toàn
không gian Rn thì nó khả dưới vi phân tại mọi điểm, vì riRn = Rn .
Ví dụ 1.4. Hàm số f (x) = |x|, khả vi tại mọi điểm khác 0 nhưng không
khả vi tại x = 0, tại đó ∂f (0) = {y ||x| ≥ hy, xi, ∀x} = [ − 1, 1]
Cũng như trong trường hợp hàm một biến, bất đẳng thức
hx∗ , z − xi + f (x) ≤ f (z), ∀z,
có nghĩa là siêu phẳng đi qua điểm (x, f (x)) nằm dưới đồ thị của hàm số.
1.2.4
Tính chất cực trị
Định nghĩa 1.7. Cho C ⊆ Rn là tập khác rỗng và f : C → R. Một điểm
x∗ ∈ C được gọi là cực tiểu địa phương của f trên C nếu tồn tại một lân
cận U của x∗ sao cho
f (x∗ ) ≤ f (x), ∀x ∈ U ∩ C.
Điểm x∗ ∈ C được gọi là cực đại địa phương nếu
f (x) ≤ f (x∗ ), ∀x ∈ U ∩ C.
Nếu
f (x∗ ) ≤ f (x), ∀x ∈ C
thì x∗ được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C ,
và nếu
f (x) ≤ f (x∗ ), ∀x ∈ C
thì x∗ được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C.
Mệnh đề 1.1. Cho f : Rn → R ∪ { + ∞} là hàm lồi.Khi đó mọi điểm cực
tiểu địa phương của f trên một tập lồi đều là cực tiểu toàn cục. Hơn nữa
tập hợp các điểm cực tiểu của f là một tập lồi. Nếu f lồi chặt thì điểm
cực tiểu nếu tồn tại sẽ là duy nhất.
Mệnh đề 1.2. (i) Giả sử f là một hàm lồi chính thường trên Rn và
C ⊆ Rn là một tập lồi. Khi đó nếu f đạt cực đại hữu hạn tại một điểm
trong tương đối của C thì f là hằng số trên C.
(ii) Nếu f là một hàm lồi, chính thường trên Rn và bị chặn trên trong
một tập affine, thì nó là hằng số trên tập này .
15
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
Hệ quả 1.1. Nếu một hàm lồi đạt cực đại trên một tập lồi có điểm cực
biên, thì cực đại sẽ đạt được tại một điểm cực biên của tập lồi đó.
Kết luận chương 1
Trong chương 1, chúng ta đã trình bày một số kiến thức cơ bản của giải
tích lồi để sử dụng cho các chương tiếp theo như tập lồi, tập lồi đa diện,
hàm lồi và một số kết quả quan trọng như bổ đề Farkas, định lý tách các
tập lồi,..
16
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
Chương 2
Phương pháp hàm phạt
Nói chung các bài toán không có ràng buộc thường dễ xử lý hơn các
bài toán có ràng buộc. Một ý tưởng nảy sinh là chuyển bài toán tối ưu có
ràng buộc về bài toán tối ưu không ràng buộc. Kỹ thuật cơ bản để thực
hiện ý tưởng này là hàm phạt. Chương này gồm hai phần, phần 1 trình
bày khái niệm về bài toán tối ưu và các điều kiện tối ưu, phần 2 trình bày
ba phương pháp hàm phạt là: Phương pháp hàm phạt điểm trong, phương
pháp hàm phạt điểm ngoài và hàm phạt kiểu Lagrange (thưởng- phạt).
Các khái niệm và kết quả được lấy từ các tài liệu: [2],[3], [4],[5].
2.1
2.1.1
Bài toán tối ưu
Phát biểu bài toán
Bài toán tối ưu được xét trong chương này có dạng sau:
min {f (x) : x ∈ C}
(P ),
là bài toán tìm điểm x∗ ∈ C sao cho f (x∗ ) ≤ f (x) với mọi x ∈ C,
trong đó C ⊆ X (X là không gian nào đó, thông thường X ≡ Rn ),
f : C → R. Hàm f được gọi là hàm mục tiêu, tập C gọi là tập ràng buộc
hay miền chấp nhận được. Một vecto x ∈ C được gọi là một phương án
chấp nhận được. Vecto x∗ ∈ C thoả mãn điều kiện f (x∗ ) ≤ f (x) với mọi
x ∈ C được gọi là một nghiệm tối ưu của bài toán và f (x∗ ) được gọi là
giá trị cực tiểu hay giá trị tối ưu của f trên C .
Trường hợp C ≡ Rn ta có bài toán tối ưu không ràng buộc
min {f (x) : x ∈ Rn }
17
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
Trái lại (P ) là bài toán tối ưu có ràng buộc. Thông thường tập C thường
được cho bởi một hệ phương trình hoặc/và bất phương trình có dạng sau:
C = {x ∈ X :gi (x) ≤ 0, hj (x) = 0, i = 1, .., m; j = 1, .., p}
(2.1)
với gi , hj : X → R là các hàm cho trước, gọi là các hàm ràng buộc.
Dễ thấy rằng nếu các hàm f lồi, gi là lồi, liên tục trên X và các hàm
hj là afin thì C là tập đóng. Khi ấy (P) được gọi là bài toán quy hoạch lồi
Nhận xét 2.1. Do
max {f (x) : x ∈ C} = −min{−f(x) : x ∈ C},
và tập nghiệm của các bài toán này trùng nhau nên bài toán tìm cực đại
có thể đưa về bài toán tìm cực tiểu và ngược lại.
Sau đây là một số ví dụ về bài toán tối ưu có ràng buộc
Ví dụ 2.1. : bài toán xác định kế hoạch sản xuất tối ưu
Một xí nghiệp sản xuất n loại sản phẩm và sử dụng m loại nguyên
liệu khác nhau. Gọi xj , (j = 1, ..n) là lượng hàng thứ j cần sản xuất,
cj , (j = 1, .., n) là lãi thu được khi sản xuất một đơn vị sản phẩm thứ j .
Biết rằng để sản xuất một đơn vị sản phẩm thứ j cần dung đến aij loại
nguyên liệu thứ i, (i = 1, .., m; j = 1, .., n.). Gọi bi là số lượng nguyên liệu
thứ i mà xí nghiệp có thể cung cấp được. Bài toán đặt ra là xác định lượng
sản xuất cho mỗi loại sản phẩm để tổng số lãi thu được là lớn nhất. Bài
toán này có mô hình toán học như sau
Tìm xj ≥ 0, (j = 1, .., n) sao cho
f (x1 , .., xn ) =
n
X
cj xj → max
j=1
Với điều kiện
n
X
aij xj ≤ bi , i = 1, .., m
(2.2)
j=1
Ví dụ 2.2. Bài toán vận tải
Cần chở hàng từ m nơi sản xuất đến n nơi tiêu thụ. Biết trước lượng
hàng có ở mỗi nơi sản xuất và lượng hàng cần thiết ở mỗi nơi tiêu thụ, biết
cước phí.Tìm phương án vận chuyển sao cho thoả mãn tiêu thụ và cước
phí vận chuyển thấp nhất.
Gọi xij : Lượng hàng cần chuyển từ i đến j
18
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
cij : Cước phí vận chuyển một đơn vị hàng hoá từ i đến j
aj : Lượng hàng cần chở ở điểm j
bi : Lượng hàng có ở nơi sản xuất i
Mô hình toán học của của bài toán như sau
Tìm xij ≥ 0, (j = 1, .., n; i = 1, .., m) sao cho
f (xij ) =
m X
n
X
cij xij → min
i=1 j=1
Với các điều kiện
n
X
xij = bi
j=1
m
X
xij = aj
i=1
m
X
n
X
i=1
j=1
bi =
2.1.2
aj
Các điều kiện tối ưu
Xét bài toán (P). Đối với nghiệm tối ưu tuyệt đối, bốn khả năng sau
có thể xảy ra:
1. C là tập rỗng (bài toán không có phương án chấp nhận được)
2. f không bị chặn dưới trên C
3. inf f (x) > −∞ nhưng giá trị nhỏ nhất không đạt được trên C
x∈C
4. Tồn tại x∗ ∈ C sao cho f (x∗ ) = min f (x)
x∈C
Câu hỏi đặt ra là: Làm thế nào kiểm tra được sự tồn tại nghiệm của bài
toán? Ta xét các định lý sau đây:
Định lý 2.1. Điều kiện cần và đủ để hàm f đạt cực tiểu trên C là tập
F + (C) := {t ∈ R : f (x) ≤ t, x ∈ C}
đóng và bị chặn dưới
Định lý sau là một điều kiện đủ cho sự tồn tại nghiệm, dựa ngay trực
tiếp từ các dữ liệu của bài toán:
19
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
Định lý 2.2. (Weistrass) Nếu C là tập compact và f nửa liên tục dưới
trên C thì f đạt cực tiểu trên C
Một vấn đề quan trọng khi nghiên cứu các bài toán tối ưu là việc tìm
kiếm những điều kiện tối ưu. Những điều kiện ấy cho phép hiểu biết được
các tính chất của lời giải, từ đó có thể xây dựng phương pháp giải. Chúng
ta xét các định lý sau về điều kiện tối ưu:
Định lý 2.3. Giả sử C là tập lồi,f là hàm lồi khả dưới vi phân trên C .
Khi đó x∗ là nghiệm tối ưu của (P) khi và chỉ khi
0 ∈ ∂f (x∗ ) + NC (x∗ ),
(2.3)
trong đó NC (x∗ ) là nón pháp tuyến của C tại x∗
Chứng minh:
i) Điều kiện đủ: Giả sử điều kiện (2.3) được thỏa mãn, khi đó tồn tại
∗
p sao cho
p∗ ∈ ∂f (x∗ ) ∩ (−NC (x∗ )).
Do p∗ ∈ ∂f (x∗ ) nên
hp∗ , x − x∗ i ≤ f (x) − f (x∗ ), ∀x.
Ta lại có hp∗ , x − x∗ i ≥ 0, ∀x do p∗ ∈ −NC (x∗ ),
suy ra f (x) − f (x∗ ) ≥ 0, ∀x ∈ C.
(ii) Điều kiện cần: Giả sử x∗ là một nghiệm tối ưu của bài toán. Do
tính afin của C nên ta có thể coi C có thứ nguyên đầy đủ. Do C là tập
lồi, int(C) 6= ∅.
Xét hai tập sau:
E := {(t, x) ∈ R × Rn : t > f (x) − f (x∗ ), x ∈ C} ,
G := {0} × C.
Dễ thấy cả E và G đều là tập lồi (do C và f là lồi) . Hơn nữa G ∩ C = ∅.
Theo định lý tách thì tồn tại vectơ (u0 , u) 6= 0 ∈ Rn+1 sao cho
u0 t + uT x ≤ u0 0 + uT y, ∀(t, x) ∈ E, y ∈ C.
⇔ u0 t ≤ hu, y − xi, ∀(t, x) ∈ E, y ∈ C.
20
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.4)
- Xem thêm -