Luận án Tiến sĩ Toán học: Bài toán quy hoạch toàn phương lồi ngặt với nhiễu giới nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:110

Thêm vào BST

Báo xấu

20
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung luận án gồm 4 chương: chương 1 - Bài toán quy hoạch lồi, toàn phương và hàm lồi thô; chương 2 - Điểm infimum toàn cục của Bài toán P; chương 3 - tính T-lồi ngoài của hàm mục tiêu và điểm infimum toàn cục của bài toán P; chương 4 - điểm supremum của bài toán Q. Để hiểu rõ hơn về đề tài, mời các bạn cùng tham khảo nội dung chi tiết luận án!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Bài toán quy hoạch toàn phương lồi ngặt với nhiễu giới nội

`.I CAM D LO - OAN Tˆoi xin cam d¯oan nh˜ u.ng kˆe´t qua˙’ d¯u.o..c tr`ınh b`ay trong luˆa.n a´n l`a m´o.i, d¯a˜ d¯u.o..c cˆong bˆo´ trˆen c´ac ta.p ch´ı To´an ho.c quˆo´c tˆe´. C´ac kˆe´t qua˙’ viˆe´t chung v´o.i GS. TSKH. Ho`ang Xuˆan Ph´ u v`a PGS. TS. Phan Th`anh An d¯a˜ d¯u.o..c su.. d¯`oˆng y ´ cu˙’a c´ac d¯`ˆong t´ac gia˙’ khi d¯u.a v`ao luˆa.n ´an. C´ac kˆe´t qua˙’ nˆeu trong luˆa.n a´n l`a trung thu..c v`a chu.a t` u.ng d¯u.o..c ai cˆong bˆo´ trong bˆa´t k`y cˆong tr`ınh n`ao kh´ac tru.o´.c d¯o´. u.u sinh Nghiˆen c´
`.I CA LO ˙’ M O.N Luˆa.n ´an d¯u.o..c ho`an th`anh du.o´.i su.. hu.o´.ng dˆa˜n, chı˙’ ba˙’o cu˙’a GS. TSKH. Ho`ang Xuˆan Ph´ u v`a PGS. TS. Phan Thanh An. T´ac gia˙’ chˆan th`anh ca˙’m o.n su.. gi´up d¯o˜. mo.i mˇa.t m`a c´ac Thˆ `ay d¯˜a d`anh cho. T´ac gia˙’ b`ay to˙’ l`ong biˆe´t o.n sˆau sˇa´c v`a chˆan th`anh t´o.i GS. TSKH. Ho`ang Xuˆan Ph´ `ay d¯a˜ u, Thˆ quan tˆam, hu.o´.ng dˆa˜n tˆa.n t`ınh, nghiˆem khˇa´c v`a ta.o mo.i d¯iˆ `eu kiˆe.n d¯ˆe˙’ t´ac gia˙’ c´o thˆe˙’ ho`an th`anh nh˜ u.ng mu.c tiˆeu d¯ˇa.t ra cho luˆa.n a´n. T´ac gia˙’ xin b`ay to˙’ l`ong biˆe´t o.n d¯ˆe´n GS. TSKH. Nguyˆ˜en D - oˆng Yˆen, PGS. TS. Ta. Duy Phu.o..ng, PGS. TS. Nguyˆ˜en Nˇang Tˆam v`a c´ac d¯`ˆong nghiˆe.p thuˆo.c Ph`ong Gia˙’i t´ıch sˆo´ v`a T´ınh to´an Khoa ho.c Viˆe.n To´an ho.c v`ı d¯a˜ c´o nh˜u.ng y ´ kiˆe´n qu´ y b´au cho t´ac gia˙’ trong qu´a tr`ınh nghiˆen c´ u.u. T´ac gia˙’ xin d¯u.o..c b`ay to˙’ l`ong ca˙’m o.n d¯ˆe´n Ban chu˙’ nhiˆe.m Khoa Cˆong Nghˆe. thˆong tin, Ph`ong Sau d¯a.i ho.c v`a Ban Gi´am d¯oˆ´c Ho.c viˆe.n K˜ y thuˆa.t Quˆan su.. d¯a˜ ta.o mo.i d¯iˆ `eu kiˆe.n thuˆa.n lo..i d¯ˆe˙’ t´ac gia˙’ c´o nhiˆ `eu th`o.i gian thu..c hiˆe.n luˆa.n ´an. ung b`ay to˙’ l`ong biˆe´t o.n d¯ˆe´n PGS. TS. D T´ac gia˙’ c˜ - a`o Thanh T˜ınh, PGS. TS. Nguyˆ˜en D -u ´.c Hiˆe´u, PGS. TS. Nguyˆ˜en Thiˆe.n Luˆa.n, PGS. TS. Tˆo Vˇan Ban, TS. Nguyˆ˜en Nam Hˆ `ong, TS. Nguyˆ˜en H˜ u.u Mˆo.ng, TS. V˜ u Thanh H`a, TS. Nguyˆ˜en Ma.nh H` ung, TS. Nguyˆ˜en Tro.ng To`an, TS. Ngˆo H˜u.u Ph´ uc, TS. Tˆo´ng Minh D -u´.c, TS. Lˆe D - `ınh So.n, TS. Trˆ`an Nguyˆen Ngo.c v`a tˆa´t ca˙’ c´ac d¯`oˆng nghiˆe.p trong Khoa Cˆong Nghˆe. thˆong tin, HVKTQS, u.ng trao d¯oˆ˙’i h˜ d¯a˜ d¯ˆo.ng viˆen, kh´ıch lˆe. v`a c´o nh˜ u.u ´ıch trong suˆo´t th`o.i gian nghiˆen c´ u.u v`a cˆong t´ac. T´ac gia˙’ ca˙’m o.n sˆau sˇa´c GS. TSKH. Pha.m Thˆe´ Long, Gi´am d¯ˆo´c Ho.c Viˆe.n KTQS, ngu.o`.i d¯a˜ ta.o mo.i d¯iˆ `eu kiˆe.n vˆ ung nhu. chuyˆen `e mˇa.t thu˙’ tu.c c˜ mˆon d¯ˆe˙’ t´ac gia˙’ c´o thˆe˙’ ho`an th`anh luˆa.n ´an n`ay. ung t´ac gia˙’ gu˙’.i l`o.i c´am o.n t´o.i vo.. v`a c´ac con, nh˜ Cuˆo´i c` u.ng ngu.o`.i d¯a˜ d¯oˆ. ng viˆen, chˇam s´oc v`a ta.o mo.i d¯iˆ `eu kiˆe.n cho t´ac gia˙’ trong qu´a tr`ınh l`am luˆa.n ´an.
Mu.c lu.c o.i cam d L` ¯oan 1 o.i ca˙’m o.n L` 2 Danh mu.c c´ ac k´ e.u thu.` y hiˆ o.ng d` ung 5 Mo˙’. d`au ¯ˆ 1 1 B`ai to´ an quy hoa.ch lˆ `oi, quy hoa.ch to` an phu.o.ng v` a h`am lˆ `oi thˆo 8 `oi, quy hoa.ch to`an phu.o.ng . . . . . . 1.1. B`ai to´an quy hoa.ch lˆ 9 `oi suy rˆo.ng thˆo . . . . . . . . . . . . . . . . . . . . . 1.2. H`am lˆ 12 `oi ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . 1.3. H`am γ-lˆ 13 `oi ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . 1.4. H`am Γ-lˆ 15 `oi trong . . . . . . . . . . . . . . . . . . . . . . . . 1.5. H`am γ-lˆ 17 - iˆ 2 D e˙’m infimum to` an cu.c cu˙’a B` ai to´ an (P˜ ) 20 2.1. T´ınh γ-lˆ `oi ngo`ai cu˙’a h`am bi. nhiˆ˜eu . . . . . . . . . . . . . . 20 2.2. D - iˆe˙’m cu..c tiˆe˙’u to`an cu.c v`a d¯iˆe˙’m infimum to`an cu.c . . . . . 27 2.3. C´ac t´ınh chˆa´t cu˙’a d¯iˆe˙’m infimum to`an cu.c . . . . . . . . . 28 2.4. T´ınh chˆa´t tu..a v`a d¯iˆ `eu kiˆe.n tˆo´i u.u . . . . . . . . . . . . . . 33 `oi ngo` 3 T´ınh Γ-lˆ ai cu˙’a h` ˜ am bi. nhiˆ e u v` a d e˙’m infimum to` ¯iˆ an 3
cu.c cu˙’a B` ai to´an (P˜ ) 43 3.1. T´ınh Γ-lˆ `oi ngo`ai cu˙’a h`am bi. nhiˆ˜eu . . . . . . . . . . . . . . 43 3.2. D- iˆe˙’m infimum to`an cu.c cu˙’a b`ai to´an nhiˆ˜eu . . . . . . . . . 52 3.3. T´ınh oˆ˙’n d¯.inh cu˙’a tˆa.p c´ac d¯iˆe˙’m infimum to`an cu.c . . . . . 55 3.4. Du.o´.i vi phˆan suy rˆo.ng thˆo v`a d¯iˆ `eu kiˆe.n tˆo´i u.u . . . . . . . 58 - iˆ 4 D e˙’m supremum cu˙’a B` ai to´ ˜ an (Q) 64 4.1. T´ınh γ-lˆ `oi trong cu˙’a h`am bi. nhiˆ˜eu . . . . . . . . . . . . . . 64 - iˆe˙’m supremum to`an cu.c cu˙’a h`am bi. nhiˆ˜eu . . . . . . . . 4.2. D 66 4.3. T´ınh chˆa´t cu˙’a tˆa.p c´ac d¯iˆe˙’m supremum to`an cu.c . . . . . . 73 4.4. T´ınh chˆa´t cu˙’a tˆa.p c´ac d¯iˆe˙’m supremum d¯.ia phu.o.ng . . . . 86 e´t luˆ Kˆ a.n chung 94 ong tr`ınh cu˙’a t´ Danh mu.c cˆ ac gia˙’ liˆ en quan d ¯ˆe´n luˆ a.n ´ an 96 T` e.u tham kha˙’o ai liˆ 97
DANH MU ´ KY . C CAC ˆ. U THU.O ´ HIE `.NG DUNG ` • IRn : Khˆong gian Euclide n chiˆ `eu • k · k : Chuˆa˙’n Euclide trong IRn • hx, yi : T´ıch vˆo hu.o´.ng cu˙’a v´ec to. x, y `au mo˙’. b´an k´ınh r tˆam x • B(x, r) := {y | ky − xk < r} : H`ınh cˆ ¯ r) := {y | ky − xk ≤ r} : H`ınh cˆ • B(x, `au d¯o´ng b´an k´ınh r tˆam x u.ng x´ac d¯.inh du.o.ng • A ∈ IRn×n , A 0 : Ma trˆa.n d¯oˆ´i x´ • AT : Ma trˆa.n chuyˆe˙’n vi. cu˙’a ma trˆa.n A • λmin , (λmax ) : Gi´a tri. riˆeng nho˙’ nhˆa´t (l´o.n nhˆa´t) cu˙’a ma trˆa.n A • λ(A) : Tˆa.p c´ac gi´a tri. riˆeng cu˙’a ma trˆa.n A √ • kAk = { max λ | λ ∈ λ(AT A)} : Chuˆa˙’n cu˙’a ma trˆa.n A trong IRn×n • f (x) = hAx, xi + hb, xi : H`am to`an phu.o.ng lˆ `oi ngˇa.t • p(x), supx∈D |p(x)| ≤ s v´o.i s ∈ [0, +∞[ : H`am nhiˆ˜eu gi´o.i nˆo.i • f˜ = f + p : H`am to`an phu.o.ng lˆ `oi ngˇa.t v´o.i nhiˆ˜eu gi´o.i nˆo.i • f (x) := hAx, xi + hb, xi → inf, x ∈ D : B`ai to´an quy hoa.ch to`an phu.o.ng (P ) • f (x) := hAx, xi + hb, xi → sup, x ∈ D : B`ai to´an quy hoa.ch to`an phu.o.ng (Q) • f (x) := hAx, xi + hb, xi + p(x) → inf, x ∈ D : B`ai to´an quy hoa.ch to`an phu.o.ng lˆ `oi ngˇa.t v´o.i nhiˆ˜eu (P˜ ) • f (x) := hAx, xi + hb, xi + p(x) → sup, x ∈ D : B`ai to´an quy hoa.ch to`an phu.o.ng lˆ `oi ngˇa.t v´o.i nhiˆ˜eu (Q) ˜ • ∂g(x∗ ) : Du.o´.i vi phˆan cu˙’a g ta.i d¯iˆe˙’m x∗
Pm • L(x, µ0 , . . . , µm ) := i=0 µi gi (x) : H`am Lagrange • T´ınh chˆa´t (Mγ ) : Mˆo˜i d¯iˆe˙’m γ-cu..c tiˆe˙’u x∗ cu˙’a f l`a d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c • T´ınh chˆa´t (Iγ ) : Mˆo˜i d¯iˆe˙’m γ-infimum x∗ cu˙’a f l`a d¯iˆe˙’m infimum to`an cu.c • Lα (f˜) := {x | x ∈ D, f˜(x) ≤ α}, α ∈ IR : Tˆa.p m´ u.c du.o´.i cu˙’a h`am f˜ = f + p 1 1 • h1 (γ) := inf x0 , x1 ∈D, kx0 −x1 k=γ 2 (f (x0 ) + f (x1 )) − f ( 2 (x0 + x1 )) • h2 (γ) := inf x0 , x1 ∈D, kx0 −x1 k=γ,−x0 +2x1 ∈D f (x0 )−2f (x1 )+f (−x0 +2x1 ) • aff D : Bao aphin cu˙’a tˆa.p D • ext D : Tˆa.p c´ac d¯iˆe˙’m cu..c biˆen cu˙’a tˆa.p lˆ `oi d¯a diˆe.n D • JD (x∗ ) := ext D \ {x∗ }, x∗ ∈ ext D u. x d¯ˆe´n D • d(x, D) := inf y∈D kx − yk : Khoa˙’ng c´ach t` `oi cu˙’a tˆa.p D • conv D : Bao lˆ • dD := minx∗ ∈ext D {d x∗ , conv JD (x∗ ) } • D(x∗ , β) := {x ∈ D | x = (1 − α)x∗ + αy, y ∈ D, 0 ≤ α ≤ 1 − β}, x∗ ∈ ext D, β ∈ [0, 1] • C 0 (D) := {p : D → IR | kpkC 0 := supx∈D |p(x)| < +∞} ¯C 0 (0, r) : H`ınh cˆ • B `au d¯o´ng b´an k´ınh r tˆam 0 trong C 0 (D)
1 ˙’. D MO -` AˆU B`ai to´an quy hoa.ch to`an phu.o.ng truyˆ `en thˆo´ng c´o da.ng f (x) := hAx, xi + hb, xi → inf, x∈D trong d¯o´ A ∈ IRn×n l`a ma trˆa.n vuˆong, b ∈ IRn l`a v´ec to. v`a D ⊂ IRn l`a tˆa.p `oi. lˆ ung v´o.i b`ai to´an quy hoa.ch lˆ C` `oi, b`ai to´an quy hoa.ch to`an phu.o.ng d¯u.o..c nhiˆ u.u, v´ı du. nhu. H. `eu nh`a to´an ho.c Viˆe.t nam v`a quˆo´c tˆe´ nghiˆen c´ W. Kuhn v`a A. W. Tucker [22], B. Bank v`a R. Hasel [5], E. Blum v`a W. Oettli [7], B. C. Eaves [12], M. Frank v`a P. Wolfe [13], O. L. Magasarian [26], G. M. Lee, N. N. Tam v`a N. D. Yen [31], H. X. Phu [45], H. X. Phu v`a N. D. Yen [53], M. Schweighofer [57], H. Tuy [63], [64], [72], H. H. Vui v`a P. T. Son [66]. . . C´ac kˆe´t qua˙’ quan tro.ng d¯a˜ thu d¯u.o..c khi nghiˆen c´ u.u c´ac b`ai to´an quy hoa.ch to`an phu.o.ng cu˙’a c´ac nh`a to´an ho.c l`a vˆ `e su.. tˆ `on ta.i nghiˆe.m tˆo´i u.u, d¯iˆ`eu kiˆe.n cˆ`an tˆo´i u.u, d¯iˆ `eu kiˆe.n d¯u˙’ tˆo´i u.u, thuˆa.t to´an t`ım nghiˆe.m tˆo´i u.u, t´ınh oˆ˙’n d¯.inh cu˙’a nghiˆe.m tˆo´i u.u khi c´ac b`ai to´an trˆen bi. t´ac d¯ˆo.ng bo˙’.i nhiˆ˜eu. Nhiˆ `eu kˆe´t qua˙’ nghiˆen c´ u.u vˆ`e b`ai to´an trˆen d¯a˜ d¯u.o..c u ´.ng du.ng d¯ˆe˙’ gia˙’i c´ac b`ai to´an trong kinh tˆe´ v`a k˜ y thuˆa.t, nhu. b`ai to´an lu..a cho.n d¯`ˆau tu. (portfolio selection) ([27], [28]), b`ai to´an ph´at d¯iˆe.n tˆo´i u.u (economic power dispatch) ([6], [11], [69]), b`ai to´an kinh tˆe´ d¯oˆ´i s´anh (matching economic), ([17]), b`ai to´an m´ay hˆo˜ tro.. v´ec to. (support vector machine) ([29]). . . Khi A l`a nu˙’.a x´ac d¯i.nh du.o.ng hoˇa.c nu˙’.a x´ac d¯i.nh ˆam th`ı b`ai to´an trˆen c´o thˆe˙’ phˆan r˜a th`anh hai b`ai to´an kh´ac nhau sau: f (x) := hAx, xi + hb, xi → inf, x∈D (P ) v`a f (x) := hAx, xi + hb, xi → sup, x ∈ D. (Q)
2 u.u c´ac b`ai to´an quy hoa.ch to`an phu.o.ng lˆ Luˆa.n ´an n`ay nghiˆen c´ `oi ngˇa.t v´o.i nhiˆ˜eu gi´o.i nˆo.i sau: f˜(x) := hAx, xi + hb, xi + p(x) → inf, x∈D (P˜ ) v`a f˜(x) := hAx, xi + hb, xi + p(x) → sup, x ∈ D, ˜ (Q) trong d¯o´ p : D → IR tho˙’a m˜an d¯iˆ `eu kiˆe.n supx∈D |p(x)| ≤ s v´o.i gi´a tri. s ∈ [0, +∞[ v`a A trong c´ac b`ai to´an (P ), (Q), (P˜ ) v`a (Q) ˜ d¯u.o..c gia˙’ thiˆe´t l`a u.ng x´ac d¯.inh du.o.ng. ma trˆa.n d¯oˆ´i x´ V`ı sao c´ac b`ai to´an trˆen d¯u.o..c cho.n d¯ˆe˙’ nghiˆen c´u.u? R˜o r`ang, khi s = 0 th`ı c´ac b`ai to´an (P˜ ) v`a (Q) ˜ ch´ınh l`a c´ac b`ai to´an (P ) v`a (Q), hay n´oi c´ach kh´ac c´ac b`ai to´an (P ) v`a (Q) l`a c´ac tru.o`.ng ho..p riˆeng cu˙’a c´ac b`ai to´an (P˜ ) ˜ D v`a (Q). - aˆy l`a l´ y do d¯ˆe˙’ tiˆe´n h`anh nghiˆen c´ u.u c´ac b`ai to´an trˆen, tˆo´i thiˆe˙’u t`u. quan d¯iˆe˙’m l´ y thuyˆe´t. Tuy nhiˆen, c`on mˆo.t sˆo´ l´ y do thu..c tˆe´ kh´ac du.o´.i d¯aˆy, cho thˆa´y viˆe.c nghiˆen c´ u.u c´ac b`ai to´an (P˜ ), (Q) ˜ l`a thu..c su.. cˆ `an. L´y do th´ u. nhˆa´t: f (x) = hAx, xi + hb, xi l`a h`am mu.c tiˆeu ban d¯`aˆu v`a p l`a h`am nhiˆ˜eu n`ao d¯o´. H`am nhiˆ˜eu p c´o thˆe˙’ bao gˆ `om c´ac t´ac d¯oˆ. ng bˆo˙’ sung (tˆa´t d¯.inh hoˇa.c ngˆa˜u nhiˆen) lˆen h`am mu.c tiˆeu v`a c´ac lˆo˜i gˆay ra trong qu´a tr`ınh mˆo h`ınh h´oa, d¯o d¯a.c, t´ınh to´an. . . D - iˆe˙’m d¯aˇ. c biˆe.t l`a o˙’. chˆo˜, ch´ ung ta ha.n chˆe´ chı˙’ x´et nhiˆ˜eu gi´o.i nˆo.i. Ha.n chˆe´ n`ay l`a khˆong qu´a ngˇa.t, c´o thˆe˙’ d¯u.o..c tho˙’a m˜an trong nhiˆ `eu b`ai to´an thu..c tˆe´, chˇa˙’ng ha.n nhu. trong hai v´ı du. minh ho.a sau d¯ˆay. Mˆo.t trong nh˜ u.ng u ´.ng du.ng nˆo˙’i bˆa.t cu˙’a quy hoa.ch to`an phu.o.ng l`a b`ai to´an lu..a cho.n d¯`ˆau tu. (H. M. Markowitz [27], [28]). B`ai to´an ph´at biˆe˙’u nhu. sau: Phˆan phˆo´i vˆo´n qua n ch´ u.ng kho´an (asset) c´o sˇa˜n d¯ˆe˙’ c´o thˆe˙’ gia˙’m thiˆe˙’u ru˙’i ro v`a tˆo´i d¯a lo..i nhuˆa.n, t´ u.c l`a t`ım v´ec to. tı˙’ lˆe. x ∈ D, D := {x = (x1 , x2 , . . . , xn ) | nj=1 xj = 1} d¯ˆe˙’ f (x) = ωxT Σx − ρT x P d¯a.t gi´a tri. nho˙’ nhˆa´t, trong d¯´o xj , j = 1, . . . , n, l`a ty˙’ lˆe. ch´ u.ng kho´an th´ u. j trong danh mu.c d¯`ˆau tu., ω l`a tham sˆo´ ru˙’i ro, Σ ∈ IRn×n l`a ma trˆa.n hiˆe.p phu.o.ng sai, ρ ∈ IRn l`a v´ec to. lo..i nhuˆa.n k` y vo.ng. V`ı Σ v`a ρ thu.o`.ng
3 khˆong d¯u.o..c x´ac d¯i.nh ch´ınh x´ac m`a chı˙’ xˆa´p xı˙’ bo˙’.i Σ ˜ v`a ρ˜, do d¯o´ ch´ ung ta pha˙’i cu..c tiˆe˙’u h´oa h`am f˜(x) = ωxT Σx ˜ − ρ˜T x = f (x) + p(x), trong d¯´o p(x) = ωxT (Σ ˜ − Σ)x − (˜ ρ − ρ)T x. Khi quy d¯.inh, khˆong d¯u.o..c b´an khˆo´ng, t´u.c l`a xj ≥ 0, j = 1, . . . , n, th`ı tˆa.p chˆa´p nhˆa.n d¯u.o..c D l`a gi´o.i nˆo.i. V`ı vˆa.y nhiˆ˜eu p c˜ ung gi´o.i nˆo.i trˆen D. N´oi mˆo.t c´ach tˆo˙’ng qu´at, t´ınh gi´o.i nˆo.i cu˙’a nhiˆ˜eu luˆon d¯u.o..c d¯a˙’m ba˙’o khi D gi´o.i nˆo.i v`a p liˆen tu.c trˆen D. Gia˙’ thiˆe´t n`ay c˜ ung ph` u ho..p v´o.i nhiˆ`eu b`ai to´an thu..c tˆe´. Mˆo.t v´ı du. n˜ u.a cho thˆa´y l`a nhiˆ˜eu gi´o.i nˆo.i luˆon xuˆa´t hiˆe.n khi gia˙’i mˆo.t b`ai to´an tˆo´i u.u (P ) hoˇa.c (Q) n`ao d¯´o bˇa` ng m´ay t´ınh. Do phˆ `an l´o.n c´ac sˆo´ thu..c khˆong thˆe˙’ biˆe˙’u diˆ˜en ch´ınh x´ac bˇa` ng m´ay t´ınh, nˆen d¯ˆo´i v´o.i hˆ `au hˆe´t x ∈ D ta khˆong thˆe˙’ t´ınh ch´ınh x´ac d¯a.i lu.o..ng f (x) = hAx, xi + hb, xi m`a chı˙’ c´o thˆe˙’ xˆa´p xı˙’ f (x) bo˙’.i mˆo.t sˆo´ dˆa´u chˆa´m d¯oˆ. ng f˜(x) n`ao d¯´o. H`am f˜ khˆong lˆ `oi, khˆong to`an phu.o.ng v`a thˆa.m ch´ı l`a khˆong liˆen tu.c trˆen D. Khi d¯o´ h`am p := f˜− f mˆo ta˙’ c´ac lˆo˜i t´ınh to´an. C´ac lˆo˜i d¯´o bi. chˇa.n bo˙’.i mˆo.t cˆa.n trˆen s ∈ [0, +∞[ n`ao d¯o´ c´o thˆe˙’ u.o´.c lu.o..ng d¯u.o..c, t´ u.c l`a supx∈D |p(x)| ≤ s. Ngo`ai ra, bˇa` ng c´ach su˙’. du.ng c´ac sˆo´ dˆa´u chˆa´m d¯oˆ. ng d`ai ho.n v`a/hoˇa.c c´ac thuˆa.t to´an tˆo´t ho.n, ta c´o thˆe˙’ gia˙’m cˆa.n trˆen s. L´ y do th´ u. hai: f˜ l`a h`am mu.c tiˆeu d¯´ıch thu..c v`a f l`a h`am mu.c tiˆeu d¯u.o..c l´ y tu.o˙’.ng h´oa hoˇa.c l`a h`am mu.c tiˆeu thay thˆe´. Trong thu..c tˆe´, nhiˆ `eu h`am thˆe˙’ hiˆe.n mˆo.t sˆo´ mu.c tiˆeu thu..c tiˆ˜en d¯u.o..c gia˙’ d¯.inh l`a lˆ `oi, hoˇa.c to`an phu.o.ng, hoˇa.c c´o mˆo.t sˆo´ t´ınh chˆa´t thuˆa.n tiˆe.n d¯a˜ d¯u.o..c nghiˆen c´ u.u k˜y, hoˇa.c dˆ˜e nghiˆen c´ u.u, nhu.ng thu..c ra th`ı khˆong pha˙’i l`a nhu. vˆa.y. D `eu n`ay d¯˜a d¯u.o..c - iˆ H. X. Phu, H. G. Bock v`a S. Pickenhain d¯`ˆe cˆa.p d¯ˆe´n trong [48]. Trong bˆo´i ca˙’nh d¯´o, p = f˜ − f l`a h`am hiˆe.u chı˙’nh. C´o thˆe˙’ gia˙’ thiˆe´t p l`a gi´o.i nˆo.i (tˆo´i thiˆe˙’u trˆen tˆa.p chˆa´p nhˆa.n d¯u.o..c) bo˙’.i mˆo.t sˆo´ du.o.ng kh´a b´e s, v`ı nˆe´u |p(x)| qu´a l´o.n th`ı su.. thay thˆe´ khˆong c`on ph` u ho..p n˜ u.a. `eu n`ay, ta d¯`ˆe cˆa.p d¯ˆe´n vˆa´n d¯`ˆe thu.o`.ng d¯u.o..c nghiˆen c´ - ˆe˙’ gia˙’i th´ıch d¯iˆ D u.u cu˙’a ph´at d¯iˆe.n tˆo´i u.u, t´ u.c l`a b`ai to´an phˆan bˆo´ lu.o..ng d¯iˆe.n nˇang cho t` u.ng tˆo˙’ m´ay ph´at nhiˆe.t d¯iˆe.n sao cho tˆo˙’ng chi ph´ı (gi´a th`anh) l`a cu..c tiˆe˙’u, d¯`oˆng th`o.i vˆa˜n d¯a´p u ´.ng d¯u.o..c nhu cˆ `au lu.o..ng d¯iˆe.n nˇang v`a thoa˙’ m˜an r`ang buˆo.c
4 `e cˆong suˆa´t ph´at ra cu˙’a mˆo˜i tˆo˙’ m´ay. Ngu.o`.i ta thu.o`.ng gia˙’ thiˆe´t (xem vˆ [6], [11], [69],. . . ) h`am chi ph´ı tˆo˙’ng cˆo.ng (bao gˆ `om c´ac chi ph´ı nhiˆen liˆe.u (fuel cost), chi ph´ı ta˙’i sau (load-following cost), chi ph´ı du.. ph`ong quay (sprinning-reserve cost), chi ph´ı du.. ph`ong bˆo˙’ sung (supplemental-reserve `en dˆa˜n d¯iˆe.n nˇang) l`a h`am to`an phu.o.ng, cost), chi ph´ı tˆo˙’n thˆa´t ph´at v`a truyˆ `oi ngˇa.t v`a c´o da.ng lˆ n X F (P ) = Fi (Pi ), i=1 trong d¯o´ n l`a sˆo´ tˆo˙’ m´ay ph´at, P := (P1 , P2 , . . . , Pn ), Pi ∈ [Pi min , Pi max ] l`a lu.o..ng d¯iˆe.n nˇang ph´at ra cu˙’a tˆo˙’ m´ay th´ u. i, Pi min , Pi max l`a cˆong suˆa´t ph´at nho˙’ nhˆa´t v`a l´o.n nhˆa´t cu˙’a tˆo˙’ m´ay ph´at th´ u. i, Fi (Pi ) = ai + bi Pi + ci Pi2 l`a h`am chi ph´ı cu˙’a tˆo˙’ m´ay ph´at th´ u. i v`a ai , bi , ci l`a c´ac hˆe. sˆo´ gi´a cu˙’a tˆo˙’ m´ay ph´at th´ u. i ∈ {1, 2, . . . , n}. D˜ı nhiˆen, gia˙’ thiˆe´t to`an phu.o.ng, lˆ `oi ngˇa.t cu˙’a h`am mu.c tiˆeu l`a qu´a l´ y tu.o˙’.ng. Chi ph´ı thu..c tˆe´ c´o thˆe˙’ khˆong l`a h`am to`an phu.o.ng v`a c˜ ung khˆong l`a h`am lˆ `oi ngˇa.t. Nhu. vˆa.y, d¯ˆe˙’ gia˙’ thiˆe´t vˆ `e t´ınh to`an phu.o.ng v`a lˆ `oi ngˇa.t cu˙’a h`am mu.c tiˆeu d¯u.o..c tho˙’a m˜an, cˆ `an h`am gi´o.i nˆo.i p hiˆe.u chı˙’nh h`am chi ph´ı thu..c tˆe´. D ´.ng d¯iˆe˙’m-van - aˇ. c biˆe.t (xem [62], [6], [11], [69],. . . ), nˆe´u hiˆe.u u d¯u.o..c x´et d¯ˆe´n th`ı h`am chi ph´ı to`an phu.o.ng pha˙’i d¯u.o..c hiˆe.u chı˙’nh bo˙’.i tˆo˙’ng h˜ u.u ha.n c´ac h`am da.ng sin, t´ u.c l`a Xn F (P ) = Fi (Pi ) + |ei sin(fi (Pi min − Pi ))| , i=1 ´.ng d¯iˆe˙’m-van. R˜o r`ang h`am hiˆe.u chı˙’nh trong d¯´o ei , fi l`a c´ac hˆe. sˆo´ hiˆe.u u p := ni=1 |ei sin(fi (Pi min − Pi ))| l`a gi´o.i nˆo.i. P - ˆe˙’ ngˇa´n go.n, ta thu.o`.ng go.i p l`a h`am nhiˆ˜eu (mˇa.c d` D u n´o khˆong chı˙’ d¯o´ng vai tr`o d¯o´ nhu. d¯a˜ gia˙’i th´ıch o˙’. trˆen), f˜ l`a h`am bi. nhiˆ˜eu v`a (P˜ ) v`a (Q)˜ l`a c´ac b`ai to´an nhiˆ˜eu. Thˆa.t ra, ch´ u. vay mu.o..n, ung chı˙’ l`a c´ac thuˆa.t ng˜ khˆong pha˙’i l´ uc n`ao c˜ung ch´ınh x´ac nhu. thu.o`.ng lˆe.. u.ng vˆa´n d¯`ˆe g`ı l`a m´o.i cu˙’a c´ac b`ai to´an (P˜ ) v`a (Q) Nh˜ ˜ cˆ `an d¯u.o..c nghiˆen u.u? Cˆau ho˙’i n`ay l`a cˆ c´ `an thiˆe´t, v`ı d¯a˜ c´o nh˜u.ng kˆe´t qua˙’ nghiˆen c´ u.u d¯aˇ. c
5 sˇa´c theo c´ac kh´ıa ca.nh kh´ac nhau vˆ `e t´ınh ˆo˙’n d¯i.nh cu˙’a c´ac b`ai to´an nhiˆ˜eu `oi v`a/hoˇa.c nhiˆ˜eu to`an phu.o.ng. D lˆ - iˆe˙’m chung cu˙’a phˆ `an l´o.n c´ac cˆong tr`ınh nghiˆen c´ u.u t` u. tru.o´.c d¯ˆe´n nay l`a nhiˆ˜eu khˆong l`am thay d¯ˆo˙’i nh˜ u.ng thuˆo.c t´ınh tiˆeu biˆe˙’u cu˙’a b`ai to´an ban d¯`aˆu. V´ı du. b`ai to´an lˆ `oi bi. nhiˆ˜eu vˆa˜n gi˜u. nguyˆen t´ınh lˆ `oi (nhu. trong c´ac nghiˆen c´ u.u cu˙’a M. J Canovas [8], D. Klatte [21], B. Kumer [23]. . . ) v`a c´ac b`ai to´an to`an phu.o.ng gi˜ u. d¯u.o..c t´ınh to`an phu.o.ng (nhu. trong c´ac nghiˆen c´ u.u cu˙’a J. V. Daniel [10], G. M. Lee, N. N. Tam v`a N. D. Yen [31], K. Mirnia v`a A. Ghaffari-Hadigheh [30], H. X. Phu [45], H. X. Phu v`a N. D. Yen [53]. . . ). D `eu kh´ac biˆe.t l`a, h`am mu.c tiˆeu f˜ - iˆ cu˙’a c´ac b`ai to´an nhiˆ˜eu trong luˆa.n a´n n`ay khˆong lˆ `oi, khˆong to`an phu.o.ng mˇa.c d` u h`am f l`a lˆ `oi ngˇa.t v`a to`an phu.o.ng. Ho.n n˜ u.a, v`ı nhiˆ˜eu p chı˙’ gia˙’ thiˆe´t l`a gi´o.i nˆo.i, nˆen h`am bi. nhiˆ˜eu f˜ c´o thˆe˙’ khˆong liˆen tu.c ta.i bˆa´t c´u. d¯iˆe˙’m n`ao. V´o.i nh˜ u.ng h`am mu.c tiˆeu nhu. vˆa.y, du.o`.ng nhu. s˜e khˆong thˆe˙’ thu d¯u.o..c `eu ngu.o..c la.i. kˆe´t qua˙’ g`ı d¯ˇa.c biˆe.t. Mu.c tiˆeu cu˙’a luˆa.n ´an l`a chı˙’ ra d¯iˆ `om 4 chu.o.ng. Luˆa.n ´an gˆ Chu.o.ng 1 v´o.i tiˆeu d¯`ˆe “B`ai to´an quy hoa.ch lˆ `oi, to`an phu.o.ng v`a h`am `oi thˆ lˆ o” tr`ınh b`ay D - i.nh l´y Kuhn-Tucker cu˙’a b`ai to´an quy hoa.ch lˆ - i.nh `oi, D l´y vˆ `eu kiˆe.n cu..c tri. cu˙’a b`ai to´an quy hoa.ch to`an phu.o.ng v`a mˆo.t sˆo´ loa.i `e d¯iˆ h`am lˆ `oi thˆo nhu. γ-lˆ `oi ngo`ai, Γ-lˆ `oi ngo`ai, γ-lˆ `oi trong c`ung mˆo.t sˆo´ t´ınh chˆa´t tˆo´i u.u cu˙’a ch´ ung. C´ac kh´ai niˆe.m, c´ac t´ınh chˆa´t, c´ac d¯i.nh l´ y d¯u.o..c dˆa˜n ra trong chu.o.ng n`ay s˜e d¯u.o..c su˙’. du.ng d¯ˆe˙’ nghiˆen c´ u.u c´ac vˆa´n d¯`ˆe d¯aˇ. t ra trong c´ac chu.o.ng sau. Chu.o.ng 2 v´o.i tiˆeu d¯`ˆe “D - iˆe˙’m infimum to`an cu.c cu˙’ a B`ai to´an (P˜ )” nghiˆen c´ u.u t´ınh γ-lˆ`oi ngo`ai cu˙’a h`am to`an phu.o.ng v´o.i nhiˆ˜eu gi´o.i nˆo.i, d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c, d¯iˆe˙’m infimum to`an cu.c cu˙’a B`ai to´an (P˜ ), kha˙’o s´at t´ınh oˆ˙’n d¯.inh nghiˆe.m v`a mo˙’. rˆo.ng D - i.nh l´ y Kuhn-Tucker cho b`ai to´an n`ay. Chu.o.ng 3 v´o.i tiˆeu d¯`ˆe “T´ınh Γ-lˆ `oi ngo`ai cu˙’ a h`am mu.c tiˆeu v`a d¯iˆe˙’m infimum to` ai to´an (P˜ )” nghiˆen c´ an cu.c cu˙’ a B` u.u t´ınh Γ-lˆ `oi ngo`ai cu˙’a h`am
6 mu.c tiˆeu f˜ (theo c´ach tiˆe´p cˆa.n tˆo pˆo), qua d¯´o nhˆa.n d¯u.o..c mˆo.t sˆo´ kˆe´t qua˙’ ma.nh ho.n nh˜ u.ng kˆe´t qua˙’ nghiˆen c´ u.u vˆ `e d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c, d¯iˆe˙’m infimum to`an cu.c cu˙’a B`ai to´an (P˜ ) d¯u.o..c chı˙’ ra trong Chu.o.ng 2. Chu.o.ng 4 cu˙’a luˆa.n ´an c´o tiˆeu d¯`ˆe “D ˜ - iˆe˙’m supremum cu˙’ a B`ai to´an (Q)” nghiˆen c´ u.u t´ınh chˆa´t v`a t´ınh oˆ˙’n d¯.inh cu˙’a c´ac d¯iˆe˙’m supremum to`an cu.c v`a d¯iˆe˙’m supremum d¯.ia phu.o.ng cu˙’a B`ai to´an (Q). ˜ C´ac kˆe´t qua˙’ d¯a.t d¯u.o..c trong luˆa.n ´an bao gˆ `om: `eu kiˆe.n d¯u˙’ d¯ˆe˙’ h`am bi. nhiˆ˜eu f˜ = f + p l`a γ-lˆ • Chı˙’ ra c´ac d¯iˆ `oi ngo`ai, Γ-lˆ `oi ngo`ai v`a γ-lˆ `oi trong. • Ch´ u.ng minh d¯u.o..c d¯u.o`.ng k´ınh cu˙’a tˆa.p c´ac d¯iˆe˙’m infimum to`an cu.c cu˙’a B`ai to´an (P˜ ) khˆong vu.o..t qu´a γ ∗ = 2 2s/λmin . p • Chı˙’ ra t´ınh oˆ˙’n d¯i.nh nghiˆe.m cu˙’a B`ai to´an (P˜ ) theo cˆa.n trˆen s cu˙’a h`am nhiˆ˜eu. • Mo˙’. rˆo.ng D y Kuhn-Tucker cho B`ai to´an (P˜ ). - i.nh l´ • Chı˙’ ra c´ac t´ınh chˆa´t (ma.nh ho.n c´ac t´ınh chˆa´t d¯a˜ c´o) cu˙’a c´ac d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c v`a d¯iˆe˙’m infimum to`an cu.c cu˙’a B`ai to´an (P˜ ) khi su˙’. du.ng t´ınh Γ-lˆ `oi ngo`ai cu˙’a h`am to`an phu.o.ng lˆ `oi ngˇa.t bi. nhiˆ˜eu gi´o.i nˆo.i f˜ = f + p. • Ch´ u.ng minh d¯u.o..c su.. tˆ `on ta.i v`a vi. tr´ı cu˙’a c´ac d¯iˆe˙’m supremum to`an `en D. cu.c trˆen miˆ • Khˇa˙’ng d¯i.nh t´ınh oˆ˙’n d¯i.nh cu˙’a tˆa.p c´ac d¯iˆe˙’m supremum to`an cu.c khi D l`a d¯a diˆe.n lˆ `oi v`a tˆa.p c´ac d¯iˆe˙’m supremum d¯i.a phu.o.ng khi D l`a tˆa.p `oi d¯a diˆe.n cu˙’a B`ai to´an (Q) lˆ ˜ theo nhiˆ˜eu p. C´ac kˆe´t qua˙’ ch´ınh cu˙’a luˆa.n a´n d¯a˜ d¯u.o..c tr`ınh b`ay ta.i c´ac xemina “Tˆo´i u.u h´oa v`a T´ınh to´an hiˆe.n d¯a.i” cu˙’a Khoa Cˆong nghˆe. thˆong tin (Ho.c viˆe.n KTQS), “Tˆo´i u.u v`a T´ınh to´an khoa ho.c” cu˙’a Ph`ong Gia˙’i t´ıch sˆo´
7 v`a T´ınh to´an khoa ho.c (Viˆe.n To´an ho.c), Hˆo.i tha˙’o “Tˆo´i u.u v`a T´ınh to´an Khoa ho.c” (Ba V`ı, H`a Nˆo.i, th´ang 4 nˇam 2010). C´ac kˆe´t qua˙’ n`ay c˜ ung d¯a˜ d¯u.o..c cˆong bˆo´ trˆen c´ac ta.p ch´ı Optimization, Mathematical Methods of Operations Research v`a Journal of Optimization Theory and Applications. Ch´ung tˆoi d¯ang tiˆe´p tu.c nghiˆen c´ u.u mˆo.t sˆo´ vˆa´n d¯`ˆe vˆ `e l´ y thuyˆe´t v`a t´ınh to´an u´.ng du.ng trong thu..c tˆe´ cu˙’a c´ac b`ai to´an (P˜ ) v`a (Q), ˜ hy vo.ng rˇa` ng trong th`o.i gian t´o.i s˜e c´o thˆem mˆo.t sˆo´ kˆe´t qua˙’ m´o.i.
. . CHU O NG 1 ` TOAN BAI ´ QUY HOA `ˆ I, . CH LO QUY HOA ` PHU.O.NG VA . CH TOAN ` HAM ` L` ˆ I THO O ˆ Trong chu.o.ng n`ay, ch´ ung tˆoi nhˇa´c la.i D- i.nh l´ y Kuhn-Tucker cho b`ai to´an quy hoa.ch lˆ - i.nh l´ `oi, D `e d¯iˆ y vˆ `an cu..c tri. cho b`ai to´an quy hoa.ch `eu kiˆe.n cˆ to`an phu.o.ng. D - `oˆng th`o.i ch´ung tˆoi c˜ ung tr`ınh b`ay la.i mˆo.t sˆo´ kh´ai niˆe.m, t´ınh chˆa´t cu˙’a h`am lˆ `oi thˆo nhu. γ-lˆ `oi ngo`ai, Γ-lˆ `oi ngo`ai v`a γ-lˆ`oi trong. C´ac kh´ai niˆe.m, c´ac kˆe´t qua˙’ dˆa˜n ra o˙’. trong chu.o.ng n`ay, s˜e d¯u.o..c su˙’. `an trong c´ac chu.o.ng sau. `eu lˆ du.ng nhiˆ Trong suˆo´t luˆa.n a´n n`ay, IRn l`a khˆong gian Euclide n-chiˆ `eu, D ⊆ IRn l`a c´ac tˆa.p lˆ `eu tru.o`.ng ho..p D d¯u.o..c gia˙’ thiˆe´t l`a tˆa.p lˆ `oi, v`a trong nhiˆ `oi d¯a diˆe.n. V´o.i x0 , x1 ∈ IRn , λ ∈ IR, ta k´ y hiˆe.u xλ := (1 − λ)x0 + λx1 , [x0 , x1 ] := {xλ | 0 ≤ λ ≤ 1}, ]x0 , x1 ] := [x0 , x1 ] \ {x0 }. C´ac tˆa.p ho..p [x0 , x1 [ v`a ]x0 , x1 [ c˜ ung d¯u.o..c d¯.inh ngh˜ıa tu.o.ng tu... V´o.i r l`a sˆo´ thu..c du.o.ng, c´ac tˆa.p ho..p B(x, r) := {y | ky − xk < r}, ¯ r) := {y | ky − xk ≤ r}, B(x, S(x, r) := {y | ky − xk = r}, `an lu.o..t d¯u.o..c go.i l`a c´ac h`ınh cˆ lˆ `au mo˙’., h`ınh cˆ `au d¯´ong v`a mˇa.t cˆ`au tˆam x b´an k´ınh r. Ngo`ai ra, trong luˆa.n ´an n`ay ch´ ung tˆoi luˆon k´ y hiˆe.u: 8
9 • f l`a h`am to`an phu.o.ng lˆ `oi ngˇa.t c´o da.ng f (x) := hAx, xi + hb, xi, x ∈ D (1.0.1) trong d¯o´ A ∈ IRn×n l`a ma trˆa.n d¯ˆo´i x´ u.ng x´ac d¯i.nh du.o.ng (nˆe´u A u.ng ta c´o thˆe˙’ thay A bo˙’.i 12 (A + AT )). khˆong d¯ˆo´i x´ • p(x) l`a h`am nhiˆ˜eu gi´o.i nˆo.i, t´ u.c l`a sup |p(x)| ≤ s < +∞. (1.0.2) x∈D • f˜(x) := f (x) + p(x) d¯u.o..c go.i l`a h`am to`an phu.o.ng lˆ `oi ngˇa.t v´o.i nhiˆ˜eu gi´o.i nˆo.i trˆen D, go.i tˇa´t l`a h`am bi. nhiˆ˜eu. • Ta c˜ ung k´ y hiˆe.u λmin , λmax v`a λ(A) lˆ `an lu.o..t l`a c´ac gi´a tri. riˆeng nho˙’ nhˆa´t, l´o.n nhˆa´t v`a tˆa.p c´ac gi´a tri. riˆeng cu˙’a ma trˆa.n A. 1.1. B` ai to´ an quy hoa.ch lˆ an phu.o.ng `oi, quy hoa.ch to` Trong mu.c n`ay, ch´ - i.nh l´ ung tˆoi tr`ınh b`ay D y Kuhn-Tucker cho b`ai to´an `oi sau: quy hoa.ch lˆ g0 (x) → inf, x∈D (L1 ) D = {x ∈ S | gi (x) ≤ 0, i = 1, . . . , m}, trong d¯o´ gi : IRn → IR, i = 0, . . . , m, l`a c´ac h`am h`am lˆ `oi, S ⊂ IRn l`a tˆa.p `oi. lˆ B`ai to´an trˆen d¯a˜ d¯u.o..c nghiˆen c´ u.u t` u. rˆa´t s´o.m, mˆo.t trong nh˜ u.ng kˆe´t qua˙’ quan tro.ng l`a d¯.inh l´y Kuhn-Tucker do W. H. Kuhn v`a A. W. Tucker d¯u.a ra v`ao nˇam 1951 trong [22] cˆong tr`ınh khai ph´a cu˙’a Quy hoa.ch lˆ `oi. Trong B`ai to´an (L1 ) h`am Lagrange d¯u.o..c d¯.inh ngh˜ıa nhu. sau: m X L(x, µ0 , . . . , µm ) := µi gi (x), (1.1.3) i=0
10 trong d¯o´ µi , i = 0, 1, . . . , m, nhˆa.n c´ac gi´a tri. thu..c, x ∈ D. Nˆe´u tˆa.p D cu˙’a B`ai to´an (P ) tr`ung v´o.i tˆa.p D cu˙’a B`ai to´an (L1 ) th`ı h`am Lagrange cu˙’a B`ai to´an (P ) c´o da.ng m X L(x, µ0 , . . . , µm ) := f (x) + µi gi (x), (1.1.4) i=1 - i.nh l´ D y 1.1.1. (D- i.nh l´ y Kuhn-Tucker, xem [74]). X´et B` ai to´ an (L). (a) Nˆe´u x∗ l`a nghiˆe.m cu..c tiˆe˙’u cu˙’ a b`ai to´an th`ı tˆ `on ta.i c´ac nhˆan tu˙’. Lagrange µi ≥ 0, i = 0, . . . , m, sao cho ch´ ung khˆong c` ung triˆe.t tiˆeu, tho˙’ a m˜ `eu kiˆe.n Kuhn-Tucker an d¯iˆ L(x∗ , µ0 , . . . , µm ) = min L(x, µ0 , . . . , µm ) (1.1.5) x∈S v` `eu kiˆe.n b` a d¯iˆ u µi gi (x∗ ) = 0 v´o.i mo.i i = 1, . . . , m. (1.1.6) Nˆe´u thˆem d¯iˆ `eu kiˆe.n Slater ∃z ∈ S : gi (z) < 0 v´o.i mo.i i = 1, . . . , m, (1.1.7) an th`ı µ0 6= 0 v`a c´o thˆe˙’ coi µ0 = 1. tho˙’ a m˜ `on ta.i x∗ tho˙’ a m˜an (1.1.5), (1.1.6) v´o.i µ0 = 1 th`ı x∗ l`a nghiˆe.m (b) Nˆe´u tˆ cu..c tiˆe˙’u cu˙’ a B` ai to´ an (L1 ). Da.ng du.o´.i vi phˆan cu˙’a D y Kuhn-Tucker d¯u.o..c ph´at biˆe˙’u nhu. sau: - i.nh l´ - i.nh l´ D y 1.1.2. (xem [74]) Gia˙’ thiˆe´t rˇ `a ng gi : IRn → IR, i = 1, . . . , m, l`a c´ ac h` am lˆ ung liˆen tu.c ´ıt nhˆa´t ta.i mˆo.t d¯iˆe˙’m cu˙’ a tˆa.p lˆ `oi, c` `oi S ⊂ IRn . Cho x∗ l`a mˆo.t nghiˆe.m chˆa´p nhˆa.n d¯u.o..c cu˙’ a B`ai to´an (L1 ). (a) Nˆe´u x∗ l`a nghiˆe.m cu..c tiˆe˙’u cu˙’ a b`ai to´an th`ı tˆ `on ta.i c´ac nhˆan tu˙’. Lagrange µi ≥ 0, i = 0, . . . , m, sao cho ch´ ung khˆong c` ung triˆe.t tiˆeu, an phu.o.ng tr`ınh tho˙’ a m˜ m X 0∈ µi ∂gi (x∗ ) + N (x∗ |S) (1.1.8) i=0
11 v` a µi gi (x∗ ) = 0 v´o.i mo.i i = 1, . . . , m, (1.1.9) trong d¯´ o tˆ a.p ∂gi (x∗ ) := {ξ | gi (x) − gi (x∗ ) ≥ hξ, x − x∗ i ∀x ∈ IRn } a du.´ l` o.i vi phˆ an cu˙’ a gi ta.i x∗ v`a tˆa.p N (x∗ |S) := {ξ | hξ, x − x∗ i ≤ 0 ∀x ∈ S} l` a n´ ap tuyˆe´n cu˙’ a S ta.i x∗ . on ph´ `eu kiˆe.n Slater (1.1.7) tho˙’ a m˜an, th`ı µ0 6= 0 v`a c´o thˆe˙’ coi µ0 = 1. Nˆe´u d¯iˆ `on ta.i x∗ tho˙’ a m˜an (1.1.8), (1.1.9) v´o.i µ0 = 1 th`ı x∗ l`a nghiˆe.m (b) Nˆe´u tˆ cu..c tiˆe˙’u cu˙’ a B` ai to´ an (L1 ). Nhˆ a.n x´ u.c et 1.1.1. Nˆe´u S = IRn th`ı khi d¯´o N (x∗ |S) = {0}, nˆen biˆe˙’u th´ (1.1.8) d¯u.o..c thay bo˙’.i Xm 0∈ µi ∂gi (x∗ ). (1.1.10) i=0 - oˆ´i v´o.i b`ai to´an quy hoa.ch to`an phu.o.ng ta c´o d¯.inh l´ D y sau: y 1.1.3. (Xem [31]). X´et b`ai to´an quy hoa.ch to`an phu.o.ng - i.nh l´ D hM x, xi + hb, xi → inf, x∈D (L2 ) D = {x ∈ IRn | hci , xi ≤ di , i = 1, . . . , m}, trong d¯´o M ∈ IRn×n l` a ma trˆa.n d¯ˆo´i x´u.ng, ci ∈ IRn , i = 1, . . . , m. Khi d¯´o, a nghiˆe.m cu..c tiˆe˙’u d¯.ia phu.o.ng th`ı tˆ nˆe´u x∗ l` `on ta.i c´ac nhˆan tu˙’. Lagrange µi ≥ 0, i = 1, . . . , m, sao cho ch´ `eu kiˆe.n ung tho˙’ a m˜an c´ac d¯iˆ m X ∗ (2M x + b) + µi ci = 0, (1.1.6) i=1 v` a µi (hci , x∗ i − di ) = 0 v´o.i mo.i i = 1, . . . , m. (1.1.7)
12 - i.nh l´ D `oi d¯a diˆe.n, khi d¯´o y 1.1.4. (xem [31], trang 79). Cho D l`a tˆa.p lˆ (a) Nˆe´u M l` a ma trˆ u.ng x´ac d¯.inh du.o.ng v`a D 6= ∅ th`ı B`ai to´an a.n d¯oˆ´i x´ o d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c duy nhˆa´t. (L2 ) c´ (b) Nˆe´u M l` a ma trˆ u.ng x´ac d¯.inh ˆam th`ı d¯iˆe˙’m cu..c tiˆe˙’u d¯.ia phu.o.ng o´i x´ a.n d¯ˆ cu˙’ a B` an (L2 ) (nˆe´u tˆ ai to´ `on ta.i) l`a mˆo.t d¯iˆe˙’m cu..c biˆen cu˙’ a D. Nhˆ a.n x´et 1.1.2. Kˆe´t luˆ a.n (b) cu˙’ a d¯.inh l´y trˆen tu.o.ng d¯u.o.ng v´o.i ph´at biˆe˙’u sau “Nˆe´u M d¯ˆ o´i x´u.ng x´ac d¯.inh du.o.ng th`ı d¯iˆe˙’m cu..c d¯a.i d¯.ia phu.o.ng cu˙’ a B`ai to´ a d¯iˆe˙’m cu..c biˆen cu˙’ a D”. an (Q) l` 1.2. H` `oi suy rˆ am lˆ o.ng thˆ o H`am g : D ⊂ IRn → IR d¯u.o..c go.i l`a lˆ `oi, nˆe´u x0 , x1 ∈ D, th`ı bˆa´t d¯ˇa˙’ng u.c th´ g(xλ ) ≤ (1 − λ)g(x0 ) + λg(x1 ), (1.2.8) tho˙’a m˜an v´o.i mo.i d¯iˆe˙’m xλ ∈ [x0 , x1 ]. H`am lˆ `oi c´o nhiˆ`eu t´ınh chˆa´t th´ u vi. khˆong nh˜ u.ng vˆ `e phu.o.ng diˆe.n gia˙’i t´ıch m`a c`on vˆ `e phu.o.ng diˆe.n tˆo´i u.u h´oa nhu.: tˆa.p m´ u.c du.o´.i cu˙’a h`am lˆ `oi d¯ang x´et l`a lˆ `oi; mˆo˜i d¯iˆe˙’m cu..c tiˆe˙’u d¯i.a phu.o.ng cu˙’a h`am d¯ang x´et l`a d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c; mˆo˜i d¯iˆe˙’m d` u.ng cu˙’a h`am d¯ang x´et l`a d¯iˆe˙’m cu..c tiˆe˙’u to`an cu.c; nˆe´u h`am d¯ang x´et d¯a.t gi´a tri. cu..c d¯a.i trˆen miˆ `en lˆ`oi compact th`ı c˜ ung d¯a.t gi´a tri. cu..c d¯a.i ta.i ´ıt nhˆa´t mˆo.t d¯iˆe˙’m cu..c biˆen. Tuy nhiˆen trong nhiˆ `eu b`ai to´an thu..c tˆe´, h`am cˆ `an x´et c´o mˆo.t sˆo´ t´ınh chˆa´t trˆen nhu.ng khˆong pha˙’i l`a h`am lˆ `oi. Do d¯´o, d¯a˜ xuˆa´t hiˆe.n nhiˆ `eu loa.i h`am lˆ `oi suy rˆo.ng d¯u.o..c d¯aˇ. c tru.ng bo˙’.i mˆo.t trong c´ac t´ınh chˆa´t cu˙’a h`am lˆ `oi nhu.: h`am tu..a lˆ `oi [71], tu..a lˆ`oi hiˆe.n [18], [26], gia˙’ lˆ`oi [25], [72], `oi bˆa´t biˆe´n [14] . . . lˆ T`u. nˇam 1989 xuˆa´t hiˆe.n mˆo.t hu.o´.ng m´o.i mo˙’. rˆo.ng kh´ai niˆe.m h`am lˆ`oi `oi d¯u.o..c H. X. Phu go.i l`a lˆ `oi thˆo. Mˆo.t h`am P -lˆ go.i l`a h`am lˆ `oi thˆo nˆe´u nhu. t´ınh chˆa´t P tho˙’a m˜an v´o.i mo.i x0 , x1 ∈ D m`a kx0 − x1 k ≥ γ, trong d¯´o γ
13 l`a mˆo.t sˆo´ du.o.ng cˆo´ d¯.inh cho tru.o´.c. H`am lˆ `oi thˆo δ-lˆ`oi, δ-tu..a lˆ `oi, δ-lˆ u.a `oi gi˜ d¯u.o..c T. C. Hu, V. Klee v`a D. Larman [16] d¯u.a ra v`ao nˇam 1989. Tiˆe´p d¯o´ nˇam 1991 R. Kl¨otzler d¯`ˆe xuˆa´t kh´ai niˆe.m ρ-lˆ `oi v`a d¯u.o..c nghiˆen c´ u.u bo˙’.i H. Hartwig [15] v`a B. S¨ollner [73]. C´ac h`am γ-lˆ `oi, γ-tu..a lˆ`oi, γ-lˆ `oi d¯ˆo´i x´u.ng, γ-lˆ `oi nhe., γ-lˆ `oi gi˜u.a d¯u.o..c d¯`ˆe xuˆa´t v`a nghiˆen c´ u.u bo˙’.i H. X. Phu [34]–[37], H. X. Phu v`a N. N. Hai [49]. Trong luˆa.n a´n n`ay ch´ ung tˆoi quan tˆam v`a su˙’. du.ng nhiˆ`eu lˆ`an c´ac t´ınh chˆa´t tˆo´i u.u cu˙’a c´ac h`am γ-lˆ `oi ngo`ai [47], Γ-lˆ `oi ngo`ai [44] v`a γ-lˆ `oi trong [41]–[43]. C´ac l´o.p h`am n`ay d¯`ˆeu do H. X. Phu d¯`ˆe xuˆa´t v`a nghiˆen c´ u.u. Tru.o´.c khi tr`ınh b`ay mu.c tiˆe´p theo, ch´ ung tˆoi nhˇa´c la.i d¯.inh ngh˜ıa vˆ `e d¯iˆe˙’m γ-cu..c biˆen, mˆo.t kh´ai niˆe.m d¯u.o..c H. X. Phu gi´o.i thiˆe.u lˆ`an d¯`aˆu tiˆen v`ao nˇam 1994 v`a nghiˆen c´ u.u trong [35]. Kh´ai niˆe.m n`ay s˜e d¯u.o..c su˙’. du.ng trong Chu.o.ng 4 cu˙’a luˆa.n ´an. - i.nh ngh˜ıa 1.2.1. ([35]) Cho γ > 0 v`a D ⊂ X l`a tˆa.p lˆ D `oi trong khˆong gian tuyˆe´n t´ınh d¯.inh chuˆ - iˆe˙’m x ∈ D go.i l`a d¯iˆe˙’m γ-cu..c biˆen (tu.o.ng u a˙’n X. D ´.ng γ-cu..c biˆen ngˇ a.t) cu˙’ a D nˆe´u x0 , x00 ∈ D tho˙’ a m˜an x = 0.5(x0 + x00 ) th`ı suy ra kx0 − x00 k ≤ 2γ (tu.o.ng u ´.ng kx0 − x00 k < 2γ). 1.3. H` `oi ngo` am γ-lˆ ai Trong mu.c n`ay ch´ `e h`am γ-lˆ ung tˆoi tr`ınh b`ay vˆ `oi ngo`ai ([46]). C´ac t´ınh chˆa´t tˆo´i u.u cu˙’a l´o.p h`am n`ay ch´ung tˆoi s˜e khai th´ac su˙’. du.ng trong Chu.o.ng 2. - i.nh ngh˜ıa 1.3.2. ([46]) Cho γ > 0. H`am g : D ⊂ IRn → IR d¯u.o..c go.i l`a D γ-lˆ`oi ngo` ai (hoˇ `oi ngo`ai ngˇa.t) v´o.i d¯ˆo. thˆo γ, nˆe´u v´o.i mo.i x0 , x1 ∈ D a.c γ-lˆ `on ta.i k ∈ IN v` tˆ a λi ∈ [0, 1], i = 0, 1, . . . , k, λ0 = 0, λk = 1, γ 0 ≤ λi+1 − λi ≤ khi i = 0, 1, . . . , k − 1, kx0 − x1 k
14 o.i xλi = (1 − λi )x0 + λi x1 , i = 0, 1, . . . , k, th`ı sao cho v´ g(xλi ) ≤ (1 − λi )g(x0 ) + λi g(x1 ) v´o.i i = 0, 1, . . . , k, (hoˇ a.c g(xλi ) < (1 − λi )g(x0 ) + λi g(x1 ) v´o.i i = 1, . . . , k − 1). - i.nh l´ D y 1.3.5. ([46]) Nˆe´u g : D ⊂ IRn →]−∞, +∞] l`a γ-lˆ `oi ngo`ai th`ı lsc g c˜ `oi ngo`ai, trong d¯o´ lsc g(x) := lim inf y→x g(y) v´o.i mo.i x ∈ D. ung l`a γ-lˆ - i.nh ngh˜ıa 1.3.3. ([46]) Cho γ > 0, M ⊂ IRn , M 6= ∅, M d¯u.o..c go.i l`a D γ-lˆ`oi ngo`ai v´o.i d¯oˆ. thˆo γ nˆe´u x0 , x1 ∈ M v`a kx0 − x1 k > γ suy ra tˆ `on ta.i z0 := x0 , z1 , . . . , zk := x1 ∈ [x0 , x1 ] ∩ M sao cho kzi+1 − zi k ≤ γ v´o.i i=0, 1,. . . , k-1. - i.nh l´ D y 1.3.6. ([46]) K´ y hiˆe.u L(g, α) := {x ∈ D : g(x) ≤ α}, v´o.i α ∈ IR u.c du.o´.i cu˙’a h`am g. Khi d¯´o, nˆe´u g l`a h`am γ-lˆ v`a go.i l`a tˆa.p m´ `oi ngo`ai th`ı `oi ngo`ai. L(g, α) l`a tˆa.p γ-lˆ - i.nh ngh˜ıa 1.3.4. (xem [1], [38]) x∗ ∈ D d¯u.o..c go.i l`a D 1) d¯iˆe˙’m γ-cu..c tiˆe˙’u cu˙’ a g nˆe´u tˆ `on ta.i > 0 sao cho g(x∗ ) ≤ g(x) v´o.i mo.i x ∈ B(x∗ , γ + ) ∩ D; 2) d¯iˆe˙’m γ-infimum cu˙’ a g nˆe´u tˆ `on ta.i > 0 sao cho lim inf ∗ g(x) = inf g(x); x→x x∈B(x∗ ,γ+)∩D 3) d¯iˆe˙’m inf imum to` an cu.c cu˙’ a g nˆe´u lim inf ∗ g(x) = inf g(x). x→x x∈D Mˆ e.nh d `e 1.3.1. ([1], [38]) x∗ l`a d¯iˆe˙’m γ-infimum cu˙’ a g khi v`a chı˙’ khi ¯ˆ d¯iˆe˙’m n` a d¯iˆe˙’m γ-cu..c tiˆe˙’u cu˙’ a lsc g. ay l` T´ınh chˆa´t tˆo´i u.u cu˙’a h`am γ-lˆ `oi ngo`ai d¯u.o..c chı˙’ ra bo˙’.i d¯.inh l´ y sau: