TẠP CHÍ KHOA HỌC, Đại học Huế, Số 53, 2009
PHƯƠNG PHÁP CHẮN LOGARIT GỐC GIẢI BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH
Bùi Văn Hiếu, Huỳnh Thế Phùng
Trường Đại học Khoa học, Đại học Huế
TÓM TẮT
Các phương pháp điểm trong cho tối ưu tuyến tính đã được giới thiệu khá chi tiết bởi C.
Roos, T. Terlaky, J.P. Vial [3]. Trong bài báo này, áp dụng các kĩ thuật của phương pháp chắn
logarit đối ngẫu vào bài toán gốc, chúng tôi đề xuất phương pháp chắn logarit gốc. Hơn nữa, độ
phức tạp đa thức của thuật toán này cũng được thiết lập.
1 Giới thiệu
Xét bài toán quy hoạch tuyến tính dạng chuẩn
(LP) : min{c
T
x | Ax = b, x ≥ 0}
trong đó c, x ∈ R
n
, b ∈ R
m
và A ∈ R
m×n
là ma trận có hạng bằng m. Bài toán đối ngẫu của
(LP) là
(LD) : max{b
T
λ | A
T
λ + s = c, s ≥ 0}.
Ý tưởng chính của phương pháp chắn logarit gốc giải bài toán (LP) dựa trên việc xử lý
ràng buộc bất đẳng thức x ≥ 0 bằng cách sử dụng hàm phạt là hàm chắn logarit φ(x) :=
−

, . . . , x
n
)
T
và s = (s
1
, . . . , s
n
)
T
là hai vectơ dương trong R
n
. Trong suốt
bài báo này, ta kí hiệu e = (1, . . . , 1)
T
∈ R
n
, x
−1
:= (1/x
1
, . . . , 1/x
n
)
T
và xs := (x
1
s
1
, . . . , x

∗
, s
∗
) là nghiệm của Bài toán (LD) khi và
chỉ khi (x
∗
, λ
∗
, s
∗
) là nghiệm của hệ KKT









A
T
λ + s = c,
Ax = b,
XSe = 0,
(x, s) ≥ 0.
(1)
Định lý 2.2. x
t
là nghiệm của Bài toán (BP) và (λ

Mệnh đề 2.3 (Theorem II.4, [3]). Cho t > 0. Các khẳng định sau là tương đương
a) F
+
:= {(x, λ, s) | Ax = b, A
T
λ + s = c, (x, s) > 0} = ∅;
b) Bài toán (BP) có nghiệm (duy nhất);
c) Bài toán (BD) có nghiệm (duy nhất);
d) Hệ KKT (2) có nghiệm (duy nhất).
Mệnh đề 2.3 suy ra rằng đường trung tâm chỉ tồn tại khi và chỉ khi miền chấp nhận được
của cả hai bài toán gốc và bài toán đối ngẫu đều chứa các vectơ dương. Do đó, trong bài báo
này ta luôn giả thiết rằng
F
+
= ∅.
Cơ sở của phương pháp chắn logarit gốc dựa trên định lý sau.
Định lý 2.4. c
T
x
t
 c
T
x
∗
khi t  0.
Chứng minh. Ta có
c
T
x
∗

− c
T
x
∗
≤ nt, suy ra điều cần chứng minh.
44
c
x
∗
x
t
Hình 1: Đường trung tâm tiến đến nghiệm của Bài toán (LP) khi t  0.
3 Xấp xỉ nghiệm của Bài toán chắn (BP)
Trong Bài toán (BP), việc tìm nghiệm x
t
là không đơn giản do hàm mục tiêu P
t
(x) :=
c
T
x −t

n
j=1
log x
j
là phi tuyến. Ta tìm nghiệm xấp xỉ của bài toán này bằng cách xấp xỉ hàm
mục tiêu P
t
(x) bởi hàm toàn phương trong khai triển Taylor của P

Đặt
P
+
:= {x | Ax = b, x > 0}.
Lúc đó, mỗi điểm x ∈ P
+
được gọi là một điểm trong chấp nhận được hay điểm chấp nhận
được chặt của Bài toán (LP). Tại bước lặp hiện hành (với nghiệm xấp xỉ x
t
là x ∈ P
+
), ta cần
xác định hướng tìm kiếm ∆x sao cho x + ∆x ∈ P
+
. Do Ax = b nên A∆x = 0. Từ đó, ∆x là
nghiệm của bài toán xấp xỉ
min{P
t
(x) + (c − tx
−1
)
T
∆x +
1
2
∆x
T
tX
−2
∆x | A∆x = 0}.

(4)
Hệ này có nghiệm duy nhất



∆x =

X
2
A
T
(AX
2
A
T
)
−1
A −I


1
t
X
2
c −x

