Chơng 3

phơng pháp hàm phạt
Trong phơng pháp hàm chắn trình bày ở chơng 2, ta đã đa vào hàm chắn
để ngăn cản di chuyển vợt ra ngoài miền chấp nhận đợc. Chơng này sẽ trình bày
phơng pháp hàm phạt. Chiến thuật giải ở đây là: đa thêm vào hàm mục tiêu
ban đầu một lợng phạt (phụ thuộc tham số), nếu điểm đợc xét vi phạm các ràng
buộc.
Trong mục 3.1 ta dùng hàm phạt bậc hai, hàm này có u điểm là trơn nhng
đòi hỏi tham số phạt tiến ra vô hạn và bài toán không ràng buộc thu đợc càng trở
nên khó giải. Để khắc phục hạn chế này, ở mục 3.2 ta xét hàm phạt chính xác
theo nghĩa nghiệm của bài toán phạt cho lời giải đúng của bài toán ban đầu với
giá trị hữu hạn của tham số phạt, tuy nhiên hàm phạt này lại không khả vi. Cuối
cùng, để nhận đợc hàm phạt chính xác khả vi ở mục 3.3, ta xét hàm phạt
Lagrange gia tăng. Nội dung trình bày ở chơng này chủ yếu dựa trên tài liệu [6].

3.1. Hàm phạt bậc hai
Xét bài toán tối u với ràng buộc đẳng thức:
(P)

min {f(x) : hi(x) = 0, i = 1, , m; x |Rn},

trong đó f(x), hi(x): |Rn |R, i = 1, , m là các hàm hai lần khả vi liên tục.
Miền ràng buộc (miền chấp nhận đợc) của bài toán (P) là tập
D = {x |Rn : hi(x) = 0, i = 1, , m}.
Định nghĩa. Hàm phạt là một hàm liên tục thoả mãn

39


(x) = 0 khi x D và (x) > 0 khi x D.

40


Đối với bài toán này ta có thể xác định Q nh sau

[

]

2

m
p
1
1
2
Q(x, ) = f(x) + ì h i ( x ) + ì max(0, g j ( x )) .
2 i=1
2
j=1

Trong trờng hợp này hàm Q có thể ít trơn hơn hàm mục tiêu và các hàm
ràng buộc ban đầu. Chẳng hạn, nếu g(x) = - x 0 thì
[max(0, g(x))]2 = [max(0, -x))]2 = [min(0, x))]2.
có đạo hàm cấp hai gián đoạn, vì thế Q không thuộc lớp C2.
Thuật toán phạt bậc hai:
Cho trớc tham số phạt 0 > 0, độ sai số 0 > 0 và điểm xuất phát x s0 .
Với mỗi k = 0, 1,
1. Xuất phát từ x sk , tìm điểm cực tiểu xấp xỉ xk của Q(x, k). Dừng tìm
cực tiểu khi ||xQ(x, k)|| k.

2 i=1
với dãy {k} tăng và hội tụ tới +. Khi đó, mọi điểm tụ x* của dãy {xk} là điểm
cực tiểu toàn cục của bài toán với ràng buộc đẳng thức (P).

42


3.0
x = x2

2.5

2.0

1.5

1.0

điểm tối ưu o

điểm xuất phát
o
o

o

o

0.5


k

k h i ( x ) = f( x ).
i
2 i=1
2 i=1

Từ đó ta có

43

(3.1)


m

2

h i2 ( x k ) [f( x ) - f(xk)].
k
i =1

(3.2)

Giả sử x* là một điểm tụ của dãy {xk} và {xk}kK là dãy con hội tụ tới x*.
Trớc hết, ta chứng minh x* là điểm chấp nhận đợc.

Qua giới hạn hai vế của (3.2) khi k + , k K, ta đợc
m


hi(x*), i = 1, 2, , m, độc lập tuyến tính và K N sao cho xk x*, k K.
Trớc hết, ta chứng minh x* chấp nhận đợc:

Theo định nghĩa của Q ta có
m

