LèI CÁM ƠN

Em xin đưoc gúi lòi cám ơn tói các thay giáo, cô giáo trong to
Giái tích và các ban sinh viên khoa Toán trưòng Đai hoc Sư pham Hà
N®i 2.
Đ¾c bi¾t, em xin bày tó lòng biet ơn sâu sac tói thay Nguyen
Văn Tuyên đã t¾n tình giúp đõ em trong suot quá trình hoc t¾p,
nghiên cúu và hoàn thành khóa lu¾n tot nghi¾p.
Cuoi cùng, em muon gúi lòi cám ơn tói gia đình và ban bè đã
luôn quan tâm, đ®ng viên em trong quá trình hoc t¾p và nghiên cúu.
Em xin chân thành cám ơn !

Hà N®i, tháng 5 năm 2013
Sinh viên

Nguyen Ngoc Mai


LèI CAM ĐOAN

Em xin cam đoan dưói sn hưóng dan cna thay giáo Nguyen Văn
Tuyên khóa lu¾n tot nghi¾p "Các đieu ki¾n toi ưu theo dãy cho
bài toán toi ưu trơn vái ràng bu®c phiem hàm" đưoc hoàn thành
không trùng vói bat kì công trình nghiên cúu khoa hoc nào khác.
Trong khi thnc hi¾n nghiên cúu khoa hoc em đã sú dung và tham
kháo các thành tnu cna các nhà khoa hoc vói lòng biet ơn trân trong.

Hà N®i, tháng 5 năm 2013
Sinh Viên

Nguyen Ngoc Mai

ii


BÁNG KÝ HIfiU
• N = {0, 1, 2, ...}.
• "·" kí hi¾u m®t chuan bat kì.
• Neu h : Rn → Rm, h = (h1, ..., hn) thì ∇h := (∇h1, ..., ∇hm).
• R+ = {t ∈ R | t ≥ 0}.
• Neu ν ∈ Rn, ta kí hi¾u ν+ = (max ν1, 0, ..., max νn, 0)T .
• Neu ν ∈ Rn, ta kí hi¾u ν− = (min , 0, ..., min , 0)T .
ν1
νn
• A ⊂ B có nghĩa rang t¾p A đưoc chúa trong t¾p B.
• B(x, δ) = {z ∈ Rn | "z − x" ≤ δ}.
• ΠΩ(x) là hình chieu Euclide cna x trên Ω.

3


Mnc lnc

Má đau

1

1 M®t so kien thNc chuan b%

4


1.1. M®t so kien thúc cơ só ve giái tích loi . . . . . . . . . . .

4

1.1.1. T¾p loi . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.2. Hình chieu . . . . . . . . . . . . . . . . . . . . . .

7

1.1.3. Các đ%nh lý tách............................................................. 11
1.1.4. Nón..................................................................................... 12
1.1.5. Hàm loi...............................................................................14
1.1.6. Hàm loi khá vi...................................................................15
1.1.7. Dưói vi phân......................................................................18
1.2. Các đieu ki¾n toi ưu cho bài toán toi ưu trơn có ràng bu®c 21
1.2.1. Các đieu ki¾n cho bài toán toi ưu không có ràng
bu®c...................................................................................21
1.2.2. Các đieu ki¾n cho bài toán toi ưu có ràng bu®c .

22

2 Các đieu ki¾n toi ưu theo dãy cho bài toán toi ưu trơn
có ràng bu®c

35



2.1. Các đieu ki¾n KKT-xap xí...........................................................35
2.1.1. AKKT(I) là m®t đieu ki¾n toi ưu . . . . . . . . .

38

2.1.2. AKKT(I) là m®t đieu ki¾n toi ưu manh . . . . . .

42

2.2. Các đieu ki¾n chieu gradient gan đúng.....................................44
2.2.1. Đieu ki¾n C-AGP.............................................................46
2.2.2. Đieu ki¾n L-AGP.............................................................52
Ket lu¾n

54

Tài li¾u tham kháo

54


Mé ĐAU

