ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

TRẦN VĂN PHƢỢNG

VỀ BÀI TOÁN TỐI ƢU
TRONG HỌC ĐỘ TƢƠNG TỰ

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019


ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

TRẦN VĂN PHƢỢNG

VỀ BÀI TOÁN TỐI ƢU
TRONG HỌC ĐỘ TƢƠNG TỰ
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Thanh Sơn



✶✳✶✳✸

❚è✐ ÷✉ ❤➔♠ ♠ö❝ t✐➯✉ ❜➟❝ ❤❛✐ ✈î✐ r➔♥❣ ❜✉ë❝ ❜➜t
✤➥♥❣ t❤ù❝

✶✳✷

✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳

✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✵

▼ët sè ♣❤÷ì♥❣ ♣❤→♣ ❣✐↔✐ ❜➔✐ t♦→♥ tè✐ ÷✉
✶✳✷✳✶

P❤÷ì♥❣ ♣❤→♣ ◆❡✇t♦♥ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✶

✶✳✷✳✷

P❤÷ì♥❣ ♣❤→♣ ❣✐↔♠ s➙✉ ♥❤➜t ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✸

✶✳✷✳✸

P❤÷ì♥❣ ♣❤→♣ ❤➔♠ ❝❤➢♥ ❧♦❣❛r✐t❤ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✺

✶✳✷✳✹

P❤÷ì♥❣ ♣❤→♣ ❝❤✐➳✉ ❣r❛❞✐❡♥t ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✶✽

❈❤÷ì♥❣ ✷ ❇➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü

❚r÷í♥❣ ❤ñ♣ ❦❤♦↔♥❣ ❝→❝❤ ❊✉❝❧✐❞❡ ❝â trå♥❣ sè ✳ ✳ ✳ ✳ ✷✽


✐✈
✷✳✷✳✷

P❤÷ì♥❣ ♣❤→♣ ❝❤✐➳✉ ❣r❛❞✐❡♥t ❝❤♦ ❜➔✐ t♦→♥ ❤å❝ ✤ë
t÷ì♥❣ tü ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✷✾

✷✳✷✳✸

❱➼ ❞ö sè ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✳ ✸✷

❑➳t ❧✉➟♥
❚➔✐ ❧✐➺✉ t❤❛♠ ❦❤↔♦

✸✻
✸✼


❇↔♥❣ ❦þ ❤✐➺✉
H

❦❤æ♥❣ ❣✐❛♥ ❍✐❧❜❡rt t❤ü❝

∇f

❣r❛❞✐❡♥t ❝õ❛ ❤➔♠ sè✱ ❣r❛❞

∇2 f


✤✐➸♠ ❝ü❝ t✐➸✉ ❤❛② ❝ü❝ t✐➸✉

f (x∗ )

❣✐→ trà ❝ü❝ t✐➸✉

n×n





ợ ữợ ở ồ tự tữ ợ
rt t r t t trt s
trt t ỳ ởt t ớ ổ trỏ
ừ õ ố ợ ởt qố ởt ũ tờ ợ ự ữủ
r ổ s t tr ở
tr ổ t
r tỹ t r t t ử t ỡ ỳ ồ
r ởt t tr tứ ừ ồ
t s t ởt t ọ tr ỹ rở ợ
ữợ õ ở t ồ õ

ồ ở tữỡ tỹ

r ởt ổ tờ qt ỡ tr ởt ổ
tr ữủ ũ ỳ
ố tữủ ố tữủ trũ
ọ ợ

x−y

A

A

=

t❤➻

(x − y)T I(x − y),
I

❜➡♥❣ ♠ët ♠❛ tr➟♥

(x − y)T A(x − y).

✭✵✳✵✳✶✮

❧➔ ♠ët ♠❛ tr➟♥ ✤ì♥ ✈à✳ ❇➙② ❣✐í✱ t❛ t❤❛②

✤è✐ ①ù♥❣ ♥û❛ ①→❝ ✤à♥❤ ❞÷ì♥❣

x, y ∈ Rn

✈➔ ✤à♥❤ ♥❣❤➽❛

