Bài giảng Tối ưu - Chương 4: Bài toán quy hoạch phi tuyến tính có ràng buộc

Nội dung text: Bài giảng Tối ưu - Chương 4: Bài toán quy hoạch phi tuyến tính có ràng buộc

1. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 1
2. NỘI DUNG − Bài toán QHPT có ràng bu ộc − Điều ki ện tối ưu − Một số ph ương pháp gi ải bài toán QHPT có ràng bu ộc. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 2
3. Bài toán Quy ho ạch phi tuy ến có ràng bu ộc có dạng: (Prb ) min{ f ( x ): x∈ X }, trong đóX ⊂ ℝ n và hàm f xác đị nhtrênX . 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 3
4. − Bài toán QHPT có ràng bu ộc − Điều ki ện tối ưu − Một số ph ương pháp gi ải bài toán QHPT có ràng bu ộc. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 4
5. I. Điều ki ện tối ưu 1. Nón ti ếp xúc Đị nh nghĩa 1. Cho dãy{}xq⊂ ℝ n hội tụ đế n q x0 ∈ℝn. Ta nói dãy {}x hội tụ đế n x0 theo hướngv∈ℝn , ký hi ệu{xq }v→ x 0 , nếu tồn = tại dãy số dương{tq }, lim t q 0 saocho q→ ∞ q =0 + + x x tvotq( q ) 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 5
6. Nói cách khác, { x q }  v → x 0 , nếu tồn tại dãy số = dương{tq }, lim t q 0 saocho q→ ∞ xq − x 0 lim= v . q → ∞ tq 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 6
7. Đị nh nghĩa 2. Chox0 ∈ X, X ⊂ ℝn . Nón ti ếp xúc vớiX tại x0 ∈ X, được kí hi ệu là T( X , x 0 ), với TXx(,){:{}:{}}0 = v ∈ℝn ∃ x q ⊂ Xx q v→ x 0 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 7
8. Bổ đề 1. Gi ả sử {}xq là một dãy thu ộc X ⊂ ℝn hội tụ đế nx0 ∈ X theo hướng v và hàm f kh ả vi liên tục cấp một trênX . Khi đó q − 0 ∇0 = x x f(), x v lim+ . t →0 q tq 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 8
9. 2. Điều ki ện tối ưu Đị nh lý 1. i) Gi ả sử f khả vi trên một tập mở chứa X. Nếux* ∈ X là nghi ệm cực ti ểu đị a phương của bài toán (Prb ) thì ∇fxv(),*≥ 0 ∀ vTXx ∈ (,) * ; ii) Ngược lại, nếux* ∈ X thỏa mãn điều ki ện ∇fxv(),*> 0 ∀ vTXx ∈ (,) * ; thìx* là một nghi ệm cực ti ểu đị a phương chặt của bài toán (Prb ) . 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 9
10. Hệ quả 1. Gi ả sử x* ∈int X vàx* là điểm cực ti ểu đị a ph ương của bài toán(Prb ) . Khi đó ∇f( x * ) = 0. Đị nh lý 2. Cho f là hàm lồi kh ả vi trên một tập mở ch ứa tập lồiX ⊂ ℝn . Điều ki ện cần và đủ để x* ∈ X là điểm cực ti ểu toàn cục của bài toán quy ho ạch lồimin{f ( x ) : x∈ X } là ∇fxv(),* ≥ 0 ∀ vTXx ∈ (,). * 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 10
11. Hệ quả 2. Cho f là hàm lồi khả vi trên tập một tập mở ch ứa tập lồiX ⊂ ℝn . Điểmx* ∈ X là điểm cực ti ểu toàn cục của bài toán quy ho ạch lồimin{f ( x ): x∈ X } khivàch ỉ khi ∇f( x* ), x − x * ≥ 0 ∀ x ∈ X . 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 11
12. 3. Đị nh lý Karush – Kuhn – Tucker Xét bài toán QH phi tuy ến rb min{f ( x ): x∈ X }, (P1 ) trong đóX ⊂ ℝn là tập nghi ệm của hệ ≤ = gi ( x ) 0, i 1, , m ,  = = hxj ( ) 0, j 1, , k , = = f, gi , i 1, , m vàhj , j 1, , k là các hàm số khả vi bất kỳ xác đị nhtrênℝn , có thể ko lồi. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 12
13. Cho x 0 ∈ X . Đặ t 0= ∈ 0 = I( x ) { i {1, , m } gi ( x ) 0} là tập các ch ỉ số của các ràng bu ộc ≤ = th ỏa mãn chặt tại 0 gi ( x ) 0, i 1, , m , x . Ký hi ệuS( x0 ) là tập hợp các véct ơ v th ỏa mãn hệ tuy ến tính sau:  ∇0 = =  hxvj ( ), 0, j 1, , k  ∇0 ≤ ∈ 0  gxvi ( ), 0, iIx ( ). 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 13
14. Bổ đề 2. Với mọix0 ∈ X ta có TXx( ,0 )⊆ Sx ( 0 ). Đị nh nghĩa 3. Ta nói điều ki ện chính quy được th ỏa mãn tại x0 nếu TXx( ,0 )= Sx ( 0 ). 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 14
15. Đị nh lý 3. Điều ki ện chính quy được th ỏa mãn tại x0 nếu có một trong các điều ki ện sau : = = i) Các hàm hj , j 1, , k và gi , i 1, , m đề u là các hàm afin. = ii) Các hàm hj , j 1, , k là afin ; các hàm = gi , i 1, , m là lồi và đk Slater sau đây t/m: ∃ ∈n < = = = xℝ : gxi ( ) 0, i 1, , mhx ; j ( ) 0, j 1, , k ; ∇0 ∈ 0 iii) Các véct ơ gxi ( ), i Ix ( ) và ∇0 = hxij ( ), 1, , k là độ c lập tuy ến tính. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 15
16. Đị nh lý 4.( Đị nh lý Karush – Kuhn – Tucker KKT) = = Cho các hàm f, gi , i 1, , m và hj , j 1, , k là các hàm khả vi liên tục trên một tập mở ch ứa X. Gi ả sử x* là nghi ệm cực ti ểu đị a ph ương của bài rb * toán(P1 ) và đk chính quy được t/m tạix . Khi đó đk KKT (đk (6.1) – (6.3)) sau đúng : * ≤ = * = = i) gi ( x ) 0, i 1, , m và hxj ( ) 0, j 1, , k ; (6.1) ∃ λ ≥ = µ ≥ = ii) i 0,i 1, , m vàj 0,j 1, , k saocho m k ∇* +λ ∇ * + µ ∇ * = fx()∑ii gx () ∑ jj hx ()0 (6.2) i=1 j = 1 λ * = ∀ = iii) i g i ( x ) 0, i 1, , m . (Điều ki ện bù ) (6.3) 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 16
17. Đị nh lý KKT cho quy ho ạch lồi Xét bài toán quy ho ạch lồi conv min{f ( x ): x∈ X }, (P1 ) trong đó = ≤ = X{ x : gi ( x ) 0, i 1, , m }, = và f vàgi , i 1, , m , làcáchàm lồi, kh ả vi liên tục trên một tập mở ch ứa X. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 17
18. Đị nh lý 5.(Đị nh lý KKT cho quy ho ạch lồi) ả ử = ồ Gi s các hàm f ,gi , i 1, , m , là các hàm l i kh ả vi trên một tập mở ch ứa X và đk Slater được th ỏa mãn. Khi đóx* ∈ ℝn là nghi ệm cực ti ểu của conv * bài toán(P1 ) khi và ch ỉ khix th ỏa mãn đk KKT ( đk (6.4) – (6.6)) sau : * ≤ = i) gi ( x ) 0, i 1, ,; m (6.4) λ ≥ = ii) Tồn tại các số i 0,i 1, , m sao cho m ∇* +λ ∇ * = fx()∑ i gx i ()0 (6.5) i=1 λ * = ∀ = iii) ig i ( x ) 0, i 1, , m . (6.6) 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 18
19. II. Các phương pháp gi ải bài toán QHPT có RB 1. PP nhân tử Lagrange Hàm số m n λ λ µ µ= + λ + µ Lx(,, ,1m , 1 , , k ): fx ()∑ ii gx () ∑ ij hx (), i=1 j = 1 λ≥ λ ≥ µ µ với các số th ực 10, ,m 0, 1 , , k , đgl hàm rb Lagrange tương ứng với bài toán (P1 ). λ≥ λ ≥ µ µ Các số10, ,m 0, 1 , , k , đgl các nhân tử L. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 19
20. ∇ Ký hi ệux L là gradient của hàm L theo x. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 20
21. Thuật toán 1 Bước 1. Lập hàm Lagrange m n λ λ µ µ= + λ + µ Lx(,, ,1m , 1 , , k ): fx ()∑ ii gx () ∑ ij hx (). i=1 j = 1 Bước 2. Gi ải hệ KKT : ∇L(, x λ , , λ , µ , , µ ) = 0  x1 m 1 k λ≥ λ ≥  1 0, ,m 0  λ = =  ig i ( x ) 0, i 1, , m  g( x )≤ 0, i = 1, , m  i  hx( )= 0, j = 1, , k 10/6/2010  MaMH C02012j Ch ươ ng 4: QHPT có ràng bu ộc 21
22. Mỗi một nghi ệm x của hệ trên tương ứng với một λ λ µ µ bộ tham số 1, ,m , 1 , , k là một điểm KKT của bài toán đang xét. Ví dụ 1 Gi ải bài toán sau bằng pp nhân tử Lagrange =2 + 2 + = min{f ( x ) x1 x 21 x x 2 10} 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 22
23. Ví dụ 2 Gi ải bài toán sau bằng pp nhân tử Lagrange =2 − + 2 − 2 + − + = min{fxx ( )1 2 xxx 123 4 xxx 312 2 x 3 2} 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 23
24. 2. Phương pháp Frank – Wolfe gi ải bài toán quy ho ạch lồi với ràng buộc tuy ến tính. Xét bài toán QH lồi conv min{f ( x ): x∈ X }, (P2 ) trong đó f là hàm lồi trên ℝn và X ⊂ ℝn là tập lồi đa di ện xác đị nh bởi X={ x ∈ℝn : Ax ≤ b }, với A là ma tr ận cấpm× n vàvéct ơ b ∈ ℝm . 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 24
25. Đị nh nghĩa 4 Cho điểmx0 ∈ X. Véct ơ d ∈ ℝn đgl một hướng chấp nhận được của tập X tại x0 > nếu tồn tại một số t* 0 sao cho 0 + ∈ < ≤ x td X với mọi t th ỏa mãn 0t t * . 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 25
26. Gi ả sử xk ∈ X. Khi đóx− x k là hướng ch ấp nh ận được của X tạixk với mọi x∈ X. Xét bài toán QHTT min{ ∇f ( xk ), x − x k x ∈ X} . Gi ả sử uk ∈ X là nghi ệm tối ưu của bt này. Khi đó: • Nếu giá tr ị tối ưu∇fx(k ), u k − x k ≥ 0 thì ∇fx(k ), x − x k ≥ 0 với mọix∈ X. Khi đó xotp:= x k là nghi ệm cực ti ểu của bài toán đang xét. • Ng ược lại, nếu giá tr ị tối ưu ∇fx(k ), u k − x k < 0 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 26
27. thìuk− x k là một hướng gi ảm ch ấp nh ận được conv của bài toán (P2 ). 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 27
28. Thuật toán 2 ( Thu ật toán Frank - Wolfe ) Bước kh ởi đầ u Tìm một điểm tùy ý x 0 ∈ X . Đặ t k := 0; Bước lặp k, (k=0,1,2, ) (k1) Gi ải bài toán QHTT min{ ∇f ( xk ), x − x k x ∈ X} k được PATƯ u∈ X ; (k2) (ki ểm tra đk tối ưu) 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 28
29. If ∇fx(k ), u k − x k ≥ 0 Then Dừng thu ật toán ( lấyxotp:= x k ) k= k − k Else Đặ td: u x vàchuy ển Bước (k3); k+1 = k + k (k3) Xác đị nhx: x tk d , trong đó =ϕ =k + k ∈ tk arg min{ ( tfxtdt ) ( ) [0,1]} . ∇k +1 ≈ (k4) If f ( x ) 0 Then Dừng thu ật toán ( lấyxotp:= x k +1 ) Else Đặ tk:= k + 1 và quay lại Bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 29
30. Ví dụ Cho bài toán  1  min fu ( )= uuuu2 + 2 + ≥ 0, u ≥ 0, uu + ≤ 10 .  2 1211 2 12  Cho u 0 = (1,1) T . Xây dựng một vài ph ần tử của dãy lặp {uk } theo thu ật toán Frank – Wolfe. 10/6/2010 MaMH C02012 Ch ươ ng 4: QHPT có ràng bu ộc 30