Điều kiện cần và đủ cực trị cho bài toán quy hoạch toàn phương trên tập lồi đa diện
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (481.87 KB, 57 trang )
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn sâu sắc tới thầy ThS. Nguyễn Quốc Tuấn,
giảng viên khoa Toán trường Đại học Sư phạm Hà Nội 2, đã tận tình hướng
dẫn, giúp đỡ để em hoàn thành khóa luận này.
Trong quá trình học tập, đặc biệt là trong suốt quá trình làm khóa luận
em đã nhận được sự dạy dỗ ân cần cũng như những động viên, chỉ bảo, tạo
điều kiện của các thầy cô giáo tham gia giảng dạy, công tác tại trường Đại học
Sư phạm Hà Nội 2. Qua đây, em xin được gửi lời cảm ơn tới các thầy cô giáo
trong tổ Giải tích, khoa Toán trường Đại học Sư phạm Hà Nội 2, cùng các
thầy cô giáo giảng dạy khóa học.
Một lần nữa em xin chân thành cảm ơn!
Hà Nội, Ngày 04 tháng 05 năm 2012
Sinh viên
Hoàng Thị Hồng Hạnh
1
LỜI CAM ĐOAN
Dưới sự hướng dẫn của thầy ThS. Nguyễn Quốc Tuấn khóa luận tốt
nghiệp đại học chuyên ngành Toán với đề tài “Điều kiện cần và đủ cực trị cho
bài toán quy hoạch toàn phương trên tập lồi đa diện” được hoàn thành bởi
chính sự nhận thức của bản thân, không trùng với bất cứ khóa luận khác.
Trong quá trình nghiên cứu thực hiện khóa luận, em đã kế thừa những
thành tựu của các nhà khoa học với lòng trân trọng và biết ơn. Một số kết quả
em đã đưa ra dựa trên những thành tựu khoa học này.
Hà Nội, Ngày 04 tháng 05 năm 2012
Sinh viên
Hoàng Thị Hồng Hạnh
2
MỤC LỤC
Trang
Mở đầu...........................................................................................................1
Chương 1 Bài toán quy hoạch toàn phương....................................................4
1.1. Bài toán quy hoạch toán học .............................................................4
1.2. Bài toán toàn phương ......................................................................14
Chương 2 Điều kiện tối ưu cần và đủ cực trị cho bài toán quy hoạch toàn
phương ..........................................................................................................22
2.1. Điều kiện cực trị đầu tiên ................................................................22
2.2. Điều kiện cực trị thứ hai..................................................................33
Kết luận........................................................................................................55
Tài liệu tham khảo.......................................................................................56
3
LỜI MỞ ĐẦU
Hiện nay, tối ưu hóa đã trở thành một lĩnh vực rất phát triển, góp phần
quan trọng trong việc ứng dụng khoa học công nghệ vào cuộc sống và sản xuất.
Từ thế kỉ XVIII, một hướng của Giải tích toán học, gọi là Phép tính
biến phân, chuyên nghiên cứu các bài toán cực trị với hàm mục tiêu là phiếm
hàm tích phân được phát triển mạnh mẽ và trở thành ngôn ngữ của khoa học
tự nhiên. Vào những năm cuối thập niên 30 40 của thế kỉ XX, nhu cầu cấp
bách của kinh tế, kĩ thuật đã thúc đẩy hình thành một lý thuyết mới đó là lý
thuyết tối ưu. Có thể nói, lý thuyết tối ưu bắt đầu từ quy hoạch tuyến tính, tiếp
đó là quy hoạch lồi. Đối tượng nghiên cứu của những lý thuyết đó ngày càng
mở rộng, hình thành những hướng khác nhau của lý thuyết tối ưu.
Bài toán tối ưu được phát biểu như sau: “Cho hàm mục tiêu f và
n
là miền ràng buộc. Tìm x sao cho f x nhận giá trị cực tiểu
(trong trường hợp muốn tìm giá trị cực đại thì có thể thay f x f x )”.
Các bài toán tối ưu còn được gọi là các bài toán quy hoạch toán học,
được chia ra thành các lớp sau đây:
Bài toán quy hoạch tuyến tính;
Bài toán tối ưu phi tuyến hay còn gọi là bài toán quy hoạch phi
tuyến, bao gồm cả bài toán quy hoạch lồi và bài toán quy hoạch toàn phương;
Bài toán tối ưu rời rạc, bài toán tối ưu nguyên và hỗn hợp nguyên;
Bài toán quy hoạch động;
Bài toán quy hoạch đa mục tiêu;
Bài toán quy hoạch ngẫu nhiên...
4
Trong thực tế, bài toán quy hoạch tuyến tính với hàm mục tiêu và các
ràng buộc tuyến tính có một số lượng lớn các ứng dụng. Bài toán mà hàm
mục tiêu của chúng không ở dạng tuyến tính mà có dạng bậc hai được gọi là
bài toán quy hoạch toàn phương. Với bài toán này thì các phương pháp giải có
mối quan hệ tới các mở rộng của bài toán quy hoạch tuyến tính.
Điều kiện tối ưu đóng một vai trò quan trọng trong lý thuyết tối ưu hóa.
Năm 1965, A. Ya. Dubovitskii và A. A. Milyutin đã đưa ra lý thuyết các điều
kiện cần tối ưu dưới ngôn ngữ giải tích hàm và cho ta phương pháp giải tích
hàm hiệu quả để nghiên cứu các bài toán tối ưu và điều khiển.
Ngày nay, điều kiện cần và đủ cực trị đầu tiên cho bài toán quy hoạch
toàn phương (không lồi) trong định lý 2.1 đã được chứng minh trong nhiều
sách. Nó được xem như là một mở rộng tự nhiên của định lý Fermat.
McCormick (1967) là người đầu tiên đặt nền móng cho điều kiện cần và đủ
cực trị thứ hai của bài toán toàn phương (xem [8]). Sau đó, Majthay (1971),
Mangasarian (1980) và Contesse (1980) đã từng bước hoàn thiện chứng minh
điều kiện cần và đủ cực trị thứ hai (định lý 2.4 2.5 ) cho bài toán quy hoạch
toàn phương.
Là một sinh viên sư phạm chuyên ngành Toán, tôi mong muốn được
tìm hiểu sâu hơn về lý thuyết tối ưu nói chung cũng như quy hoạch toàn
phương nói riêng. Đặc biệt, dưới sự gợi mở, hướng dẫn, chỉ bảo tận tình của
thầy ThS. Nguyễn Quốc Tuấn, tôi đã chọn đề tài
“Điều kiện cần và đủ cực trị cho bài toán quy hoạch toàn phương
trên tập lồi đa diện”.
Khóa luận tập trung làm rõ một số nội dung liên quan đến bài toán quy
hoạch toán học, quy hoạch toàn phương, điều kiện cần và đủ cực trị cho bài
5
toán quy hoạch toàn phương trên tập lồi đa diện. Ngoài phần mở đầu, kết
luận, tài liệu tham khảo, khóa luận gồm 2 chương:
Chương 1. Bài toán quy hoạch toàn phương
Chương 2. Điều kiện cần và đủ cực trị cho bài toán quy hoạch toàn phương
Do thời gian nghiên cứu có hạn và khả năng của bản thân còn hạn chế
nên khóa luận này mới chỉ dừng lại ở việc tìm hiểu, trình bày các nội dung
chính theo chủ đề đặt ra. Trong quá trình viết khóa luận cũng như trong quá
trình xử lý văn bản, đề tài không tránh khỏi những thiếu sót nhất định. Vì vậy,
tôi rất mong được sự đóng góp ý kiến của quý thầy cô và bạn đọc để đề tài
được hoàn thiện hơn.
Chương 1
6
Bài toán quy hoạch toàn phương
Bài toán quy hoạch toàn phương là một phần của bài toán học quy
hoạch phi tuyến. Chương này, trình bày một số nội dung liên quan đến quy
hoạch toán học, bài toán quy hoạch toàn phương. Chẳng hạn, khái niệm bài
toán quy hoạch toán học, nghiệm toàn cục, nghiệm địa phương, bài toán quy
hoạch toàn phương, ma trận xác định dương (tương ứng, xác định âm), ma
trận xác định nửa dương (tương ứng, xác định nửa âm)…
1.1. Bài toán quy hoạch toán học
Trong phần này, ta ký hiệu
thẳng thực mở rộng,
n
,
là đường
là không gian Euclid n chiều với chuẩn
1/2
n
x xi2 ,
i 1
n
với mọi x x1 , x2 ,..., xn
và tích vô hướng
n
x, y xi yi xT y ,
i 1
với mọi x x1 , x2 ,..., xn , y y1 , y2 ,..., yn
n
. Trong đó, xT là ma trận
chuyển vị của ma trận x . Trong tính toán ma trận, vector được hiểu như là
một ma trận cột những số thực.
Hình cầu mở trong
n
có tâm tại x với bán kính 0 được ký hiệu là
B x, . Hình cầu đóng tương ứng được ký hiệu là B x, .
7
Vì vậy, B x, y
n
: y x , B x, y
n
: y x .
Hình cầu đóng đơn vị B 0,1 được kí hiệu là B n . Cho một tập
n
, các
kí hiệu int , và bd được sử dụng tương ứng để biểu thị phần trong của
, bao đóng của và biên của .
Do đó, x
n
trong
: 0, B x, là tập đóng nhỏ nhất
chứa và int x : 0, B x, là tập con mở lớn
nhất trong
n
n
, bd \ int .
n
Ta nói, U
là một lân cận của x
n
nếu tồn tại 0 sao cho
B x, U .
Nón tiếp tuyến T x của tại x được định nghĩa bởi công thức
T x t x x : x , t 0.
Cho hàm f :
n
n
là một hàm khả vi liên tục cấp hai trên tập
, điểm x , v
n
. Khi đó, ta ký hiệu f x là đạo hàm của hàm
f tại điểm x , ký hiệu 2 f x là đạo hàm cấp hai (ma trận Hessian) của
hàm f tại điểm x và ký hiệu f x , v là đạo hàm theo hướng v của hàm f
tại điểm x . Ta có,
f x , v lim
t 0
f x tv f x
f x , v .
t
Ký hiệu, f x là dưới vi phân của hàm f tại điểm x , ta có
f x x*
n
: f x f x x* , x x , x
n
.
8
Trong thực tế và lý thuyết, nhiều bài toán được mô tả dưới dạng
min f x , x , P
trong đó, f :
n
là một hàm cho trước,
n
là một tập hợp con xác
định. Bài toán P có thể viết lại dưới dạng
min f ( x) : x .
Định nghĩa 1.1. Bài toán P được gọi là một bài toán quy hoạch toán học.
Hàm f gọi là hàm mục tiêu và ∆ là tập ràng buộc (hay miền chấp nhận
được) của bài toán P . Các phần tử của tập ràng buộc ∆ được gọi là các
vector chấp nhận được của bài toán P .
Nếu
n
thì ta nói bài toán P là một bài toán không có ràng buộc,
ngược lại, bài toán P là bài toán có ràng buộc.
Ví dụ 1.1. Bài toán min f x cx1 cx2 ... cn xn , với điều kiện ràng buộc
a11 x1 a12 x2 ... a1n xn b1
a x a x ... a x b
2n n
2
21 1 22 2
............................................
a x a x ... a x b
mn n
m
m1 1 m 2 2
x1 , x2 ,..., xn 0.
Ví dụ 1.2. Bài toán min f x 3x1 2 x2 với điều kiện ràng buộc
9
x1 2 x2 4
x x 3
1 2
2
x
x
4
1
2
x1 , x2 0.
Định nghĩa 1.2. Vector chấp nhận được x của bài toán P gọi là
nghiệm (nghiệm toàn cục) của bài toán P nếu f x và f ( x) f x ,
với mọi x .
Ta nói, x là nghiệm tối ưu địa phương của bài toán P nếu
f x và tồn tại một lân cận U của x sao cho
f x f x , x U . (1.1)
Tập các nghiệm tối ưu toàn cục của bài toán P , kí hiệu là Sol P
(hoặc Sol f ). Tập các nghiệm tối ưu địa phương của bài toán P , kí hiệu
là loc P (hoặc loc f ). Hai bài toán tối ưu gọi là tương đương nếu tập
nghiệm của chúng trùng nhau.
Định nghĩa 1.3. Giá trị tối ưu ( P) của P được xác định bởi
( P) inf f ( x) : x .
(1.2)
Nếu thì qui ước ( P) .
Nhận xét 1.1. Hiển nhiên, ta có Sol P loc P , vì theo định nghĩa
Sol ( P) x : f ( x) ; f ( x) ( P) loc p .
10
Ví dụ 1.3. Xét bài toán P với f x cos x, x
. Khi đó, min f x ,
với mọi x , có vô số nghiệm tối ưu toàn cục, cụ thể
Sol f x : cos x 1 x 2k 1 , k
và f x 1 .
Ví dụ 1.4 . Xét bài toán P với f x min f1 x , f 2 x , f1 x x 2,
3
f 2 x x , x , 0,2
2
. Ta có,
Sol f x 2 , loc f x 0,2 .
f
f x x
.
3
2
2
1,5
1,5
O
x
2
f x x 2
Hình 1.1.
Nhận xét 1.2. Nói chung, loc( P ) \ Sol ( P ) .
Ví dụ 1.5. Cho bài toán P với hàm f ( x) 2 x3 3x 2 1 và tập 1,
thì x 1 là nghiệm địa phương nhưng không phải là nghiệm toàn cục của bài
toán P , vì Sol P 1 .
f x
2
1
1
1 O 1
2
2
x
11
Hình 1.2
Ví dụ 1.6. Xét bài toán P với hàm
mục tiêu f x x1 và tập ràng buộc
x
2
: x12 x22 4, x12 1 . Hàm
f có nghiệm toàn cục là x 2,0
và có vô số nghiệm địa phương, đó là
cả đoạn thẳng nối x 1, 3 và
x 1, 3 .
Giá
trị
tối
ưu
f x 2 .
Hình 1.3
Ví dụ 1.7. Với trường hợp
loc( P ) \ Sol ( P ) , chẳng hạn cho bài toán P với f x x 2 thì x 0 là
nghiệm địa phương cũng là nghiệm toàn cục.
f x
2
1
1
O 1
2
2
x
12
Hình 1.4
Nhận xét 1.3. Thay bài toán P ở trên bằng bài toán tìm giá trị lớn nhất sau
max f ( x) , x . P1
Nghiệm x được gọi là nghiệm (nghiệm tối ưu toàn cục) của P1 nếu
f x và f x f x , với mọi x .
Ta nói, x là nghiệm địa phương của P1 nếu f x và tồn
tại một lân cận U của x sao cho f x f x , với mọi x U .
Trong hình 1.5 các điểm
A, C , E là nghiệm cực tiểu địa phương;
B, D là nghiệm cực đại địa phương;
C là nghiệm cực tiểu toàn cục;
F là nghiệm cực đại toàn cục.
f x
F
D
E
O
B
13
x
Hình 1.5
Rõ ràng, x là nghiệm tối ưu (tương ứng, nghiệm tối ưu địa phương)
của bài toán P1 khi và chỉ khi x là nghiệm tối ưu (tương ứng, nghiệm tối ưu
địa phương) của bài toàn tìm giá trị nhỏ nhất sau
min( f ( x)) , x .
Do vậy, bất kì bài toán tìm giá trị lớn nhất dưới dạng P1 đều có thể
đưa về bài toán tìm giá trị nhỏ nhất dưới dạng P . Chẳng hạn, ta xét bài toán
tìm giá trị lớn nhất dạng
max f x 3x1 x2 x32 ,
với các ràng buộc
x1 x2 x3 0
2
x1 2 x2 x3 0.
Ta có, bài toán tìm giá trị nhỏ nhất dạng
min f x 3 x1 x2 x32 ,
14
với các ràng buộc
x1 x2 x3 0
2
x1 2 x2 x3 0.
Nhận xét 1.4. Trong trường hợp ( P) là một số thực hữu hạn, vẫn có thể xảy
ra khả năng Sol ( P) .
Ví dụ 1.8. Xét bài toán P với 1,
1
khi
f ( x) x
khi
và hàm
x0
x 0,
thì P 0 trong khi Sol ( P) .
Thật vậy, giả sử Sol P thì suy ra tồn tại x0 Sol P sao cho
P khi
f x0
khi
Mà P 0 , suy ra f x0
1
0 , mâu thuẫn. Vì vậy, Sol ( P) .
x0
f x
f x x
x 0,
x 0.
f x
f x
1
x
x
O
x
O
15
Hình 1.6
Ví dụ 1.9. Cho bài toán min f x x22 2 x2 : x x1 , x2 , x1 0, x2 0 .
Ta có, Sol f x , loc f x x
2
: x1 0, x2 0 .
Có những cách khác nhau để phân loại bài toán quy hoạch toán học:
Lồi với lõm.
Trơn với không trơn.
Tuyến tính với phi tuyến tính.
1.2. Bài toán toàn phương
Định nghĩa 1.4. Chúng ta nói rằng, hàm f :
phương nếu tồn tại một ma trận vuông D
nn
n
là một hàm toàn
cấp n , một vector c
n
và
một số thực thỏa mãn
f ( x)
1 T
1
x Dx cT x x, Dx c, x , x
2
2
n
. (1.3)
d11 ... d1n
c1
x1
Nếu D ... ... ... ; c ... ; x ... thì (1.3) có nghĩa là
d
c
x
n1 ... d nn
n
n
n
1 n n
f ( x) dij xi x j ci xi .
2 j 1 i 1
i 1
16
Từ xT Dx
1 T
x D DT x , với mọi x
2
n
D trong công thức (1.3) bằng ma trận đối xứng
, ta có thể thay thế ma trận
1
D DT . Do đó, chúng ta
2
giả thiết rằng các ma trận vuông của hàm toàn phương là đối xứng. Tập các
ma trận đối xứng cấp n n được kí hiệu là
nn
S
.
Định nghĩa 1.5. Bài toán P được gọi là bài toán quy hoạch toàn phương
trên tập lồi đa diện nếu hàm f là một hàm toàn phương và là một tập lồi
đa diện.
Trong (1.3), nếu ma trận D là ma trận không thì hàm f là một hàm
afin. Do đó, việc nghiên cứu bài toán tuyến tính là một phần của bài toán toàn
phương. Nói chung, bài toán toàn phương là bài toán không lồi.
Rõ ràng, nếu xóa hằng số của f trong công thức (1.3) thì chúng
không làm thay đổi các giả thiết của bài toán min f ( x) : x trong đó
n
là một tập lồi đa diện.
Vì vậy, để đơn giản hóa hàm mục tiêu, chúng ta thay (1.3) bằng công thức
f ( x)
1 T
x Dx cT x .
2
Vẫn dùng các thuật ngữ trong quy hoạch tuyến tính, chúng ta gọi các
dạng của bài toán toàn phương
1
min xT Dx cT x : x
2
n
, Ax b ,
17
1
min xT Dx cT x : x
2
1
min xT Dx cT x : x
2
n
n
, Ax b, x 0 ,
, Ax b, Cx d .
lần lượt là dạng chuẩn tắc, dạng chính tắc và tổng quát. Trong đó,
D là ma trận vuông đối xứng cấp n ;
A là ma trận cấp m n ;
C là ma trận cấp s n ;
c là vector n chiều mô tả hệ số của hàm mục tiêu;
x là vector biến quyết định;
b là vector m chiều;
d là vector s chiều.
Các định nghĩa trên của quy hoạch toàn phương được chấp nhận bởi vì
quy hoạch tuyến tính là dạng đặc biệt của quy hoạch toàn phương (với D
nhận ma trận không).
Định nghĩa 1.6. Một ma trận vuông D
nn
cấp n được gọi là xác định
dương (tương ứng, xác định âm) nếu vT Dv 0, (tương ứng, vT Dv 0 ), với
mọi v
n
\ 0 . Nếu vT Dv 0 , (tương ứng, vT Dv 0 ) với mọi v
n
thì ma
trận D được gọi là nửa xác định dương (tương ứng, nửa xác định âm).
18
Mệnh đề 1.1. Cho f ( x)
1 T
x Dx cT x , trong đó D
2
nn
S
, c
n
và
. Nếu D là một ma trận nửa xác định dương thì f là một hàm lồi.
Chứng minh. Ta biết, f :
n
, x cT x là hàm lồi và tổng của hai
hàm lồi là một hàm lồi. Suy ra, ta cần chứng minh f1 ( x) :
1 T
x Dx là hàm lồi.
2
Khi D là một ma trận nửa xác định dương, đối với mỗi u
v
n
n
và
ta có,
T
T
T
0 u v D(u v) u v Du u v Dv
uT Du vT Du u T Dv vT Dv
uT Du 2vT Du vT Dv.
Điều này có nghĩa là vT Dv uT Du 2vT D(u v) . (1.4)
Cho x, y bất kỳ, với x, y
n
và t 0,1 , đặt z tx 1 t y . Khi đó,
áp dụng (1.4) chúng ta có
z T Dz yT Dy 2 zT D( y z ),
z T Dz xT Dx 2 z T D( x z ).
Vì y z t y x và x z 1 t x y , từ hai bất đẳng thức cuối
cùng, suy ra z T Dz (1 t ) zT Dz tzT Dz (1 t ) yT Dy txT Dx .
Do đó, f1 (tx (1 t ) y ) f1 ( z ) tf1 ( x ) (1 t ) f ( y ) .
Vì vậy, f1 là một hàm lồi.
19
Nếu D là ma trận nửa xác định âm, thì hàm f được cho bởi 1.3 là
lõm, tức là với bất kỳ x, y
n
và t 0,1 , đặt z tx 1 t y ta có,
z T Dz (1 t ) z T Dz tz T Dz (1 t ) y T Dy txT Dx , suy ra,
f (tx (1 t ) y ) tf ( x) (1 t ) f ( y ) ,
với mọi x
n
, y
n
và t 0,1 .
Trong trường hợp ma trận D không phải là nửa xác định dương và
cũng không phải là nửa xác định âm, ta nói rằng f ( x)
đó c
n
1 T
x Dx cT x trong
2
là một hàm toàn phương không xác định.
Bài toán toàn phương với hàm mục tiêu toàn phương không xác định
được gọi là bài toán toàn phương không xác định.
Nhận xét 1.5. Rõ ràng, nếu hàm f cho bởi (1.3), trong đó ma trận D
thì ma trận Hessian 2 f ( x) D , với mọi x
n
nn
S
. Vì vậy, mệnh đề 1.1 là một
hệ quả trực tiếp của định lý 1.1.
Định lý 1.1. Nếu f :
n
là một hàm khả vi liên tục cấp hai và ma trận
Hessian 2 f ( x) là nửa xác định dương với mọi x
n
thì f là hàm lồi.
Bằng cách sử dụng mệnh đề 1.1, ta có thể chứng minh được một bài
toán toàn phương là lồi hay không.
Ví dụ 1.10. Bài toán toàn phương sau đây là không lồi
min f ( x) x12 x22 : x x1 , x2 ,1 x1 3,1 x2 3 .
20
2 0
Ta thấy, f là một hàm không lồi, vì với D
, tại x 1,3 ta có
0 2
x1
x1
2 0 x1
2
2
x2
x 2 x1 2 x2 x 2 x1 2 x2 ,
0 2 2
2
2
không lớn hơn 0 với mọi x 1,3 , nên trận D không xác định dương.
Nghiệm của bài toán Sol P 1,3 và ( P) 8 .
Ví dụ 1.11. Cho k điểm a1 , a2 ,..., ak trong
x
n
n
, chúng ta tìm thấy một điểm
2
2
mà tại đó tổng f ( x) : x a1 ........ x ak đạt giá trị nhỏ nhất.
k
T
k
k
Nhận thấy, f ( x) x ai ( x ai ) kxT x 2( ai )T x aiT ai là
i 1
i 1
i 1
một hàm toàn phương lồi. Và x là nghiệm của bài toán này khi và chỉ khi
k
f ( x ) 0 . Từ f ( x ) 2kx 2 ai , ta có thể viết điều kiện 0 f ( x ) tương
i 1
1 k
1 k
ứng với x ai . Do đó, x ai là kết quả duy nhất của bài toán này.
k i 1
k i 1
Điểm x đặc biệt này được gọi là trọng tâm của a1 , a2 ,..., ak .
Ví dụ hình học sau đây dẫn đến một bài toán toàn phương (không lồi)
của dạng tổng quát.
Ví dụ 1.12. Cho x
và d
S
n
: Ax b, Cx d , với A
mn
, C
S n
, b
m
. (Đẳng thức Cx d có thể vắng mặt trong công thức. Tương tự
như vậy, bất đẳng thức Ax b cũng có thể vắng mặt).
21
Cho i (i 1,..., n), i (i 1,..., n), và là 2n 2 số thực thỏa mãn
các điều kiện
n
n
i2 1, i2 1. (1.5)
i 1
i 1
Nhận thấy rằng,
n
n
M x R n : i xi 0 và M x R n : i xi 0
i 1
i 1
là hai siêu phẳng trong
n
.
Ta tìm x sao cho hàm f ( x) (d ( x, M )) 2 (d ( x, M )) 2 , trong đó
d ( x, ) inf x z : z là khoảng cách từ x đến tập hợp con
n
.
Ta có,
n
d ( x, M )
x . (1.6)
i i
i 1
Để chứng minh công thức này, chúng ta xét bài toán lồi sau
2
min ( z ) x z : z M . (1.7)
Ta có, z z1 , z2 ,...., zn M là nghiệm của (1.7) khi và chỉ khi tồn tại
sao cho 0 ( z ) (1 ,..., n ).
Từ đó,
( z ) ( z ) 2( x z ) 2( x z ) (1 ,..., n ).
22
Điều này có nghĩa là z x
thì 0 , z , x
2
2
khi : (1 ,..., n ). Hay, khi z M
,x
2
, .
Từ điều kiện (1.5) chúng ta có, 2 , x . Khi đó,
2
( d ( x, M )) x z
2
x (x
2
2
)
2
2
, , x .
2
Vì vậy, công thức (1.6) được chứng minh.
Chứng minh tương tự, với d ( x, M )
n
x , do đó
i i
i 1
n
n
f ( x) ( i xi ) ( i xi ) 2
2
i 1
n
i 1
n
n
) x ( 2 2 ).
( i j i j ) xi x j 2 ( i
i
i
j 1 i 1
i 1
Từ điều này, chúng ta kết luận rằng f x là một hàm toàn phương, vì
thế bài toán tối ưu hóa được xem như bài toán toàn phương dạng tổng quát.
Dễ dàng chứng minh được, nếu chúng ta chọn
23
1 0
1
0 1
1
, b , (1,0), 0, (0,1), 0 ,
A
1 0
3
0 1
3
thì đẳng thức Cx d không có mặt trong bài toán trên, trường hợp này đã
được nêu trong ví dụ 1.10. Trong đó,
M x ( x1 , x2 ) : x1 0, x2
,
M x ( x1 , x2 ) : x1 , x2 2 ,
d ( x, M ) x1 ,
d ( x, M ) x2 .
Chương 2
Điều kiện cần và đủ cực trị
cho bài toán quy hoạch toàn phương
Chương này, tập trung làm rõ điều kiện cần và đủ cực trị cho bài toán
quy hoạch toàn phương. Cụ thể, chúng ta nghiên cứu điều kiện cần và đủ cực
trị đầu tiên (định lý 2.1), điều kiện cần và đủ tối ưu thứ hai (định lý 2.4-2.5)
24
của bài toán quy hoạch toàn phương và điều kiện để bài toán có nghiệm duy
nhất (định lý 2.6-2.7).
2.1. Điều kiện cực trị đầu tiên
Khẳng định đầu tiên của những mệnh đề sau đây là một dạng của quy tắc
Fermat, điều kiện cần cực trị cơ bản, cho bài toán quy hoạch toàn phương. Khẳng
định thứ hai được gọi là điều kiện đủ cho bài toán quy hoạch toàn phương.
Định lý 2.1. Cho x là vector chấp nhận được của bài toán tối ưu
1
min f ( x ) xT Dx cT x : x ,
2
trong đó, D
nn
S
, c
n
và
n
(2.1)
là một tập lồi đa diện.
i) Nếu x là nghiệm địa phương của bài toán này thì
Dx c, x x 0 , x .
ii) Nếu Dx c, x x 0 , x \ x ,
(2.2)
(2.3)
thì x là nghiệm địa phương của (2.1) và hơn nữa, tồn tại 0 và ñ 0 sao cho
f ( x) f ( x ) ñ x x , x B x , . (2.4)
Chứng minh.
i) Cho x là nghiệm địa phương của bài toán (2.1). Chọn 0 thỏa
mãn f ( x ) f x , với mọi x B x , .
Với bất kỳ x \ x , ta thấy tồn tại 0 sao cho
25