▲÷✉ þ r➡♥❣ ❦❤✐ ✤â ✭✵✳✵✳✶✮ ❝❤➾ ❧➔ ♠ët ❣✐↔ ❦❤♦↔♥❣ ❝→❝❤✱ tù❝ ❧➔ ❤❛✐ ✤✐➸♠

0✳ ◆❤÷ ✈➟②✱ ✈✐➺❝ ①➙② ❞ü♥❣ ❦❤♦↔♥❣

❝❤ù❛ ♥❤ú♥❣ ✤è✐ t÷ñ♥❣ ❦❤æ♥❣ t÷ì♥❣ tü✳ ▼ët ♣❤➨♣ ✤♦ tèt✱

A✱

tr♦♥❣ tr÷í♥❣ ❤ñ♣ ♥➔② ✤➦❝ tr÷♥❣ ❜ð✐ ♠❛ tr➟♥
✐✮ ❑❤♦↔♥❣ ❝→❝❤ ❣✐ú❛ ❝→❝ ✤è✐ t÷ñ♥❣ t❤✉ë❝

S

♣❤↔✐ t❤ä❛ ♠➣♥ ❜❛ ✤✐➲✉✿

t❤❡♦ ♠❛ tr➟♥

A

❝➔♥❣ ♥❤ä

❝➔♥❣ tèt❀
✐✐✮ ❑❤♦↔♥❣ ❝→❝❤ ❣✐ú❛ ❝→❝ ✤è✐ t÷ñ♥❣ t❤✉ë❝

D t❤❡♦ ♠❛ tr➟♥ A ♣❤↔✐ t÷ì♥❣

✤è✐ ❧î♥❀
✐✐✐✮ ▼❛ tr➟♥

A ♣❤↔✐ t❤ä❛ ♠➣♥ ❝→❝ ✤✐➲✉ ❦✐➺♥ ✤➸ ①➙② ❞ü♥❣ ✤÷ñ❝ ❣✐↔ ❦❤♦↔♥❣

❝→❝❤✱ tù❝ ❧➔

A



✹
▼ö❝ ✤➼❝❤ ❝õ❛ ✤➲ t➔✐ ❧➔ tr➻♥❤ ❜➔② ✈✐➺❝ ❣✐↔✐ ❜➔✐ t♦→♥ tè✐ ÷✉ ♥↔② s✐♥❤
tr♦♥❣ ❤å❝ ✤ë t÷ì♥❣ tü ✭✵✳✵✳✷✮✱ ✭✵✳✵✳✸✮✳
◆ë✐ ❞✉♥❣ ❝õ❛ ✤➲ t➔✐ ❧✉➟♥ ✈➠♥ ✤÷ñ❝ tr➻♥❤ ❜➔② tr♦♥❣ ❤❛✐ ❝❤÷ì♥❣✳

❈❤÷ì♥❣ ✶✳ ❇➔✐ t♦→♥ tè✐ ÷✉ tr♦♥❣ ❦❤æ♥❣ ❣✐❛♥ ❤ú✉ ❤↕♥ ❝❤✐➲✉
◆ë✐ ❞✉♥❣ ❝❤➼♥❤ ❝õ❛ ❝❤÷ì♥❣ ♥➔② ❧➔ ❝→❝ ❦✐➳♥ t❤ù❝ ✈➲ tè✐ ÷✉ ❤â❛✳ ❈❤ó♥❣
tæ✐ ♥❤➢❝ ❧↕✐ ♠ët ❝→❝❤ sì ❧÷ñ❝ ❝→❝ ❦❤→✐ ♥✐➺♠ ❝ì ❜↔♥ ❝õ❛ ❜➔✐ t♦→♥ tè✐ ÷✉
✈➔ ♠ët sè ♣❤÷ì♥❣ ♣❤→♣ ❝❤♦ ❜➔✐ t♦→♥ tè✐ ÷✉ ❦❤æ♥❣ r➔♥❣ ❜✉ë❝✳ ❚r♦♥❣ ✤â✱
❝❤ó♥❣ tæ✐ ✤✐ s➙✉ ✈➔♦ tr➻♥❤ ❜➔② ❝❤✐ t✐➳t ♣❤÷ì♥❣ ♣❤→♣ ❝❤✐➳✉ ❣r❛❞✐❡♥t s➩
❞ò♥❣ ð ❈❤÷ì♥❣ ✷✳ ❚➔✐ ❧✐➺✉ t❤❛♠ ❦❤↔♦ ❝❤➼♥❤ ❝❤♦ ❝❤÷ì♥❣ ♥➔② ❧➔ ❬✷❪✱ ❬✹❪✳

❈❤÷ì♥❣ ✷✳ ❇➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü
❚r♦♥❣ ❝❤÷ì♥❣ ♥➔②✱ ❧✉➟♥ ✈➠♥ tr➻♥❤ ❜➔② ♥❤ú♥❣ ❝❤õ ✤➲ ❦❤→✐ q✉→t ✈➲ ❜➔✐
t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü✳ ❙❛✉ ✤â✱ ❝❤ó♥❣ tæ✐ ✤✐ ✈➔♦ tr➻♥❤ ❜➔② ❝❤✐ t✐➳t ❜➔✐
t♦→♥ ❍å❝ ✤ë t÷ì♥❣ tü t❤❡♦ ❧♦↕t✳ ❈á♥ ♠ët sè ❝❤õ ✤➲ r➜t t❤ó ✈à ❦❤→❝ ♥❤÷
❍å❝ ✤ë t÷ì♥❣ tü ♦♥❧✐♥❡✱ ❍å❝ ✤ë t÷ì♥❣ tü ❞ü❛ tr➯♥ ❧þ t❤✉②➳t t❤æ♥❣ t✐♥
✤➣ ❦❤æ♥❣ t❤➸ ✤÷ñ❝ tr➻♥❤ ❜➔② ❞♦ ❦❤✉æ♥ ❦❤ê ❝â ❤↕♥ ❝õ❛ ❧✉➟♥ ✈➠♥ ❝ô♥❣
♥❤÷ sü ❤↕♥ ❝❤➳ ✈➲ t❤í✐ ❣✐❛♥ ✈➔ ♥➠♥❣ ❧ü❝✳ ❙❛✉ ❝ò♥❣✱ ❝❤÷ì♥❣ ♥➔② tr➻♥❤
❜➔② ♣❤÷ì♥❣ ♣❤→♣ ❝❤✐➳✉ ❣r❛❞✐❡♥t ❝❤♦ ❇➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü ✈➔ ✈➼ ❞ö
sè ♠✐♥❤ ❤å❛ ❝❤♦ ♣❤÷ì♥❣ ♣❤→♣ ✤â✳ ❈❤÷ì♥❣ ♥➔② t❤❛♠ ❦❤↔♦ ❝→❝ t➔✐ ❧✐➺✉
❬✸❪✱ ❬✺❪✳
▲✉➟♥ ✈➠♥ ✤÷ñ❝ ❤♦➔♥ t❤➔♥❤ t↕✐ ❚r÷í♥❣ ✣↕✐ ❤å❝ ❑❤♦❛ ❤å❝ ✲ ✣↕✐ ❤å❝
❚❤→✐ ◆❣✉②➯♥✳ ❚r♦♥❣ q✉→ tr➻♥❤ ❤å❝ t➟♣ ✈➔ t❤ü❝ ❤✐➺♥ ❧✉➟♥ ✈➠♥ ♥➔②✱ ❚r÷í♥❣
✣↕✐ ❤å❝ ❑❤♦❛ ❤å❝ ✤➣ t↕♦ ♠å✐ ✤✐➲✉ ❦✐➺♥ tèt ♥❤➜t ✤➸ t→❝ ❣✐↔ ❤å❝ t➟♣✱
♥❣❤✐➯♥ ❝ù✉✳ ❚→❝ ❣✐↔ ①✐♥ ✤÷ñ❝ ❜➔② tä ❧á♥❣ ❜✐➳t ì♥ ❝❤➙♥ t❤➔♥❤ ✤➳♥ ❝→❝
t❤➛②✱ ❝æ tr♦♥❣ ❦❤♦❛ ❚♦→♥ ✲ ❚✐♥✱ tr♦♥❣ ❚r÷í♥❣ ✣↕✐ ❤å❝ ❑❤♦❛ ❤å❝ ✲ ✣↕✐
❤å❝ ❚❤→✐ ◆❣✉②➯♥✳ ✣➦❝ ❜✐➺t✱ t→❝ ❣✐↔ ①✐♥ ❜➔② tä ❧á♥❣ ❜✐➳t ì♥ s➙✉ s➢❝ tî✐

