1
Đại Học Quốc Gia Hà Nội
Trƣờng Đại Học Khoa Học Tự Nhiên
Hà Nội - 2012 2
Người hướng dẫn khoa học
GS.TSKH.LÊ DŨNG MƢU
Hà Nội - 2012 3
Mục lục
Lời nói đầu 2
Chƣơng I Những kiến thức cơ bản về tập lồi và hàm lồi 4
I. 1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
I.1.1. Tập lồi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
I.1.2. Nón lồi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
I.1.3. Tập Affine và bao Affine. . . . . . . . . . . . . . . . . . . . . . . . .9
I.1.4. Điểm trong tương đối. . . . . . . . . . . . . . . . . . . . . . . . 13
I.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
I.3. Các phép toán về hàm lồi. . . . . . . . . . . . . . . . . . . . . . . . . . .22
vực khác nhau của toán học ứng dụng, đặc biệt là trong tối ưu hóa, bất đẳng thức
biến phân và bài toán cân bằng…
Một trong những ứng dụng quan trọng của giải tích lồi là trong tối ưu hóa. Lý
thuyết tối ưu đóng vai trò quan trọng trong nhiều lĩnh vực nghiên cứu: quy hoạch
tuyến tính, lý thuyết điều khiển, lý thuyết trò chơi, kinh tế toán,… trong đó, giả thiết
về tính lồi của hàm không thể thiếu trong nhiều định lý về sự tồn tại nghiệm. Vì
vậy, tìm hiểu về hàm lồi, tìm hiểu về ứng dụng của hàm lồi trong tối ưu hóa là thực
sự cần thiết và hữu ích.
Mục tiêu của luận văn là tìm hiểu, sắp xếp lại một cách chi tiết các khái niệm
cùng những tính chất liên quan đến hàm lồi, dưới vi phân của hàm lồi và các bài
toán ứng dụng dưới vi phân trong tối ưu hóa. Với những công việc đó, bản luận văn
gồm 3 chương:
Chƣơng I “Những kiến thức cơ bản về tập lồi và hàm lồi” giới thiệu về tập
lồi, hàm lồi và những tính chất liên quan. Bên cạnh đó là những khái niệm: tập
affine, nón, điểm trong tương đối,…
Chƣơng II “Dƣới vi phân của hàm lồi” đề cập tới khái niệm đạo hàm theo
phương, điều kiện khả dưới vi phân của hàm lồi cùng các tính chất cơ bản của
dưới vi phân.
Chƣơng III “Ứng dụng dƣới vi phân vào bài toán tối ƣu” trình bày khái niệm
tổng quát về bài toán tối ưu và điều kiện tồn tại nghiệm. Trọng tâm của chương là 8
bài toán tối ưu mà tác giả kí hiệu từ (P1)-(P8). 5
Do thời gian và trình độ còn hạn chế, bản luận văn mới chỉ dừng lại ở việc tìm
hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề
đặt ra. Trong quá trình viết luận văn, chắc chắn không tránh khỏi những hạn chế,
thiếu sót, tác giả rất mong nhận được sự góp ý của thầy, cô và bạn bè đồng nghiệp.
Qua đây, tác giả xin được gửi lời cảm ơn sâu sắc đến người thầy, người hướng
dẫn khoa học của mình, GS.TSKH. Lê Dũng Mưu đã đưa ra đề tài và tận tình
6 CHƢƠNG I
Những kiến thức cơ bản về tập lồi và hàm lồi
Trong chương này, tác giả trình bày những khái niệm cơ bản của giải tích lồi
cùng những tính chất quan trọng như tập lồi, tập affine, điểm trong tương đối, hàm
lồi…
I.1. Tập lồi
Tập lồi là một khái niệm cơ bản không chỉ trong giải tích lồi mà ở trong toán học
nói chung. Những tập quen thuộc mà chúng ta biết đến như không gian con, siêu
phẳng, đoạn thẳng…đều là tập lồi. Trong phần này, tác giả trình bày định nghĩa,
tính chất của tập lồi nói chung và một số tập lồi đặc biệt.
I.1.1. Tập lồi
Cho X là không gian tuyến tính tô pô Haussdoff.
Định nghĩa I.1[2]. Với
12
,xx
Ví dụ 1
a- Trong
2
, Tập
2
0,1 : 1B x x
là tập lồi. 7
Thật vậy, lấy
, 0,1 1x y B x
,
1y
, với
0,1
ta có:
(1 ) 1x y x y
11
cũng là một tập lồi.
Chứng minh
Lấy
1 2 1 2
,,x x A x x A
12
,x x A
( Do
A
lồi) ,
I
Từ đó suy ra
12
,
I
x x A
Ayx ,
:
11
,
nn
i i i i
ii
x a y b
với
, 1,
i i i
a b A i n
.
Khi đó,
0,1
, ta có:
1
11
n
i i i
i
X
là các không gian tuyến tính.
i
A
i
X
là các tập lồi (i=
1, n
).
Khi đó, tập A=
12
n
A A A
là một tập lồi trong
12
n
X X X
.
Chứng minh
Lấy
1 2 1 2
, : , , , , ,
nn
x y A x a a a y b b b
,
( , )
Vậy, A là tập lồi trong
12
n
X X X
Tóm lại: Lớp các tập lồi là đóng với phép lấy giao,cộng đại số và tích đề các.
Định nghĩa I.3[2]. Véc tơ
xX
gọi là tổ hợp lồi của các véc tơ:
12
, ,
n
x x x
nếu :
11
0,( 1, ), 1:
nn
i i i i
ii
i n x x
Mệnh đề I.4. Tập
AX
là tập lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các
điểm của nó. Tức là: A lồi khi và chỉ khi
12
1 , 0,1x x A
,
A
lồi.
Giả sử A lồi. Ta chứng minh bằng quy nạp
*k=2:
1 2 1 2 1 2 1 1 2 2
, 0: 1, ,x x A x x A
(do A lồi)
*Giả sử kết luận đúng với k điểm.Tức là:
1 2 1 2
1
, , , , 0: 1, , ,
k
k i k
i
k x x x A
1
k
1
k
ii
i
x x A
.
Không mất tổng quát, ta giả sử
1
1
k
, ta có
1
1
10
k
ik
i
.
Do A lồi
1 1 1
1
k k k
y x A
xA
.
Vậy A là tập lồi.
Nhận xét . Giả sử X, Y là các không gian tuyến tính,
:f X Y
là ánh xạ tuyến tính.
Tập
XA
là tập lồi. Khi đó
f
(A) cũng là tập lồi.
Thật vậy, lấy
1 2 1 2
, ( ) ,y y f A x x A
sao cho:
XA
. Giao của tất cả các tập lồi chứa A được gọi là
bao lồi của A và kí hiệu là CoA.
Nhận xét
a) CoA là một tập lồi và là tập lồi nhỏ nhất chứa A.
b) A là một tập lồi khi và chỉ khi A = CoA.
Định nghĩa I.5 [2]. Giả sử
XA
. Giao của tất cả các tập lồi đóng chứa A được
gọi là bao lồi đóng của tập A và kí hiệu là:
ACo
Nhận xét
a)
ACo
là một tập lồi đóng và là tập lồi đóng nhỏ nhất chứa A.
b) A là tập lồi đóng
ACoA
.
Định lý I.4 [2]. Bao lồi đóng của tập A trùng với bao đóng của bao lồi của A. Tức
là
CoAACo
10
Chứng minh
Trước hết, ta chứng minh bao đóng của một tập lồi là tập lồi. Tức là, nếu A là tập
lồi thì
A
2
'
1
'
1 xxx
. Khi đó
'
1 2 1 2
11x x U x U x x U
.
Hay là
Uxx
'
Vì A lồi nên
Ax
'
. Do đó
AUx
Vậy,
xA
0
là nón có đỉnh tại 0. Nón K có đỉnh tại 0
được gọi là nón lồi nếu K là một tập lồi.
Ví dụ
a)
:0A x x
là một nón, không lồi.
b)
12
: , , , ; 0, 1,
n
ni
B x x x x i n
là một nón lồi. 11
Dưới đây ta sẽ xét hai nón lồi điển hình thường được sử dụng trong giải tích lồi.
Đó là nón lùi xa và nón pháp tuyến.
Định nghĩa I.7[1]. Cho C là một tập lồi trong
X
. Véctơ
0y
được gọi là hướng
lùi xa của C nếu mọi tia xuất phát từ một điểm bất kì của C theo hướng y đều nằm
trọn trong C, tức là, y là một hướng lùi xa khi và chỉ khi
CyxCx
: ( ) 0,
C
N x X y x y C
gọi là nón pháp tuyến trong của C tại x.
Hiển nhiên, nón
xN
C
chứa đỉnh 0
I.13. Tập affine và bao affine
Trong đại số tuyến tính, chúng ta đã làm quen với các khái niệm: không gian con,
siêu phẳng,…Đó là các trường hợp riêng của tập affine được định nghĩa như sau:
Định nghĩa I.9[1]. Một tập C được gọi là tập affine nếu nó chứa mọi đường thẳng
đi qua hai điểm bất kỳ của nó. Tức là:
, , (1 )x y C R x y C
.
Nhận xét
1) Tập affine là một trường hợp riêng của tập lồi.
2) Mọi siêu phẳng trong
n
đều là tập affine.
Mệnh đề sau đây cho ta thấy tập affine chính là ảnh tịnh tiến của một không gian
con.
1
.
Vậy
Myx
1
. Suy ra M là một tập affine.
Không gian con L ở trên là duy nhất. Thật vậy, nếu M = L + a và
''
aLM
,
trong đó L, L
’
là những không gian con và
Maa
'
,
thì
' ' ' '
L M a L a a L a a
.
Do
aLMa
'
nên
Laa
'
. Suy ra
. Do đó L có dạng:
0
n
L x Ax
, 13
trong đó
,A Mat m n
và rank A = n – r. từ M = L +a, suy ra
0
nn
M x A x a a Ax Aa b
.
Điều kiện đủ: Giả sử
n
M x Ax b
với
,,A Mat m n
m
b
k
j
j
.
Định nghĩa I.12[1]. Bao affine của C là giao của tất cả các tập affine chứa C. Ký
hiệu là aff C
Mệnh đề sau đây cho chúng ta biết cấu trúc của aff C.
Mệnh đề I.8 [1]. AffC là tập hợp các tổ hợp affine của các điểm thuộc C.
Chứng minh
Ta gọi M là tập hợp các tổ hợp affine của các điểm thuộc C, tức là:
k
j
k
j
j
jj
j
j
yy
1
,
Trong đó
hjCykiCx
ji
, ,1,;, ,1,
,
và
1
11
h
j
j
k
i
i
.
Với
j
h
j
k
i
i
Như vậy, z là một tổ hợp affine của các điểm thuộc C nên
Mz
. Từ đó suy ra M là
một tập affine. Vậy M = aff C.
Định nghĩa I.13[1]. Thứ nguyên (hay chiều) của một tập C bất kỳ là thứ nguyên
(hay chiều) của bao affine của nó. Tức là dim C = dim (aff C).
Định nghĩa I.14[1]. Các điểm
k
xxx , ,,
10
trong
n
được gọi là độc lập affine nếu
bao affine căng bởi chúng có thứ nguyên k.
Mệnh đề dưới đây cho ta một tính chất đặc trưng của các điểm độc lập affine.
Mệnh đề I.9 [1]. Các điều sau đây tương đương:
a. Các điểm
k
xxx , ,,
10
độc lập affine.
j
xx
0
là một tổ hợp affine bất kỳ của các điểm
k
xxx , ,,
10
. Vì
1
0
k
j
j
nên
k
j
j
1
k
yyy , ,,
21
. Theo mệnh đề 1.1.10, ta có
k
yyyspanL , ,,
21
.
Vậy dim L = k khi và chỉ khi
k
yyy , ,,
21
độc lập tuyến tính trong
n
.
Mệnh đề I.10[1]. Cho hai tập affine A và B trong
n
. Giả sử dim A = dim B, khi đó
tồn tại một ánh xạ affine 1 – 1 T:
BA
sao cho TA = B.
Chứng minh
Theo giả thiết, A và B là các tập affine đồng thời dim A = dim B = m nên chúng
là bao affine của m + 1 điểm độc lập affine. Giả sử
Ax
đều biểu diễn duy nhất dưới dạng
j
m
j
j
x
1
Trong đó
0
aa
jj
. Đặt
mjTbb
jjjj
, ,1,0,,
0
. Ta lấy
,
trong đó B là một lân cận mở của gốc tọa độ 0.
Hiển nhiên
:riC a affC B a B affC C
.
Ta ký hiệu
C
là bao đóng của C. Khi đó tập hợp
riCC \
được gọi là biên tương
đối của C. Tập C được gọi là mở tương đối nếu
riCC
. Theo định nghĩa, dễ thấy
rằng mọi tập affine đều mở tương đối. 16
Nhận xét
1. Nếu
Cint
thì
CriC int
.
2. Nếu
21
CC
thì chưa chắc
CraB ,
.
Từ đó suy ra với
đủ nhỏ thì
Caxa
.
Điều kiện đủ: Không giảm tổng quát, ta giả sử a = 0. Gọi
nie
i
, ,2,1
là véctơ
đơn vị thứ i của
n
. Theo giả thiết điều kiện đủ, với
i
ex
tồn tại
0
i
sao
cho
Ce
i
, trong đó
1
1
n
i
i
xx
với
nT
xxxx , ,,
21
. Lấy
nieu
ii
, ,2,1
. Vì C là tập lồi nên
Cu
i
. Với mọi
Bxxxx
10
n
i i i
ii
i I i I i
x x x
x u u
.
Vì
Bx
nên
n
i
i
xx
1
1
, hay
. Vậy
CB
.
Mệnh đề I.12 [1]. Cho
n
C
là một tập lồi. Giả sử
riCx
. Khi đó với mọi
Cy
,
tất cả các điểm trên đoạn thẳng nối x và y, có thể trừ y, đều thuộc
riC
. Nói cách
khác với mọi
1,0
thì
riCCriC
1
.
Chứng minh
Không mất tính tổng quát, bằng cách lấy bao affine, ta có thể giả sử
naffC dim
, suy ra
=
CBx
1
1
1
.
Đặt
BxD
Hay
riCCriC
1
.
Từ mệnh đề trên ta rút ra hệ quả sau:
Hệ quả. Nếu C lồi thì riC lồi.
Chứng minh
Thật vậy, vì
CriC
nên từ mệnh đề trên ta suy ra
1,0,1
riCriCriC
18
Hay riC là tập lồi.
Chúng ta biết rằng nếu một tập
n
C
có thứ nguyên không đầy đủ hay
nC dim
thì C không có điểm trong. Mệnh đề sau chỉ ra rằng mọi tập lồi trong
n
đều biểu diễn được
dưới dạng
j
m
j
j
xx
0
với
1
0
m
j
j
.
Từ đó suy ra với
t
nào đó thì
j
m
j
m
j
j
nên
Caxta
.
Theo mệnh đề I.11, ta có
riCa
.
I.2. HÀM LỒI
Trong chương trình toán học phổ thông, chúng ta đã làm quen với khái niệm hàm
lồi (sử dụng tính chất lồi, lõm của hàm số để vẽ đồ thị và chứng minh bất đẳng
thức). Trong phần này, tác giả trình bày khái niệm tổng quát về hàm lồi và những
tính chất quan trọng của nó.
Định nghĩa I.16 [2 ]. Cho X là không gian lồi địa phương; D
X.
: { }fD
. 19
Trên đồ thị của hàm f, kí hiệu: epif, được định nghĩa:
Epif:=
là ảnh của tập lồi qua ánh xạ tuyến tính.
Vậy,
omfD
là tập lồi .
Ví dụ
1. Cho
C
, lồi. Hàm chỉ
0,
,
C
x
là một hàm lồi.
2. Hàm chuẩn Euclide trên
n
:
1
2 2 2
2
(0,1)
Nếu
x domf
hoặc
omfyd
thì
()fx
hoặc
()fy
.
Suy ra
nếu
Cx
nếu
Cx
20
( ) (1 ) ( )f x f y
Định lí đúng.
Nếu
, omfx y d
( (1 ) ) 1f x y f x f y
.
*Điều kiện đủ: Ngược lại, lấy
(x,r) Epif, (y,s) Epif, [0,1]
, Ta cần chỉ ra:
( , ) (1 )( , ) ifx r y s Ep
.
Thật vậy
( ) ; ( )
( (1 ) ) (x)+ (1- )f(y)
(1 )
( (1 ) , (1 ) ) if
(x,r)+ (1- )(y,s) Epif
f x r f y s
f x y f
rs
x y r s Ep
epifepig
. Bao đóng của f ký hiệu là
f
.
Nhận xét
1. Từ định nghĩa của epif, ta thấy rằng một hàm lồi hoàn toàn được xác định nếu 21
biết epif.
2. Nếu f là hàm lồi trên một tập lồi
n
C
thì ta có thể khai triển f lên toàn
không gian
n
bằng cách đặt
,
,xf
xf
e
Định nghĩa I.21[2]. Cho
n
C
là một tập lồi khác rỗng.
Hàm
:
n
f
được gọi là lồi chặt trên C nếu
, , 0,1x y C
ta có:
11f x y f x f y
.
Hàm
:
n
f
được gọi là lồi mạnh trên C với hệ số
nếu
Mệnh đề I.14 (Bất đẳng thức Jensen) [1].
Nếu f là hàm lồi xác định và nhận giá trị hữu hạn trên tập lồi C thì, với mọi
1
, ,
m
x x C
,
*
mN
và
0
j
thỏa mãn
1
1
m
j
j
, ta có:
nếu
Cx
nếu
Cx
Với m = 2: Bất đẳng thức (1.5) được suy ra từ hàm lồi.
Giả sử bất đẳng thức đúng với m – 1, ta chứng minh nó đúng với m. Thật vậy, giả
sử
1
m
, đặt
1
1
m
j
j
. Khi đó
0
và
m
m
j
m
j
j
m
m
j
1
1
m
j
j
nên điểm
Cxy
j
m
j
j
1
1
.
Mặt khác
1
1
1
11
.
Ta suy ra
j
m
j
j
m
j
j
j
xfxf
Chứng minh
Điều kiện cần: Giả sử f là hàm lồi trên C. Khi đó
yfxfCyx
,,,
ta suy ra
,x
và
,y
đều thuộc epif . Do f là hàm lồi nên epif là tập lồi. Từ đó 23
1,0,,1,
epifyx
.
Suy ra
epifyx
1,1
11 yxf
Hay
.,1, epifyx
Vậy epif là tập lồi hay f là hàm lồi trên C.
Định nghĩa I.21[2]. Hàm f xác định trên X gọi là thuần nhất dương nếu
)()( xfxf
,
Xx
,0
.
Định lý I.2. Hàm thuần nhất dương
;: Xf
là hàm lồi khi và chỉ khi:
yfxfyxf
1
2
.
hay là
yfxfyxf
.
b) Ngược lại, giả sử
yfxfyxf
Xyx ,
Lấy
2,1, iepifrx
ii
, vì
212121
rrxfxfxxf
cho nên
1 2 1 2
,x x r r epif
.
Hơn nữa, vì f là hàm thuần nhất dương, nên nếu
epifrx ,
i
im
:
mmmm
xfxfxxf
1111
.
Hệ quả 2. Giả sử f là hàm lồi chính thường, thuần nhất dương. Khi đó,
:Xx
0 xfxf
.
I.3. Các phép toán về hàm lồi
Định lý I.3. Giả sử
m
ff , ,
1
là các hàm lồi chính thường trên X. Khi đó, tổng
m
ff
1
là một hàm lồi.
Định lý I.4. Giả sử F là tập lồi trong
là hàm lồi trên X.
Định lý I.6. Giả sử
If
là các hàm lồi trên X. Khi đó, các hàm:
xfSup
I
và
xf
I
inf
là hàm lồi.
Để hiểu rõ hơn về các phép toán trên, độc giả có thể xem [2], từ trang 47 đến
trang 50.
Tóm lại: Nội dung chương I đề cập tới tập lồi, hàm lồi và và các tính chất liên
quan: Dấu hiệu nhận biết, các phép toán,… Bên cạnh đó là một số tập lồi quan
trọng: Tập affine, nón,…. Vấn đề dưới vi phân của hàm lồi sẽ được trình bày ở
chương sau.
, kí hiệu:
( , )f x d
được
định nghĩa là giới hạn:
( , )f x d
=
0
( ) ( )
lim
f x d f x
,
nếu giới hạn này tồn tại (hữu hạn hoặc vô hạn).
Nhận xét.
( , )f x d
là hàm thuần nhất dương.
Thật vậy
( , )f x d
=
0
có đạo hàm
phải
,
tại mọi điểm của dom
. Đồng thời,
)(
,
t
là hàm không giảm và nhận giá
trị hữu hạn khi
)int(
domt
.
Copyright: Tài liệu đại học ©