Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM
NGUYỄN LỆ THUỶ
VỀ ĐỐI NGẪU LAGRANGE
CỦA BÀI TOÁN TỐI ƢU LỒI CÓ RÀNG BUỘC LUẬN VĂN THẠC SĨ TOÁN HỌC
LUẬN VĂN THẠC SĨ TOÁN HỌC
Ngƣời hƣớng dẫn khoa học: PGS. TS. Đỗ Văn Lƣu THÁI NGUYÊN, 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
MỤC LỤC
Trang
MỤC LỤC i
MỞ ĐẦU 1
Chƣơng 1. ĐỐI NGẪU MẠNH CHO BÀI TOÁN TỐI ƢU LỒI VÀ
ÁP DỤNG CHO QUY HOẠCH BÁN XÁC ĐỊNH 4
1.1. HÀM LIÊN HỢP 4
1.1.1.CÁC PHÉP TOÁN VỀ HÀM LỒI 4
1.1.2. HÀM LIÊN HỢP 7
1.2. ĐẶC TRƢNG CỦA TÍNH ĐỐI NGẪU MẠNH 14
1.2.1. MỘT SỐ KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ 14
1.2.2. ĐẶC TRƯNG HÀM TỰA CỦA TẬP CHẤP NHẬN ĐƯỢC 19
1.2.3. ĐẶC TRƯNG CỦA SỰ SAI KHÁC ĐỐI NGẪU 0 ỔN ĐỊNH 21
1.3. QUY HOẠCH BÁN XÁC ĐỊNH LỒI 31
Về đối ngẫu Lagrange của bài toán
tối ưu lồi có ràng buộc
''
. Đề tài này có tính thời sự, đã và đang được nhiều nhà
toán học quan tâm nghiên cứu.
2.Mục đích và nhiệm vụ nghiên cứu.
2.1.Mục đích nghiên cứu.
Mục đích nghiên cứu của luận văn này là trình bày các định lí đối ngẫu
Lagrange cho các bài toán tối ưu lồi có ràng buộc nón, bao gồm: Các điều
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
kiện chính quy đặc trưng cho đối ngẫu Lagrange mạnh và đối ngẫu min-max
của Jeyakumar [6] cho bài toán quy hoạch lồi với ràng buộc nón và ràng buộc
tập, và các điều kiện đặc trưng cho tính chất sai khác đối ngẫu 0 ổn định của
Jeyakumar-Li [8] cho bài toán tối ưu lồi với ràng buộc nón cùng với các áp
dụng cho bài toán quy hoạch bán xác định lồi.
2.2.Nhiệm vụ nghiên cứu.
Luận văn tập trung vào các nhiệm vụ chính sau đây:
- Đọc, dịch tài liệu từ hai bài báo tiếng Anh của Jeyakumar và Jeyakumar-Li.
- Sử dụng các kết quả của hai bài báo đó để viết luận văn.
3.Phƣơng pháp nghiên cứu.
Sử dụng công cụ giải tích hàm, giải tích lồi và các kiến thức của lí thuyết
tối ưu.
4.Bố cục của luận văn.
Luận văn bao gồm phần mở đầu, hai chương, phần kết luận và danh mục
các tài liệu tham khảo.
Chƣơng 1 ĐỐI NGẪU MẠNH CHO BÀI TOÁN TỐI ƯU LỒI
VÀ ÁP DỤNG CHO QUY HOẠCH BÁN XÁC ĐỊNH
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Chƣơng I
ĐỐI NGẪU MẠNH CHO BÀI TOÁN TỐI ƢU LỒI VÀ
ÁP DỤNG CHO QUI HOẠCH BÁN XÁC ĐỊNH
Chương I trình bày các định lí đối ngẫu Lagrange của Jeyakumar-Li [8]
(2009), về các điều kiện đặc trưng cho tính chất sai khác đối ngẫu 0 ổn định
của bài toán quy hoạch lồi với ràng buộc nón, cùng với các áp dụng cho bài
toán quy hoạch bán xác định lồi.
1.1.HÀM LIÊN HỢP
Một số kiến thức giải tích lồi sẽ được trình bày trong mục này là cần thiết
cho nội dung của luận văn.
1.1.1. CÁC PHÉP TOÁN VỀ HÀM LỒI
Giả sử X là không gian tôpô tuyến tính lồi địa phương,
, : .D X f D
Nhắc lại:
Trên đồ thị (epigraph) của hàm
f
được định nghĩa như sau:
epi , :f x r D f x r
.
được gọi là chính thường (proper) nếu
domf
và
, f x x D
.
Định lý 1.1.1[1]
Giả sử
1
, ,
m
ff
là các hàm lồi chính thường trên X. Khi đó, tổng
1
m
ff
là một hàm lồi.
Định lý 1.1.2
Giả sử F là tập lồi trong
X
và
inf : ,
f x x F
. (1.1.1)
Suy ra:
1 2 1 2
1 , 1x x F
(0<
<1).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
1 2 1 2
1 inf : 1 ,
f x x x x F
được xác định như sau:
11
1
inf : , ,
m
m m i i
i
f x f x f x x X x x
(1.1.2)
và được ký hiệu là
1
m
i
i
f
hay
1.
m
ff
i i m
F f F F F
. Khi đó,
F
là tập lồi trong
X
.
Theo Định nghĩa,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
,
xF
,
n
ii
x
sao cho
11
( 1, , ), ,
X
,
f
là hàm xác định trên
X
.
Định nghĩa 1.1.2
Phép biến đổi Young-Fenchel, của hàm
f
, hay hàm liên hợp với
,f
được xác
định trên
*
X
như sau
* * *
sup ,
xX
f x x x f x
. (1.1.3)
Chú ý: cận trên trong (1.1.3) chỉ lấy theo
dom .xf
yếu.
Trên đồ thị của
**
fx
là giao của trên đồ thị các hàm
*
gx
, tức là giao của
các tập lồi đóng
*
yếu.
Vì vậy,
*
epif
lồi đóng
*
yếu.
Nhận xét 1.1.3
Từ Định nghĩa 1.1.2 suy ra:
* * *
,f x f x x x
**
0
**
0
, Õu ,
, nÕu .
n x x
xx
Ví dụ 1.1.2
Giả sử
,
A X f x x A
(hàm chỉ của tập A). Khi đó,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
** * * * *
sup ,
x
f x f x x x f x
Mệnh đề 1.1.2
Với hàm
f
bất kỳ, ta có
**
ff
. (1.1.5)
Chứng minh
*
** * * *
sup ,
x
f x x x f x
*
**
x
x
x x f x x x
fx
.
Định lý 1.1.4 (Fenchel-Moreau)
Giả sử X là không gian lồi địa phương Hausdorff,
:, fX
.
Khi đó,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
**
f f f
lồi đóng.
Chứng minh
Chú ý rằng: đối với tập lồi A trong không gian lồi địa phương Hausdorff, thì
do Hệ quả 3.3.2 [1], bao đóng và bao đóng yếu của A trùng nhau.
a) Giả sử
**
ff
. Theo Mệnh đề 1.1.1,
**
f
**
00
f x f x
. Ta có
epif
là tập
lồi đóng khác
và
**
00
, epix f x f
. Theo Định lý tách thứ hai, tồn tại
**
,yX
tách ngặt
**
00
,x f x
và
epi ,f
tức là:
domf
.
Nếu
0
: lấy
**
1
domyf
, với
0t
, ta có:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
* * * * *
11
dom
sup ,
yf
f y ty y ty y f y
**
0
dom
, sup ,
yf
y x y y
.
Vì vậy, từ (1.1.7) ta nhận được:
** * * * * *
0 1 0 1
, f x y ty x f y ty
* * * * *
1 0 1 0
dom
, , sup ,
yf
y x f y t y x y y
xy
, ta nhận được:
* ** *
00
, epi
, sup ,
yf
x x f x x y
*
dom
sup ,
yf
x y f y
**
epif
là tập lồi đóng. Do
**
ff
, nên
**
epi epiff
.
Do đó,
epi co epi epi **.f f f**
co .f f f
(1.1.8)
Nếu
12
ff
, thì
**
12
ff
. Vì thế,
*
f
*
*
co .ff
Chứng minh
Theo Hệ quả 1.1.1,
**
coff
.
**
*
f
*
(co ) .f
Hơn nữa, theo Mệnh đề 1.1.1,
*
f
là hàm lồi đóng, cho nên theo
Định lý 1.1.4,
**
**
*
**
11
.
mm
f f f f
b) Giả sử
1
, ,
m
ff
là các hàm lồi chính thường:
0
1
dom
m
i
i
xf
; có thể trừ
ra một hàm, còn lại đều liên tục tại
0
x
. Khi đó,
*
* * * * *
1 1 1
.
m m m
f f x f x f x
1.2 ĐẶC TRƯNG CỦA TÍNH ĐỐI NGẪU MẠNH
1.2.1.MỘT SỐ KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ
Xét bài toán quy hoạch lồi:
inf : ,P f x g x S
trong đó
,XY
là các không gian Banach, S là nón lồi đóng trong
,Y
: fX
là một hàm lồi nửa liên tục dưới chính thường và
: g X Y
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
trong đó
S
là nón đối ngẫu dương
+*
: , 0 S X v v S
của
S
.
Giá trị tối ưu
vD
của bài toán đối ngẫu
D
cho một cận dưới của giá trị
tối ưu
vP
của bài toán xuất phát
P
. Như vậy
f x f x y g x
(1.2.1)
Bài toán
P
được gọi là có đối ngẫu mạnh (strong duality) nếu:
1
*
*
inf maxinf , ,
xX
x g S
yS
f x f x y g x
(1.2.2)
trong đó
1
: : .
xX
x g S
yS
f x x x f x x x y g x
(1.2.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
trong đó
*
X
là đối ngẫu tôpô của
X
. Hơn nữa, thậm chí với bài toán
P
một chiều, (1.2.3) có thể không đúng khi mà đẳng thức sau đúng:
**
,xX
1
*
*
. ,.fx
đạt được cực tiểu trên
1
gS
, với mỗi
**
xX
ta dẫn điều kiện đẳng thức dưới vi phân đặc trưng cho sự sai khác đối
ngẫu 0 min- sup ổn định (stable min-sup zero duality gap). Ta có thể phát
biểu dưới ngôn ngữ toán học như sau:
**
,xX
1
*
* * *
min , supinf , , .
tương ứng là các hình cầu mở và đóng trong
X
với tâm
x
, bán kính
. Với một tập
AX
, ta ký hiệu phần trong, phần trong tương đối, bao
đóng, bao lồi, bao affin của
A
được ký hiệu tương ứng là:
int A
,
riA
,
,A
coA
,
affA
. Nếu
A
là tập con của
*
X
thì bao đóng yếu
*
được ký hiệu là:
*
(1.2.6)
Hàm tựa
A
được định nghĩa bởi
*
sup , , .
A
xA
u u x u X
Nếu :
'
'
liminf
xx
f x f x
, với
xX
thì ta nói
, nÕu .
x X x y x f y f x y X x domf
fx
x domf
Tổng quát hơn với bất kỳ
0
,
dưới vi phân của
f
tại
xX
được định
nghĩa bởi:
* * *
: , 0, ,
AA
N a a x X x x a x A
* * *
: , , .
AA
N a a x X x x a x A
Với bất kỳ
0
và
domxf
ta có:
12
,ff
ta có:
* * * *
1 2 1 2 1 2
epi epif f f f f f
. (1.2.10)
Giả sử
12
,ff
là các hàm lồi nửa liên tục dưới trên
X
. Tổng chập infimal của
1
f
và
2
f
, ký hiệu:
12
ff
, được định nghĩa bởi:
1 2 1 2
inf , .
(1.2.11)
Bao đóng yếu
*
trong các đẳng thức trên có thể bỏ đi được nếu:
12
intdom dom .ff
(xem [14]).
Bổ đề sau đây sẽ được sử dụng trong phần này:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Bổ đề 1.2.1. [13]
Giả sử
I
là tập chỉ số bất kỳ và
i
f
là hàm lồi nửa liên tục dưới chính
thường trên
X
. Giả sử
0
xX
sao cho
0
sup
iI
fX
được xác định bởi:
sup x =sup , .
ii
i I i I
f f x x X
1.2.2. ĐẶC TRƯNG HÀM TỰA CỦA TẬP CHẤP NHẬN ĐƯỢC
Giả sử
Y
là không gian Banach với đối ngẫu tôpô
*
Y
,
SY
là nón lồi
đóng, nón đối ngẫu dương
S
được định nghĩa bởi:
.yY
Ta định nghĩa
*
,: y g X
như sau:
**
, , , . y g x y g x x XSố hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Ký hiệu
1
gS
được xác định bởi:
1
: : .
g S x X g x S
Hàm
*
*
* * *
inf , ,
yS
h x y g x
**
.xX
Khi đó từ Định nghĩa ta suy ra
h
là hàm lồi chính thường thuần nhất dương
trên
*
X
. Hơn nữa, với bất kỳ
1
**
, , .
1
gS
theo nghĩa:
1
*
*
* * * * * * *
inf , , .
gS
yS
x y g x h x x X
(1.2.12)
Định lý 1.2.1
Giả sử
: g X Y
là ánh xạ
S
*
epi epi
gS
h
.
Bởi vì
1
*
epi
gS
là một tập con
*
w
- đóng của
*
X
, ta suy ra:
*
1
*
1
*
w
*
**
epi co epi , .
gS
yS
yg
Chú ý rằng:
*+
*
*
epi epi ,
yS
h y g
*
1
*
epi epi .
w
gS
h
1.2.3. ĐẶC TRƯNG CỦA SỰ SAI KHÁC ĐỐI NGẪU 0 ỔN ĐỊNH
Trong phần này ta sẽ trình bày các đặc trưng đối ngẫu cho sự sai khác đối
ngẫu 0 ổn định cho bài toán quy hoạch lồi.
Giả sử
SY
là nón lồi đóng,
: fX
là hàm lồi nửa liên tục
dưới chính thường,
: g X Y
là một ánh xạ
S
-lồi liên tục và
1
X
bởi công thức:
**
* * * *
inf , .
yY
x x y
Khi đó,
* * * * *
,
, sup , , ,
x X y Y
x y x x y y x y
x X q S
x x y g x q f x
x x y g x f x y q
Do đó,
* * * +
* * *
*+
sup , , , nÕu ,
,
, nÕu .
xX
x x y g x f x y S
xy
yS
(1.2.14)
Cố định
Copyright: Tài liệu đại học ©