▼ö❝ ♥➔② s➩ tr➻♥❤ ❜➔② ❦❤→✐ ♥✐➺♠✱ ❦➳t q✉↔ ❝ì ❜↔♥ ✤➸ ❝â ❝→✐ ♥❤➻♥ ❦❤→✐
q✉→t ✈➲ ❜➔✐ t♦→♥ tè✐ ÷✉✳

✶✳✶✳✶ ❇➔✐ t♦→♥ tè✐ ÷✉
❈❤♦

f : Rn → R✳

❚➻♠ ❝ü❝ t✐➸✉ ✤à❛ ♣❤÷ì♥❣

x∗

f (x∗ ) ≤ f (x), ∀x ∈ Ux∗ ,
tr♦♥❣ ✤â✱

U x∗

❧➔ ❧➙♥ ❝➟♥ ✤à❛ ♣❤÷ì♥❣ ♥➔♦ ✤â ❝õ❛

min f (x).
x

❝õ❛

f✱

♥❣❤➽❛ ❧➔✱
✭✶✳✶✳✶✮

x∗ ✳ ✣➸ ♥❣➢♥ ❣å♥✱ t❛ ✈✐➳t

❇➔✐ t♦→♥ ❝ü❝ t✐➸✉ t♦➔♥ ❝ö❝ ✭❣❧♦❜❛❧ ♦♣t✐♠✐③❛t✐♦♥✮ ❧➔ ❜➔✐ t♦→♥ t➻♠ x∗
s❛♦ ❝❤♦

f (x∗ ) ≤ f (x), ∀x.

✭✶✳✶✳✹✮

✣✐➲✉ ❦✐➺♥ tè✐ ÷✉
❈→❝ ✤✐➲✉ ❦✐➺♥ ❝➛♥ t❤✐➳t ❝❤♦ sü tè✐ ÷✉ ✤÷ñ❝ rót r❛ ❜➡♥❣ ❝→❝❤ ❣✐↔ sû
r➡♥❣

x∗

∇f (x∗ )

❧➔ ✤✐➸♠ ❝ü❝ t✐➸✉ ✤à❛ ♣❤÷ì♥❣ ✈➔ s❛✉ ✤â ❝❤ù♥❣ ♠✐♥❤ t➼♥❤ ❝❤➜t ❝õ❛
✈➔

∇2 f (x∗ )✳

✣à♥❤ ❧þ ✶✳✶✳✶ ✭✣✐➲✉ ❦✐➺♥ ❝➛♥✮✳ ❈❤♦ f ∈ C 2(Ux ) ✈➔ x∗ ❧➔ ♠ët ❝ü❝ t✐➸✉
∗

✤à❛ ♣❤÷ì♥❣ ❝õ❛ f ✳ ❑❤✐ ✤â

∇f (x∗ ) = 0.

❍ì♥ ♥ú❛✱ t❛ ❝á♥ ❝â
∇2 f (x∗ ) ≥ 0.
❚ø ✤à♥❤ ❧➼ tr➯♥ t❛ ✤à♥❤ ♥❣❤➽❛ ❝→❝ ❦❤→✐ ♥✐➺♠ s❛✉✿

ci (x) = 0, i E

s

trỡ

I, E

t số ỳ

ữủ ồ ử t

ở tự

cj (x), j I



cj (x) 0, j I

ci (x), i E

r

r ở t tự



= {x Rn : ci (x) = 0, i E, cj (x) 0, j I},
ồ õ


f (x) f (x ), x N .
t t tr > t õ

ữỡ t








✾

✣à♥❤ ♥❣❤➽❛ ✶✳✶✳✹ ❈❤♦ x ∈ Ω✱ t➟♣ ❤♦↕t ✭❛❝t✐✈❡ s❡t✮ ❦➼ ❤✐➺✉ A(x) ✤÷ñ❝

✤à♥❤ ♥❣❤➽❛ ❧➔

A(x) = E ∪ {i ∈ I : ci (x) = 0}.