λ = (AX
2
A
T

,
d ∈ R
m
khi và chỉ khi x là nghiệm của phương trình chuẩn tắc C
T
Cx = C
T
d. Thật vậy,
Cx − d đạt cực tiểu khi và chỉ khi Cx = proj
Im(C)
d. Hơn nữa
Cx = proj
Im(C)
d ⇔ proj
Im(C)
(Cx − d) = 0
⇔ Cx − d ∈ Im(C)
⊥
= Ker(C
T
)
⇔ C
T
(Cx − d) = 0
⇔ C
T
Cx = C
T
d
Trở lại mệnh đề, với bất kì s = c − A

(tx
−1
− tX
−2
∆x) = tAx − tA∆x = tAx.
Do đó s(x, t) := c − A
T
λ = tx
−1
− tX
−2
∆x được định nghĩa như trong (6) chính là điểm
cực tiểu của bài toán đã cho.
4 Các tính chất của bước lặp Newton
Ở bước lặp hiện hành, tại x ∈ P
+
, ta cập nhật
x
+
= x + ∆x = x(e + x
−1
∆x).
Rõ ràng x
+
là điểm chấp nhận được nếu và chỉ nếu e + x
−1
∆x ≥ 0. Hơn nữa, từ (6) ta có
s(x, t) = tx
−1
(e −x

Newton không thể trùng với x
t
, do đó ta cần một đại lượng, kí hiệu là δ(x, t), dùng để đo mức
độ gần nhau giữa điểm x và x
t
trên đường trung tâm. Từ Mệnh đề 4.1 ta có thể chọn δ(x, t)
chính là x
−1
∆x
∞
. Tuy nhiên để thuận tiện trong việc phân tích độ phức tạp của thuật toán,
ta thay chuẩn vô cùng bằng chuẩn Euclide. Tức là
δ(x, t) := x
−1
∆x.
Từ (6) và Mệnh đề 3.1 ta có
δ(x, t) := x
−1
∆x =




e −
xs(x, t)
t





+
, t) ≤
1
t
te −x
+
s(x, t).
Do (7) nên
te −x
+
s(x, t) = te − (x + ∆x)s(x, t) = t(x
−1
∆x)
2
.
Vì vậy
δ(x
+
, t) ≤ (x
−1
∆x)
2
 ≤ x
−1
∆x
2
= δ(x, t)
2
.
5 Lỗ hổng đối ngẫu

đơn điệu
giảm và b
T
λ
t
đơn điệu tăng về giá trị tối ưu chung của hai bài toán (LP) và (LD). Mệnh đề
sau cho ta một ước lượng của lỗ hổng đối ngẫu tại (x, s(x, t)).
Mệnh đề 5.1. Nếu δ := δ(x, t) ≤ 1 thì lỗ hổng đối ngẫu tại (x, s(x, t)) thỏa mãn
nt(1 −δ) ≤ x
T
s(x, t) ≤ nt(1 + δ).
Chứng minh. Ta có
x
T
s(x, t) = x
T
[tx
−1
(e −x
−1
∆x)] = te
T
(e −x
−1
∆x).
Do δ ≤ 1 nên tọa độ của vectơ e −x
−1
∆x nằm trong khoảng [1 −δ, 1 + δ], từ đó suy ra bất
đẳng thức cần chứng minh.
47




≤ τ.
Ở mỗi bước lặp, ta tính ∆x và λ theo công thức (5) và cập nhật

x
+
:= x + ∆x,
t
+
:= (1 −θ)t.
Thuật toán dừng khi lỗ hổng đối ngẫu nt ≤ .
Thuật toán chắn logarit gốc cho Bài toán (LP).
Input:
A, b, c;
Sai số xấp xỉ τ, 0 ≤ τ < 1;
Sai số  > 0;
Điểm xuất phát x
0
thỏa mãn x
0
> 0, Ax
0
= b và
tham số chắn t
0
> 0 sao cho δ(x
0
, t

(8)
luôn được đảm bảo ở mỗi bước lặp, do đó tính đúng đắn của thuật toán được thiết lập.
Bổ đề 6.1. Giả sử δ(x, t) ≤ 1. Lúc đó
δ(x
+
, t
+
)
2
= δ(x, t)
4
+
θ
2
n
(1 −θ)
2
48
Hình 2: Minh họa các bước lặp của thuật toán chắn logarit gốc.
trong đó t
+
:= (1 −θ)t.
Chứng minh. Ta có
δ(x
+
, t
+
) ≤
1
t

+
) ≤




e −
e −h
2
1 −θ




=




h
2
−
θ
1 −θ
(e −h
2
)




Do giả thiết h = δ(x, t) ≤ 1 nên 0 ≤ e −h
2
≤ e, và do đó
(h
2
)
T
(e −h
2
) ≥ 0, e −h
2

2
≤ e
2
.
Vì vậy
δ(x
+
, t
+
)
2
≤ h
2

2
+ η
2
e

1
4
. Do đó nếu δ(x, t) ≤ τ = 1/
√
2 thì từ Bổ đề 6.1 suy ra
δ(x
+
, t
+
)
2
≤
1
4
+
1
4
=
1
2
hay δ (x
+
, t
+
) ≤ 1/
√
2 = τ . Như vậy, sau mỗi bước lặp, điều kiện (8) luôn thỏa mãn nên tính
đúng đắn của thuật toán được thiết lập.
49
Định lý sau khẳng định tốc độ hội tụ đa thức của thuật toán chắn logarit gốc.

) ≤ log .
Hơn nữa do −log(1 − θ) ≥ θ nên bất đẳng thức trên được thỏa mãn nếu
kθ ≥ log(nt
0
) −log  = log
nt
0

