Luận văn Thạc sĩ Toán học: Bài toán quy hoạch lồi

Chia sẻ: Quỳnh Quỳnh | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

329
lượt xem 76
download

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

Luận văn Thạc sĩ Toán học - Bài toán quy hoạch lồi nhằm trình bày một số phương pháp cơ bản nhất cho bài toán quy hoạch lồi. Cụ thể luận văn trình bày các phương án sau: các phương pháp sử dụng đạo hàm bậc nhất, phương pháp Newton và các phương pháp hàm phạt. Mời bạn đọc cùng tham khảo.

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: Bài toán quy hoạch lồi

i M cl c M c l c............................................ i L i c m ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii M đ u............................................ 1 Chương 1. Các ki n th c cơ b n v t p l i và hàm l i . . . . . . . . . 2 1.1. T p l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Hàm l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Chương 2. Đi u ki n c c ti u hàm l i . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1. Bài toán quy ho ch l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1. Các khái ni m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.2. S t n t i nghi m t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.3. Đi u ki n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. T i ưu có ràng bu c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1. Đ i ng u Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.2. Đi u ki n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chương 3. M t s phương pháp gi i bài toán quy ho ch l i . . 27 3.1. Các thu t toán s d ng đ o hàm b c nh t . . . . . . . . . . 27 3.1.1. Thu t toán gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.2. Phương pháp chi u Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.1.3. Thu t toán chi u dư i gradient x p x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.4. Thu t toán Frank-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2. Phương pháp Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3. Phương pháp hàm ph t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.1. Phương pháp hàm ph t đi m ngoài. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.2. Phương pháp hàm ph t đi m trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 K t lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Tài li u tham kh o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
ii L I C M ƠN Trư c khi trình bày n i dung chính c a khóa lu n, em xin bày t lòng bi t ơn sâu s c t i GS.TSKH. Lê Dũng Mưu ngư i đã t n tình hư ng d n và giúp đ em trong su t quá trình h c t p và nghiên c u đ em có th hoàn thành khóa lu n này. Em cũng xin bày t lòng bi t ơn chân thành t i quý th y, cô giáo Vi n Toán h c - Vi n Khoa h c và Công ngh Vi t Nam đã gi ng d y và giúp đ em hoàn thành khóa h c. Nhân d p này em cũng xin chân thành c m ơn Ban Giám hi u, các b n đ ng nghi p Trư ng Đ i h c Công ngh Thông tin và Truy n thông - Đ i h c Thái Nguyên, gia đình và b n bè đã luôn đ ng viên, giúp đ và t o đi u ki n cho em v m i m t trong su t quá trình h c t p và th c hi n khóa lu 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. Tác gi r t mong nh n đư c ý ki n đóng góp c a quý 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à N i, ngày 30 tháng 08 năm 2011 Tác gi Quách Th Mai Liên
1 M Đ U Quy ho ch l i là m t l p bài toán cơ b n c a t i ưu hóa. M t đ c đi m cơ b n nh t c a l p bài toán này là m i đi m c c ti u đ a phương đ u là c c ti u tuy t đ i. Tính ch t quan tr ng này cho phép các lý thuy t có tính đ a phương, như gi i h n, vi phân,... có th áp d ng tr c ti p vào quy ho ch l i. Lý thuy t v bài toán quy ho ch l i đã đư c quan tâm nghiên c u nhi u và đã thu đư c nhi u k t qu quan tr ng d a trên lý thuy t c a gi i tích l i và t i ưu hóa; v phương di n tính toán, đã có khá nhi u phương pháp h u hi u cho l p bài toán này. Các phương pháp đó đã đư c gi i thi u trong cu n sách T i ưu l i (Convex Optimization) c a các tác gi Stephen Boyd and Lieven Vandenberghe do nhà xu t b n Cambridge University Press in năm 2004. M c đích c a b n lu n văn này là đ trình bày m t s phương pháp cơ b n nh t cho bài toán quy ho ch l i. C th lu n văn trình bày các phương pháp sau: các phương pháp s d ng đ o hàm b c nh t, phương pháp Newton và các phương pháp hàm ph t. Lu n văn g m có 3 chương: • Chương 1: Gi i thi u các ki n th c cơ b n nh t v gi i tích l i, đ c bi t chú tr ng vào phép chi u vuông góc lên m t t p l i đóng và tính dư i vi phân c a hàm l i; chúng đư c s d ng trong các chương ti p theo. • Chương 2: Trình bày đ i ng u Lagrange và áp d ng Đ nh lý Krush - Kuhn - Tucker, Đ nh lý Kuhn - Tucker đ gi i bài toán quy ho ch l i và các đ nh lý v s t n t i nghi m t i ưu c a bài toán quy ho ch l i. • Chương 3: Trình bày các phương pháp gi i bài toán quy ho ch l i như: phương pháp dùng đ o hàm b c nh t gradient, chi u gradient và trư ng h p t ng quát c a nó là chi u dư i gradient x p x , thu t toán Frank - Wolf, phương pháp Newton dùng đ o hàm b c hai và các phương pháp hàm ph t.
2 Chương 1 Các ki n th c cơ b n v t p l i và hàm l i Trong lu n văn này, ta ch xét không gian h u h n chi u I n v i tích R vô hư ng đư c ký hi u là ., . và chu n tương ng đư c ký hi u là . . Chương này trình bày m t s ki n th c cơ b n nh t c a gi i tích l i s đư c s d ng chương sau. N i dung c a chương đư c trích d n ch y u t tài li u tham kh o [1] và [3]. 1.1. T pl i Đ nh nghĩa 1.1. Cho hai đi m a, b ∈ I n . R (i) M t đư ng th ng đi qua hai đi m a, b là t p h p có d ng {x ∈ I n : x = αa + βb, α, β ∈ I α + β = 1}. R R, (ii) Đo n th ng n i hai đi m a, b trong I n có d ng R {x ∈ I n : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. R Đ nh nghĩa 1.2. M t t p D đư c g i là t p affine n u D ch a m i đư ng th ng đi qua hai đi m b t kỳ x, y ∈ D, t c là ∀x, y ∈ D, ∀λ ∈ I ⇒ λx + (1 − λ)y ∈ D. R M nh đ 1.1. T p D = ∅ là t p affine khi và ch khi nó có d ng D = M + a v i M là m t không gian con c a I n và a ∈ I n . Không gian M R R đư c xác đ nh duy nh t và đư c g i là không gian con song song c a D.
3 Đ nh nghĩa 1.3. Th nguyên (hay chi u) c a m t t p affine D là th nguyên c a không gian con song song v i D và đư c ký hi u là dim D. Đ nh nghĩa 1.4. Siêu ph ng trong không gian I n là m t t p h p các R đi m có d ng {x ∈ I n : aT x = α}, R trong đó a ∈ I n là m t vectơ khác 0 và α ∈ I . R R Đ nh nghĩa 1.5. Cho a ∈ I n là m t vectơ khác 0 và α ∈ I . T p R R {x : aT x ≥ α}, đư c g i là n a không gian đóng và t p {x : aT x > α} g i là n a không gian m . Đ nh nghĩa 1.6. M t t p D đư c g i là m t t p l i n u ∀a, b ∈ D và 0 ≤ λ ≤ 1 ⇒ λa + (1 − λ)b ∈ D. Đ nh lí 1.1. T p l i là đóng v i phép giao, phép c ng, phép nhân v i m t s th c. T c là, n u C và D là hai t p l i trong I n thì C ∩ D, λC + βD R cũng là các t p l i. Đ nh nghĩa 1.7. Ta nói x là t h p l i c a các đi m (vectơ) x1 , ..., xk n u k k x= λj xj , λj ≥ 0 (j = 1, ..., k), λj = 1. j=1 j=1 M nh đ 1.2. T p h p D là l i khi và ch khi nó ch a m i t h p l i c a các đi m c a nó. T c là, D l i khi và ch khi k k ∀k ∈ I ∀λ1 , ..., λk ≥ 0 : N, λj = 1, ∀x1 , ..., xk ∈ D ⇒ λj xj ∈ D. j=1 j=1 Đ nh nghĩa 1.8. M t t p đư c g i là t p l i đa di n n u nó là giao c a m t s h u h n các n a không gian đóng.
4 Đ nh nghĩa 1.9. Bao l i c a m t t p D là giao c a t t c các t p l i ch a D. Bao l i c a t p D đư c ký hi u là coD. Bao l i c a m t t p D là t p l i nh nh t ch a D. Đ nh nghĩa 1.10. Th nguyên c a m t t p l i D đư c cho b i th nguyên c a đa t p affine nh nh t ch a D. Đa t p affine này đư c g i là bao affine c a D và đư c ký hi u là aff D. Th nguyên c a t p l i D s đư c ký hi u là dimD. Đ nh nghĩa 1.11. M t đi m a c a m t t p l i D g i là đi m trong tương đ i n u v i m i x ∈ D đ u có m t s λ > 0 đ cho a + λ(x − a) ∈ D. T p các đi m trong tương đ i c a D đư c ký hi u riD. Đ nh nghĩa 1.12. M t t p D đư c g i là nón n u ∀λ > 0, ∀x ∈ D ⇒ λx ∈ D. M t nón đư c g i là nón nh n n u nó không ch a đư ng th ng. M t nón đư c g i là nón l i n u nó đ ng th i là t p l i. N u nón l i này l i là m t t p l i đa di n thì ta nói nó là nón l i đa di n. Đ nh nghĩa 1.13. Cho D ⊆ I n là m t t p l i và x0 ∈ D. R (i) T p ND (x0 ) := {ω ∈ I n : R ω, x − x0 ≤ 0, ∀x ∈ D}. g i là nón pháp tuy n ngoài c a D t i x0 và t p −ND (x0 ) đư c g i là nón pháp tuy n trong c a D t i x0 . (ii) T p ND (x0 ) := {ω ∈ I n : R ω, x − x0 ≤ , ∀x ∈ D} đư c g i là nón pháp tuy n c a D t i x0 . Hi n nhiên 0 ∈ ND (x0 ) và dùng đ nh nghĩa ta có ND (x0 ) là m t nón l i đóng. Trong chương 2 và chương 3, ta s s d ng các đ nh lý tách t p l i, đây cũng là nh ng đ nh lý cơ b n nh t c a gi i tích l i.
5 Đ nh nghĩa 1.14. Cho hai t p C và D, ta nói r ng siêu ph ng H := {x : v, x = λ} (i) tách hai t p C và D n u v, a ≤ λ ≤ v, b , ∀a ∈ C, b ∈ D. (ii) tách ch t C và D n u: v, a < λ < v, b , ∀a ∈ C, b ∈ D. (iii) tách m nh C và D n u: sup v, x < λ < inf v, y . x∈A y∈B Đ nh lí 1.2 (Đ nh lý tách 1). Cho C và D là hai t p l i khác r ng trong I n sao cho C ∩ D = ∅. Khi đó có m t siêu ph ng tách C và D. R Đ nh lí 1.3 (Đ nh lý tách 2). Cho C và D là hai t p l i khác r ng trong I n sao cho C ∩ D = ∅. Gi s có ít nh t m t t p là compăc. Khi đó hai R t p C và D có th tách m nh đư c b i m t siêu ph ng. H qu 1.1 (B đ Farkas). Cho a ∈ I n và A là ma tr n c p m × n. R Khi đó a, x ≥ 0 v i m i x th a mãn Ax ≥ 0, khi và ch khi t n t i y ≥ 0 thu c I m sao cho a = AT y . R Ý nghĩa hình h c c a b đ Farkas: siêu ph ng đi qua g c t a đ a, x = 0 đ nón Ax ≥ 0 v m t phía c a nó khi và ch khi vectơ pháp tuy n a c a siêu ph ng n m trong nón sinh b i các hàng c a ma tr n A. Đ nh nghĩa 1.15. Cho D = ∅ (không nh t thi t l i) và y là m t vectơ b t kỳ, đ t: dD (y) := inf x − y . x∈D Ta nói dD (y) là kho ng cách t y đ n D. N u t n t i π ∈ D sao cho dD (y) = y − π , thì ta nói π là hình chi u (vuông góc) c a y trên D và ký hi u là π = PD (y).
6 Theo đ nh nghĩa, ta th y r ng hình chi u PD (y) c a y trên D là nghi m c a bài toán t i ưu 1 2 min x−y : x∈D . x∈D 2 Nói cách khác vi c tìm hình chi u c a y trên D có th đưa v vi c tìm c c ti u c a hàm toàn phương ||x − y||2 trên D. N u D = ∅ thì dD (y) h u h n, vì 0 ≤ dD (y) ≤ x − y , ∀x ∈ D. M nh đ 1.3. Cho D là m t t p l i đóng khác r ng. Khi đó (i) V i m i y ∈ I n , π ∈ D hai tính ch t sau là tương đương: R a) π = PD (y), b) y − π ∈ ND (π). (ii) V i m i y ∈ I n , hình chi u PD (y) c a y trên D luôn t n t i và duy R nh t. (iii) PD (x) − PD (y) ≤ x − y , ∀x, y ∈ I n (tính không giãn), R 2 (iv) PD (x)−PD (y) ≤ PD (x)−PD (y), x−y , ∀x, y ∈ I n (tính đ ng b c). R 1.2. Hàm l i Trong ph n này ta ch xét nh ng hàm f không nh n giá tr −∞. Đ nh nghĩa 1.16. M t hàm s f xác đ nh trên t p l i D đư c g i là (i) l i trên D n u f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 < λ < 1. (ii) l i ch t n u f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 < λ < 1. (iii) lõm (lõm ch t) n u −f là l i (l i ch t).
7 Đ nh lí 1.4. Cho f và g là các hàm l i trên t p l i C và D tương ng. Khi đó các hàm s αf +βg, (∀α, β ≥ 0) và max{f, g} cũng l i trên C ∩D. M t hàm l i có th không liên t c t i m t đi m trên biên mi n xác đ nh c a nó. Tuy nhiên, nó liên t c t i m i đi m trong c a t p đó theo đ nh lý sau: Đ nh lí 1.5. M t hàm l i xác đ nh trên t p l i D thì liên t c t i m i đi m trong c a D. Tính ch t sau đây đ c trưng cho m t hàm l i kh vi, và thu n l i đ ki m tra tính l i c a m t hàm s . Ký hi u f (a) ho c f (a) là đ o hàm c a f t i a. Đ nh lí 1.6. Cho f : D → I là m t hàm kh vi trên t p l i m D. Đi u R ki n c n và đ đ f l i trên D là f (x) + f (x), y − x ≤ f (y), ∀x, y ∈ D. N u f kh vi hai l n thì đi u ki n c n và đ đ f l i trên D là v i m i x ∈ A ma tr n Hessian H(x) c a f t i x xác đ nh không âm, t c là y T H(x)y ≥ 0, ∀x ∈ D, y ∈ I n . R Như v y, m t d ng toàn phương xT Qx là m t hàm l i khi và ch khi Q xác đ nh không âm. M t d ng toàn phương là m t hàm l i ch t khi và ch khi ma tr n c a nó xác đ nh dương. Tính kh vi c a m t hàm l i gi vai trò quan tr ng trong các phương pháp t i ưu hóa. L p các hàm l i có nh ng tính ch t kh vi r t đ p mà các l p hàm khác không có. Gi s f : I n → I ∪ {+∞} là hàm l i. Ta R R có các khái ni m sau Đ nh nghĩa 1.17. Cho > 0. M t véc tơ w ∈ I n đư c g i là m t − R dư i gradient c a f t i x0 ∈ I n n u: R w, x − x0 ≤ f (x) − f (x0 ) + , ∀x ∈ I n . R
8 T p h p t t c các −dư i gradient g i là − dư i vi phân c a hàm f t i x0 , kí hi u là ∂ f (x0 ) := {w ∈ I n : R w, x − x0 ≤ f (x) − f (x0 ) + , ∀x ∈ I n }. R Đ nh nghĩa 1.18. Véctơ w ∈ I n đư c g i là dư i gradient c a f t i R x0 ∈ I n n u: R w, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ I n . R T p h p t t c các dư i gradient c a hàm f t i x0 đư c g i là dư i vi phân c a f t i x0 , kí hi u là: ∂f (x0 ) := {w ∈ I n : R w, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ I n }. R Hàm f đư c g i là kh dư i vi phân t i x0 n u ∂f (x0 ) = ∅. Ví d 1.1. Cho D là m t t p l i, khác r ng c a không gian I n . Xét hàm R ch trên t p D 0 n u x ∈ D, δD (x) := +∞ n u x ∈ D. / V i m i x0 ∈ D ta có: w ∈ ∂δD (x0 ) ⇔ δD (x) − δD (x0 ) ≥ w, x − x0 , ∀x ∈ D ⇔ 0 ≥ w, x − x0 , ∀x ∈ D ⇔ w ∈ ND (x0 ). Ch ng t ∂δD (x0 ) = ND (x0 ), ∀x0 ∈ D. Cũng có trư ng h p t n t i nh ng đi m x∗ t i đó f không có dư i vi phân, nghĩa là t p ∂f (x∗ ) có th là m t t p r ng. Tuy nhiên, đ i v i hàm l i, ta có đ nh lý sau: Đ nh lí 1.7. Cho f là m t hàm l i (h u h n) trên t p l i D. Lúc đó f có dư i vi phân t i m i đi m thu c riD. T đ nh lý này suy ra r ng n u f là m t hàm l i trên toàn không gian I n thì nó có dư i vi phân t i m i đi m, vì riI n = I n . R R R
9 Đ nh nghĩa 1.19. Ta g i đ o hàm theo hư ng d c a m t hàm s f (không nh t thi t là l i) t i đi m x là đ i lư ng f (x + λd) − f (x) f (x, d) := lim+ λ→0 λ n u gi i h n này t n t i. Đ nh lí 1.8. N u f là m t hàm l i trên t p l i D thì v i m i x ∈ D và m i d sao cho x + d ∈ D, đ o hàm theo hư ng d c a f t i x luôn t n t i và nghi m đúng f (x, d) ≤ f (x + d) − f (x). Ngoài ra v i m i đi m x c đ nh, f (x, .) là m t hàm l i trên t p l i {d : x + d ∈ D}. T đ nh lý này d dàng suy ra r ng n u f kh vi thì f (x, d) = f (x), d , ∀d. (1.1) Nói chung m t hàm l i không nh t thi t kh vi t i m i đi m. Dư i vi phân là m t khái ni m m r ng c a đ o hàm trong trư ng h p hàm không kh vi. Trong trư ng h p ∂f (x∗ ) ch g m duy nh t m t đi m thì f kh vi t i x∗ . Trong ph n ti p theo, ta s đ nh nghĩa v - nghi m và - chi u c a m t hàm l i. Đ nh nghĩa 1.20. Cho D ⊆ I n là t p l i, f : D → I là hàm l i và R R ≥ 0. Xét bài toán: min f (x). (P ) x∈D M t đi m x ∈ D đư c g i là ¯ - nghi m c a bài toán (P ) n u: f (¯) ≤ min f (x) + . x x∈D M nh đ 1.4. Vectơ x ∈ D là ¯ - nghi m c a bài toán (P ) khi và ch khi 0 ∈ ∂ f (¯). x
10 Ch ng minh. Gi s x ∈ D là ¯ - nghi m c a bài toán (P ). Khi đó f (¯) ≤ f (x) + , ∀x ∈ D. x Suy ra 0, x − x ≤ f (x) − f (¯) + , ∀x ∈ D ⇔ 0 ∈ ∂ (f (¯)) . ¯ x x Ngư c l i, n u 0 ∈ ∂ (f (¯)) thì ta có: x 0, x − x ≤ f (x) − f (¯) + , ∀x ∈ D. ¯ x Ch ng t x là − nghi m c a bài toán (P ). ¯ Đ nh nghĩa 1.21. Cho D là m t t p l i đóng khác r ng trong I n , x ∈ I n R R và ≥ 0 . M t đi m px ∈ D đư c g i là - chi u c a x trên D n u px là m t - nghi m c a bài toán 1 2 min x−y (Q) y∈D 2 nghĩa là: 1 1 x − px 2 ≤ x − PD (x) 2 + , 2 2 trong đó PD (x) là hình chi u c a x trên D. M nh đ 1.5. Cho D là t p l i đóng khác r ng. Khi đó px là - chi u c a x trên D khi và ch khi x − px , px − y ≥ − , ∀y ∈ D. (1.2) Ch ng minh. Gi s px là − chi u c a x trên D. Ta có 1 2 1 2 min x−y ⇔ min x−y + δD (y) (1.3) y∈D 2 2 trong đó δD (y) là hàm ch c a y trên t p D. Đ t 1 f (y) := x − y 2, x ∈ I n. R 2
11 Theo Đ nh nghĩa 1.21, px là − nghi m c a bài toán (1.3). T M nh đ 1.4 ta đư c 0 ∈ ∂ [f (px ) + δD (px )] = ∂ f (px ) + ∂ δD (px ). (1.4) Theo Ví d 1.1, ∂ δD (px ) = ND (px ) nên t (1.4) ta có: 0 ∈ {−x + px } + ND (px ). Suy ra (x − px ) ∈ ND (px ) ⇔ x − px , ω − px ≤ , ∀ω ∈ D. Ngư c l i, gi s có (1.2). Ta có 2 2 2 x − PD (x) = x − px + 2 x − px , px − PD (x) + px − PD (x) 2 ≥ x − px + 2 x − px , px − PD (x) . Suy ra 2 2 x − PD (x) ≥ x − px −2 . Ch ng t px là − chi u c a x trên D.
12 Chương 2 Đi u ki n c c ti u hàm l i Chương này trình bày m t s ki n th c quan tr ng ph c v cho chương 3. Đó là đ i ng u Lagrange và áp d ng vào gi i bài toán t i ưu l i; các đ nh lý cơ b n như Đ nh lý Karush - Kuhn - Tucker, Đ nh lý Kuhn - Tucker. N i dung c a chương ch y u đư c trích d n t tài li u tham kh o [1]. 2.1. Bài toán quy ho ch l i 2.1.1. Các khái ni m Cho D ⊆ I n và f : I n → I . Xét bài toán quy ho ch toán h c R R R min{f (x) : x ∈ D}. (P ) Bài toán này đư c hi u là hãy tìm m t đi m x∗ ∈ D sao cho f (x∗ ) ≤ f (x) v i m i x ∈ D. M i đi m x∗ ∈ D đư c g i là m t phương án ch p nh n đư c c a bài toán (P ). T p D đư c g i là mi n (t p) ch p nh n đư c, f đư c g i là hàm m c tiêu c a bài toán (P ). Thông thư ng, t p D đư c cho như là t p nghi m c a m t h b t đ ng th c ho c đ ng th c có d ng D := {x ∈ X : gj (x) ≤ 0, hi (x) = 0, j = 1, ..., m, i = 1, ..., p}, (2.1) trong đó ∅ = X ⊆ I n và gj , hi : I n → I (j = 1, ...m, i = 1, ...p). Bài R R R toán (P ) v i D cho b i (2.1) g i là trơn n u c hàm m c tiêu và các ràng bu c đ u trơn (kh vi).
13 Bài toán (P ) có r t nhi u ng d ng trong các lĩnh v c khác nhau. Ví d , trong kinh t nó là bài toán xác đ nh phương án s n xu t sao cho chi phí th p nh t. Trong ví d này, x là phương án s n xu t mà m i t a đ xj c a nó là s lư ng s n ph m lo i j c n s n xu t, còn f (x) là chi phí ng v i phương án x. Bài toán (P ) trong mô hình này có nghĩa là tìm m t phương án s n xu t trong t p h p các phương án ch p nh n đư c D sao cho chi phí s n xu t ng v i phương án này là th p nh t. Đ nh nghĩa 2.1. Đi m x∗ ∈ D đư c g i là l i gi i t i ưu đ a phương c a bài toán (P) n u t n t i m t lân c n U c a x∗ sao cho f (x∗ ) ≤ f (x), ∀x ∈ U ∩ D. và x∗ g i là l i gi i t i ưu toàn c c c a (P) n u f (x∗ ) ≤ f (x), ∀x ∈ D. 2.1.2. S t n t i nghi m t i ưu Xét bài toán t i ưu toàn c c (P ). Có 4 trư ng h p t n t i nghi m t i ưu c a bài toán này • D = ∅ (Không có nghi m). • f không b ch n dư i trên D inf f (x) = −∞ . x∈D • inf f (x) < ∞ nhưng giá tr c c ti u không đ t đư c trên D. x∈D • t n t i x∗ ∈ D sao cho f (x∗ ) = min f (x). x∈D Câu h i đ t ra: Làm th nào đ ki m tra đư c bài toán (P ) có nghi m hay không? Câu tr l i là, nói chung đi u này là không d dàng. Đ nh lí 2.1. Đi u ki n c n và đ đ t n t i nghi m t i ưu toàn c c c a bài toán (P ) là F + (D) := {t ∈ I : f (x) ≤ t, x ∈ D}, R đóng và b ch n dư i.
14 Ch ng minh. N u x∗ là nghi m t i ưu thì F + (D) = [f (x∗ ), +∞] đóng (là ph n bù c a m t t p m ) và b ch n dư i. Ngư c l i, gi s F + (D) b ch n dư i. Đ t t∗ = inf F + (D) thì t > −∞. Do F + (D) đóng, t∗ ∈ F + D nên t n t i x∗ ∈ D sao cho f (x∗ ) = t∗ . Ch ng t x∗ là m t đi m c c ti u c a f trên D. Đ nh lí 2.2 (Weierstrass). N u D là t p compact và f n a liên t c dư i trên D, thì bài toán (P ) có nghi m t i ưu. Ch ng minh. Đ t α := inf x∈D f (x). Theo đ nh nghĩa có m t dãy {xk } ⊂ D sao cho limk→+∞ f (xk ) = α. Do D compact nên có m t dãy con h i t v x0 ∈ D, không gi m tính t ng quát có th coi xk → x0 . Vì f n a liên t c dư i nên α > −∞. Nhưng x0 ∈ D nên theo đ nh nghĩa c a α, ta ph i có f (x0 ) ≥ α. V y f (x0 ) = α. Đ nh lí 2.3. N u f n a liên t c dư i trên D và th a mãn đi u ki n b c sau f (x) → +∞ khi x ∈ D, x → +∞ thì f có đi m c c ti u trên D. Ch ng minh. Đ t D(a) := {x ∈ D : f (x) ≤ f (a)} v i a ∈ D. Rõ ràng, D(a) đóng và b ch n nên f có đi m c c ti u trên D(a) và đi m đó cũng chính là đi m c c ti u c a f trên D. 2.1.3. Đi u ki n t i ưu Đ nh lí 2.4. Gi s D là t p l i và f là hàm l i, kh dư i vi phân trên D. Khi đó x∗ là nghi m t i ưu c a bài toán (P) n u và ch n u 0 ∈ ∂f (x∗ ) + ND (x∗ ), (2.2) trong đó ND (x∗ ) ký hi u nón pháp tuy n c a D t i x∗ . Ch ng minh. ” ⇐ ” : Gi s có (2.2). Khi đó t n t i p∗ sao cho p∗ ∈ ∂f (x∗ ) ∩ (−ND (x∗ )).
15 Do p∗ ∈ ∂f (x∗ ) nên p∗ , x − x∗ ≤ f (x) − f (x∗ ), ∀x. và vì p∗ ∈ ND (x∗ ) nên p∗ , x − x∗ ≥ 0, ∀x ∈ D. Vy f (x) − f (x∗ ) ≥ 0, ∀x ∈ D. Ch ng t x∗ là nghi m t i ưu c a bài toán (P ). ” ⇒ ” : Gi s x∗ là nghi m t i ưu. B ng cách l y không gian affine c a D, ta có th gi s D là m t t p có s chi u đ y đ . Do D là t p l i, intD = ∅. Xét hai t p sau E := {(t, x) ∈ I × I n : t > f (x) − f (x∗ ), x ∈ D}; G := {0} × D. R R C E và G đ u là t p l i (do D và f l i). Hơn n a, G ∩ E = ∅. Áp d ng đ nh lý siêu ph ng tách t n t i (u0 , u) = 0 ∈ I × I n sao cho R R u0 t + uT x ≤ u0 0 + uT y, ∀(t, x) ∈ E, y ∈ D (2.3) T (2.3), cho t → +∞, ta th y u0 ≤ 0. Cũng t (2.3) n u u0 = 0 thì u, x − y ≤ 0, ∀x, y ∈ D. (2.4) Hi n nhiên, 0 ∈ D và b ng phép t nh ti n ta có th gi s 0 ∈ intD. Theo (2.4) ta có u = 0 (không x y ra vì u0 = 0). Do đó u0 < 0. Chia c 2 v c a (2.3) cho −u0 > 0, ta có −t + uT x ≤ uT y, ∀x, y ∈ D. Cho t → f (x) − f (x∗ ), ta đư c −[f (x) − f (x∗ )] + uT x ≤ uT y, ∀x, y ∈ D. (2.5) Thay y = x∗ vào (2.5), ta đư c −[f (x) − f (x∗ )] + uT x ≤ uT x∗ , ∀x ∈ D.
16 Do đó f (x∗ ) − f (x) + uT (x − x∗ ) ≤ 0, ∀x ∈ D. (2.6) N u x ∈ C , b ng cách l y f (x) = ∞ nên t (2.6) ta cũng nh n đư c f (x∗ ) − f (x) + uT (x − x∗ ) ≤ 0, ∀x ∈ X. nghĩa là u ∈ ∂f (x∗ ). M t khác, thay x = x∗ vào (2.5), ta có uT (y − x∗ ) ≥ 0, ∀y ∈ D. Suy ra −u ∈ ND (x∗ ). K t h p v i u ∈ ∂f (x∗ ), ta đư c 0 ∈ ∂f (x∗ ) + ND (x∗ ). H qu 2.1. V i các gi thi t như Đ nh lý 2.4, n u x∗ ∈ intD là nghi m t i ưu c a bài toán (P ) thì 0 ∈ ∂f (x∗ ). Hơn n a, n u f kh vi và D = I n R thì 0 = f (x∗ ). 2.2. T i ưu có ràng bu c 2.2.1. Đ i ng u Lagrange Đ i ng u là m t ph n quan tr ng c a bài toán t i ưu. Có r t nhi u ki u đ i ng u, nhưng đ i ng u Lagrange đư c s d ng r ng rãi hơn c . Đ i ng u Lagrange d a trên cơ s hàm Lagrange. Ta xét bài toán min{f (x) : x ∈ X, gj (x) ≤ 0, j = 1, ..., m} (P ) trong đó X ⊆ I n là t p l i khác r ng. T bài toán trên, ta đ nh nghĩa R bài toán t i ưu khác có d ng max{d(y) : y ∈ Y } (D) trong đó Y ⊆ I m . R Đ nh nghĩa 2.2. Bài toán (D) đư c g i là đ i ng u c a bài toán (P ) n u v i m i đi m ch p nh n đư c x c a (P ) và m i y ch p nh n đư c c a (D), ta có f (x) ≥ d(y).
17 Bài toán (D) đư c g i là đ i ng u chính xác c a bài toán (P ) n u (D) là bài toán đ i ng u c a (P ) và t n t i x∗ ∈ (P ), y ∗ ∈ (D) sao cho f (x∗ ) ≤ d(y ∗ ). T Đ nh nghĩa 2.2 ta th y r ng, n u bài toán (D) là đ i ng u chính xác c a bài toán (P ) thì f (x∗ ) = d(y ∗ ) và hi n nhiên (P ) cũng là đ i ng u chính xác c a (D). Xét bài toán (P ), ta đ nh nghĩa hàm Lagrange m L(x, y) := f (x) + yj gj (x). j=1 L y hàm m c tiêu c a bài toán đ i ng u là d(y) := inf L(x, y). (LD) x∈X Rm và mi n ràng bu c c a (LD) b ng I + . Khi đó bài toán đ i ng u tr thành sup d(y) := sup inf L(x, y). y≥0 y≥0 x∈X Đ nh lí 2.5. Bài toán (LD) là đ i ng u c a bài toán (P ). Ch ng minh. Ta có m d(y) = inf L(x, y) ≤ f (x) + yj gj (x) ≤ f (x), ∀x ∈ X, ∀y ∈ Y. x∈X j=1 Ch ng t (LD) là đ i ng u c a bài toán (P ). Nh n xét 2.1. Nhìn chung, m t c p đ i ng u chưa ch c đã là đ i ng u chính xác như ví d sau đây s ch ra. Ví d 2.1. Xét bài toán min{f (x) = −x2 , x ∈ X = [0, 2], x − 1 ≤ 0},
18 Ta th y f (1) = min f = −1. Hàm Lagrange c a bài toán là L(x, y) = −x2 + y(x − 1), y ≥ 0, x ∈ X = [0, 2]. Ta th y max d(y) = 0. y≥0 V y c p đ i ng u là không chính xác. V y c n thêm đi u ki n gì đ hai bài toán (P ) và (LD) là c p đ i ng u chính xác? Ta có đ nh lý sau: Đ nh lí 2.6 (Đ i ng u chính xác). Gi s (i) (P ) có m t l i gi i t i ưu, (ii) Các hàm f và gj , (j = 1, ..., m) l i và liên t c trên X . (iii) Đi u ki n Slater th a mãn, nghĩa là có x0 sao cho gj (x0 ) < 0 v i m i j. Khi đó (P ) và (LD) là c p đ i ng u chính xác. Ch ng minh. Gi s g(x) := (g1 (x), . . . , gm (x))T . L y A := {(t, z) ∈ I × I n : t > f (x), z ≥ g(x), x ∈ X}. R R Do f và gj (j = 1, ..., m) l i nên t p A là l i. Gi s x∗ là nghi m t i ưu c a bài toán (P ) thì (f (x∗ ), 0) ∈ A. Theo đ nh lý tách t n t i (α, y) = 0 thu c I × I n sao cho: R R αt + y T z ≥ αf (x∗ ), ∀(t, z) ∈ A. (2.7)