❘➔♥❣ ❜✉ë❝ ❜➜t ✤➥♥❣ t❤ù❝ i ✤÷ñ❝ ❣å✐ ❧➔ ❤♦↕t ✭❛❝t✐✈❡✮ ♥➳✉ ci(x) = 0 ✈➔
♥❣÷ñ❝ ❧↕✐ ♥➳✉ ci(x) > 0 t❤➻ ✤÷ñ❝ ❣å✐ ❧➔ ❦❤æ♥❣ ❤♦↕t✳

✣à♥❤ ♥❣❤➽❛ ✶✳✶✳✺ ❚❛ ♥â✐ t↕✐ ✤✐➸♠ x ✤✐➲✉ ❦✐➺♥ r➔♥❣ ❜✉ë❝ ✤ë❝ ❧➟♣ t✉②➳♥

t➼♥❤ ✭▲■❈◗✮ ✤÷ñ❝ t❤ä❛ ♠➣♥ ♥➳✉ t↕✐ ✤â t➟♣ ❝→❝ ❣r❛❞✐❡♥t ❝õ❛ ❝→❝ r➔♥❣
❜✉ë❝ ❤♦↕t✱
{∇ci (x), i ∈ A(x)}



❈❤ù♥❣ ♠✐♥❤ ❝õ❛ ✤à♥❤ ❧þ ♥➔② ✤÷ñ❝ tr➻♥❤ ❜➔② ❝❤✐ t✐➳t tr♦♥❣ ❬✹❪✳

✭✶✳✶✳✶✷✮
✭✶✳✶✳✶✸✮




ố ữ ử t ợ r ở t
tự
r ử t t tờ qt ú tổ s t t s

1
min q(x) = xT Gx + xT c,
x
2



aTi x = bi , i E,



aTi x bi , i I,



s


L(x, ) = xT Gx + xT c
2
õ t số t t

x A(x )

i (aTi x bi ).
iIE

ỗ số tọ

A(x ) = i E I : aTi x = bi .
ử ừ ỵ t s r tố ữ





x

tỗ t tỷ r

Gx + c

i , i A(x )



i ai = 0,



G

ữỡ t

x

t

ởt số ữỡ t tố ữ
ở tr ử ữủ tr tứ t t

Pữỡ t
r ử t sỷ r s ổ ữủ tọ


s ữủ ồ tt t

f t st ợ ss
2 f (x) 2 f (x) x y .






f tọ t x
f (x ) = 0.



0 = mc (x+ ) = f (xc ) + 2 f (xc )(x+ xc ).
õ

x+ = xc (2 f (xc ))1 f (xc ).
õ ữợ t s

x+ = xc + s,
ợ

s = (2 f (xc ))1 f (xc )

ữ ỵ r


x+

xc

ỹ t t

2 f (xc )

õ t ổ s

õ t ỹ ỹ

trứ tt

2 f (x ) > 0


❜ð✐ ❝æ♥❣ t❤ù❝

x+ = xc − λ∇f (xc ),
tr♦♥❣ ✤â

x

✭✶✳✷✳✶✮

❧➔ ✤ë ❞➔✐ ❜÷î❝✳

▼➦❝ ❞ò t❛ ✤➣ ①→❝ ✤à♥❤ ✤÷ñ❝ ❤÷î♥❣ ❣✐↔♠ s➙✉ ♥❤➜t✱ ♥❤÷♥❣ ✈✐➺❝ ①→❝
✤à♥❤ ✤÷ñ❝ ✤ë ❞➔✐ ❜÷î❝
❝❤å♥ tèt ♥❤➜t ❝❤♦

λ

λ

❧➔ tè✐ q✉❛♥ trå♥❣ ❝õ❛ ♣❤÷ì♥❣ ♣❤→♣ ♥➔②✳ ▲ü❛

❧➔ ♥â tè✐ t❤✐➸✉ ❤â❛ ❤➔♠