1. Lý do chon đe tài
Trong khóa lu¾n này chúng tôi trình bày các đieu ki¾n toi ưu
b¾c nhat theo dãy cho bài toán quy hoach phi tuyen. Các đieu ki¾n
toi ưu can phái thóa mãn cnc tieu cna bài toán toi ưu hóa. Thông
thưòng, các đ%nh lý ho tro m®t đieu ki¾n toi ưu có dang: ‘Neu cnc
tieu đ%a phương x thóa mãn CQ, thì nó thóa mãn KKT, trong đó
KKT là viet tat cna các đieu ki¾n Karush -Kuhn-Tucker và CQ là m®t

ràng bu®c chính quy. Nói cách khác, thưòng thì các đieu ki¾n toi ưu
can b¾c nhat ó dang KKT ho¾c không là CQ’.
Trên thnc te, phương pháp so đe giái các bài toán toi ưu hóa có
ràng bu®c thưòng đưoc sú dung là phương pháp l¾p. Ngưòi ta phái
quyet đ%nh ó moi lan l¾p có thnc hi¾n bưóc l¾p tiep theo thu¾t toán
hay ket thúc thu¾t toán. Do vi¾c kiem tra tính toi ưu thnc sn là rat
khó, nên m®t cách tn nhiên chúng ta se ket thúc thu¾t toán khi m®t
đieu ki¾n can toi ưu thóa mãn m®t cách xap xí. Tuy nhiên, hau het
các phương pháp giái so bài toán toi ưu không kiem tra đưoc tat cá
các đieu ki¾n chính qui ràng bu®c, m¾c dù các đieu ki¾n KKT (xap
xí) luôn luôn đưoc thóa mãn. Nhieu ngưòi dưòng như không nh¾n
thay rang các ràng bu®c chính quy ton tai. Vi¾c tính toán này có the
kiem tra đưoc bang các tính chat lý thuyet cna cnc tieu đ%a phương:
Can nhan manh rang, m®t cnc tieu đ%a phương có the không phái là
KKT, nhưng nó có the luôn luôn đưoc xap xí bói m®t dãy các điem
‘KKT-xap xí’.
1


Thnc te này dan đen vi¾c nghiên cúu m®t loai đieu ki¾n toi ưu
khác. Chúng ta nói rang x thóa mãn ‘đieu ki¾n toi ưu theo dãy’ đưoc
xác đ%nh bói m¾nh đe toán hoc P neu ton tai m®t dãy {xk} h®i tu đen
x và thóa mãn P({xk}). Thông thưòng, m®t đieu ki¾n toi ưu theo
dãy tương úng vói m®t đai lưong sk nào đó mà sk → 0. Các tiêu chuan
dùng tn nhiên tương úng vói các đieu ki¾n toi ưu theo dãy chí ra đe
dùng vi¾c thnc hi¾n thu¾t toán khi sk là đn nhó.
Các đieu ki¾n toi ưu can theo dãy có các yêu cau tương tn như
các đieu ki¾n toi ưu thông thưòng: Chúng phái đưoc thóa mãn bói các
cnc tieu cna bài toán, và chúng càng manh càng tot. Hơn nua, các đieu
ki¾n toi ưu huu ích (hay là thu¾t toán đ%nh hưóng) se đưoc tương

úng vói m®t so thu¾t toán thnc te.

2. Mnc đích nghiên cNu
Nghiên cúu ve các đieu ki¾n toi ưu theo dãy cho bài toán toi ưu
trơn vói ràng bu®c phiem hàm.

3. Nhi¾m vn nghiên cNu
-Nghiên cúu lý thuyet cơ só ve giái tích loi.
-Nghiên cúu ve các đieu ki¾n toi ưu cho bài toán toi ưu trơn có
ràng bu®c.
-Nghiên cúu ve các đieu ki¾n KKT-xap xí.
-Nghiên cúu ve các đieu ki¾n chieu gradient gan đúng.


4. Phương pháp nghiên cNu
Tra cúu tài li¾u, phân tích, so sánh, tong hop.

5. Cau trúc khóa lu¾n
Khóa lu¾n đưoc bo cuc như sau:
Chương 1. Trình bày m®t so kien thúc cơ só ve giái tích loi.
Trong chương này có trình bày m®t so tính chat cơ bán ve t¾p loi,
hàm loi và các đieu ki¾n toi ưu cho bài toán toi ưu trơn có ràng bu®c.
Chương 2. Trình bày các đieu ki¾n toi ưu theo dãy cho bài toán
toi ưu trơn có ràng bu®c. N®i dung chính cna chương này trình bày
chi tiet các ket quá trong bài báo [2]. Muc 2.1 trình bày các đieu ki¾n
KKT xap xí. Muc 2.2 trình bày các đieu ki¾n chieu gradient xap xí.


