ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN NGỌC HẢI
BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG
CÓ RÀNG BUỘC NÓN
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: PGS. TS. NGUYỄN NĂNG TÂM
Thái Nguyên - 2014
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
LỜI CẢM ƠN
Luận văn được hoàn thành tại trường Đại học khoa học - Đại học
Thái Nguyên dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm.
Tác giả xin được bày tỏ lòng biết ơn chân thành sâu sắc tới PGS.
TS. Nguyễn Năng Tâm, người đã tận tình hướng dẫn về phương hướng,
nội dung và phương pháp nghiên cứu trong suốt quá trình nghiên cứu,
thực hiện và hoàn thành luận văn.
Tác giả cũng xin gửi lời cảm ơn chân thành tới Ban giám hiệu
trường Đại học khoa học - Đại học Thái Nguyên, phòng sau đại học đã
tạo điều kiện rất thuận lợi về mọi mặt cho tác giả trong quá trình tác
giả học tập, nghiên cứu và hoàn thành luận văn.
Thái Nguyên, tháng 06 năm 2014
Tác giả
Nguyễn Ngọc Hải
i
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi
dưới sự hướng dẫn trực tiếp của PGS. TS. Nguyễn Năng Tâm.
Trong quá trình nghiên cứu đề tài luận văn, tôi đã kế thừa thành
quả khoa học của các nhà toán học và các nhà khoa học khác với sự trân
trọng và biết ơn.
Thái Nguyên, tháng 06 năm 2014
Tác giả
Nguyễn Ngọc Hải
ii
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
Mục lục
Mở đầu
1
1 KIẾN THỨC CHUẨN BỊ
5
1.1.
Khái niệm về không gian Hilbert . . . . . . . . . . . . .
5
1.2.
Khái niệm về ánh xạ đa trị . . . . . . . . . . . . . . . .
11
2 BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG CÓ RÀNG
BUỘC NÓN
12
2.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . .
12
2.2. Bài toán quy hoạch toàn phương có ràng buộc nón . . .
13
2.3. Điều kiện cực trị cho bài toán qui hoạch toàn phương có
ràng buộc nón . . . . . . . . . . . . . . . . . . . . . . . .
14
2.4. Sự ổn định của bài toán quy hoạch toàn phương có ràng
buộc nón . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.4.1. Sự ổn định của tập hợp điểm KKT . . . . . . . .
17
2.4.2. Sự ổn định của tập nghiệm toàn cục . . . . . . .
22
2.4.3. Tính liên tục của hàm giá trị tối ưu . . . . . . . .
26
2.5. Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . .
29
iii
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
Kết luận
30
Tài liệu tham khảo
30
iv
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
CÁC KÝ HIỆU THƯỜNG DÙNG
Rn
không gian Euclid n-chiều
k.k
chuẩn Euclid trong Rn
hx, yi
tích vô hướng của hai véc tơ x; y
B x0 , ε = x ∈ Rn :
x − x0
< 0 hình cầu mở trong Rn có tâm tại x0 ,
bán kính ε
A ∈ Rn×n
ma trận đối xứng
clS
bao đóng của tập hợp S
intS
miền trong của tập hợp S
S (Q, a, c)
tập hợp các điểm KKT
loc (Q, c, a)
nghiệm địa phương của (P )
Sol (Q, c, a)
nghiệm (toàn cục) của (P )
1
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
MỞ ĐẦU
1. Lý do chọn đề tài
Lý thuyết tối ưu có nhiều ứng dụng trong lý thuyết cũng như trong
các bài toán thực tế chẳng hạn, trong quy hoạch tài nguyên, thiết kế
chế tạo máy, điều khiển tự động, quản trị kinh doanh, kiến trúc đô thị,
công nghệ thông tin.... Chính vì vậy, các lĩnh vực của Tối ưu hóa ngày
càng trở nên đa dạng. Hiện nay, môn học Tối ưu hóa được đưa vào giảng
dạy trong nhiều chương trình đào tạo đại học cho các ngành khoa học
cơ bản, kỹ thuật - công nghệ, kinh tế - quản lý, sinh học - nông nghiệp,
xã hội - nhân văn, sinh thái - môi trường ... Quy hoạch toàn phương là
một trong những lĩnh vực của Tối ưu hóa. Lý thuyết quy hoạch toàn
phương đã và đang được nhiều tác giả quan tâm nghiên cứu [5], [7]. Sau
một thời gian học cao học, với mong muốn tìm hiểu sâu hơn về toán ứng
dụng, tôi chọn đề tài Bài toán quy hoạch toàn phương có ràng buộc nón
để nghiên cứu.
2. Mục đích nghiên cứu
Mục đích nghiên cứu nhằm nắm được các định nghĩa, định lí, tính
chất của Bài toán quy hoạch toàn phương có ràng buộc nón và các ứng
dụng của bài toán liên quan đến các vấn đề thực tiễn. Qua đó, giúp củng
cố các kiến thức đã được học như: không gian Rn , không gian affine, giải
tích hàm,. . .
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
3
3. Nhiệm vụ nghiên cứu
Hệ thống hoá các vấn đề lý luận về các kiến thức cơ sở liên quan
đến nội dung chính của bài toán.
Hệ thống hoá các định nghĩa, tính chất, ví dụ và ứng dụng của
Bài toán quy hoạch toàn phương có ràng buộc nón.
4. Giả thuyết khoa học
Trên cơ sở nghiên cứu mở rộng bài toán quy hoạch toàn phương
để áp dụng giải quyết các vấn đề thực tiễn, các bài toán thực tế của con
người nhằm nâng cao hiệu quả công việc.
5. Phương pháp nghiên cứu
Quá trình làm luận văn đã sử dụng kết hợp nhiều phương pháp
nghiên cứu, nhưng chủ yếu là phương pháp tổng kết kinh nghiệm.
Cụ thể, kết hợp phương pháp tổng hợp, so sánh, phân tích, nhận
xét trong quá trình nghiên cứu lí thuyết. Đầu tiên, sau khi tìm được
nguồn tài liệu tham khảo thì tổng hợp các kiến thức trong đó với các
kiến thức sẵn có. Sau đó, tiến hành so sánh, phân tích chúng, chọn ra
những kiến thức trọng tâm, đáng ghi nhớ, từ đó đưa ra những nhận xét
riêng. Cuối cùng, tổng hợp, trình bày lại theo ý hiểu một cách rõ ràng.
6. Đóng góp của luận văn
Hệ thống hoá các vấn đề lý luận liên quan đến đề tài.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
4
Vận dụng Bài toán quy hoạch toàn phương có ràng buộc nón vào
giải quyết các bài toán, các vấn đề thực tế trong cuộc sống con người.
7. Cấu trúc luận văn
Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo,
luận văn có 2 chương:
Chương 1: Kiến thức chuẩn bị
1.1. Khái niệm về không gian Hilbert
1.2. Khái niệm về ánh xạ đa trị
1.3. Kết luận chương 1
Chương 2: Bài toán Quy hoạch toàn phương có ràng buộc
nón
2.1. Bài toán tối ưu
2.2. Bài toán quy hoạch toàn phương có ràng buộc nón
2.3. Điều kiện cực trị cho bài toán quy hoạch toàn phương có ràng
buộc nón
2.4. Sự ổn định của bài toán quy hoạch toàn phương có ràng buộc
nón
2.5. Kết luận chương 2
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
Chương 1
KIẾN THỨC CHUẨN BỊ
Những nội dung trình bày trong chương này chủ yếu lấy từ [1], [3],
[4] và [7].
1.1.
Khái niệm về không gian Hilbert
Cho V là không gian véc tơ trên trường số thực R.
Định nghĩa 1.1. Ta gọi mỗi ánh xạ
h., .i : V × V → R;
(x, y) 7→ hx, yi
là một tích vô hướng trên V nếu các điều kiện sau đây thỏa mãn: Với
mọi x, y, z ∈ V và α ∈ R
i) hx, yi = hy, xi
ii) hαx, yi = α hx, yi
iii) hx, y + zi = hx, yi + hx, zi
iv) hx, xi ≥ 0,
hx, xi = 0 khi và chỉ khi x = 0
Số hx, yi được gọi là tích vô hướng của x và y. Không gian véc tơ
V cùng với một tích vô hướng xác định được gọi là không gian có tích vô
hướng và thường được viết là (V, h., .i).
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
6
Định nghĩa 1.2. Cho không gian véc tơ V cùng với một tích vô hướng
h., .i xác định . Khi đó công thức
kxk =
p
hx, xi
xác định một chuẩn trên V . Nếu không gian có tích vô hướng (V, h., .i)
với chuẩn xác định như trên là một không gian đủ, thì ta goi (V, h., .i) là
một không gian Hilbert.
Ta gọi số chiều của V là số chiều của không gian Hilbert (V, h., .i).
Định nghĩa 1.3. Cho V là một không gian Hilbert và a ∈ V . Ta gọi
mỗi không gian con tuyến tính X của V là một không gian con, mỗi tập
có dạng a + X trong V là một không gian affine con của V .
Ví dụ 1.1. Lấy V = Rn . Với x = (x1 , . . . , xn ), y = (y1 , . . . , yn ) ∈ V biểu
thức
hx, yi =
n
X
xi yi
i=1
xác định một tích vô hướng trên không gian Rn và với chuẩn
kxk =
p
hx, xi
Rn trở thành một không gian Hilbert hữu hạn chiều.
Định nghĩa 1.4. Cho x0 ∈ V, ε > 0 ta gọi tập
B x0 , ε = x ∈ V | kx − x0 k < 0
là hình cầu mở trong không gian V có tâm tại x0 , bán kính ε.
Tập U ∈ V gọi là mở nếu với mọi x0 ∈ U tồn tại ε > 0 sao cho
B x0 , ε ⊂ U.
Tập F ∈ V được gọi là đóng nếu U = V \ F là mở.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
7
Định nghĩa 1.5. Tập S ⊂ V được gọi là lồi nếu với mọi x, y ∈ S, đoạn
thẳng nối x, y đều nằm trong S. Nói cách khác, S ⊂ V là tập lồi khi và
chỉ khi:
∀x, y ∈ S, ∀λ ∈ [0, 1] ta cóx = λx1 + (1 − λ) x2 ∈ S.
Ví dụ 1.2. Các tập S sau đây là tập lồi:
i) S = x = x1 , x2 , x3 ∈ R3 : 2x1 − x2 + 3x3 = 5 .
ii) S = x = x1 , x2 , x3 ∈ R3 : 2x1 − x2 + 3x3 ≤ 5 .
iii) S = x ∈ R : x = x1 , x2 : x1 + x2 ≤ 9 .
Các tính chất của tập lồi
Cho tập lồi S1 , S2 ⊂ Rn . Khi đó:
1) S1 ∩ S2 là tập lồi.
2) S1 + S2 = x : x = x1 + x2 với x1 ∈ S1 , x2 ∈ S2 là tập lồi.
3) S1 − S2 cũng là tập lồi.
Định nghĩa 1.6. Cho tập lồi khác rỗng S ⊂ V . Hàm số f : S → R được
gọi là hàm lồi nếu ∀x, y ∈ S, ∀λ ∈ [0, 1] ta có
f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) .
Ví dụ 1.3. i) Hàm số f : R → R với f (x) = x2 là một hàm lồi.
ii) Hàm số hai biến f : R2 → R với f (x, y) = x2 + y 2 là hàm lồi.
Định nghĩa 1.7. Cho S ⊂ V là một tập hợp khác rỗng. S được gọi là
nón nếu ∀λ > 0 và x ∈ S ta luôn có λx ∈ S.
Nón S được gọi là nón lồi nếu S là tập lồi.
Nón S được gọi là nón lồi đóng nếu S vừa là nón lồi vừa là tập
đóng.
Định nghĩa 1.8. Cho một tập hợp khác rỗng S ⊂ V. Nón đối cực của
∗
S, được ký hiệu là S , là tập hợp {y ∈ V | hy, xi ≤ 0, ∀x ∈ S}. Nếu S là
tập rỗng thì nón đối cực sẽ là V .
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
8
Định lý 1.1. Cho V là không gian Hilbert với x, y ∈ V ta luôn có bất
đẳng thức sau
|hx, yi| ≤ kxkkyk.
Bất đẳng thức này được gọi là bất đẳng thức Cauchy- Schwartz.
Chứng minh. Nếu x = 0 thì hiển nhiên nhiên bất đẳng thức CauchySchwartz đúng. Xét trường hợp x 6= 0. Với t ∈ R, đặt ϕ(t) = htx +
y, tx + yi. Theo định nghĩa tích vô hướng ta có ϕ(t) ≥ 0, ∀t. Ta lại có
ϕ(t) = hx, xit2 + 2hx, yit + hy, yi
là một tam thức bậc hai biến t. Do tính không âm của ε(t) ta phải có
∆ = hx, yi2 − hx, xi.hy, yi ≤ 0. Từ đây suy ra |hx, yi| ≤ kxkkyk, ta có
điều phải chứng minh.
Định lý 1.2. Cho V là một không gian Hilbert. Khi đó
h., .i : V × V → R
là một hàm liên tục
Chứng minh. Cho {xn }, {yn } là hai dãy trong không gian Hilbert V lần
lượt hội tụ về x0 và y0 . Khi đó, ta có
|hxn , yn i − hx0 , y0 i| 6 |hxn , yn i − hxn , y0 i| + |hxn , y0 i − hx0 , y0 i|
= |hxn , yn − y0 i| + |hxn − x0 , y0 i|
≤ kxn kkyn − y0 k + kxn − x0 kky0 k.
Theo giả thiết {xn } hội tụ trong V nên nó bị chặn, nghĩa là tồn tại số
M > 0 sao cho kxn k ≤ M với mọi n ∈ N. Vì vậy, ta có
|hxn , yn i − hx0 , y0 i| ≤ M kyn − y0 k + kxn − x0 kky0 k.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
9
Chuyển qua giới hạn ta được
lim |hxn , yn i − hx0 , y0 i| = 0.
n→∞
Vậy định lý được chứng minh.
Định lý 1.3. Cho S là một tập lồi đóng khác rỗng trong không gian
Hilbert V . Khi đó, với mỗi x ∈ V tồn tại duy nhất y ∈ S sao cho
kx − yk = inf{kx − zk | z ∈ S}.
Ta kí hiệu d(x, S) = inf{kx − zk | z ∈ S}.
Định nghĩa 1.9. Hai phần tử x và y của không gian Hilbert V gọi là
trực giao nếu hx, yi = 0, kí hiệu x⊥y.
Nếu S là một tập con của không gian Hilbert V thì tập
S ⊥ = {x ∈ V | x⊥y
∀y ∈ S}
gọi là phần bù trực giao của S.
Định lý 1.4. Giả sử S là một không gian con đóng của không gian
Hilbert V . Khi đó mỗi phần tử x ∈ V biểu diễn được một cách duy nhất
dưới dang x = y + z, trong đó y ∈ S và z ∈ S ⊥ .
Chứng minh. Nếu x ∈ S thì đặt y = x, z = 0. Ta có khẳng định đúng.
Xét trường hợp x ∈
/ S. Vì S đóng nên tồn tại duy nhất y ∈ S sao cho
kx − yk = d(x, S).
Đặt z = x − y, ta có x = y + z, Ta phải chứng minh z ∈ S ⊥ . Thật
vậy, với mọi α ∈ R, u ∈ S ta có
kzk = kx − yk ≤ kx − (y + αu)k
= kz − αuk.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
10
Từ đó suy ra
kzk2 ≤ hz − αu, z − αu
= kzk2 − αhu, zi − αhz, ui + α2 kuk2 .
Chọn α = hz, ui và kuk, ta suy ra 0 ≤ −|hz, ui|2 . Do đó, hz, ui = 0 với
mọi u ∈ S và kuk = 1. Như vậy ta đã chỉ ra z ∈ S ⊥ .
Tiếp theo ta chứng minh sự biểu diễn là duy nhất, giả sử x = y1 +z1
với y1 ∈ S, z1 ∈ S ⊥ . Khi đó, y−y1 = z1 −z, ta có y−y1 ∈ S và y−y1 ∈ S ⊥ .
Từ đó suy ra hy − y1 , y − y1 i = 0. Do vậy y = y1 và do đó z = z1 . Vậy
định lý được chứng minh.
Định nghĩa 1.10. Theo định lý trên, mọi x ∈ V đều biểu diễn được duy
nhất dạng x = y + z với y ∈ S, z ∈ S ⊥ . Như vậy, V = S ⊕ S ⊥ . Ánh xạ
P : V → S, xác định P (x) = y với x = y + z ∈ S ⊕ S ⊥ , được gọi là phép
chiếu trực giao từ V lên S
Định lý 1.5. Phép chiếu trực giao P từ không gian Hilbert V lên không
gian con đóng S 6= {0} là một toán tử tuyến tính liên tục.
Chứng minh. Với x1 , x2 ∈ V, α ∈ R, theo định lý 1.4 ta có
x1 = P x1 + z1 ; x2 = P x2 + z2 ,
trong đó z1 , z2 ∈ S ⊥ .
Vì vậy
x1 + x2 = P x1 + P x2 + z1 + z2 ,
trong đó P x1 + P x2 ∈ S, z1 + z2 ∈ S ⊥ . Từ tính duy nhất của sừ biểu
diễn trong định lý trên ta suy ra
P (x1 + x2 ) = P x1 + P x2 .
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
11
Tương tự P (αx1 ) = αP (x1 ). Vậy P tuyến tính.
Mặt khác, với x ∈ V ta có
kxk2 = kP xk2 kzk2 ≥ kP xk2 .
Từ đó suy ra P bị chặn. Vậy P liên tục. Định được chứng minh.
1.2.
Khái niệm về ánh xạ đa trị
Định nghĩa 1.11. Cho X, Y là những tập hợp tập hợp. Ta gọi mỗi quy
tắc F cho ứng với mỗi phần tử x của X với duy nhất một tập con F (x)
của Y là một ánh xạ đa trị từ X vào Y , kí hiệu F : X ⇒ Y .
Cho anh xạ đa trị F : W ⇒ V trong đó W là tập hợp con của
không gian Hilbert.
Định nghĩa 1.12. Ta nói F là nửa liên tục trên (usc) tại ω ∈ W nếu
đối với mỗi tập hợp mở Ω ⊂ V thỏa mãn F (ω) ⊂ Ω, khi đó tồn tại δ > 0
sao cho F (ω 0 ) ⊂ Ω với mọi ω 0 ∈ W thoả mãn tính chất kω 0 − ωk < δ.
Định nghĩa 1.13. Chúng ta nói rằng F là nửa liên tục dưới (lsc) tại
ω ∈ W nếu đối với mỗi tập hợp mở Ω ⊂ V thỏa mãn F (ω) ∩ Ω 6= ∅, khi
đó tồn tại δ > 0 sao cho F (ω 0 ) ∩ Ω 6= ∅ với mọi ω 0 ∈ W thoả mãn tính
chất kω 0 − ωk < δ. Nếu F đồng thời nửa liên tục trên và là nửa liên tục
dưới tại ω, thì ta nói rằng nó là liên tục tại ω.
Kết luận chương 1
Trong chương này đã sơ lược trình bày một số kiến thức cơ bản sẽ
sử dụng trong phần sau.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
Chương 2
BÀI TOÁN QUY HOẠCH TOÀN
PHƯƠNG CÓ RÀNG BUỘC NÓN
Mục đích của chương này là trình bày một vài tính chất định tính
của bài toán cực tiểu hoá hàm toàn phương trên giao của không gian
con affine và hình nón lồi đóng n chiều có miền trong khác rỗng. Những
nội dung trình bày trong chương này lấy từ [3], [5], [6] và [7].
2.1.
Bài toán tối ưu
Bài toán tối ưu là bài toán có dạng:
inf f (x)
với x ∈ D,
(2.1)
trong đó D là một tập con của một không gian tô pô X, f : D → R là
một hàm số. Hàm f gọi là hàm mục tiêu, tập D gọi là miền ràng buộc
hoặc tập chấp nhân được của bài toán (2.1). Nếu D = X thì ta nói bài
toán (2.1)không có ràng buộc. Như vậy, ta cần tìm điểm x ∈ D sao cho
hàm mục tiêu f (x) đạt được giá trị bé nhất - cực tiểu hoá. Điểm x ∈ D
được gọi là điểm chấp nhận được của bài toán (2.1).
Định nghĩa 2.1. Điểm x∗ ∈ X được gọi là nghiệm tối ưu (hay nghiệm)
Soá hoùa bôûi Trung taâm Hoïc lieäu
12
ĐHTN
http://www.lrc.tnu.edu.vn/
13
toàn cục của bài toán (2.1) nếu
x∗ ∈ D
và
f (x∗ ) 6 f (x) ∀x ∈ D.
Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương của (2.1) nếu tồn
tại một lân cận mở U trong X của điểm x∗ sao cho
f (x∗ ) ≤ f (x) , ∀x ∈ U ∩ D.
Dễ thấy, mọi nghiệm tối ưu toàn cục cũng là phương án tối ưu
địa phương, trong khi đó một phương án tối ưu địa phương không nhất
thiết là phương án tối ưu toàn cục.
2.2.
Bài toán quy hoạch toàn phương có ràng buộc
nón
Cho (V, h., .i) là không gian Hinbert hữu hạn chiều và K ⊂ V là
hình nón lồi đóng với đối ngẫu dương
K ∗ := {y ∈ V : hy, xi ≥ 0, ∀x ∈ K} .
Giả sử miền trong intK của K là khác rỗng và K nhọn, nghĩa là
K ∩ (−K) = {0} . Kí hiệu LS (V ) là tập hợp các toán tử tuyến tính đối
xứng Q : V → V . Do đó, cho bất kỳ Q ∈ LS (V ) và x, y ∈ V, luôn có
hQx, yi = hx, Qyi .
Ta gọi bài toán sau là Bài toán quy hoạch toàn phương có ràng
buộc nón
1
inf f (x, Q, c) := hx, Qxi + hc, xi
2
với x ∈ a + X, x ∈ K
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
(2.2)
14
trong đó Q ∈ LS (V ) , c, a ∈ V và X ⊂ V là một không gian con
tuyến tính.
Gần đây, đã có thuật toán cho (2.2) được đề nghị trong khuôn khổ
của đại số Jordan-Euclide [6] . Dễ dàng chỉ ra rằng bài toán quy hoạch
toàn phương với ràng buộc tuyến tính là trường hợp đặc biệt của (2.2).
Bài toán phụ miền tin cậy cũng là một trường hợp đặc biệt của (2.2).
Thật thế, lấy V = Rn và K là hình nón Lorentz trong V , nghĩa là
(
)
n−1
X
K = x = (x1 , ..., xn ) : x2n ≥
x2i .
i=1
Lấy X = {x = (x1 , ..., xn ) : xn = 0} và a = (0, ..., 0, µ) với µ > 0,
ta có
(
(a + X) ∩ K =
x = (x1 , ..., xn−1 , µ) :
n−1
X
)
x2i ≤ µ2
.
i=1
Do đó (2.2) trở thành vấn đề về cực tiểu hoá hàm toàn phương
trên hình cầu đóng với tâm 0 và bán kính µ > 0 trong không gian Rn−1 .
Đó chính là bài toán phụ miền tin cậy.
2.3.
Điều kiện cực trị cho bài toán qui hoạch toàn
phương có ràng buộc nón
Bổ đề 2.1. Cho x ∈ K, giả sử
K (x) = y ∈ E : x + ty ∈ K, t > 0 đủ nhỏ
Khi đó đối ngẫu của nó K (x)∗ = {s ∈ K ∗ : hx, si = 0} .
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
15
Chứng minh. Dễ dàng thấy rằng K(x) là một nón lồi. Vì K ⊂ K(x), ta
có K (x)∗ ⊂ K ∗ . Giả sử s ∈ K ∗ , hx, si = 0. Nếu y ∈ K (x) thì tồn tại
t > 0 sao cho x + ty ∈ K. Khi đó
hs, x + tyi = t hs, yi ≥ 0.
Do đó, hs, yi ≥ 0. Như vậy
{s ∈ K ∗ : hx, si = 0} ⊂ K (x)∗ .
Ngược lại, giả sử s ∈ K (x)∗ ⊂ K ∗ . Khi đó ta có hs, yi ≥ 0. Tuy
nhiên, −x ∈ K (x) . Thực vậy, nếu 0 < t < 1, x + t (−x) = (1 − t) x ∈ K,
nghĩa là −x ∈ K (x), nhưng khi đó hs, −xi ≥ 0, nghĩa là hs, xi ≤ 0. Vì
vậy, hs, xi = 0. Ta đi đến kết luận K (x)∗ ⊂ {s ∈ K ∗ | hx, si = 0} .
Điều kiện cần cực trị bậc nhất cho (2.2) có thể phát biểu như sau
Định lý 2.1. Nếu x ∈ K ∩ (a + X) là cực tiểu địa phương của (2.2),
thì có r ≥ 0 và s ∈ K ∗ sao cho (r, s) 6= (0, 0) , r (Qx + c) − s ∈ X ⊥ , và
hx, si = 0, trong đó X ⊥ thay cho không gian con trực giao của X. Nếu
thêm vào đó (a + X) ∩ (intK) là rỗng, thì có thể lấy r = 1.
Chứng minh. Kí hiệu f (x) =
1
2
hx, Qxi + hc, xi. Giả sử π : E → X ⊥ là
phép chiếu trực giao. Đặt
N = (t, π (p)) ∈ R × X ⊥ | t = hf 0 (x∗ ) , pi , p ∈ K (x∗ )
và
P = (t, y) ∈ R × X ⊥ : t < 0, y = 0 .
Ta khẳng định rằng N ∩ P = ∅. Thực vậy, nếu N ∩ P 6= ∅,
thì tồn tại p ∈ K (x∗ ) ∩ X sao cho hf 0 (x∗ ) , pi < 0. Tuy nhiên, khi đó
x∗ + tp ∈ (a + X) ∩ K, với t > 0 đủ bé.
Soá hoùa bôûi Trung taâm Hoïc lieäu
ĐHTN
http://www.lrc.tnu.edu.vn/
- Xem thêm -