hay
k ≥

3
√
n log
nt
0


.
Hơn nữa, nếu x là bước lặp kết thúc thuật toán và t là tham số chắn tương ứng thì từ Mệnh
đề 5.1 suy ra
x
T
s(x, t) ≤ nt[1 + δ(x, t)] ≤ nt(1 + τ) ≤ 2nt.
Khi thuật toán kết thúc ta có nt ≤ , do đó x
T
s(x, t) ≤ 2. Định lý được chứng minh.
7 Điểm xuất phát của thuật toán
Thuật toán chắn logarit gốc mà ta giới thiệu ở phần trên đòi hỏi điểm xuất phát phải là một
điểm trong của miền chấp nhận được và phải gần hoặc nằm trên đường trung tâm. Đôi khi một

có nghiệm. Đặt
M :=


0 A −b
−A
T
0 c
b
T
−c
T
0


, z :=


λ
x
α


;
50
và
M :=

M u
−u

Mệnh đề 7.1 (Theorem I.5, I.6, [3]). Các khẳng định sau là tương đương
a) Bài toán (P) và (D) có nghiệm tối ưu với lỗ hổng đối ngẫu bằng 0;
b) Hệ (12) có nghiệm với α > 0;
c) Hệ (13) có nghiệm với α > 0 và β = 0;
d) Bài toán (SP) có nghiệm với α > 0.
Như vậy, ta đã qui việc giải bài toán (P) về bài toán tương đương (SP). Để ý rằng (SP) là
bài toán tự đối ngẫu (bài toán đối ngẫu trùng với chính nó). Hơn nữa, với k := m + n + 2 và
z = e
k
, ta có
Mz + q =

M u
−u
T
0

e
k−1
1

+

0
k−1
k

=

Me

k−1
+ k = 1
(e
T
k−1
Me
k−1
= 0 vì M là ma trận phản đối xứng). Từ đó suy ra Me
k
+ q = e
k
hay z = e
k
là
một điểm trong chấp nhận được của bài toán (SP).
Bây giờ, trở lại bài toán quy hoạch tuyến tính dạng chuẩn ban đầu
(LP) : min c
T
x | Ax = b, x ≥ 0}, (15)
trong đó c, x ∈ R
n
, b ∈ R
m
và A ∈ R
m×n
là ma trận có hạng bằng m. Gọi I ⊂ {1, 2, . . . , n}
là tập các chỉ số cột của ma trận A sao cho ma trận A
I
tạo thành từ các cột này là ma trận
vuông cấp m không suy biến. Bằng cách sắp xếp lại các cột của A, ta có thể viết A = (A

I
b + (c
J
− A
T
J
A
−T
I
c
I
)
T
x
J
. Vì c
T
I
A
−1
I
b là
hằng số nên bài toán dạng chuẩn (LP) tương đương với bài toán dạng chính tắc
min{(c
J
− A
T
J
A
−T

n+2
σ(e
n+2
) = e
n+2
. Điều này suy
ra z = e
n+2
là một điểm nằm trên đường trung tâm của Bài toán (SLP) ứng với tham số chắn
t
0
= 1. Bằng cách kí hiệu A := [M, −I], c :=

q
0

, b := −q và x :=

z
σ

, ta có Bài toán (SLP)
tương đương với bài toán dạng chuẩn
(LP) : min{c
T
x | Ax = b, x ≥ 0}. (16)
Bây giờ, ta chứng tỏ x = e
2(n+2)
là điểm nằm trên đường trung tâm của bài toán (LP) với
tham số chắn t

Do đó x s = e
2(n+2)
hay x = e
2(n+2)
là điểm nằm trên đường trung tâm của bài toán (LP)
với tham số chắn t
0
= 1.
Tóm lại, bằng phương pháp tự đối ngẫu, ta đã đưa Bài toán (LP) về Bài toán tương đương
(LP) có ngay một điểm xuất phát x = e
2(n+2)
nằm trên đường trung tâm ứng với tham số chắn
t
0
= 1. Giải Bài toán (LP) bằng phương pháp chắn logarit gốc ta thu được x
J
, từ đó tính được
x
I
= A
−1
I
(b −A
J
x
J
) và suy ra nghiệm của Bài toán (LP).
TÀI LIỆU THAM KHẢO
[1] Bùi Văn Hiếu, Phương pháp điểm trong giải bài toán quy hoạch toán học, Luận văn thạc
sĩ toán học, trường Đại học Khoa học Huế, 2008.