Chương 1
M®t so kien thNc chuan b%

1.1.
1.1.1.

M®t so kien thNc cơ sá ve giái tích loi
T¾p loi
Khái ni¾m t¾p loi là khái ni¾m quan trong trong lý thuyet toi ưu.

T¾p loi là t¾p mà khi lay 2 điem bat kì cna t¾p thì đoan thang noi 2
điem đó cũng nam trong t¾p đó.
Đ%nh nghĩa 1.1. T¾p X ⊂ Rn đưoc goi là t¾p loi neu vói moi x1, x1 ∈
X
và vói moi t ∈ (0; 1) thì: (1 − t)x1 + tx2 ∈ X.
Bo đe 1.1. Cho I là m®t t¾p bat kì. Neu các t¾p Xi ⊂ Rn, vói i ∈ I,
T
là các t¾p loi thì t¾p X =
Xi là t¾p loi.
i∈I

Chúng minh. Ta xét 2 trưòng hop:
T
+Neu X = Xi = ∅ thì X là t¾p loi tam thưòng.
i∈I

+Neu X =

T

Xi ƒ= ∅, ta có: ∀x, y ∈

T


suy ra
i∈I

i∈I

Xi, ∀t ∈ (0; 1),


x, y ∈ Xi, ∀i ∈ I. Khi đó, (1 − t)x + ty ∈ Xi, ∀i ∈ I, suy ra (1 − t)x
+ ty ∈
T
Xi, ∀i ∈ I. V¾y X là t¾p loi.
i∈I


Bo đe 1.2. Cho X, Y là t¾p loi trong Rn và các so thnc λ, µ. Khi đó,
λX + µY là t¾p loi.
Chúng minh. Lay tùy ý x, y ∈ λX + µY , vói moi t ∈ (0; 1). Suy ra,
x = λx1 + µy1( vói x1 ∈ X, y1 ∈
Y ), y = λx2 + µy2( vói x2 ∈ X, y2
∈ Y ).
Khi đó
(1 − t)x + ty
= (1 − t)(λx1 + µy1) + t(λx2 + µy2)
= λ((1 − t)x1 + tx2) + µ((1 − t)y1 + ty2).
Do X, Y là các t¾p loi nên λ((1 − t)x1 + tx2) ∈ λX và µ((1 − t)y1 +
ty2) ∈
µY . Suy ra, λ((1 − t)x1 + tx2) + µ((1 − t)y1 + ty2) ∈ λX +
µY hay

(1 − t)x + ty ∈ λX + µY . V¾y λX + µY là t¾p loi.
Đ%nh nghĩa 1.2. M®t điem x đưoc goi là to hop loi cna các điem
x1, x2, ..., xm, neu ton tai các so thnc không âm α1, α2, ..., αm sao cho
x = α1x1 + α2x2 + ... + αmxm
và
α1 + α2 + ... + αm = 1.
Đ%nh nghĩa 1.3. Bao loi cna X ( kí hi¾u: convX) là giao cna tat cá các
t¾p loi chúa X.
Bo đe 1.3. Bao loi cúa X là t¾p hop các to hop loi cúa các điem thu®c
X.
m

m


convX = {x | x =

.

αixi, xi ∈ X, α ≥ 0,

N}.
i=1

i=1

.

αi = 1, m ∈



Chúng minh. Xét t¾p Y là to hop loi cna tat cá các điem thu®c X. Neu
y1 ∈ Y, y2 ∈ Y , khi đó:
y1 = α1x1 + α2x2 + ... +
αmxm, y2 = β1 z1 + β2 z2 +
... + βl zl ,
trong đó, x1, ..., xm, z1, ..., zm ∈ X, các h¾ so α, β là các h¾ so không
âm
và
l
. m
.
αi = 1,
βi = 1.
i=1

i=1

Do đó, vói moi t ∈ (0; 1) thì
m

l

.

(1 − t)y1 + ty2 = (1 − t)αixi +
i=1

.


tβizi

i=1

là m®t to hop loi cna các điem x1, ..., xm, z1, ..., zm. Do đó, t¾p Y là
t¾p loi. Rõ ràng, Y ⊃ X. Vì v¾y,
convX ⊂ Y
M¾t khác, neu y ∈ Y thì y là m®t to hop loi cna tat cá các điem thu®c
X và phái đưoc chúa trong moi t¾p loi chúa X. Do đó, convX ⊃ Y .
Đen đây ta hoàn thành đieu phái chúng minh.
Bo đe 1.4. (Đ%nh lý Carathéodory) Neu X ⊂ Rn thì moi phan tú
cúa convX là to hop loi cúa không quá (n + 1) điem thu®c X.
Chúng minh. Cho x là m®t to hop loi cna m > n + 1 điem thu®c X.
Ta se chí ra rang m có the b% giám giá tr% đi m®t đơn v%. Neu αj =
0 vói m®t vài j thì ta có the xóa điem thú j đó và thnc hi¾n. Vì v¾y,
cho tat cá αi > 0. Vì m > n + 1, ton tai các so γ1, γ2, ...., γm không
đong thòi bang 0, do đó:
. 1.
γ1 x
1

+ γ2

.

2.

x
1


+ ... + γm


.

x

1

m.

Đ¾t τ =

γ

min{αi

i

= 0.

(1.1)

: γi > 0}. Chú ý rang τ đưoc đ%nh nghĩa tot vì m®t
vài

γj > 0, neu tong cna chúng bang 0. Đ¾t α¯ i = αi − τ γi, i = 1, 2, ...,
m. Tù

.


(1.1) ta có

m
i=
1

α¯ i = 1 và i= α¯ ixi = x. Tù cách đ¾t cna τ , ít nhat
.m
1 có

m®t α¯ j = 0 và ta có the xóa điem thú j đó. Cú tiep tuc quá trình
trên, ta có the giám giá tr% cna m tói n + 1.
Bo đe 1.5. Neu X ⊂ Rn là t¾p loi thì khi đó intX và X cũng là các
t¾p loi.
Chúng minh. Cho B là m®t hình cau đơn v%. Neu x1 ∈ intX, x2 ∈
intX, khi đó, ta có the tìm ε > 0 sao cho x1 + εB ⊂ X và x2 + εB ⊂
X. Do đó, (1 − t)x1 + tx2 + εB ⊂ X vói t ∈ (0; 1). Vì v¾y, (1 −
t)x1 + tx2 ∈ intX. Đe chúng minh phan 2 cna bo đe, ta cho xk → x
và yk → y vói xk ∈ X và yk ∈ X. Khi đó, dãy cna các điem
(1 − t)xk + tyk
chúa trong X và h®i tu tói (1 − t)x + ty ∈ X.
1.1.2.

Hình chieu
Cho m®t t¾p loi, đóng V ⊂ Rn và x ∈ Rn. Ta goi t¾p hop các

điem trong V gan nhat đoi vói điem x là hình chieu cna x trên V và kí
hi¾u là: ΠV (x).
ΠV (x) = {z ∈ V | "z − x" = inf "y − x"}.

y∈V

(Ta nói điem z ∈ V đưoc goi là điem gan nhat đoi vói x hay z là
chân hình chieu cna x trên V neu "z − x" = inf "y − x").
y∈V


Đ%nh lý 1.1. Cho V ⊂ Rn là t¾p loi, đóng và khác rong. Khi đó, vói
moi x ∈ Rn, ton tai duy nhat điem là chân hình chieu cúa x trên V .


Chúng minh. Đ¾t µ = inf "y − x" . Vì V ƒ= ∅ nên 0 ≤ µ < +∞.
Lay
y∈V

{yk ⊂ V } sao cho yk − x → µ. Rõ ràng {yk} là dãy b% ch¾n. Khi
đó,

j

}klà dãy con cna {yk} sao cho lim
y

j

j

= z. Vì
} ⊂ V và
k