k
k
xQ(xk, k) = f(xk) + k h i ( x )h i ( x ) .
i =1

(3.3)

Do ||xQ(xk, k)|| k nên ta có
m

k
k
||f(xk) + k h i ( x )h i ( x ) || k.
i =1

Từ đó, sử dụng bất đẳng thức tam giác, ta đợc
m

m

i =1

i =1


m





|| h i ( x )h i ( x ) || = 0 h i ( x )h i ( x ) = 0.
i =1

i =1

Theo giả thiết các véctơ hi(x*), i = 1, , m, độc lập tuyến tính nên đẳng
thức cuối cùng kéo theo hi(x*) = 0, i = 1, , m. Do vậy x* là chấp nhận đợc.
Tiếp theo, ta chỉ rõ tồn tại à* |Rm thoả mãn f(x*) + h(x*)Tà* = 0:

Đặt àk = kh(xk). Ta chứng minh àk hội tụ tới véctơ trong |Rm, ký hiệu à*.
Dùng định nghĩa của àk, từ (3.3) suy ra
h(xk)Tàk = - f(xk) + xQ(xk, k)
Vì thế sau khi nhân với h(xk) ta có
h(xk)h(xk)Tàk = - h(xk)f(xk) + h(xk)xQ(xk, k)

(3.5)

Do h(xk) có hạng m và h(xk) h(x*), k K, nên hạng của f(xk)
bằng m với k K đủ lớn. Vì thế với k đủ lớn ma trận vuông h(xk)h(xk)T (cấp
m) không suy biến. Vì thế từ (3.5) ta có

46




Khi x gần điểm cực tiểu của Q(., k) và khi các điều kiện của Định lý 3.2 đợc thoả mãn ta có
kh(x) kh(xk) à* khi k đủ lớn.
Khi đó
2x Q(x,

m

2
k) f(x) + à i h i ( x ) + kh(x)Th(x).
2

i =1

m

2
Để ý rằng ma trận 2f(x) + à i h i ( x ) không phụ thuộc k và ma trận
i =1

h(x)Th(x) có hạng m do h(x) có hạng m. Hơn nữa, h(x)Th(x) là đối xứng
và nửa xác định dơng. Vì thế, h(x)Th(x) có m giá trị riêng dơng và n m
giá trị riêng bằng 0. Điều này kéo theo 2x Q(x, k) có một số giá trị riêng tiến tới
hằng số, trong khi các giá trị riêng khác dần tới + khi k +. Điều này đợc
minh hoạ ở ví dụ sau đây.
Ví dụ 3.3. Xét bài toán
min f(x) x 12 + x 22 với điều kiện h(x) x1 + x2 1 = 0.
Hàm phạt bậc hai có dạng Q(x, ) = x 12 + x 22 + (/2)(x1 + x2 1)2. Vì thế,
Q(x, ) = (2x1 + (x1 + x2 1), 2x2 + (x1 + x2 1))T,


1
h ( x )
k I


Hệ này tơng đơng với hệ (3.6) theo nghĩa d là nghiệm của cả hai hệ. Thật
vậy, do h(x)d - k1 = 0, nghĩa là = kh(x)d nên ta có
m

2
[ f(x) + k h i ( x ) h i ( x ) ]d + h(x)T =
2

i =1

m

2
= [2f(x) + k h i ( x ) h i ( x ) + kh(x)Th(x)]d
i =1

= 2x Q(x, k)d.

49


Ta còn phải chứng minh rằng ma trận mới này tiến dần tới một ma trận có
điều kiện tốt. Khi x xk và k +, ma trận mới dần tới ma trận
m
2

h(x*)u = 0.

(3.8)

Ta cần chứng minh u = 0 và v = 0. Muốn vậy, nhân hai vế của (3.7) với u T
ta đợc
uT2L(x*, à*)u + uTh(x*)Tv = 0,
nghĩa là theo (3.8) ta có uT2L(x*, à*)u = 0. Nhng khi đó u = 0. Thật vậy, nếu u
0 thì từ (3.8) và điều kiện đủ cấp hai suy ra u T2L(x*, à*)u > 0. Vậy u = 0.

