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
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 7
1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Định nghĩa và tính chất . . . . . . . . . . . . . . . . 11
1.2.2 Tính liên tục . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Tính chất cực trị . . . . . . . . . . . . . . . . . . . 15
2 Phương pháp hàm phạt 17
2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 17
2.1.2 Các điều kiện tối ưu . . . . . . . . . . . . . . . . . . 19
2.2 Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Hàm phạt điểm ngoài . . . . . . . . . . . . . . . . . 24
2.2.2 Hàm phạt điểm trong . . . . . . . . . . . . . . . . . 26
2.2.3 Hàm phạt kiểu Lagrange . . . . . . . . . . . . . . . 31
3 Hàm phạt chính xác và áp dụng 42

4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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ơ

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 R
n
là tập
hợp tất cả các vecto x ∈ R
n
có dạng
{x ∈ R
n
|x = αa + βb, α + β = 1}.
Đoạn thẳng nối hai điểm trong không gian R
n
là tập hợp tất cả các
vecto x ∈ R
n
có dạng
{x ∈ R
n
|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 R
n
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

T
x =α},
với 0 = a ∈ R
n
và α ∈ R chia R
n
thành hai nửa không gian đóng :
H
−
= {x ∈ R
n
| a
T
x ≤ α} và H
+
= {x ∈ R
n
| a
T
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 R
n
thành hai nửa không gian mở:
{x ∈ R
n
| a
T
x < α} và {x ∈ R

3. A × C := {x ∈ R
n+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à affA.
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 R
n
có thể không có điểm trong (khi xét trong
R
n
), nhưng nó luôn có điểm trong khi xét trong affA, đ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 = ∅.
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 ∈ R
n
< a
j
, x >≤ b
j
, j = 1, 2, , m}.
Một tập con A

lùi xa của C, ký hiệu là reC.
Cho C là một tập lồi trong R
n
và x ∈ C, tập hợp:
N
C
(x) = {w |w, y −x ≤ 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
−N
C
(x) = {w |w, y −x ≥ 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 | w, x ≤ 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 ∈ R
n
là một
hướng chấp nhận được của C nếu tồn tại t
0
> 0 sao cho x + td ∈ C với
mọi 0 ≤ t ≤ t
0
. 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 a
T

n
là một tập lồi khác rỗng. Giả sử x
0
/∈ C. Khi
đó tồn tại t ∈ R
n
, t = 0 thỏa mãn t, x ≥ t, x
0
, ∀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 R
n
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 R
n
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 ∈ R
n
và A là ma trận cỡ m ×n. Khi đó a, x ≥ 0 với mọi x thỏa
mãn Ax ≥ 0, khi và chỉ khi tồn tại y ≥ 0 thuộc R
m
sao cho a = A
T
y.

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
Đị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) + ∇f(x), y −x ≤ f(y), ∀x, y ∈ C,
trong đó ký hiệu f

(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à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 R
n
và x
0
∈ int(domf),
các khẳng định sau đây là tương đương:
(i) f liên tục tại điểm x
0
;
(ii) f bị chặn trong một lân cận của x
0
;
(iii) int(epif) = ∅;
(iv) int(domf) = ∅ 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
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 = 0 là một hướng cho
trước xuất phát từ điểm x
0
. Khi đó mọi điểm thuộc đường thẳng đi qua
x
0

, 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 : R
n
→ R ∪{ + ∞}. Ta nói x
∗
∈ R
n
là dưới đạo
hàm của f tại x nếu:
x
∗
, z −x + 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) = ∅ 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 : R
n
→ R ∪{+ ∞} là một hàm lồi, khi đó ∂f(x) = ∅
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

∈ 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 : R
n
→ 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 R
n
và
C ⊆ R
n
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

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 ≡ R
n
),
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 ≡ R
n
ta có bài toán tối ưu không ràng buộc
min {f(x) : x ∈ R
n
}
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 :g

loại
nguyên liệu thứ i, (i = 1, , m; j = 1, , n.). Gọi b
i
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 x
j
≥ 0, (j = 1, , n) sao cho
f(x
1
, , x
n
) =
n
j=1
c
j
x
j
→ max
Với điều kiện
n
j=1
a
ij
x
j
≤ b

n
j=1
c
ij
x
ij
→ min
Với các điều kiện
n
j=1
x
ij
= b
i
m
i=1
x
ij
= a
j
m
i=1
b
i
=
n
j=1
a
j
2.1.2 Các điều kiện tối ưu

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
∗
) + N
C
(x
∗
), (2.3)
trong đó N
C
(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
∗
) ∩(−N
C
(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) = ∅.
Xét hai tập sau:
E := {(t, x) ∈ R × R
n
: 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ơ (u
0
, u) = 0 ∈ R
n+1
sao cho
u
0
t + u
T
x ≤ u
0
0 + u
T
y, ∀(t, x) ∈ E, y ∈ C.
⇔ u
0
t ≤ u, y − x, ∀(t, x) ∈ E, y ∈ C. (2.4)
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

T
y, ∀x, y ∈ C. (2.6)
Cho y = x
∗
trong (2.6) ta được:
−[f(x) − f(x
∗
)] + ¯u
T
x ≤ ¯u
T
x
∗
, ∀x, y ∈ C.
Hay
f(x
∗
) −f(x) + ¯u
T
(x −x
∗
) ≤ 0, ∀x ∈ C. (2.7)
Do f(x) = ∞ nếu x /∈ C nên từ (2.7) ta có:
f(x
∗
) −f(x) + ¯u
T
(x −x
∗
) ≤ 0, ∀x ∈ X.

∗
∈ S(C, f) (Tập nghiệm tối ưu của
(P)) thì 0 ∈ ∂f(x
∗
). Đặc biệt, nếu f khả vi và C là toàn bộ không gian thì
0 = f(x
∗
).
Một công cụ hữu ích, được sử dụng rộng rãi khi nghiên cứu các điều
kiện tối ưu là hàm Lagrange. Đối với bài toán (P), khi C được cho bởi
(2.1), hàm Lagrange được định nghĩa như sau:
L(x, λ, µ) := f(x) +
m
i=1
λ
i
g
i
(x) +
p
j=1
µ
j
h
j
(x)
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Sử dụng hàm Lagrange, ta thu được điều kiện cần (và đủ nếu bài toán là
một quy hoạch lồi) tối ưu. Ta cần đến khái niệm sau:

0
) được gọi là nón chấp nhận được
tuyến tính hóa.
Cho X
0
∈ C , ta nói rằng điều kiện chính quy được thỏa mãn tại điểm x
0
nếu
¯
D(x
0
) = S(x
0
)
Định lý 2.4. (Kuhn- Tucker)
Cho f, g
i
, h
j
là các hàm khả vi liên tục trên một tập mở chứa C. Cho x
∗
là một cực tiểu địa phương của bài toán (P) và tại đó điều kiện chính quy
được thỏa mãn. Khi đó tồn tại các vectơ λ
∗
= (λ
∗
1
, , λ
∗
m

(x
∗
) = 0. (2.10)
λ
∗
i
g(x
∗
) = 0. (2.11)
Nếu (P) là một quy hoạch lồi thì các điều kiện trên cũng là điều kiện
đủ để x
∗
∈ C là lời giải của bài toán (P)
Chứng minh. Sử dụng khai triển Taylor
f(x
∗
+ λd) = f(x
∗
) + ∇f(x
∗
), λd + r(λd),
ta có ∇f(x
∗
), d ≥ 0 với mọi d ∈
¯
C(x
∗
).
Hơn nữa, do tại x
∗

∗
) và α
j
≥ 0, β
j
≥ 0, j = 1, , p
sao cho
∇f(x
∗
) +
i∈A(x
∗
)
λ
i
g
i
(x
∗
) +
p
j=1
(α
j
− β
j
)∇h
j
(x
∗

∗
).
Đặt d := x − x
∗
= 0. Khi đó
∇f(x
∗
), d = lim
t0
f(x
∗
+ td) −f(x
∗
)
t
< 0. (2.12)
Mặt khác, λ
∗
i
g
i
(x
∗
) = 0 với mọi i, nên λ
∗
i
= 0 nếu i ∈ A(x
∗
). Với x ∈ D,
lập luận tương tự, ta có

j
(x
∗
), d = 0. (2.14)
Suy ra
µ
∗
j
∇h
j
(x
∗
), d = 0, j = 1, , p.
Kết hợp (2.12), (2.13) và (2.14), ta được
∇f(x
∗
), d +
m
i=1
λ
∗
i
∇g
i
(x
∗
), d +
k
j=1
µ

m
j=1
(max{0, g
j
(x)})
2
, (2.15)
hoặc
p(x) :=
m
j=1
max(0, g
j
(x)), (2.16)
còn nếu D cho bởi
D := {x : h
i
(x) = 0, i = 1, , p},
thì ta có thể chọn hàm phạt
p(x) :=
p
i=1
h
i
(x)
2
. (2.17)
Với mỗi t > 0, ta định nghĩa bài toán phạt như sau:
min{F
t

j
(x) : R
n
→ R là
các hàm lồi với mọi j thì (2.15), (2.16) cũng là các hàm lồi. Hơn nữa,
nếu g
j
, j = 1, m khả vi thì (2.15) cũng khả vi
Định lý 2.5. Giả sử bài toán (P ) có nghiệm với mọi t > 0. Lấy dãy số
dương {t
k
} đơn điệu tăng đến +∞ và x
k
là lời giải của (P
t
k
). Khi đó:
1. p(x
k
) ≥ p(x
k+1
),
2. f(x
k
) hội tụ tăng dần đến f
∗
và mọi điểm tụ của dãy {x
k
} là lời giải
tối ưu của bài toán gốc (P ).

k+1
). (2.18)
Cộng hai bất đẳng thức trên và giản ước ta được
(t
k
− t
k+1
)(p(x
k
) −p(x
k+1
)) ≤ 0
Vì {t
k
} đơn điệu tăng nên p(x
k
) ≥ p(x
k+1
). Thay vào bất phương trình
(2.18) ta được f(x
k
) ≤ f(x
k+1
) với mọi k.
(2) Giả sử x
∗
là một lời giải tối ưu của bài toán (P). Do p(x
∗
) = 0, ta có
f(x

p(u
∗
) ≥ f
∗
khi k đủ lớn. (2.20)
Lấy giới hạn (2.19), ta được
f(u
∗
) + lim t
k
p(u
∗
) ≤ f
∗
.
Mâu thuẫn với (2.20) vậy u
∗
∈ D. Và f(u
∗
) = f
∗
vì theo tính chất xác
định hàm p và theo (2.19) ta có
f(x
k
) < f
∗
.
Do f liên tục nên qua giới hạn ta được f(u
∗