φ(λ) = f (xc − λ∇f (xc )).
◆❤÷♥❣ ❜➔✐ t♦→♥ ♥➔② tr♦♥❣ ❤➛✉ ❤➳t tr÷í♥❣ ❤ñ♣ ❝ô♥❣ ❦❤æ♥❣ ❞➵ ❣✐↔✐ ❤ì♥
❜➔✐ t♦→♥ ❝ü❝ trà ❜❛♥ ✤➛✉✳ ❱➻ t❤➳✱ ♥❣÷í✐ t❛ t➻♠ ♠ët ❝→❝❤ t✐➳♣ ❝➟♥ ♥î✐
❧ä♥❣✳ ❚❛ ①➨t ♠æ ❤➻♥❤ ①➜♣ ①➾ ❜➟❝ ♠ët ❝õ❛

f (x)


m

α

❞÷ì♥❣✳ ❚❤æ♥❣

α = 10−4 ✳
λ✱

t❛ ❝â t❤➸ sû ❞ö♥❣ ♠ët

β ∈ (0; 1)

t❤õ tö❝ tr✉② ♥❣÷ñ❝

✭❝â t❤➸ ❝❤å♥ ❜➡♥❣

♥❤ä ♥❤➜t s❛♦ ❝❤♦

λ = β m✳

0, 9✮

✈➔ s❛✉ ✤â✱

❚❤õ tö❝ ♥➔② ✤÷ñ❝

✇❤✐❧❡ tr♦♥❣ ❝õ❛ ❚❤✉➟t t♦→♥ ✶✳ ✣➙② ❝ô♥❣ ❧➔ ♠ët

❝→❝❤ t❤æ♥❣ ❞ö♥❣ ✤➸ ①→❝ ✤à♥❤ ✤ë ❞➔✐ ❜÷î❝ ✤è✐ ✈î✐ ♥❤ú♥❣ ♣❤÷ì♥❣ ♣❤→♣


✺✿

m=1

✻✿

ar❡❞ = f (x) − f (x − β∇f (x))

✼✿

pr❡❞ = β ∇f (x)

✽✿ ✇❤✐❧❡
✾✿

❞♦

2

ar❡❞ ≤ αpr❡❞

❞♦

m=m+1

✶✵✿

ar❡❞ = f (x) − f (x − β m ∇f (x))



α = 10−4 ✳

✣✐➲✉ ❦✐➺♥ ♥➔② ❝❤➼♥❤ ❧➔

✤✐➲✉ ❦✐➺♥

❆r♠✐❥♦ ✈➔ t❤÷í♥❣ ✤÷ñ❝ ❣å✐ ❧➔ ✤✐➲✉ ❦✐➺♥ ❣✐↔♠ ✤õ ✭s✉❢❢✐❝✐❡♥t ❝♦♥❞✐t✐♦♥✮✳

✶✳✷✳✸ P❤÷ì♥❣ ♣❤→♣ ❤➔♠ ❝❤➢♥ ❧♦❣❛r✐t❤
❚r♦♥❣ ♠ö❝ ♥➔②✱ ❝❤ó♥❣ t❛ t➻♠ ❤✐➸✉ ♣❤÷ì♥❣ ♣❤→♣ ❤➔♠ ❝❤➢♥ ❧♦❣❛r✐t❤
❝❤♦ ❜➔✐ t♦→♥ tè✐ ÷✉ r➔♥❣ ❜✉ë❝ ❞↕♥❣ ❜➜t ✤➥♥❣ t❤ù❝✳ ❈ö t❤➸ t❛ ①➨t ❜➔✐
t♦→♥ tè✐ ÷✉

min f (x),
x

s❛♦ ❝❤♦

: ci (x) ≥ 0, i ∈ I.

✭✶✳✷✳✸✮

❚❛ ✤à♥❤ ♥❣❤➽❛ ♠✐➲♥ ❤ú✉ ❤↕♥ ♥❣➦t

F 0 := {x ∈ Rn : ci (x) > 0,

✈î✐ ♠å✐

i ∈ I},


✭✶✳✷✳✺✮

i∈I
✈î✐

log

❧➔ ❧♦❣❛r✐t❤ ❝ì sè tü ♥❤✐➯♥✱ t❤ä❛ ♠➣♥ ❝→❝ t➼♥❤ ❝❤➜t ✭✐✮✲✭✐✐✐✮✳ ◆â

