Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cho bài toán quy hoạch bán vô hạn

Chia sẻ: Tri Tâm | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

13
lượt xem 2
download

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

Đề tài có cấu trúc gồm 2 chương trình bày điều kiện tối ưu cho bài toán quy hoạch bán vô hạn trơn đơn mục tiêu không trơn; điều kiện tối ưu cho bài toán quy hoạch bán vô hạn trơn đơn mục tiêu không trơn. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cho bài toán quy hoạch bán vô hạn

I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC o0o É HÚU NGHÀ IU KIN TÈI ×U CHO BI TON QUY HOCH BN VÆ HN LUN VN THC S TON HÅC THI NGUYN, 4/2018
I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC o0o É HÚU NGHÀ IU KIN TÈI ×U CHO BI TON QUY HOCH BN VÆ HN Chuy¶n ng nh: To¡n ùng döng M¢ sè: 8460112 LUN VN THC S TON HÅC NG×ÍI H×ÎNG DN KHOA HÅC PGS.TS. É VN L×U THI NGUYN, 4/2018
1 Möc löc B£ng kþ hi»u 2 Mð ¦u 3 1 i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n ìn möc ti¶u khæng trìn 6 1.1. C¡c kh¡i ni»m v k¸t qu£ bê trñ . . . . . . . . . . . . . . . 6 1.2. i·u ki»n ch½nh quy . . . . . . . . . . . . . . . . . . . . . 10 1.3. i·u ki»n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . 17 2 i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n a möc ti¶u khæng trìn 23 2.1. C¡c k¸t qu£ bê trñ . . . . . . . . . . . . . . . . . . . . . . 23 2.2. i·u ki»n c¦n tèi ÷u . . . . . . . . . . . . . . . . . . . . . 24 2.3. i·u ki»n õ tèi ÷u . . . . . . . . . . . . . . . . . . . . . . 31 K¸t luªn 35 T i li»u tham kh£o 37
2 B£ng kþ hi»u M bao âng cõa tªp M convM bao lçi cõa tªp M coneM nân lçi sinh ra bði M ∅ tªp réng T (M, x) nân ti¸p li¶n cõa M t¤i x A(M, x) nân c¡c ph÷ìng ch§p nhªn ÷ñc cõa M t¤i x ϕ0 (x, d) ¤o h m suy rëng Clarke cõa ϕ t¤i x theo ph÷ìng d ∂c ϕ(x) d÷îi vi ph¥n Clarke cõa ϕ t¤i x ∂ϕ(x) d÷îi vi ph¥n cõa h m lçi ϕ t¤i x (GCQ) i·u ki»n ch½nh quy Guigard (KT CQ) i·u ki»n ch½nh quy KuhnTucker (CCQ) i·u ki»n ch½nh quy Cottle (ACQ) i·u ki»n ch½nh quy Abadie (BCQ) i·u ki»n ch½nh quy cì b£n T x0 tªp c¡c ch¿ sè r ng buëc t½ch cüc (SIP ) b i to¡n quy ho¤ch to¡n håc b¡n væ h¤n ìn möc ti¶u (M OSIP ) b i to¡n quy ho¤ch to¡n håc b¡n væ h¤n a möc ti¶u
3 Mð ¦u 1. Lþ do chån · t i B i to¡n quy ho¤ch b¡n væ h¤n l mët b i to¡n tèi ÷u câ væ h¤n r ng buëc b§t ¯ng thùc. i·u ki»n tèi ÷u l mët bë phªn quan trång cõa lþ thuy¸t tèi ÷u hâa. i·u ki»n tèi ÷u cho c¡c b i to¡n quy ho¤ch b¡n væ h¤n ¢ v ang ÷ñc nhi·u t¡c gi£ quan t¥m nghi¶n cùu. N. Kanzi ([5], 2011) ¢ nghi¶n cùu c¡c i·u ki»n c¦n tèi ÷u cho b i to¡n quy ho¤ch ìn möc ti¶u khæng trìn vîi c¡c h m Lipschitz àa ph÷ìng. C¡c i·u ki»n Karush - Kuhn - Tucker ÷ñc d¨n vîi c¡c i·u ki»n ch½nh quy Guignard, Kuhn - Tucker, Cottle. N. Kanzi v S. Nobakhtian ([6], 2014) ¢ thi¸t lªp c¡c i·u ki»n tèi ÷u cho nghi»m húu hi»u y¸u cõa b i to¡n quy ho¤ch b¡n væ h¤n a möc ti¶u khæng trìn. ¥y l v§n · câ t½nh thíi sü trong to¡n ùng döng. Ch½nh v¼ vªy, tæi chån · t i: "i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n". 2. Nëi dung · t i Luªn v«n tr¼nh b y c¡c i·u ki»n c¦n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n ìn möc ti¶u khæng trìn cõa N. Kanzi «ng tr¶n t¤p ch½ Journal of Global Optimization 49 (2011), 713 - 725, v c¡c i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n a möc ti¶u khæng trìn cõa N. Kanzi v S. Nobakhtian «ng tr¶n t¤p ch½ Optimization Letters 8 (2014), 1517 - 1528. Luªn v«n bao gçm ph¦n mð ¦u, hai ch÷ìng, k¸t luªn v danh möc c¡c t i li»u tham kh£o.
4 Ch÷ìng 1 "i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n trìn ìn möc ti¶u khæng trìn" tr¼nh b y c¡c k¸t qu£ cõa N. Kanzi ([5], 2011) v· i·u ki»n ch½nh quy v i·u ki»n c¦n tèi ÷u KarushKuhnTucker cho b i to¡n quy ho¤ch b¡n væ h¤n ìn möc ti¶u Lipschitz àa ph÷ìng vîi r ng buëc b§t ¯ng thùc. Ch÷ìng 2 "i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n a möc ti¶u khæng trìn" tr¼nh b y c¡c k¸t qu£ cõa N. Kanzi v S. Nobakhtian ([6], 2014) v· i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch to¡n håc b¡n væ h¤n a möc ti¶u Lipschitz àa ph÷ìng vîi r ng buëc b§t ¯ng thùc. C¡c i·u ki»n ch½nh quy ÷ñc ÷a v o º d¨n c¡c i·u ki»n c¦n tèi ÷u Karush KuhnTucker cho nghi»m húu hi»u y¸u. C¡c i·u ki»n õ ÷ñc chùng minh vîi c¡c gi£ thi¸t v· t½nh lçi suy rëng. Luªn v«n n y ÷ñc thüc hi»n t¤i Tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n v ho n th nh d÷îi sü h÷îng d¨n cõa PGS.TS. é V«n L÷u. T¡c gi£ xin ÷ñc b y tä láng bi¸t ìn ch¥n th nh v s¥u sc tîi th¦y h÷îng d¨n khoa håc cõa m¼nh, ng÷íi ¢ °t v§n · nghi¶n cùu, d nh nhi·u thíi gian h÷îng d¨n v tªn t¼nh gi£i ¡p nhúng thc mc cõa t¡c gi£ trong suèt qu¡ tr¼nh l m luªn v«n. T¡c gi£ công ¢ håc tªp ÷ñc r§t nhi·u ki¸n thùc chuy¶n ng nh bê ½ch cho cæng t¡c v nghi¶n cùu cõa b£n th¥n. T¡c gi£ xin b y tä láng c£m ìn s¥u sc tîi c¡c th¦y gi¡o, cæ gi¡o ¢ tham gia gi£ng d¤y lîp cao håc To¡n K10Y, nh tr÷íng v c¡c pháng chùc n«ng cõa tr÷íng, khoa To¡n - Tin, tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n ¢ quan t¥m v gióp ï t¡c gi£ trong suèt thíi gian håc tªp t¤i tr÷íng. Xin ch¥n th nh c£m ìn anh chà em lîp cao håc K10Y, b¤n b± v çng nghi»p ¢ trao êi, ëng vi¶n v kh½ch l» t¡c gi£ trong qu¡ tr¼nh håc tªp, nghi¶n cùu v l m luªn v«n.
5 Th¡i Nguy¶n, ng y 05 th¡ng 4 n«m 2018 T¡c gi£ luªn v«n é Húu Nghà
6 Ch÷ìng 1 i·u ki»n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n ìn möc ti¶u khæng trìn Ch÷ìng 1 tr¼nh b y c¡c k¸t qu£ cõa N. Kanzi ([5], 2011) v· i·u ki»n ch½nh quy v i·u ki»n c¦n tèi ÷u cho b i to¡n quy ho¤ch b¡n væ h¤n ìn möc ti¶u Lipschitz àa ph÷ìng vîi r ng buëc b§t ¯ng thùc. C¡c i·u ki»n ch½nh quy Guignard, KuhnTuckerCottle v t½nh ch§t Pshenichnyi LevinValadire (PLV) ÷ñc tr¼nh b y còng vîi mèi quan h» giúa c¡c i·u ki»n ch½nh quy v t½nh ch§t (PLV). i·u ki»n c¦n tèi ÷u KarushKuhn Tucker ÷ñc chùng minh vîi vîi mët trong i·u ki»n ch½nh quy â. 1.1. C¡c kh¡i ni»m v k¸t qu£ bê trñ B i to¡n quy ho¤ch b¡n væ h¤n (SIP) l mët b i to¡n tèi ÷u vîi tªp ch§p nhªn ÷ñc, ÷ñc mæ t£ bði væ h¤n c¡c r ng buëc b§t ¯ng thùc. Ta x²t b i to¡n quy ho¤ch b¡n væ h¤n sau ¥y:
7 inf f (x), gi (x) ≤ 0, i ∈ I, (SIP) x ∈ Rn , trong â f , gi , i ∈ I l c¡c h m Lipschitz àa ph÷ìng tø Rn v o R∪{+∞}; tªp ch¿ sè I l tòy þ, khæng nh§t thi¸t húu h¤n ph¦n tû, kh¡c ∅. Cho mët tªp M 6= ∅ trong Rn , k½ hi»u M , conv(M ) v cone(M ) l¦n l÷ñt l bao âng, bao lçi v nân lçi (chùa iºm 0) sinh bði M . Nân cüc v nân cüc ch°t cõa M ÷ñc x¡c ành bði: M 0 := {d ∈ Rn |hx, di ≤ 0, ∀x ∈ M } M s := {d ∈ Rn |hx, di < 0, ∀x ∈ M }, trong â h·, ·i l t½ch væ h÷îng trong Rn . Chó þ r¬ng M 0 l nân lçi âng. D¹ d ng ch¿ ra r¬ng, n¸u M s 6= ∅ th¼ M s = M 0 . ành lþ song cüc ph¡t biºu r¬ng M 00 = cone(M ), trong â cone(M ) l k½ hi»u nân lçi âng cõa M. Nhc l¤i mët sè kh¡i ni»m v ành ngh¾a cõa gi£i t½ch Lipschitz trong [2]. ành ngh¾a 1.1 Gi£ sû M ⊆ Rn v x b ∈ M. I. Nân ti¸p li¶n cõa M t¤i x b ÷ñc x¡c ành bði b) := h ∈ Rn |tçn t¤i {tk } ⊂ R+ , tk → 0, {hk } ⊂ Rn , hk → h T (M, x sao cho: xb + tk hk ∈ M vîi måi k ∈ N . II. Nân c¡c ph÷ìng ch§p nhªn ÷ñc cõa M ÷ñc x¡c ành bði b) := h ∈ Rn | vîi måi {tk } ⊂ R+ , tk → 0, tçn t¤i {hk } ⊂ Rn , A(M, x hk → h, sao cho: x b + tk hk ∈ M vîi måi k ∈ N .
8 Chó þ r¬ng T (M, x b) v A(M, x b) l c¡c nân âng (nâi chung khæng lçi) trong Rn , v ta luæn câ quan h» b) ⊆ T (M, x A(M, x b). (1.1) ành ngh¾a 1.2 Gi£ sû ϕ : Rn → R ∪ {+∞} l h m Lipschitz v x b ∈ dom(ϕ). I. ¤o h m suy rëng Clarke cõa ϕ t¤i x b theo ph÷ìng d ∈ Rn ÷ñc x¡c ành bði ϕ(y + td) − ϕ(y) ϕ0 (b x; d) := lim sup ; y→b x;t→0 t II. D÷îi vi ph¥n Clarke cõa ϕ t¤i x b ÷ñc x¡c ành bði x) := ξ ∈ Rn |ϕ0 (b x; d) ≥ hξ, di, ∀d ∈ Rn ; ∂c ϕ(b III. Ta nâi r¬ng ϕ l ch½nh quy theo ngh¾a Clarke t¤i x b n¸u x; d) = ϕ0 (b ϕ0 (b x, d), ∀d ∈ Rn , trong â ϕ0 (b x, d) l ¤o h m theo ph÷ìng cê iºn cõa ϕ t¤i x b theo ph÷ìng d. Chó þ r¬ng d÷îi vi ph¥n Clarke cõa h m Lipschitz àa ph÷ìng t¤i måi iºm trong cõa mi·n húu hi»u th¼ luæn kh¡c réng, compact v lçi. D÷îi vi ph¥n Clarke quy v· gradient cê iºn cõa h m kh£ vi li¶n töc v quy v· d÷îi vi ph¥n theo gi£i t½ch lçi cho c¡c h m lçi (xem [1]). C¡c h m lçi húu h¤n v kh£ vi li¶n töc l c¡c v½ dö v· c¡c h m ch½nh quy theo ngh¾a Clarke. Mët lîp rëng cõa c¡c h m ch½nh quy theo ngh¾a Clarke l lîp c¡c h m trìn. Ta nhc l¤i mët k¸t qu£ trong gi£i t½ch lçi [1] m ta s³ sû döng sau n y.
9 ành l½ 1.1 Gi£ sû {Mα|α ∈ Λ} l mët hå b§t ký c¡c tªp lçi kh¡c réng trong Rn. Khi â, måi vec tì kh¡c khæng cõa conv(∪α∈ΛMα) ·u biºu di¹n ÷ñc th nh tê hñp tuy¸n t½nh khæng ¥m cõa n ho°c ½t hìn c¡c vec tì ëc lªp tuy¸n t½nh, m méi vec tì thuëc Mα kh¡c nhau. ành l½ 1.2 Gi£ sû M l mët tªp con kh¡c réng cõa Rn sao cho 0 ∈/ conv(M ). Khi â cone(M ) l mët nân âng. C¡c k¸t qu£ sau ¥y cõa gi£i t½ch Lipschitz [2] l cæng cö chùng minh c¡c k¸t qu£ cõa ch÷ìng n y. ành l½ 1.3 Gi£ sû ϕ v ψ l Lipschitz àa ph÷ìng tø Rn v o R, v xb ∈ dom(ϕ) ∩ dom(ψ). Khi â, c¡c t½nh ch§t sau óng: a. ϕ0(bx; d) = max {hξ, di|ξ ∈ ∂cϕ(bx)} ∀d ∈ Rn b. d −→ ϕ0(bx; d) l mët h m lçi, v x) = ∂ϕ0 (b ∂c ϕ(b x; ·)(0). trong â ∂ϕ0(bx; ·) k½ hi»u d÷îi vi ph¥n cõa h m lçi ϕ0(bx; ·). c. x −→ ∂cϕ(x) l mët h m a trà nûa li¶n töc tr¶n. d. ∂c(ϕ + ψ)(x) ⊆ ∂cϕ(x) + ∂cψ(x). Hìn núa, n¸u ϕ v ψ l ch½nh quy theo ngh¾a Clarke t¤i x th¼ ϕ + ψ còng ch½nh quy theo ngh¾a Clarke t¤i x v ¯ng thùc óng trong cæng thùc tr¶n. e. N¸u xb l mët iºm cüc tiºu cõa ϕ tr¶n Rn th¼ 0 ∈ ∂cϕ(x).
10 ành l½ 1.4 (ành l½ gi¡ trà trung b¼nh Lebourg) Gi£ sû x, y ∈ Rn, v ϕ l h m Lipschitz àa ph÷ìng tø Rn v o R. Khi â, tçn t¤i iºm u trong o¤n (x, y) sao cho ϕ(y) − ϕ(x) ∈ h∂c ϕ(u), y − xi. 1.2. i·u ki»n ch½nh quy Trong möc n y ta ÷a v o v so s¡nh mët sè i·u ki»n ch½nh quy (gåi tt l CQ) cho mët h» b¡n væ h¤n Lipschitz àa ph÷ìng. Gi£ sû I l mët tªp ch¿ sè b§t k¼ (nh÷ng kh¡c réng) v gi£ sû {gi : Rn → R|i ∈ I} l mët hå c¡c h m Lipschitz àa ph÷ìng. Ta x²t h» b¡n væ h¤n c¡c r ng buëc, gåi tt l π . Sau ¥y ta gi£ sû r¬ng tªp ch§p nhªn ÷ñc cõa b i to¡n l kh¡c réng, tùc l P := {x ∈ Rn |gi (x) ≤ 0, ∀i ∈ I} = 6 ∅. Vîi iºm x ∈ P , ta ành ngh¾a (quy ÷îc l ∪i∈∅ Xi = ∅): I x := {i ∈ I|gi (x) = 0}, v [ Z(x) := ∂c gi (x). i∈I x Düa v o kh¡i ni»m nân ti¸p li¶n, nân ch§p nhªn ÷ñc v d÷îi vi ph¥n Clarke, chóng tæi tr¼nh b y mð rëng i·u ki»n ch½nh quy cho π . ành ngh¾a 1.3 Gi£ sû x ∈ P . Ta nâi r¬ng π thäa m¢n (a) i·u ki»n ch½nh quy Guignard (k½ hi»u GCQ) t¤i x, n¸u Z 0 (x) ⊆ conv(T (P, x)), trong â Z 0 (x) l nân cüc cõa Z(x); (b) i·u ki»n ch½nh quy Kuhn - Tucker (k½ hi»u KTCQ) t¤i x, n¸u Z 0 (x) ⊆ A(P, x);
11 (c) i·u ki»n ch½nh quy Cottle (k½ hi»u CCQ) t¤i x, n¸u Z s (x) 6= ∅, trong â Z s (x) l nân cüc ch°t cõa Z(x). Nhªn x²t 1.1 i·u ki»n ch½nh quy (GCQ) v mèi quan h» cõa nâ vîi c¡c i·u ki»n ch½nh quy Abadie, Zangwill, v i·u ki»n ch½nh quy cì b£n ÷ñc nghi¶n cùu trong [7]. ành lþ sau ¥y ch¿ ra r¬ng (GCQ) t÷ìng ÷ìng vîi ¯ng thùc Z 0 (x) = conv(T (P, x)). ành l½ 1.5 [5] Gi£ sû x ∈ P v vîi méi i ∈ I x, gi l mët h m ch½nh quy theo ngh¾a Clarke t¤i x. Khi â, conv(T (P, x)) ⊆ Z 0(x). Chùng minh Gi£ sû d ∈ T (P, x) l ph¦n tû b§t k¼. Khi â, tçn t¤i tk ↓ 0 and dk → d sao cho x + tk dk ∈ P . Nh÷ vªy theo ành ngh¾a cõa P , ta câ gi (x + tk dk ) ≤ 0, ∀i ∈ I. Gi£ sû r¬ng i0 ∈ I x . Khi â, gi0 (x) = 0 v v¼ vªy, gi0 (x + tk dk ) − gi0 (x + tk d) gi0 (x + tk d) − gi0 (x) + tk tk k gi (x + tk d ) = 0 ≤ 0. tk Ta k½ hi»u h¬ng sè Lipschitz cõa gi ð g¦n x l Li . Bði v¼ tk l õ g¦n 0, cho n¶n ta câ
gi0 (x + tk dk ) − gi0 (x + tk d)
≤ Li kdk − dk → 0 0 (khi tk → 0).
tk