50


Khi đó (3.7) trở thành h(x*)Tv = 0. Phơng trình này kéo theo v = 0, bởi vì
h(x*) có hạng bằng m.

3.2. hàm phạt chính xác
Để tránh điều kiện xấu, ta sẽ cải tiến phơng pháp hàm phạt bậc hai sao cho
tham số không cần tiến ra vô hạn. Trong mục này ta sẽ xét các hàm phạt chính
xác, theo nghĩa lời giải của bài toán phạt cho lời giải đúng của bài toán ban đầu
đối với giá trị hữu hạn của tham số phạt. Khó khăn là ở chỗ các hàm phạt này
không khả vi. Xét bài toán
f(x) min,

(P)
với các điều kiện ràng buộc

hi(x) = 0, i = 1, 2, , m,
gj(x) 0, j = 1, 2, , p,
và hàm phạt

2.0
1.5
1.0
0.5
0.0

= 10

3.0
2.5
2.0
1.5
1.0
0.5
0.0

=1

x2 + (/2)(x
1)2

0.0 0.4 0.8 1.2 1.6 2.0

x2 + 3|x
1|

f(x) = x2

0.0 0.4 0.8 1.2 1.6 2.0



p(u) = p(u) + u i .
i =1

1. u = 0 là cực tiểu địa phơng của p, > maxi |ui|:
Dùng định lý giá trị trung bình ta có thể viết
53


p(u) = p(0) + p(u)Tu với nào đó [0, 1].
Vì thế
m

p(u) = p(0) + p(u) u + u i .
T

i =1

(3.9)

Cho > 0. Do građiên p liên tục tại 0 và p(0) = - à nên tồn tại lân cận N0
của 0 sao cho
u N0 |p(u)i + ài| < , i = 1, 2, , m,
nghĩa là
u N0 |p(u)i| < + |ài|, i = 1, 2, , m.

(3.10)

Mặt khác, ta có
m

i =1

Vì thế, với > + maxi |ài| nên ta có
p(u) p(0) = p(0) với mọi u N0.
Do > 0 chọn tuỳ ý nên cuối cùng ta đợc
|ài|, 0 là điểm cực tiểu địa phơng của p.
> max
i
2. x* là cực tiểu địa phơng của f(x) + im=1 h i ( x ) :
Từ phần đầu chứng minh ta thấy
m

u N0 p(0) p(u) + u i .
i =1

Do h(x*) = 0 và h liên tục tại x* nên tồn tại lân cận N(x*) của x* sao cho
h(x) N0 với mọi x N(x*). Do vậy, với mỗi x N(x*)
m

p(0) p(h(x)) + h i ( x ) .
i =1

Do p(0) = f(x*), h(x*) = 0 và p(h(x)) = inf h(z) = h(x) f(z) f(x) nên ta có với
mọi x N(x*)
m

m

i =1




(h(x) - )T(h(x) - ),
2

56


trong đó |Rm. Các tham số i tơng ứng với sự đổi gốc của số hạng phạt, còn
> 0 điều khiển qui mô phạt. Ví dụ sau minh hoạ cho cách làm này.
Ví dụ 3.5. Xét bài toán tìm min f(x) = x với điều kiện h(x) = x 1 = 0. Rõ
ràng lời giải của bài toán là x* = 1. Điểm cực tiểu của hàm
(x, , ) = x +


(x - 1 - )2
2

là x(, ) = 1 + - -1. Vì thế, với mỗi > 0 có thể chọn sao cho x(, ) = x*
= 1. Muốn thế, chỉ cần chọn = -1.
Cách làm thuận tiện hơn là đa vào các tham số ài = - i, i = 1, , m.

Khi đó (x, , ) = f(x) + h(x)Tà + (/2)h(x)Th(x) + (/2)T. Do số hạng
cuối không phụ thuộc x nên hàm cần làm cực tiểu trở thành
(x, , ) = f(x) + h(x)Tà +