✤÷ñ❝ ❣å✐ ❧➔ ❤➔♠ ❝❤➢♥ ❧♦❣❛r✐t❤✳ ❑❤✐ ✤â✱ ❤➔♠ ❦➳t ❤ñ♣ ✭❝õ❛ ❤➔♠ ♠ö❝ t✐➯✉
✈➔ ❤➔♠ ❝❤➢♥✮ ❝❤♦ ❇➔✐ t♦→♥ ✭✶✳✷✳✸✮✱ ✭✶✳✷✳✹✮ ✤÷ñ❝ ❝❤♦ ❜ð✐

P (x; µ) = f (x) − µ

log ci (x),
i∈I

✭✶✳✷✳✻✮



tr õ

à

ởt số trỏ ừ tr

tờ ủ ữủ ồ
ồ

r k = 0, 1, 2, . . .

ởt tố t ú xk ừ P (.; àk ) t tứ xsk
t tú P (x; àk ) k

tr sỹ ở tử ố ũ tọ
st ợ ú x
k

ồ t số ợ àk+1 (0, àk )
ồ t ợ xsk+1

r

t ỹ t ữợ tr t t t õ t sỷ ử
ữỡ t t tố ữ ổ r ở tr
ử
ỵ s s ú t ố q ỳ t
tố ữ ổ r ở t tố ữ õ r ở

ỵ sỷ r f ci, i I ỗ

ỳ t F 0 ổ rộ t {àk } ởt s
àk 0 sỷ r t ủ M ổ trố ợ ở
õ s ú
ợ ồ à > 0, P (x; à) ỗ tr F 0 õ ởt ỹ t x(à)
ổ t tt t tr F 0 t ý ỹ t





õ x ởt ữỡ t ừ

ỵ sỷ r F 0 ổ rộ x ởt

ữỡ ừ t t õ ữủ tọ
ởt số sỷ r ở ở t t
ờ s t ừ tọ t (x, )
õ s ú


✶✽

✭✐✮ ❈â ❞✉② ♥❤➜t ♠ët ❤➔♠ ✈❡❝tì ❦❤↔ ✈✐ ❧✐➯♥ tö❝ x(µ)✱ ①→❝ ✤à♥❤ ✈î✐ ♠å✐
❣✐→ trà ✤õ ♥❤ä µ ✤➸ x(µ) ❧➔ ❝ü❝ t✐➸✉ ✤à❛ ♣❤÷ì♥❣ ❝õ❛ P (x, µ) tr♦♥❣
♠ët sè ❧➙♥ ❝➟♥ ❝õ❛ x∗✱ s❛♦ ❝❤♦ limµ↓0 x(µ) = x∗✳
✭✐✐✮ ✣è✐ ✈î✐ ❤➔♠ x(µ) tr♦♥❣ ✭✐✮✱ ÷î❝ ❧÷ñ♥❣ ♥❤➙♥ tû ▲❛❣r❛♥❣❡ λ(µ) ❤ë✐ tö
✈➲ λ∗ ❦❤✐ µ ↓ 0✳
✭✐✐✐✮ ❍❡ss✐❛♥ ∇2xxP (x; µ) ❧➔ ①→❝ ✤à♥❤ ❞÷ì♥❣ ✈î✐ ♠å✐ µ ✤õ ♥❤ä✳

✶✳✷✳✹ P❤÷ì♥❣ ♣❤→♣ ❝❤✐➳✉ ❣r❛❞✐❡♥t
✣➙② ❧➔ ♠ët ♠ð rë♥❣ ❝❤♦ ❚❤✉➟t t♦→♥ ❣✐↔♠ s➙✉ ♥❤➜t ❝❤♦ ❜➔✐ t♦→♥ ❝ü❝
trà ✈î✐ r➔♥❣ ❜✉ë❝ ❝➟♥✳ ●✐↔ sû t❛ ✤❛♥❣ ð

xc ✱

t❛ ❝➟♣ ♥❤➟t ♥â ❜➡♥❣ ❝æ♥❣

t❤ù❝



✭✶✳✷✳✼✮




rt t t rt rr
t x, f, k
tt ởt x ừ x
r k = 1, ..., k
max

k





max



f f tr ứ



số ữỡ m ọ t s tọ ợ = m






x

s