{y
j→∞
k
y − x = µ = inf "y − x" .

ton tai
{yk
V là t¾p đóng nên z ∈ V ,
"z − x" =
lim

k→∞

y∈V

Suy ra z là hình chieu cna x trên V .
Giá sú z1, z2 là chân hình chieu cna x trên V (z1, z2 ∈ ΠV
(x)).
Chon
z¯ =
+ z2

2

z1

ta có z¯ ∈ V . Khi đó,
2

1


2

2

2

"z1 − z2 " = µ − "z − x"

4
suy ra z1 = z2. V¾y đ%nh lý đã đưoc chúng minh.
Bo đe 1.6. Giá sú V ⊂ Rn là m®t t¾p loi, đóng, khác rong và x ∈ Rn.
Khi đó, z = ΠV (x) khi và chs khi z ∈ V, (v − z, x − z) ≤ 0 ∀v ∈ V.
Chúng minh. Giá sú z = ΠV (x) và z ∈ V, v ∈ V . Đ¾t:
w(α) = αv + (1 − α)z, α ∈ [0; 1], w(α) ∈ V.
Do z = ΠV (x), suy ra
"w(α) − x" ≥ "z − x" , ∀α ∈ [0; 1]
hay là

Ta
có:

"w(α) −
x"

, ∀α ∈ [0; 1].

2

≥ "z −

2
x"


"w(α) −

2

= (α(v − z) + z − x, α(v − z) + z − x)
2

x"
= α2 "v −
z"

2

+ 2α (v − z, z − x) + "z − x"

2

≥ "z − x" , ∀α ∈ [0; 1].
Suy ra α2 "v − z"

+ 2α (v − z, z − x) + "z − ≥ 0, ∀α ∈ [0; 1].

2

2


x"
Vói α ∈ [0; 1] : (v − z, x − z) 2≤
− z"

1

2

α "v

. Cho α → 0+ suy ra

(v − z, x − z) ≤ 0.
Ngưoc lai, giá sú rang z ∈ V và (v − z, x − z) ≤ 0, ∀v ∈ V.
Suy ra, vói v = ΠV (x) thì
(ΠV (x) − z, x − z) ≤ 0.

(1.2)

Theo chúng minh ó phan thu¾n ta có:
(v − ΠV (x), x − ΠV (x)) ≤ 0, ∀v ∈ V
(z − ΠV (x), x − ΠV (x)) ≤ 0.

suy
ra

(1.3)

C®ng theo ve cna (1.2) và (1.3), ta đưoc:
(ΠV (x) − z, ΠV (x) − z) ≤ 0.

Suy ra

"ΠV (x) −
z"

2

≤ 0.

V¾y ΠV (x) =
z.

Nh¾n xét: Neu V là m®t đa tap tuyen tính, túc là vói moi x, y ∈


V , vói moi α, β ∈ R suy ra αx + βy ∈ V , thì vói moi v ∈ V , w
= 2ΠV (x) − v ∈ V. Ta có:
(v − ΠV (x), x − ΠV (x)) ≤ 0, ∀v ∈ V

(1.4)

(w − ΠV (x), x − ΠV (x)) ≤ 0.

và

(ΠV (x) − v, x − ΠV (x)) ≤ 0,

Suy
ra


(v − ΠV (x), x − ΠV (x)) ≥ 0.

hay là

(1.5)

Tù (1.4) và (1.5) ta có: (v − ΠV (x), x − ΠV (x)) = 0, suy ra:
v − ΠV (x) ⊥ x − ΠV (x).
Đ%nh lý 1.2. Giá sú V ⊂ Rn là m®t t¾p loi, đóng và khác rong. Khi đó,
vói moi x, y ∈ Rn ta có: "ΠV (x) − ΠV (y)" ≤ "x − y".
Chúng minh. Tù Bo đe 1.6 ta có:
(ΠV (y) − ΠV (x), x − ΠV (x)) ≤ 0,

(1.6)

(ΠV (x) − ΠV (y), y − ΠV (y)) ≤ 0.

(1.7)

C®ng theo ve cna (1.6) và (1.7) ta có:
(ΠV (x) − ΠV (y), (ΠV (x) − ΠV (y)) + (y − x)) ≤ 0 (1.8)
2

⇒ "ΠV (x) − ΠV (y)" + (ΠV (x) − ΠV (y), y − x) ≤ 0.
Ta
có:

1

"(ΠV (x) − ΠV (y)) + (y − x)"

1
2
2 + (ΠV (x) − ΠV (y), y − x) .
= "ΠV (x) − ΠV
"y −
2
2
(y)" +
x"
1

0≤

2

2


Tù (1.8)

2

1
≤

2
(y)"

1


2

2

2
+ "y −
x"

"ΠV (x) − ΠV
1
⇒ ("y −
2
x"

− "ΠV (x) − ΠV (y)"

2

2

− "ΠV (x) − ΠV
(y)"

)≥0

⇒ "ΠV (x) − ΠV (y)" ≤ "y − x" .
Đ%nh lý đưoc chúng minh.


1.1.3.


Các đ%nh lý tách

Đ%nh lý 1.3. Giá sú X ⊂ Rn là m®t t¾p loi, đóng, khác rong và x ∈/
X.
Khi đó, ton tai y ∈ Rn, y ƒ= 0 và ε > 0.
(y, v) ≤ (y, x) − ε, ∀v ∈ X.
Chúng minh. Goi z = ΠV (x) theo Bo đe 1.6, ta có (x − z, v − z)
≤
0, ∀v ∈ X. Đ¾t y = x − z suy ra (y, v − z) ≤ 0, ∀v ∈ X. Khi đó
2

(y, v) ≤ (y, z) = (y, x − y) = (y, x) − "y" .
(y, v) ≤ (y, x) − ε,

Suy ra
2

vói ε =
"y"

. Do x ∈/ X, suy ra y ƒ= 0 v¾y ε > 0.

Đ%nh lý 1.4. Cho X ⊂ Rn là t¾p loi, khác rong, x ∈/ X. Khi đó, ton
tai
y ∈ Rn, y ƒ= 0 sao cho
(y, v) ≤ (y, x) , ∀v ∈ X.
Chúng minh. Lay (xk) ⊂ Rn X, xk → x khi k → ∞. Vói moi xk ton tai
yk ƒ= 0, εk > 0:


.

k

.

.

k

k

.

.

k

y , v ≤ y , x − εk ≤ y , x
.
. .
.
⇒ y k , v < y k , xk .

k

.

Do yk ƒ= 0, ∀k, nên ta coi y k = 1. Do B(0; 1) là t¾p compact trong
Rn

nên (yk) ⊂ B(0; 1). Suy ra ton tai dãy con (ykl ) ⊂ (yk ) sao cho: lim
yk l =


.

.

.

.

l→∞

y ∈ B(0; 1). Tù ykl , v < ykl , xkl vói moi l và tích vô hưóng là
m®t
hàm liên tuc theo 2 bien nên cho l → ∞ ta đưoc: (y, v) ≤ (y, x) , ∀v ∈
X,
vói "y" = 1.


Đ%nh lý 1.5. Giá sú X1, X2 ⊂ Rn là các t¾p loi. Neu X1 ∩ X2 = ∅
thì
khi đó ton tai y ƒ= 0, y ∈ Rn sao cho:
.
.
.
.
1
2

y, x ≤ y, x , ∀x1 ∈ X1, x2 ∈ X2.
Chúng minh. Đ¾t:
X = X1 − X2 = {x = x1 − x2 | x1 ∈ X1, x2 ∈ X2}.
Do X1 ∩ X2 = ∅ nên 0 X. Tù X1, X2 là hai t¾p loi, suy ra X là t¾p
∈/
loi. Theo Đ%nh lý 1.4 ta có:
(y, v) ≤ 0, ∀v ∈ X
.
.
⇒ y, x1 − x2 ≤ 0, ∀x1 ∈ X1, x2 ∈ X2
.
.
.
.
⇒ y, x1 ≤ y, x2 , ∀x1 ∈ X1, x2 ∈ X2.

Đ%nh lý 1.6. Cho X1, X2 ⊂ Rn là hai t¾p con loi đóng và X1 b% ch¾n.
Neu X1 ∩ X2 = ∅ thì ton tai y ∈ Rn, y ƒ= 0 và ε > 0 sao cho:
.
.
.
.
y, x1 ≤ y, x2 − ε, ∀x1 ∈ X1, x2 ∈ X2.
Chúng minh. Tù X1, X2 là các t¾p đóng và X1 b% ch¾n, suy ra X =
X1 − X2 là t¾p đóng và X là t¾p loi. Do 0 ∈/ X, theo Đ%nh lý 1.3
ton tai y ƒ= 0, ε > 0 sao cho (y, v) ≤ −ε, ∀v ∈ X. Suy ra:
.
.
1
2

y, x − x ≤ −ε, ∀x1 ∈ X1, x2 ∈ X2.
.
. .
.
Do đó y, x1 ≤ y, x2 − ε, ∀x1 ∈ X1, x2 ∈ X2.
1.1.4.

Nón


Đ%nh nghĩa 1.4. M®t t¾p K ⊂ Rn đưoc goi là nón neu vói moi x ∈
K, và vói moi α > 0 ta có: αx ∈ K. K đưoc goi là nón loi neu K là
m®t nón và là m®t t¾p loi.


Bo đe 1.7. Cho K là m®t nón loi. Khi đó, neu x1 ∈ K, x2 ∈ K, ..., xm
∈
K và α1 > 0, α2 > 0, ..., αm > 0 thì α1x1 + α2x2 + ... + αmxm ∈
K.
Chúng minh. Bang tính loi, ta có:
α1x1 + α2x2 + ... + αmxm
∈ K.
α1 + α2 + ... + αm
Vì K là nón, ta có the nhân ve trái vói α1 + α2 + ... + αm và ta
đưoc đieu phái chúng minh.
Đ%nh nghĩa 1.5. T¾p cone(X) = {αx | x ∈ X, α ≥ 0} đưoc goi là
nón sinh bói t¾p X.
Bo đe 1.8. Neu X là t¾p loi thì cone(X) là m®t t¾p loi.
Đ%nh nghĩa 1.6. Cho x ⊂ Rn, t¾p KX (x) = cone(X − x) đưoc goi
là

nón các phương chap nh¾n đưoc cna X tai x.
Đ%nh nghĩa 1.7. Cho X ⊂ Rn là m®t t¾p loi. T¾p
X∞ = {d ∈ Rn | X + d ⊂ X}
đưoc goi là nón lùi xa cna X.
Đ%nh nghĩa 1.8. Cho K là m®t nón trong Rn. T¾p
Ko = {y ∈ Rn : (y, x) ≤ 0, ∀x ∈ K}
đưoc goi là nón cnc cna X.
Đ%nh nghĩa 1.9. Cho X là m®t t¾p loi trong Rn và x ∈ X. T¾p
o

NX (x) = [cone(X − x)]
đưoc goi là nón pháp tuyen đoi vói X tai x.

Nh¾n xét : v ∈ NX (x) ⇔ (v, y − x) ≤ 0, ∀y ∈ X.


1.1.5.

Hàm loi
Kí hi¾u R := R ∪ {+∞, −∞} và goi là t¾p so thnc mó r®ng.

Cho hàm f : Rn → R. Ta có:
Mien huu hi¾u cna f : domf := {x ∈ Rn | f (x) <
+∞}. Đo th% cna hàm f : gphf := {(x, f (x)) | x ∈
domf }.
Trên đo th% cna f : epif := {(x, v) ∈ Rn × R : v ≥ f (x)}.
Đ%nh nghĩa 1.10. Hàm f đưoc goi là hàm loi neu epif là t¾p loi.
Hàm f đưoc goi là hàm lõm neu −f là hàm loi.
Hàm f đưoc goi là hàm chính thưòng neu f (x) > −∞, vói
moi

x ∈ Rn và ton tai x¯ ∈ Rn sao cho f (x¯) < +∞.
Bo đe 1.9. (Bat đang thNc Jensen) M®t hàm f là loi khi và chs khi
vói moi x1, x2 ∈ Rn, vói moi t ∈ (0; 1):
f ((1 − t)x1 + tx2) ≤ (1 − t)f (x1 + tf (x2)).
Chúng minh. Giá sú f là hàm loi, ta có
(x1, f (x1), (x2, f (x2))) ∈ epif,
suy
ra

((1 − t)x1 + tx2, (1 − t)f (x1) + tf
(x2)) ∈ epif,

hay là

(1 − t)f (x1) + tf (x2) ≥ f ((1 − t)x1
+ tx2).

Ngưoc lai, giá sú bat đang thúc Jensen thóa mãn, ta lay
(x1, v1), (x2, v2) ∈ epif