h(x)Th(x) = L(x, à) + h(x)Th(x).
2


Khi đó, LA (x*, à*, ) = 3x*2 3 + (x* + 1) và LA (x*, à*, ) = - 6 + .
Vì thế, nếu > 6 thì x* là cực tiểu địa phơng của LA(., à*, ). Điều này đợc
minh hoạ ở Hình 3.3 (tr. sau) với = 9. Cũng ở hình này ta thấy x* không phải
cực tiểu địa phơng của L(.,à*).
58


Một hệ quả rút ra từ Định lý 3,4: nếu à* biết trớc thì một điểm cực tiểu
không ràng buộc của LA(x, à*, ) sẽ là x*. Tuy nhiên ta không biết trớc đợc giá
trị của à*. Vì thế, ta cần ớc lợng giá trị này thông qua dãy {àk} à*. Cho trớc
àk. Khi đó, xk đợc xác định nh điểm cực tiểu của hàm
LA(x, àk, ) = f(x) + h(x)Tàk +


h(x)Th(x).
2

Theo định nghĩa của xk ta có LA(xk, àk, ) = 0, tức là
f(xk) + [àk + h(xk)]Th(xk) = 0.
Do f(x*) + h(x*)Tà* = 0, nên chiến thuật là lấy
àk+1 = àk + h(xk)
làm xấp xỉ tiếp theo cho à*.

59


1.0
0.5
0.0

cực tiểu khi ||xLA(xk, àk, k)|| k.
2. Chỉnh sửa các nhân tử Lagrange theo công thức àk+1 = àk + kh(xk).
3. Chọn tham số phạt mới k+1 k, k+1 [0, k], đặt x sk +1 = xk. Trở lại 1.

60


Ví dụ 3.7. Xét bài toán sau đây:
min 2x2 + 2xy + y2 2y với điều kiện x = 0.
Điểm cực tiểu của hàm Lagrange gia tăng
LA(x, à, ) = 2x2 + 2xy + y2 2y + àx + (/2)x2
là
x=-

2+à
4++à
và y =
2+
2+

Do h(x, y) = x nên ta có
à

k+1

2
2
( 2 + à k )
= à + h(x , y ) = à =
.

có thể vận dụng lý thuyết đã trình bày cho trờng hợp các ràng buộc đẳng thức.
Hàm Lagrange gia tăng là
LA(x, z, , ) = f(x) + T(g(x) + z) + (/2)||g(x) + z||2,
trong đó > 0 và g(x) = (g1(x), g2(x), , gp(x))T.
ở vòng lặp k của thuật toán, ta giải bài toán phụ sau với cố định:
min {LA(x, z, , ) : x |Rn, z 0}.
Để giải bài toán này, trớc hết ta giữ cố định x và tìm cực tiểu của hàm
Lagrange gia tăng đối với z 0, tức là
min {f(x) + T(g(x) + z) + (/2)||g(x) + z||2 : z 0}.
Do x cố định nên bài toán này có thể đợc viết lại thành
min {[ + g(x)]Tz + (/2)||z||2 : z 0}.
Bài toán này đợc tách ra thành p bài toán con nh sau:
min {[j + gj(x)]zj + (/2)z 2j : zj 0}, j = 1, , m.
Ký hiệu lời giải của p bài toán này là z j , j = 1, 2, , p. Do điểm cực tiểu
không ràng buộc của hàm mục tiêu trong mỗi bài toán này là nghiệm của
j + gj(x) + zj = 0

62


nên ta có
(1 / )[ j + g j ( x )] nếu j + g j ( x ) 0,
z j =
0
nếu j + g j ( x ) > 0.

Vì thế
j / nếu j + g j ( x ) 0,
gj(x) + z j =
g j ( x ) nếu j + g j ( x ) > 0.


]

và phép lặp theo trở thành (trớc hết với biến z rồi sau không có biến z):
k +1

j

= kj + [gj(xk+1) + zj], j = 1, 2, , p

63