Chương 4: Bài toán Quy hoạch phi tuyến có ràng buộc

10/6/2010 1MaMH C02012 Chương 4: QHPT có ràng buộc 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 2MaMH C02012 Chương 4: QHPT có ràng buộc Bài toán Quy hoạch phi tuyến có ràng buộc có dạng: trong đó và hàm f xác định trên . ( ) min{ ( ) : },rbP f x x X∈ nX ⊂ ℝ X 10/6/2010 3MaMH C02012 Chương 4: QHPT có ràng buộc − 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 4MaMH C02012 Chương 4: QHPT có ràng buộc I. Điều kiện tối ưu 1. Nón tiếp xúc Định nghĩa 1. Cho dãy hội tụ đến Ta nói dãy hội tụ đến theo { }q nx ⊂ℝ 0 . nx ∈ℝ { }qx 0x hướng , ký hiệu nếu tồn tại dãy số dương sao cho nv∈ℝ 0{ } ,vqx x→ { }, lim 0q q q t t →∞ = 0 ( )q q qx x t v o t= + + 10/6/2010 5MaMH C02012 Chương 4: QHPT có ràng buộc Nói cách khác, nếu tồn tại dãy số dương sao cho 0{ } ,vqx x→ { }, lim 0q q q t t →∞ = 0 lim . qx x v − = q qt→∞ 10/6/2010 6MaMH C02012 Chương 4: QHPT có ràng buộc Định nghĩa 2. Cho . Nón tiếp xúc với tại được kí hiệu là với nX ⊂ℝ 0 ,x X∈ 0( , ),T X x 0 0vn q q = ∈ ∃ ⊂ →ℝ 0 ,x X∈ X ( , ) { : { } : { } }T X x v x X x x 10/6/2010 7MaMH C02012 Chương 4: QHPT có ràng buộc Bổ đề 1. Giả sử là một dãy thuộc hội tụ đến theo hướng v và hàm f khả vi liên tục cấp một trên . Khi đó nX ⊂ℝ 0x X∈ X { }qx 0qx x−0 0 ( ), lim . qt q f x v t+→ ∇ = 10/6/2010 8MaMH C02012 Chương 4: QHPT có ràng buộc 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ếu là nghiệm cực tiểu địa phương của bài toán thì * *( ), 0 ( , );f x v v T X x∇ ∀ ∈≥ *x X∈ ( )rbP ii) Ngược lại, nếu thỏa mãn điều kiện thì là một nghiệm cực tiểu địa phương chặt của bài toán . * *( ), 0 ( , );f x v v T X x∇ ∀ ∈> *x X∈ *x ( )rbP 10/6/2010 9MaMH C02012 Chương 4: QHPT có ràng buộc Hệ quả 1. Giả sử và là điểm cực tiểu địa phương của bài toán . Khi đó Định lý 2. Cho f là hàm lồi khả vi trên một tập * intx X∈ ( )rbP *x *( ) 0.f x∇ = mở chứa tập lồi . Điều kiện cần và đủ để là điểm cực tiểu toàn cục của bài toán quy hoạch lồi là nX ⊂ℝ *x X∈ min{ ( ) : }f x x X∈ * *( ), 0 ( , ).f x v v T X x∇ ≥ ∀ ∈ 10/6/2010 10MaMH C02012 Chương 4: QHPT có ràng buộc 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ồi . Điểm là điểm cực tiểu toàn cục của bài toán quy hoạch nX ⊂ℝ *x X∈ lồi khi và chỉ khimin{ ( ): }f x x X∈ * *( ), 0 .f x x x x X∇ − ≥ ∀ ∈ 10/6/2010 11MaMH C02012 Chương 4: QHPT có ràng buộc 3. Định lý Karush – Kuhn – Tucker Xét bài toán QH phi tuyến trong đó là tập nghiệm của hệ min{ ( ): },f x x X∈ 1( )rbP nX ⊂ℝ và là các hàm số khả vi bất kỳ xác định trên , có thể ko lồi. ( ) 0, 1,..., , ( ) 0, 1,..., , i j g x i m h x j k ≤ =  = = , , 1,...,if g i m= , 1,...,jh j k= n ℝ 10/6/2010 12MaMH C02012 Chương 4: QHPT có ràng buộc Cho Đặt là tập các chỉ số của các ràng buộc thỏa mãn chặt tại 0 .x X∈ 0 0( ) { {1,..., } ( ) 0}iI x i m g x= ∈ = ( ) 0, 1,..., ,ig x i m≤ = 0.x Ký hiệu là tập hợp các véctơ thỏa mãn hệ tuyến tính sau: 0( )S x v 0 0 0 ( ), 0, 1,..., ( ), 0, ( ). j i h x v j k g x v i I x  ∇ = =  ∇ ≤ ∈ 10/6/2010 13MaMH C02012 Chương 4: QHPT có ràng buộc Bổ đề 2. Với mọi ta có Định nghĩa 3. Ta nói điều kiện chính quy được thỏa mãn tại nếu 0x X∈ 0 0( , ) ( ).T X x S x⊆ 0x 0 0( , ) ( ).T X x S x= 10/6/2010 14MaMH C02012 Chương 4: QHPT có ràng buộc Định lý 3. Điều kiện chính quy được thỏa mãn tại nếu có một trong các điều kiện sau: i) Các hàm và đều là các hàm afin. ii) Các hàm là afin; các hàm 0x , 1,...,jh j k= , 1,...,ig i m= , 1,...,jh j k= là lồi và đk Slater sau đây t/m: iii) Các véctơ và là độc lập tuyến tính. , 1,...,ig i m= : ( ) 0, 1,..., ; ( ) 0, 1,..., ;n i jx g x i m h x j k∃ ∈ < = = =ℝ 0 0( ), ( )ig x i I x∇ ∈ 0( ), 1,...,jh x i k∇ = 10/6/2010 15MaMH C02012 Chương 4: QHPT có ràng buộc Định lý 4.(Định lý Karush – Kuhn – Tucker KKT) Cho các hàm và là các hàm khả vi liên tục trên một tập mở chứa Giả sử là nghiệm cực tiểu địa phương của bài toán và đk chính quy được t/m tại Khi đó đk KKT (đk (6.1) – (6.3)) sau đúng: i) và , , 1,...,if g i m= , 1,...,jh j k= .X *x 1( )rbP *.x *( ) 0, 1,...,g x i m≤ = *( ) 0, 1,..., ; (6.1)h x j k= = ii) và sao cho iii) (Điều kiện bù) (6.3) i j 0, 1,...,i i mλ ≥ = 0, 1,...,j j kµ ≥ = * * * 1 1 ( ) ( ) ( ) 0 (6.2) m k i i j j i j f x g x h xλ µ = = ∇ + ∇ + ∇ =∑ ∑ ∃ *( ) 0, 1,..., .i ig x i mλ = ∀ = 10/6/2010 16MaMH C02012 Chương 4: QHPT có ràng buộc Định lý KKT cho quy hoạch lồi Xét bài toán quy hoạch lồi trong đó min{ ( ): },f x x X∈ 1( )convP { : ( ) 0, 1,..., },X x g x i m= ≤ = và f và là các hàm lồi, khả vi liên tục trên một tập mở chứa X. i , 1,..., ,ig i m= 10/6/2010 17MaMH C02012 Chương 4: QHPT có ràng buộc Định lý 5. (Định lý KKT cho quy hoạch lồi) Giả sử các hàm f , 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 đó là nghiệm cực tiểu của bài toán khi và chỉ khi thỏa mãn đk KKT ( đk (6.4) – (6.6)) sau: , 1,..., ,ig i m= * nx ∈ℝ 1( )convP *x i) ii) Tồn tại các số sao cho iii) *( ) 0, 1,..., ; (6.4)ig x i m≤ = 0, 1,...,i i mλ ≥ = * * 1 ( ) ( ) 0 (6.5) m i i i f x g xλ = ∇ + ∇ =∑ *( ) 0, 1,..., . (6.6)i ig x i mλ = ∀ = 10/6/2010 18MaMH C02012 Chương 4: QHPT có ràng buộc 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 với các số thực đgl hàm Lagrange tương ứng với bài toán Các số đgl các nhân tử L. 1 1 1 1 ( , ,..., , ,..., ) : ( ) ( ) ( ),m k i i i j i j L x f x g x h xλ λ µ µ λ µ = = = + +∑ ∑ 1 10,..., 0, ,..., ,m kλ λ µ µ≥ ≥ 1( ).rbP 1 10,..., 0, ,..., ,m kλ λ µ µ≥ ≥ 10/6/2010 19MaMH C02012 Chương 4: QHPT có ràng buộc Ký hiệu là gradient của hàm L theo x. xL∇ 10/6/2010 20MaMH C02012 Chương 4: QHPT có ràng buộc Thuật toán 1 Bước 1. Lập hàm Lagrange Bước 2. Giải hệ KKT : 1 1 1 1 ( , ,..., , ,..., ) : ( ) ( ) ( ). m n m k i i i j i j L x f x g x h xλ λ µ µ λ µ = = = + +∑ ∑ 1 1 1 ( , ,..., , ,..., ) 0 0,..., 0 ( ) 0, 1,...., ( ) 0, 1,..., ( ) 0, 1,..., x m k m i i i j L x g x i m g x i m h x j k λ λ µ µ λ λ λ ∇ =  ≥ ≥  = =  ≤ =   = =10/6/2010 21MaMH C02012 Chương 4: QHPT có ràng buộc Mỗimột nghiệm của hệ trên tương ứng với một bộ tham số 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 x 1 1,..., , ,...,m kλ λ µ µ 2 2 1 2 1 2min{ ( ) 10}f x x x x x= + + = 10/6/2010 22MaMH C02012 Chương 4: QHPT có ràng buộc Ví dụ 2 Giải bài toán sau bằng pp nhân tử Lagrange 2 2 2 1 1 2 3 3 1 2 3min{ ( ) 2 4 2 2}f x x x x x x x x x= − + − + − + = 10/6/2010 23MaMH C02012 Chương 4: QHPT có ràng buộc 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 trong đó f là hàm lồi trên và là tập min{ ( ): },f x x X∈ 2( )convP n ℝ nX ⊂ ℝ lồi đa diện xác định bởi với A là ma trận cấp và véctơ { : },nX x Ax b= ∈ ≤ℝ m n× .mb∈ℝ 10/6/2010 24MaMH C02012 Chương 4: QHPT có ràng buộc Định nghĩa 4 Cho điểm Véctơ đgl một hướng chấp nhận được của tập X tại nếu tồn tại một số sao cho với mọi t thỏa mãn 0 .x X∈ nd ∈ℝ 0x * 0t > 0x td X+ ∈ *0 .t t< ≤ 10/6/2010 25MaMH C02012 Chương 4: QHPT có ràng buộc Giả sử Khi đó là hướng chấp nhận được của X tại với mọi Xét bài toán QHTT . kx X∈ kx x− kx .x X∈ { }min ( ), .k kf x x x x X∇ − ∈ Giả sử là nghiệm tối ưu của bt này. Khi đó: • Nếu giá trị tối ưu thì với mọi Khi đó 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 ku X∈ ( ), 0k k kf x u x∇ − ≥ ( ), 0k kf x x x∇ − ≥ .x X∈ :otp kx x= ( ), 0k k kf x u x∇ − < 10/6/2010 26MaMH C02012 Chương 4: QHPT có ràng buộc thì là một hướng giảm chấp nhận được của bài toán k ku x− 2( ).convP 10/6/2010 27MaMH C02012 Chương 4: QHPT có ràng buộc Thuật toán 2 ( Thuật toán Frank - Wolfe) Bước khởi đầu Tìm một điểm tùy ý Đặt Bước lặp k, (k=0,1,2,… ) (k ) Giải bài toán QHTT 0 .x X∈ : 0;k = 1 được PATƯ (k2) (kiểm tra đk tối ưu) { }min ( ),k kf x x x x X∇ − ∈ ;ku X∈ 10/6/2010 28MaMH C02012 Chương 4: QHPT có ràng buộc If Then Dừng thuật toán ( lấy ) Else Đặt và chuyển Bước (k3); (k3) Xác định trong đó ( ), 0k k kf x u x∇ − ≥ :otp kx x= :k k kd u x= − 1 : ,k k kkx x t d + = + { }argmin ( ) ( ) [0,1] .k kkt t f x td tϕ= = + ∈ (k4) If Then Dừng thuật toán ( lấy ) Else Đặt và quay lại Bước lặp k. 1( ) 0kf x +∇ ≈ 1:otp kx x += : 1k k= + 10/6/2010 29MaMH C02012 Chương 4: QHPT có ràng buộc Ví dụ Cho bài toán Cho Xây dựng một vài phần tử của dãy lặp theo thuật toán Frank – Wolfe. 2 2 1 2 1 1 2 1 2 1 min ( ) 0, 0, 10 . 2 f u u u u u u u u = + + ≥ ≥ + ≤    0 (1,1) .Tu = { }ku 10/6/2010 30MaMH C02012 Chương 4: QHPT có ràng buộc