Về bài toán quy hoạch lồi

„I HÅC THI NGUYN

TR×ÍNG „I HÅC KHOA HÅC

BÒI THÀ THU HUYN

V B€I TON QUY HO„CH LÇI

LUŠN V‹N TH„C Sž TON HÅC

Th¡i Nguy¶n - N«m 2014

„I HÅC THI NGUYN

TR×ÍNG „I HÅC KHOA HÅC

BÒI THÀ THU HUYN

V B€I TON QUY HO„CH LÇI

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

GS-TSKH L DÔNG M×U

Th¡i Nguy¶n - N«m 2014

i

LÍI CƒM ÌN

Líi ¦u ti¶n cõa khâa luªn n y, tæi xin b y tä láng bi¸t ìn s¥u s­c nh§t

tîi th¦y gi¡o h÷îng d¨n GS.TSKH. L¶ Dông M÷u, ng÷íi th¦y ¢ tªn t¼nh

h÷îng d¨n, gióp ï tæi trong suèt qu¡ tr¼nh l m v  ho n thi»n luªn v«n.

Trong qu¡ tr¼nh håc tªp ch÷ìng tr¼nh cao håc t¤i tr÷íng ¤i håc khoa

håc - ¤i håc Th¡i nguy¶n, tæi ¢ nhªn ÷ñc sü gióp ï v  sü gi£ng d¤y

tªn t¼nh cõa GS.TSKH L¶ Dông M÷u, GS.TS. Tr¦n Vô Thi»u, PGS. Næng

Quèc Chinh, PGS.TS. L¶ Thà Thanh Nh n, PGS.TS. T¤ Duy Ph÷ñng, TS.

Nguy¹n Thà Thu Thõy, còng r§t nhi·u th¦y cæ cæng t¡c t¤i Vi»n To¡n håc

Vi»t Nam, tr÷íng ¤i håc Th«ng Long, tr÷íng ¤i håc khoa håc - ¤i

håc Th¡i Nguy¶n. Tæi xin b y tä láng bi¸t ìn s¥u s­c ¸n c¡c th¦y, c¡c cæ.

Nhªn dàp n y, tæi công xin gûi líi c£m ìn tîi c¡c th¦y gi¡o, cæ gi¡o

tr÷íng ¤i håc khoa håc - ¤i håc Th¡i Nguy¶n ¢ quan t¥m, t¤o i·u

ki»n gióp ï tæi trong suèt qu¡ t¼nh håc tªp.

çng thíi, tæi công xin gûi líi c£m ìn tîi Tr÷íng THCS H÷ng ¤o ¢

t¤o i·u ki»n, tîi gia ¼nh v  b¤n b± ¢ luæn ëng vi¶n, gióp ï tæi trong

suèt qu¡ tr¼nh håc tªp v  l m luªn v«n tèt nghi»p.

M°c dò ¢ câ nhi·u cè g­ng nh÷ng luªn v«n khâ tr¡nh khäi nhúng thi¸u

sât v  h¤n ch¸. T¡c gi£ mong nhªn ÷ñc nhúng þ ki¸n âng ghâp cõa c¡c

th¦y cæ v  b¤n åc º luªn v«n ÷ñc ho n thi»n hìn.

Xin tr¥n trång c£m ìn!

H£i Pháng, ng y 11 th¡ng 08 n«m 2014

T¡c gi£

Bòi Thà Thu Huy·n

i

Möc löc

Mð ¦u 1

1 Mët sè kh¡i ni»m cì b£n 2

1.1 Mët sè kh¡i ni»m v  t½nh ch§t cì b£n . . . . . . . . . . . . 2

1.2 Ph¡t biºu b i to¡n v  v½ dö . . . . . . . . . . . . . . . . . 9

1.2.1 B i to¡n quy ho¤ch tuy¸n t½nh . . . . . . . . . . . . 10

1.2.2 B i to¡n quy ho¤ch to n ph÷ìng lçi . . . . . . . . . 10

1.3 Sü tçn t¤i v  t½nh ch§t cõa tªp nghi»m . . . . . . . . . . . 10

1.4 i·u ki»n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . 13

2 MËT SÈ PH×ÌNG PHP GIƒI CÌ BƒN 22

2.1 Ph÷ìng ph¡p ¤o h m v  d÷îi ¤o h m . . . . . . . . . . 22

2.1.1 Thuªt to¡n h÷îng ¤o h m (dèc nh§t) gi£i quy ho¤ch

lçi . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.2 Ph÷ìng ph¡p Newton . . . . . . . . . . . . . . . . . 25

2.1.3 Ph÷ìng ph¡p Frank  Wolfe . . . . . . . . . . . . . 27

2.1.4 Ph÷ìng ph¡p chi¸u d÷îi ¤o h m . . . . . . . . . . 29

2.2 Ph÷ìng ph¡p h m ph¤t . . . . . . . . . . . . . . . . . . . 31

2.2.1 Ph÷ìng ph¡p h m ph¤t iºm trong . . . . . . . . . 32

2.2.2 Ph÷ìng ph¡p h m ph¤t iºm ngo i . . . . . . . . . 35

K¸t luªn 37

T i li»u tham kh£o 38