ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
HÀ THỊ MINH TRANG
QUI HOẠCH TOÀN PHƯƠNG
VÀ BÀI TOÁN BÙ TUYẾN TÍNH
Quadratic Programming and the Linear Complementarity Problem
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: GS.TS Trần Vũ Thiệu
Thái Nguyên - 2014
Mục lục
Lời nói đầu
2
Chương 1. Kiến thức chuẩn bị về ma trận
4
1.1
Ma trận xác định dương và nửa xác định dương . . . . . . . . . .
4
1.2
Một số kết quả về ma trận . . . . . . . . . . . . . . . . . . . . . .
6
1.3
P - ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.4
Kiểm tra tính xác định của ma trận . . . . . . . . . . . . . . . . .
12
1.5
Hàm lồi và hàm toàn phương . . . . . . . . . . . . . . . . . . . .
15
Chương 2. Bài toán qui hoạch toàn phương
18
2.1
Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.2
Một số ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3
Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . .
22
2.4
Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
Chương 3. Bài toán bù tuyến tính
30
3.1
Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2
Khái niệm nón bù . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.3
Phương pháp liệt kê giải bài toán . . . . . . . . . . . . . . . . . .
35
3.4
Ứng dụng vào qui hoạch tuyến tính . . . . . . . . . . . . . . . . .
39
3.5
Quan hệ với qui hoạch toàn phương . . . . . . . . . . . . . . . . .
41
Kết luận
43
1
Lời nói đầu
Qui hoạch toàn phương (Quadratic Programming, viết tắt là QP) là bài toán
tìm cực tiểu của một hàm bậc hai với các ràng buộc tuyến tính:
1
min{f (x) = xT Qx + cT x : x ∈ D},
(QP)
2
trong đó Q ∈ S n (ma trận vuông đối xứng), c ∈ Rn và D là tập lồi đa diện cho
trước. Nếu Q xác định dương hay nửa xác định dương thì (QP) là bài toán qui
hoạch toàn phương lồi, còn nếu Q không xác định thì (QP) là bài toán qui hoạch
toàn phương không lồi. Các bài toán qui hoạch toàn phương rất được quan tâm
nghiên cứu, vì nhiều vấn đề nảy sinh trong thực tiễn có thể diễn đạt dưới dạng
bài toán (QP). Qui hoạch toàn phương, nói riêng là qui hoạch tuyến tính (Linear
Programming, viết tắt là LP), liên quan chặt chẽ với bài toán bù tuyến tính.
Bài toán bù tuyến tính (Linear Complementarity Problem, viết tắt là LCP), do
R. W. Cottle và G. B. Dantzig [2] đề xuất năm 1968, là bài toán tổng quát mô tả
thống nhất các bài toán qui hoạch tuyến tính, qui hoạch toàn phương và trò chơi
song ma trận. Các nghiên cứu về bài toán bù tuyến tính đã đem lại nhiều lợi ích,
vượt xa các kết quả cụ thể. Chẳng hạn, thuật toán xoay bù (complementarity pivot
algorithm) lúc đầu được đề xuất cho bài toán bù tuyến tính đã được mở rộng trực
tiếp để tạo ra các thuật toán hiệu quả tính điểm bất động Brouwer và Kakutani,
tính các trạng thái cân bằng kinh tế, giải các hệ phương trình phi tuyến và tìm
nghiệm tối ưu cho bài toán qui hoạch phi tuyến. Tương tự, các phương pháp lặp
được đề xuất cho bài toán bù tuyến tính đã tạo điều kiện tốt cho việc xử lý các
bài toán qui hoạch tuyến tính cỡ rất lớn mà không thể giải quyết bằng phương
pháp đơn hình quen thuộc, do kích thước bài toán quá lớn đã gây ra nhiều khó
khăn trong tính toán số. Vì những lẽ đó, trong lĩnh vực nghiên cứu bài toán bù
tuyến tính người ta đã dành nhiều giải thưởng có giá trị cao cho những ai có
thành tích xuất sắc trong học tập hoặc nghiên cứu về tối ưu hóa hoặc gắn bó với
sự nghiệp ứng dụng tối ưu trong thực tiễn.
2
Mục tiêu của luận văn là tìm hiểu và trình bày khái quát về bài toán qui hoạch
toàn phương (lồi và không lồi ), bài toán bù tuyến tính và phân tích mối quan hệ
giữa bài toán qui hoạch toàn phương và bài toán bù tuyến tính.
Nội dung luận văn được viết thành ba chương:
Chương 1: “Kiến thức chuẩn bị về ma trận” nhắc lại khái niệm về ma trận xác
định dương, nửa xác định dương và tóm tắt một số kết quả lý thuyết bổ ích về
ma trận, cách kiểm tra tính xác định của ma trận. Các ma trận xác định dương
và nửa xác định dương liên quan chặt chẽ với hàm toàn phương và qui hoạch toàn
phương. Các kiến thức này sẽ được sử dụng đến ở các chương sau khi đề cập đến
bài toán qui hoạch toàn phương và bài toán bù tuyến tính.
Chương 2: “Bài toán quy hoạch toàn phương” trình bày nội dung bài toán qui
hoạch toàn phương, một số ứng dụng của bài toán, sự tồn tại nghiệm của bài
toán, đáng chú ý là Định lý Frank - Wolfe (1956) và Định lý Eaves (1971). Cuối
chương trình bày định lý về điều kiện cần tối ưu KKT cho nghiệm cực tiểu địa
phương và định lý điều kiện đủ tối ưu khi hàm mục tiêu f(x) lồi.
Chương 3: “Bài toán bù tuyến tính” giới thiệu khái quát về bài toán bù tuyến
tính và cách tiếp cận tổ hợp giải bài toán dựa trên khái niệm nón bù. Phân tích
mối quan hệ của bài toán bù tuyến tính với qui hoạch tuyến tính và qui hoạch
toàn phương, đặc biệt chỉ ra rằng bài toán qui hoạch tuyến tính và bài toán qui
hoạch toàn phương có thể qui được về bài toán bù tuyến tính.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có
những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để
tác giả tiếp tục hoàn thiện luận văn này.
Trong quá trình học tập và thực hiện luận văn, tôi đã nhận được sự dạy bảo
tận tình của các thầy cô giáo ở trường Đại học Khoa Học - Đại học Thái Nguyên.
Đặc biệt là sự chỉ bảo, hướng dẫn trực tiếp của GS. TS Trần Vũ Thiệu. Nhân dịp
này tôi xin bày tỏ lòng biết ơn sâu sắc tới GS. TS Trần Vũ Thiệu, tới Sở Giáo
dục và Đào tạo Hải Phòng, trường THPT An Dương - Hải Phòng, các thầy cô
giáo và các bạn đồng nghiệp đã giúp đỡ tôi trong suốt thời gian qua.
Thái Nguyên, tháng 4 năm 2014
Tác giả
Hà Thị Minh Trang
Chương 1
Kiến thức chuẩn bị về ma trận
Chương này nhắc lại khái niệm về ma trận xác định dương, nửa xác định dương
và nêu một số kết quả lý thuyết hữu ích về ma trận, cách kiểm tra tính xác định
của ma trận. Các ma trận xác định dương và nửa xác định dương liên quan chặt
chẽ với hàm toàn phương và qui hoạch toàn phương. Nội dung của chương được
tham khảo chủ yếu từ các tài liệu [1], [3] - [5].
1.1.
Ma trận xác định dương và nửa xác định dương
Mục này nhắc lại khái niệm về ma trận xác định dương và nửa xác định dương
thường gặp trong qui hoạch toàn phương và bài toán bù tuyến tính.
Định nghĩa 1.1. Ma trận Q vuông cấp n, đối xứng hay không đối xứng, gọi là
xác định dương (positive definte matrix) nếu xT Qx > 0 với mọi x ∈ Rn , x 6= 0; Q
gọi là nửa xác định dương (positive definte matrix) nếu xT Qx ≥ 0 với x ∈ Rn . Ma
trận Q gọi là xác định âm (negative definite matrix) (nửa xác định âm - negative
semidefinite matrix) nếu - Q là xác định dương (nửa xác định dương). Ma trận
Q gọi là không xác định (indefinite matrix) nếu xT Qx dương với x này và âm với
x khác.
Nếu Q không đối xứng, ta có thể thay nó bằng ma trận đối xứng Q + QT /2
mà không làm thay đổi tính xác định của ma trận, bởi vì xT Q + QT x = 2xT Qx.
Ví dụ 1.1. Cho các ma trận
!
1 −1
A=
,B=
−1 2
D=
−1
1
1
−1
1
−1
−1
!
1
,E=
4
!
,C=
1
0
0 −1
!
−2
1
1
−2
!
Có thể thấy A xác định dương, B nửa xác định dương, C xác định âm, D nửa
xác định âm và E không xác định.
Định nghĩa 1.2. Cho Q = (qij ) là ma trận vuông cấp n. Giả sử {i1 , . . . , ik } ⊆
{1, . . . , n} là tập chỉ số với các phần tử xếp theo thứ tự tăng dần. Xóa tất cả các
phần tử của Q ở hàng i và cột i với i ∈
/ {i1 , . . . , ik }, ta nhận được ma trận con
cấp k × k của Q
qi1 i1 · · · qi1 ik
.
..
...
..
.
qik i1 · · · qik ik
Ma trận này gọi là ma trận con chính (principal submatrix) của Q xác định
bởi tập chỉ số {i1 , . . . , ik }. Bằng cách đặt J = {i1 , . . . , ik }, ta ký hiệu ma trận con
chính là QJJ . Đó là ma trận (qij : i ∈ J, j ∈ J}. Định thức của ma trận con chính
gọi là định thức con chính (principal determinatnt) của Q xác định bởi tập chỉ số
J. Ma trận con chính của Q xác định bởi tập J = ∅ (tập rỗng) là ma trận rỗng
(không chứa phần tử nào). Qui ước định thức của ma trận rỗng bằng 1. Ma trận
con chính của Q xác định bởi tập J = {1, . . . , n} chính là Q. Ma trận con chính
của Q xác định bởi tập J 6= ∅ gọi là ma trận con chính khác rỗng (non-empty
principal submatrix) của Q. Do số tập con khác rỗng của {1, . . . , n} là 2n − 1
nên có tất cả 2n − 1 ma trận con chính khác rỗng của Q. Các ma trận con chính
của Q xác định bởi tập chỉ số J ⊂ {1, . . . , n} gọi là ma trận con chính thực sự
(proper principal submatrix) của Q. Vì thế, mỗi ma trận con chính thực sự của
Q có cấp k ≤ n − 1.
Ví dụ 1.2. Cho
1 2 3
Q=
4
5
6
7 8 9
Ma trận con chính cấp 1, lần lượt tương ứng với J = {1} , {2} và {3}, là các
phần tử đường chéo 1, 5 và 9. Ma trận con chính cấp 2, lần lượt tương ứng với
J = {1, 2} , {1, 3} và {2, 3} là các ma trận 2 × 2 sau đây:
!
!
!
1 2
1 3
5 6
,
và
4 5
7 9
8 9
5
Ma trận con chính cấp 3 × 3, tương ứng với J = {1, 2, 3}, chính là Q. Có tất
cả 23 − 1 = 7 ma trận con chính khác rỗng.
Định nghĩa 1.3. Ma trận con chính cấp k của Q, xác định bởi tập chỉ số J =
{1, . . . , k}, tức là ma trận nhận được từ Q bằng cách bỏ đi n − k hàng và cột
cuối, gọi là ma trận con chính chủ đạo (leading principal submatrix) cấp k của
Q. Định thức của ma trận con chính chủ đạo được gọi là định thức con chính chủ
đạo (leading principal subdeterminant).
Trong Ví dụ 1.2, ma trận con chính chủ đạo cấp 1 là 1 (bỏ đi 2 hàng và 2 cột
cuối). Ma trận con chính chủ đạo cấp 2 là ma trận con chính thứ nhất trong 3
ma trận con chính cấp 2 đã liệt kê và ma trận con chính chủ đạo cấp 3 chính là
Q. Số ma trận con (định thức con) chính chủ đạo của ma trận cấp n × n bằng n.
1.2.
Một số kết quả về ma trận
Mục này nêu một số kết quả hữu ích trong nghiên cứu các ma trận xác định
dương và nửa xác định dương.
Kết quả 1.1. Nếu A = (a11 ) là ma trận cấp 1 × 1 thì A xác định dương khi và
chỉ khi a11 > 0 và A nửa xác định dương khi và chỉ khi a11 ≥ 0.
Chứng minh.Giả sử y = (y1 ) ∈ R1 . Khi đó, yT Ay =a11 y12 . Vì thế yT Ay > 0 với
mọi y ∈ R1 , y 6= 0, khi và chỉ khi a11 > 0, do đó A xác định dương khi và chỉ khi
a11 > 0. Cũng vậy, yT Ay ≥ 0 với mọi y ∈ R1 khi và chỉ khi a11 ≥ 0, do đó A nửa
xác định dương khi và chỉ khi a11 ≥ 0.
Kết quả 1.2. Nếu Q là ma trận xác định dương (đối xứng hay không đối xứng)
thì mọi ma trận con chính của Q đều xác định dương.
Chứng minh. Xét ma trận con chính G xác định bởi tập chỉ số {1, 2}.
!
!
q11 q12
y1
G=
. Giả sử z =
q21 q22
y2
Lấy y = (y1 , y2 , 0, 0, ..., 0)T . Khi đó y T Qy = z T Gz. Tuy nhiên, do Q xác định
dương nên y T Qy > 0 với mọi y 6= 0. Do vậy z T Gz > 0 với mọi z 6= 0. Vì thế G
cũng xác định dương. Dùng lập luận tương tự có thể chứng minh rằng mọi ma
trận con chính của Q cũng xác định dương.
6
Kết quả 1.3. Nếu Q xác định dương thì qii > 0 với mọi i.
Chứng minh suy từ Kết quả 1.2
Kết quả 1.4. Nếu Q là ma trận nửa xác định dương (đối xứng hay không đối
xứng) thì mọi ma trận con chính của Q cũng nửa xác định dương.
Chứng minh tương tự như trong chứng minh Kết quả 1.2.
Kết quả 1.5. Nếu Q là ma trận nửa xác định dương thì qii ≥ 0 với mọi i.
Chứng minh suy từ Kết quả 1.4.
Kết quả 1.6. Cho Q là ma trận nửa xác định dương. Nếu qii = 0 thì qij + qji = 0
với mọi j khi Q không đối xứng và qij = qji = 0 với mọi j khi Q đối xứng.
Chứng minh. Để xác định, giả sử q11 = 0 và giả sử q12 + q21 6= 0. Theo kết quả
1.4, ma trận con chính:
q11 q12
!
=
q21 q22
0
q12
!
q21 q22
phải nửa xác định dương, nghĩa là q22 y22 + (q12 + q21 ) y1 y2 ≥ 0 với mọi y1 , y2 . Do
q12 + q21 6= 0 nên nếu chọn y1 = (−q22 − 1) / (q12 + q21 ) và y2 = 1 thì bất đẳng
thức trước đó trở thành −1 ≥ 0, ta gặp mâu thuẫn. Vậy phải có q12 + q21 = 0.
Trường hợp Q đối xứng thì q12 = q21 . Theo trên q12 + q21 = 0. Từ đó suy ra
2q12 = 2q21 = 0, tức q12 = q21 = 0.
Định nghĩa 1.4. (Bước xoay Gauss - Gaussian Pivot Step). Cho A = (aij ) là
ma trận cấp m × n. Phần tử ở hàng r, cột s là ars . Với ars 6= 0, bước xoay Gauss
biến đổi ma trận A theo công thức:
aij → a0ij = aij − arj × (ais /ars ) với mọi i = r + 1, ... , m và mọi j = 1, ..., n
tức là trừ mỗi hàng i > r một bội số thích hợp (cụ thể là ais /ars ) của hàng r. Có
thể thấy a0is = 0 với mọi i > r. Ở bước xoay này, hàng r gọi là hàng xoay (pivot
row), cột s gọi là cột xoay (pivot column) và ars gọi là phần tử trụ(pivot element).
Bước xoay Gauss này gọi tắt là phép xoay (r, s) trên A và nó chỉ thực hiện được
khi ars 6= 0 (r < m).
Ví dụ 1.3. Phép xoay (1, 2) (a12 = 2 là phần tử trụ) trên ma trận A biến A
thành B:
7
2 2 −2 0
2 2 −2 0
⇒ B = 3 0 4 2 .
A =
4
1
3
2
2 −2 0 1
4 0 −2 1
Kết quả 1.7. Cho D là một ma trận vuông đối xứng cấp n ≥ 2. Giả sử D xác
định dương. Thực hiện phép xoay (1, 1) trên D để biến mọi phần tử ở cột 1, trừ
phần tử đầu, thành 0. Ta nhận được ma trận E. Giả sử E1 là ma trận con nhận
được từ E bằng cách bỏ đi hàng 1 và cột 1. Khi đó, E1 vẫn còn đối xứng và xác
định dương.
Ví dụ 1.4. Với phép xoay (1, 1) trên ma trận D vuông đối xứng xác định dương
(cấp 3) ta nhận được ma trận E1 vuông đối xứng xác định dương (cấp 2):
Kết quả 1.8. Ma trận vuông Q là xác định dương (hay nửa xác định dương) khi
và chỉ khi Q + QT xác định dương (hay nửa xác định dương).
Chứng minh. Suy ra từ đẳng thức xT Q + QT x = 2xT Qx
Kết quả 1.9. Giả sử Q là ma trận vuông cấp n và A là ma trận cấp m × n. Khi
đó ma trận vuông:
E=
Q −AT
A
!
0
cấp (m + n) là nửa xác định dương khi và chỉ khi Q nửa xác định dương.
T
T
Chứng minh. Đặt z = (y1 , ..., yn , t1 , ..., tm ) ∈ Rm+n và y = (y1 , ..., yn ) . Với mọi
z ta có zT Ez = yT Qy. Vì thế zT Ez ≥ 0 với mọi z ∈ Rm+n khi và chỉ khi yT Qy ≥ 0
với mọi y ∈ Rn , nghĩa là E nửa xác định dương khi và chỉ khi Q nửa xác định
dương.
Kết quả 1.10. Nếu B là ma trận vuông (cấp n) không suy biến thì ma trận
D = BT B là ma trận đối xứng và xác định dương.
T
Chứng minh. Tính đối xứng là do DT = BT B = BT B = D. Với mọi y ∈
T
2
Rn , y 6= 0, ta có yT Dy = yT BT B y = (By) By = ||By|| > 0 do By 6= 0(B
không suy biến và y 6= 0 kéo theo By 6= 0). Vì thế D xác định dương.
8
Kết quả 1.11. Nếu A là một ma trận tùy ý (vuông hay chữ nhật) thì AAT và
AT A là đối xứng và nửa xác định dương.
Chứng minh. Tương tự như chứng minh Kết quả 1.10.
Ví dụ 1.5. Với ma trận A cho dưới đây thì AAT xác định dương và AT A nửa
xác định dương
1 0
A=
⇒ AT =
0 1
0 1 −1
1 −1
!
1
2
−1
⇒ AAT =
, AT A =
0
−1 2
1
1 0
1
!
0
1
−1
.
−1 2
1
• Nếu Q xác định dương thì nghịch đảo Q−1 tồn tại và xác định dương
• Sau đây là một số kết quả liên quan đến định thức con chính của các ma
trận xác định dương và nửa xác định dương.
Kết quả 1.12. Cho Q là một ma trận xác định dương, đối xứng hay không đối
xứng. Mọi định thức con chính của Q là số dương. Nói riêng, detQ > 0.
Kết quả 1.13. Cho Q là một ma trận nửa xác định dương, đối xứng hay không
đối xứng. Mọi định thức con chính của Q không âm. Nói riêng, detQ ≥ 0.
Kết quả 1.14. (Tiêu chuẩn Silvester).
a) Để cho ma trận vuông đối xứng Q là xác định dương thì điều kiện cần và đủ là
mọi định thức con chính chủ đạo của Q dương, tức ∆1 > 0, ∆2 > 0, ... , ∆n > 0,
trong đó
q q
11 12
∆1 = |q11 | , ∆2 =
q21 q22
q11 q12
q
21 q22
, ..., ∆n = .
..
..
.
qn1 qn2
···
···
...
···
q1n
q2n
.. .
.
qnn
b) Để cho ma trận vuông đối xứng Q là xác định âm thì điều kiện cần và đủ
là các định thức con chính chủ đạo của Q luân phiên đổi dấu, trong đó định thức
n
đầu tiên có dấu âm, tức là ∆1 < 0, ∆2 > 0, ..., (−1) ∆n > 0.
9
Ví dụ 1.6. Khác với Kết qủa 1.14, một ma trận vuông đối xứng có mọi định
thức con chính chủ đạo không âm, nhưng ma trận đó không nửa xác định dương,
như chỉ ra ở ma trận Q sau đây:
1 0 −1
có ∆1 = 1 > 0, ∆2 =
Q=
0
0
0
−1 0 −1
1 0
0 0
!
= 0 và ∆3 = detQ = 0
T
nhưng Q không nửa xác định dương, do (0, 0, 1) Q(0, 0, 1) = − 1 < 0
Kết quả 1.15. Một ma trận vuông đối xứng là xác định dương khi và chỉ khi mọi
định thức con chính của nó thực sự dương.
Chứng minh. Suy ra từ các Kết quả 1.12 và 1.14.
Nhận xét 1.1. Điều đáng chú ý là nếu Q là ma trận vuông đối xứng cấp n và
nếu n định thức con chính chủ đạo (xem Định nghĩa 1.3) của Q là số dương thì
theo các Kết quả 1.14 và 1.15, mọi định thức con chính của Q cũng là số dương.
Kết quả này có thể sai nếu Q không đối xứng.
Có thể chứng minh kết quả đáng chú ý sau.
Kết quả 1.16. Nếu Q là một ma trận vuông đối xứng nửa xác định dương và
nếu detQ > 0 thì Q xác định dương.
Nhận xét 1.2. Kết quả trên có thể không còn đúng nếu Q không đối xứng. Chẳng
hạn, ma trận Q dưới đây nửa xác định dương (theo Kết quả 1.9) và detQ > 0,
nhưng Q không xác định dương (theo Kết quả 1.3) do Q không đối xứng:
!
1 −1
Q=
, detQ = 1 > 0
1 0
Kết quả 1.17. Cho Q là một ma trận vuông cấp n nửa xác định dương, đối xứng
hay không đối xứng, nếu x̄ ∈ Rn sao cho x̄T Qx̄ = 0 thì Q + QT x̄ = 0
Chứng minh. Đặt D = Q + QT . D là ma trận đối xứng và nửa xác định dương
(theo Kết quả 1.8). Với mọi x ∈ Rn thì xT Dx = 2xT Qx. Vì thế cũng có x̄T Dx̄ = 0.
Ta cần chứng minh rằng Dx̄ = 0. Thật vậy, lấy bất kỳ x ∈ Rn . Với mọi λ ∈ Rn
ta có (x̄ + λx)T D(x̄ + λx) ≥ 0, nghĩa là:
λ2 xT Dx + 2λx̄T Dx̄ ≥ 0
10
do x̄T Dx̄ = 0. Nếu xT Dx = 0 thì ở bất đẳng thức trên cho λ = 1, sau đó - 1 ta suy
ra x̄T Dx = 0. Còn nếu xT Dx 6= 0 thì do D nửa xác định dương nên xT Dx > 0.
Trong trường hợp này, ta kết luận rằng 2x̄T Dx ≥ −λxT Dx với mọi λ > 0 và
2x̄T Dx ≤ −λxT Dx với mọi λ < 0. Chọn λ nhỏ tùy ý về giá trị tuyệt đối, từ các
bất đẳng thức trên ta kết luận rằng trong trường hợp này phải có x̄T Dx = 0.
Vậy, dù xT Dx = 0 hay xT Dx 6= 0 ta đều có xT Dx = 0 với mọi x ∈ Rn . Từ đó
suy ra phải có x̄T D = 0 hay Dx̄ = 0 (nhớ là D đối xứng). Đó là điều cần chứng
minh
1.3.
P - ma trận
Mục này đề cập tới một lớp ma trận đặc biệt thường gặp trong các ứng dụng
có tên gọi là P - ma trận.
Định nghĩa 1.5. Một ma trận vuông, đối xứng hay không đối xứng, gọi là một
P - ma trận (P - matrix) nếu và chỉ nếu mọi định thức con chính của nó đều thực
sự dương.
!
Ví dụ 1.7. Các ma trận sau là P - ma trận:
1 −1
Ma trận đơn vị I,
,
−1 2
1 2
Các ma trận sau không phải là P - ma trận:
!
!
0 1
−1 0
,
,
0 1
0 10
!
!
0 3
1 1
1 1
Kết quả 1.18. Một P - ma trận đối xứng là ma trận xác định dương. Một P ma trận không đối xứng có thể không xác định dương.
Chứng minh. Theo Kết qủa 1.15, ma trận vuông đối xứng là xác định dương
khi và chỉ khi nó là một P - ma trận. Xét ma trận không đối xứng:
!
!
1 0
2 3
B=
, B + BT =
3 1
3 2
Ta thấy mọi định thức con chính của B bằng 1 nên B là một P - ma trận. Tuy
nhiên, vì det B + BT = − 5 < 0 nên theo Kết quả 1.12, B + BT không xác
định dương, do đó theo Kết quả 1.8, B cũng không xác định dương. Thực ra có
T
thể kiểm tra thấy (1, − 1) B(1, − 1) = − 1 < 0.
11
Nhận xét 1.3. Theo Kết quả 1.15 và Định nghĩa 1.5, lớp ma trận xác định dương
là một lớp con của lớp P - ma trận. Theo Kết quả 1.18, khi hạn chế ở ma trận đối
xứng, tính chất của ma trận xác định dương trùng với tính chất của P - ma trận.
Một P - ma trận không đối xứng có thể không xác định dương, như ma trận B
cho trong chứng minh Kết quả 1.18, nhưng nó có thể nửa xác định dương, như
ma trận M̃ (n) cho dưới đây, hoặc không
1
2
M̃ (n) = .
..
2
nửa xác định dương.
0 ··· 0
1 ··· 0
.. . . ..
. .
.
2 ··· 1
là ma trận tam giác dưới với mọi phần tử đường chéo bằng 1 và mọi phần tử dưới
đường chéo bằng 2. Rõ ràng mọi định thức con chính của M̃ (n) bằng 1, do đó
T
M̃ (n) là một P - ma trận. Tuy nhiên, M̃ (n) + M̃ (n) là ma trận với mọi phần
tử bằng 2. Có thể kiểm tra lại rằng đó là ma trận nửa xác định dương, nhưng
không xác định dương.
1.4.
Kiểm tra tính xác định của ma trận
• Có một số qui tắc kiểm tra đơn giản để nhận biết một ma trận vuông đối
xứng cấp n là xác định dương (xác định âm), nửa xác định dương (nửa xác định
âm) hay không xác định. Các qui tắc kiểm tra này chỉ đúng khi ma trận là đối
xứng. Nếu Q = (qij ) không đối xứng thì cần thay Q bởi Q + QT /2, rồi mới
tiến hành kiểm tra.
a) Kiểm tra ma trận xác định dương: Mọi định thức con chính chủ đạo của Q
phải là số dương (Kết quả 1.14). Nói riêng, mọi phần tử đường chéo phải dương
(Kết qủa 1.3), tức qii > 0 với mọi i = 1, ... , n.
b) Kiểm tra ma trận nửa xác định dương: Mọi định thức con chính của Q phải
không âm (suy từ Kết quả 1.13). Nói riêng, mọi phần tử đường chéo phải không
âm (Kết quả 1.5), tức qii ≥ 0 với mọi i = 1, ... , n.
Nhận xét 1.4. a) Cần phân biệt rõ sự khác nhau khi kiểm tra các ma trận xác
định dương và nửa xác định dương: Để ma trận xác định dương, chỉ cần kiểm tra
các định thức con chính chủ đạo dương là đủ, trong khi đó để ma trận nửa xác
định dương ta cần kiểm tra mọi định thức con chính không âm.
12
b) Để chỉ rõ ma trận xác định âm (nửa xác định âm), ta chỉ cần kiểm tra ma
trận đối của ma trận đó là xác định dương (nửa xác định dương).
c) Nếu thấy ma trận vuông đối xứng có (ít nhất) hai phần tử đường chéo trái
dấu nhau thì chắc chắn ma trận đó không xác định.
Qui tắc kiểm tra tính xác định dương (xác định âm) của ma trận đã nêu trên
dựa vào tiêu chuẩn Silvester nêu trong Kết quả 1.14. Tuy nhiên, đây không phải
là một phương pháp hiệu quả (trừ khi n rất nhỏ) bởi vì việc tính các định thức
con chính chủ đạo tốn khá nhiều thời gian và công sức.
• Sau đây là một phương pháp khác kiểm tra tính xác định dương của ma trận
vuông (cấp n) đối xứng Q, chỉ đòi hỏi nhiều nhất n bước xoay Gauss trên Q dọc
theo đường chéo chính. Độ phức tạp tính toán của phương pháp này là O (n3 ) .
Phương pháp dựa trên Kết quả 1.7.
i) Nếu có bất kỳ phần tử đường chéo của Q không dương thì Q không xác định
dương: dừng kiểm tra.
ii) Trong Q, trừ các bội số thích hợp của hàng 1 vào tất cả các hàng (từ 2 tới
n) sao cho mọi phần tử ở cột 1 (từ hàng 2 tới hàng n) biến thành 0. Ta nhận
được ma trận Q1 . Nếu có phần tử đường chéo của Q1 không dương thì Q không
xác định dương: dừng kiểm tra.
iii) Trong Q1 , trừ các bội số thích hợp của hàng 2 vào tất các hàng (từ 3 tới n)
sao cho mọi phần tử ở cột 2 (từ hàng 3 tới hàng n) biến thành 0. Ta nhận được
ma trận Q2 . Nếu có phần tử đường chéo của Q2 không dương thì Q không xác
định dương: dừng kiểm tra.
iv) Tiếp tục làm như trên. Nếu quá trình kiểm tra không dừng ở các ma trận
Q1 , Q2 , ... , Qn−1 thì mọi phần tử đường chéo của Qn−1 đều dương. Ta kết luận
Q xác định dương và quá trình kiểm tra kết thúc.
Ví dụ 1.8. Kiểm tra xem ma trận D sau đây có xác định dương
1 1
0
1 1
0
1
D=
1 2 −1 ⇒ D1 = 0 1 −1 ⇒ D2 = 0
0 −1 2
0 −1 2
0
hay không?
1 0
1 −1
.
0 1
Do D đối xứng và có mọi phần tử đường chéo là số dương nên ta thực hiện
phép xoay (1, 1) trên D, ta nhận được D1 . D1 có mọi phần tử đường chéo dương
nên ta thực hiện phép xoay (2, 2) trên D1 và nhận được D2 . D2 có mọi phần tử
13
đường chéo dương nên ta kết luận D xác định dương và dừng kiểm tra.
Ví dụ 1.9. Kiểm tra xem ma trận B sau đây có xác định dương
1 0 1
1 0 0 2
0 2 2
0 2 0 4
T
B=
⇒ D = (B + B )/2 =
1 2 5
2 4 5 4
1 2 3
0 0 2 3
1 0 1 1
1 0 1 1
0 2 2 2
0 2 2 2
⇒ D1 =
⇒ D2 =
0 0 2 0
0 2 4 2
0 0 0 0
0 2 2 2
không?
1
2
3
3
Do B không đối xứng nên ta thay B bởi D = (B + B T )/2 (đối xứng). D có
mọi phần tử đường chéo dương nên ta thực hiện phép xoay (1, 1) trên D và nhận
được D1 . D1 có mọi phần tử đường chéo dương nên ta thực hiện phép xoay (2, 2)
trên D1 và nhận được D2 . Do D2 có phần tử đường chéo không dương nên ta kết
luận D không xác định dương, do đó B không xác định dương và dừng kiểm tra.
• Bây giờ giả sử Q = (qij ) là một ma trận vuông đối xứng cấp n. Nếu Q có
phần tử đường chéo là số âm thì Q không thể là ma trận nửa xác định dương
(Kết quả 1.5): dừng kiểm tra. Cũng vậy, nếu Q có phần tử đường chéo bằng 0 và
nếu trên hàng hoặc cột chứa phần tử 0 này có phần tử khác 0 thì Q không thể là
ma trận nửa xác định dương (Kết quả 1.6): dừng kiểm tra.
Nếu chưa dừng kiểm tra thì xét phần tử đường chéo khác 0 đầu tiên của Q.
Giả sử phần tử này nằm ở hàng r, cột r. Gọi ma trận Q lúc này là Qr . Nếu Qr
là ma trận tam giác trên và mọi phần tử đường chéo là số dương thì Q xác định
dương, còn nếu mọi phần tử đường chéo không âm thì Q nửa xác định dương.
Trái lại, trong Qr trừ các bội số thích hợp của hàng r vào các hàng (từ r + 1
trở đi) sao cho các phần tử ở cột r và hàng từ r + 1 trở đi biến thành 0. Xóa hàng
r và cột r khỏi ma trận nhận được sau biến đổi, gọi ma trận con còn lại là Er .
Nếu Er có phần tử đường chéo âm thì Q không nửa xác định dương: dừng kiểm
tra. Cũng vậy, nếu Er có phần tử đường chéo bằng 0 và trên hàng hoặc cột chứa
phần tử 0 này có phần tử khác 0 thì Q không nửa xác định dương: dừng kiểm tra.
Trái lại, trong Qr xét phần tử đường chéo khác 0 đầu tiên tiếp theo (nếu còn).
Giả sử phần tử này nằm ở hàng s, cột s. Gọi ma trận Qr lúc này là Qs . Tiếp tục
14
xét Qs như đã xét ở trên đối với Qr , v.v ...
Cuối cùng, nếu mọi phần tử đường chéo của ma trận tam giác trên Qn−1 là các
số không âm thì kết luận Q nửa xác định dương: kết thúc quá trình kiểm tra.
Ví dụ 1.10. Kiểm tra xem ma trận Q sau có nửa xác định dương không?
Q đối xứng và mọi phần tử trên đường chéo đều dương. Thực hiện phép xoay
(1, 1) ta nhận được Q1 . Xóa khỏi Q1 hàng và cột đầu, ma trận còn lại E1 có phần
tử đường chéo thứ nhất là 0, nhưng cả hàng và cột đầu của E1 đều là véctơ 0.
Thực hiện phép xoay trên Q1 theo phần tử đường chéo khác 0 tiếp theo 3 ta được
Q2 . Q2 là ma trận tam giác trên với mọi phần tử đường chéo không âm, vì thế
ta kết luận Q là ma trận nửa xác định dương, nhưng không là ma trận xác định
dương.
Ví dụ 1.11. Kiểm tra xem ma trận B, D sau có nửa xác
2 4 0
1 −1 4
B=
0
−1 2
,D = 4 0 5
0 5 3
4
0 −3
định dương không?
.
B và D là các ma trận đối xứng. B có phần tử đường chéo là số âm, còn D có
phần tử đường chéo bằng 0 và trên hàng (cột) chứa phần tử 0 này có các phần
tử khác 0. Vì thế, cả B và D đều không nửa xác định dương.
1.5.
Hàm lồi và hàm toàn phương
Định nghĩa 1.6. a) Hàm f : C → [−∞, +∞] xác định trên một tập lồi C ⊆ Rn gọi
là một hàm lồi trên C nếu với mọi x1 , x2 ∈ C và mọi λ ∈ [0, 1] ta có
f[λx1 + (1 − λ)x2 ] ≤ λf x1 + (1 − λ)f x2
15
mỗi khi vế phải xác định, nghĩa là hệ thức trên cần được thỏa mãn trừ khi
f (x1 ) = −f (x2 ) = ±∞ (vì biểu thức +∞ − ∞ không có nghĩa).
b) Hàm f được gọi là hàm lồi chặt trên C nếu với mọi x1 , x2 ∈ C, x1 6= x2 , và
mọi số thực λ ∈ (0, 1) ta có
f[λx1 + (1 − λ)x2 ] < λf x1 + (1 − λ)f x2
Hiển nhiên, một hàm lồi chặt là hàm lồi, nhưng điều ngược lại không đúng.
Định nghĩa 1.7. a) Hàm f gọi là hàm lõm (hàm lõm chặt) trên C nếu -f là hàm
lồi (hàm lồi chặt) trên C.
b) Hàm f gọi là hàm tuyến tính afin (hay đơn giản là hàm afin) trên C nếu f
hữu hạn và vừa lồi, vừa lõm trên C.
Một hàm afin trên Rn có dạng f (x) = aT x + α với a ∈ Rn , α ∈ R bởi vì với
mọi x1 , x2 ∈ Rn và mọi λ ∈ [0, 1] ta có
f[λx1 + (1 − λ)x2 ] = λf x1 + (1 − λ)f x2
Hàm tuyến tính là trường hợp riêng của hàm afin, khi α = 0. Tuy nhiên, hàm
afin (nói riêng, hàm tuyến tính) không lồi chặt hay lõm chặt.
Nhận xét 1.5. Hàm lồi f : C → [−∞, +∞] có thể được mở rộng thành hàm lồi
xác định trên toàn không gian Rn bằng cách đặt f (x) = + ∞ với mọi x ∈
/ C. Vì
vậy để đơn giản, ta thường xét hàm lồi trên toàn Rn .
Hàm lồi, hàm lõm có các tính chất quan trọng được nêu trong 2 định lý sau.
Định lý 1.1. Mọi điểm cực tiểu địa phương của hàm lồi f trên tập lồi C khác
rỗng đều là điểm cực tiểu toàn cục. Tập Argmin
x∈C f
(x) là tập con lồi của C.
Tương tự, mọi điểm cực đại địa phương của hàm lõm f trên tập lồi C khác rỗng
đều là điểm cực đại toàn cục. Tập Argmax
x∈C f
(x) là tập con lồi của C.
Định lý 1.2. Một hàm lồi chặt f trên tập lồi C có nhiều nhất một điểm cực tiểu
trên C, nghĩa là tập Argmin
x∈C f
(x) gồm nhiều nhất một phần tử. Tương tự,
một hàm lõm chặt f trên tập lồi C có nhiều nhất một điểm cực đại trên C, nghĩa
là tập các điểm cực đại Argmax
x∈C f
(x)gồm không quá một phần tử.
Định nghĩa 1.8. Hàm toàn phương (quadratic function), còn gọi là hàm bậc
hai là hàm có dạng q(x) =
1 T
x Qx
2
+ pT x + c, trong đó Q ∈ Rn×n đối xứng,
16
p ∈ Rn , c ∈ R, q(x) xác định trên toàn Rn . Lưu ý: khi Q = 0 (ma trận không)
thì q(x) là hàm afin.
Bây giờ ta xét đến tính lồi (lồi chặt), lõm (lõm chặt) của hàm toàn phương.
Ta có sự kiện quan trọng sau.
Định lý 1.3. Hàm toàn phương q(x) = 12 xT Qx + pT x + c lồi (lồi chặt) trên Rn
khi và chỉ khi ma trận Q nửa xác định dương (xác định dương) và q lõm (lõm
chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định âm (xác định âm).
Ví dụ 1.12. Xét hàm bậc hai q(x) = 12 (x21 − 2x1 x2 + 3x22 ) + x1 − 2x2 . Ta thấy
!
!
1 −1
1
Q=
,p =
−1 3
−2
Do ma trận Q xác định dương nên hàm q(x) đã cho là lồi chặt trên R2 .
Tóm lại, chương này đã nhắc lại khái niệm và kết qủa cơ bản về các ma trận
xác định dương và nửa xác định dương. Hàm toàn phương và qui hoạch toàn
phương liên quan mật thiết với ma trận xác định dương và nửa xác định dương.
Đáng chú ý là hàm toàn phương là lồi (lồi chặt) khi và chỉ khi ma trân tương ứng
là nửa xác định dương (xác định dương) và là lõm (lõm chặt) khi và chỉ khi ma
trận tương ứng là nửa xác định âm (xác định âm).
17
Chương 2
Bài toán qui hoạch toàn phương
Chương này trình bày một số kiến thức cơ bản về bài toán qui hoạch toàn
phương: nội dung và ý nghĩa bài toán, sự tồn tại nghiệm và điều kiện tối ưu cho
nghiệm bài toán. Nội dung của chương được tham khảo từ tài liệu [3] - [7].
2.1.
Phát biểu bài toán
Qui hoạch toàn phương (Quadratic Programming, viết tắt là QP) là bài toán
tối ưu với hàm mục tiêu bậc hai và với các ràng buộc đẳng thức hay bất đẳng
thức tuyến tính. Mô hình toán học của qui hoạch toàn phương có dạng:
1
(QP)
f (x) = xT Qx + pT x + c → min
2
với điều kiện:
(2.1)
aTi x = bi , i = 1, 2, . . . , k,
(2.2)
aTi x 6 bi , i = k + 1, . . . , m,
(2.3)
trong đó Q là ma trận đối xứng cấp n × n; p, ai ∈ Rn , bi , c ∈ R, k, m là các số
nguyên không âm (0 6 k 6 m). Ký hiệu tập ràng buộc (hay miền chấp nhận
được) của bài toán (2.1) - (2.3) là
D = {x ∈ Rn : aTi x = bi , i = 1, 2, . . . , k, aTi x 6 bi , i = k + 1, . . . , m}.
Nếu ma trận Q nửa xác định dương thì (QP) là bài toán qui hoạch toàn phương
lồi (Convex QP) và nghiệm cực tiểu địa phương x∗ là nghiệm cực tiểu toàn cục.
Nếu Q xác định dương thì (QP) là bài toán qui hoạch toàn phương lồi chặt
(Strictly Convex QP) và x∗ là nghiệm cực tiểu toàn cục duy nhất. Nếu Q là
ma trận không xác định thì (QP) là bài toán qui hoạch toàn phương không lồi
(Nonconvex QP) rất đáng được chú ý.
18
Trường hợp hàm mục tiêu và các hàm ràng buộc bất đẳng thức đều là hàm lồi
bậc hai, ta có bài toán qui hoạch toàn phương lồi với các ràng buộc toàn phương
lồi (Quadratically Constrained Quadratic Program, viết tắt là QCQP):
1
f (x) = xT Q0 x + pT0 x + c0 → min
(QCQP)
2
với các điều kiện
1
gi (x) = xT Qi x + pTi x + ci 6 0, i = 1, . . . , m, Ax = b,
2
n
trong đó Qi ∈ S+ (nửa xác định dương), pi ∈ Rn , A ∈ Rm×n , b ∈ Rm , ci ∈ R,
(i = 0, 1, . . . , m). Bài toán (QCQP) tìm cực tiểu hàm bậc hai lồi trên miền chấp
nhận được là giao của các ellipsoid khi mọi Qi > 0 (xác định dương).
Qui hoạch tuyến tính là trường hợp riêng của qui hoạch toàn phương và qui
hoạch toàn phương lồi (khi Q = 0). Qui hoạch toàn phương lồi lại là trường hợp
riêng của qui hoạch toàn phương lồi với các ràng buộc toàn phương lồi (khi Qi = 0
với mọi i = 1, . . . , m).
Một trường hợp riêng quan trọng của bài toán qui hoạch toàn phương (QP)
là khi nó chỉ có các ràng buộc về dấu đối với các biến. Khi đó, bài toán (QP) có
dạng đơn giản
1
f (x) = xT Qx + pT x + c → min
2
với điều kiện x > 0.
Nếu Q nửa xác định dương thì bài toán dạng đơn giản này hoàn toàn tương
đương với bài toán bù tuyến tính LCP (p, Q) xét ở chương sau. Có nhiều ứng
dụng trong công nghiệp và vật lý dẫn tới mô hình qui hoạch toàn phương lồi dạng
đặc biệt trên. Các ứng dụng đó bao gồm bài toán tiếp xúc, bài toán chất lỏng
nhớt, bài toán vật cản, bài toán xoắn chất dẻo đàn hồi cũng như nhiều bài toán
biên tự do khác.
2.2.
Một số ứng dụng
Sau đây là một số ví dụ về bài toán qui hoạch toàn phương.
A. Hồi qui tuyến tính
Một trong những bài toán thống kê thường gặp là bài toán hồi qui tuyến tính:
Tìm đường thẳng xấp xỉ tốt nhất dãy số liệu thống kê cho bởi n cặp điểm quan
sát: (x1 , y1 ), (x2 , y2 ), . . . , (xn , yn ).
19
- Xem thêm -