f (x ) f (x), x Ux ,
tr õ

U x

ởt õ ừ

x



t ữủ ồ

t tố ữ ỹ tr ữỡ õ r ở
ổ ữ t ỹ tr ổ r ở sỷ ử

f

ọ

ổ trữ ỹ tr t ổ t sỷ ử õ t
ứ s sỷ ử

x x(1)



✷✶

❈❤÷ì♥❣ ✷

❇➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü
❚r♦♥❣ ❝❤÷ì♥❣ ♥➔②✱ tr÷î❝ t✐➯♥ ❝❤ó♥❣ tæ✐ tr➻♥❤ ❜➔② ♠❛♥❣ t➼♥❤ ❣✐î✐ t❤✐➺✉
✈➲ ❜➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü✳ ❈❤ó♥❣ t❛ s➩ t❤➜② ✤➙② t❤ü❝ r❛ ❧➔ ♠ët ❧î♣
❝♦♥ ❝õ❛ ❜➔✐ t♦→♥ ❤å❝ ♠❡tr✐❝✱ ✈è♥ ❞ò♥❣ ✤➸ ❣✐↔✐ q✉②➳t ♥❤✐➲✉ ❧î♣ ❜➔✐ t♦→♥
❦❤→❝✱ tr♦♥❣ ✤â ❜❛♦ ❣ç♠ ❜➔✐ t♦→♥ ✈➲ ✤ë t÷ì♥❣ tü✳ ❚❛ s➩ q✉② ❜➔✐ t♦→♥
♥➔② ✈➲ ♠ët ❜➔✐ t♦→♥ tè✐ ÷✉ ✈➔ ♥❣❤✐➯♥ ❝ù✉ ♠ët sè t➼♥❤ ❝❤➜t ❝õ❛ ❜➔✐ t♦→♥
tè✐ ÷✉ ✤â✳ ❙❛✉ ❝ò♥❣✱ ✈➟♥ ❞ö♥❣ ♥❤ú♥❣ ♣❤÷ì♥❣ ♣❤→♣ tè✐ ÷✉ ✤➣ tr➻♥❤ ❜➔②
ð ❝❤÷ì♥❣ ✶✱ ❝❤ó♥❣ tæ✐ tr➻♥❤ ❜➔② ❧í✐ ❣✐↔✐ ❝❤♦ ❜➔✐ t♦→♥✳ ❈❤÷ì♥❣ ♥➔② ❝ô♥❣
❜❛♦ ❣ç♠ ♠ët sè ✈➼ ❞ö t❤ü❝ t➳ ✈î✐ ❞ú ❧✐➺✉ ✤÷ñ❝ ❧➜② tø ♥❣✉ç♥ ♣❤ê ❜✐➳♥
tr♦♥❣ ❝ë♥❣ ✤ç♥❣ ❤å❝ ♠→②✳

✷✳✶ ❇➔✐ t♦→♥ ❤å❝ ✤ë t÷ì♥❣ tü ✈➔ ❝→❝ ❦✐➳♥ t❤ù❝ ❧✐➯♥
q✉❛♥
✷✳✶✳✶ ▼ët sè ❦✐➳♥ t❤ù❝ ❧✐➯♥ q✉❛♥
❛✮ ❉ú ❧✐➺✉ ↔♥❤ tr♦♥❣ ▼❆❚▲❆❇
▼❆❚▲❆❇ ❝â t❤➸ ❧÷✉ r➜t ♥❤✐➲✉ ❦✐➸✉ ❞ú ❧✐➺✉ ♥❤÷ ➙♠ t❤❛♥❤✱ ❤➻♥❤ ↔♥❤✱
✈➠♥ ❜↔♥✱ ✳ ✳ ✳ ✳ ❉♦ ❧✉➟♥ ✈➠♥ ♥➔② ❝❤➾ q✉❛♥ t➙♠ ✤➳♥ ❞ú ❧✐➺✉ ↔♥❤ ♥➯♥ t❛ ❝❤➾
t❤↔♦ ❧✉➟♥ ✈➲ ❦✐➸✉ ❞ú ❧✐➺✉ ♥➔②✳

❜✮ ❍➺ tå❛ ✤ë ↔♥❤