intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Tối ưu: Chương 4 - ThS. Trần Thị Thùy Nương

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

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

Bài giảng Tối ưu: Chương 4 Bài toán quy hoạch phi tuyến có ràng buộc trình bày về bài toán quy hoạch phi tuyến 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 quy hoạch phi tuyến có ràng buộc...cùng tìm hiểu bài giảng để hiểu thêm về quy hoạch phi tuyến có ràng buộc.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Tối ưu: Chương 4 - ThS. Trần Thị Thùy Nương

  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: rb (P ) min{ f ( x) : x ∈ X }, trong đó X ⊂ ℝ n và hàm f xác định trên X . 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 {x } ⊂ ℝ hội tụ đến q n x ∈ℝ . Ta nói dãy {x } hội tụ đến x0 theo 0 n q hướng v ∈ℝ , ký hiệu { x }  x , nếu tồn n → q v 0 tại dãy số dương {t q }, lim t q = 0 sao cho q→∞ x = x + t q v + o (t q ) q 0 10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 5
  6. Nói cách khác, { x q }  x 0 , nếu tồn tại dãy số v → dương {t q }, lim t q = 0 sao cho q→∞ x −x q 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. Cho x ∈ X , X ⊂ ℝn.0 Nón tiếp xúc với X tại x ∈ X , được kí hiệu là 0 0 T ( X , x ), với T ( X , x ) = {v ∈ ℝ : ∃{x } ⊂ X : {x }  x } 0 n →q q v 0 10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 7
  8. Bổ đề 1. Giả sử {x } là một dãy thuộc X ⊂ ℝn q hội tụ đến x ∈ X theo hướng v và hàm f khả 0 vi liên tục cấp một trên X . Khi đó x −x q 0 ∇ f ( x ), v = lim+ 0 . tq → 0 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ếu x ∈ X là nghiệm cực tiểu * địa phương của bài toán (Prb ) thì ∇f ( x* ), v ≥ 0 ∀v ∈T ( X , x* ); ii) Ngược lại, nếu x ∈ X thỏa mãn điều kiện * ∇f ( x* ), v > 0 ∀v ∈T ( X , x* ); * thì x là một nghiệm cực tiểu địa phương rb chặt của bài toán ( P ) . 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ồi X ⊂ ℝ . Điều kiện cần và đủ n để x ∈ X là điểm cực tiểu toàn cục của bài * toán quy hoạch lồi min{ f ( x) : x ∈ X } là ∇f (x ), v ≥ 0 ∀v ∈T( X , x ). * * 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ồi X ⊂ ℝ . Điểm x ∈ X là n * điểm cực tiểu toàn cục của bài toán quy hoạch lồi min{ f ( x): x ∈ X} khi và 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 min{ f (x): x ∈ X}, ( Prb ) 1 trong đó X ⊂ ℝn là tập nghiệm của hệ  gi ( x) ≤ 0, i = 1,..., m,   h j ( x) = 0, j = 1,..., k ,  f , gi , i = 1,..., m và h j , j = 1,..., k là các hàm n số khả vi bất kỳ xác định trên ℝ , có thể ko lồi. 10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 12
  13. Cho x ∈ X. Đặt 0 I ( x ) = {i ∈ {1,..., m} gi ( x ) = 0} 0 0 là tập các chỉ số của các ràng buộc gi ( x) ≤ 0, i = 1,..., m, thỏa mãn chặt tại x . 0 0 Ký hiệu S ( x ) là tập hợp các véctơ v thỏa mãn hệ tuyến tính sau:  ∇h j ( x 0 ), v = 0, j = 1,..., k    ∇gi ( x ), v ≤ 0, i ∈ I ( x ). 0 0  10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 13
  14. Bổ đề 2. Với mọi x ∈ X ta có T ( X , x ) ⊆ S ( x ). 0 0 0 Định nghĩa 3. Ta nói điều kiện chính quy được 0 thỏa mãn tại x nếu T ( X , x ) = S ( x ). 0 0 10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 14
  15. 0 Định lý 3. Điều kiện chính quy được thỏa mãn tại x nếu có một trong các điều kiện sau: i) Các hàm h j , j = 1,..., k và g i , i = 1,..., m đều là các hàm afin. ii) Các hàm h j , j = 1,..., k là afin; các hàm gi , i = 1,..., m là lồi và đk Slater sau đây t/m: ∃ x ∈ ℝ : gi ( x ) < 0, i = 1,..., m; h j ( x ) = 0, j = 1,..., k ; n iii) Các véctơ ∇g i ( x 0 ), i ∈ I ( x 0 ) và ∇h j ( x ), i = 1,..., k là độc lập tuyến tính. 0 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 , g i , i = 1,..., m và h j , 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 ( P ) và đk chính quy được t/m tại x . Khi đó 1 đk KKT (đk (6.1) – (6.3)) sau đúng: i) gi ( x* ) ≤ 0, i = 1,..., m và h j ( x* ) = 0, j = 1,..., k ; (6.1) ii) ∃ λi ≥ 0, i = 1,..., m và µ j ≥ 0, j = 1,..., k sao cho m k ∇f ( x* ) + ∑ λi ∇gi ( x* ) + ∑ µ j ∇h j ( x* ) = 0 (6.2) i =1 j =1 iii) λi gi ( 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 min{ f (x): x ∈ X}, ( Pconv ) 1 trong đó X = {x : gi ( x) ≤ 0, i = 1,..., m}, và f và gi , i = 1,..., m, là các hà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 ∈ ℝ là nghiệm cực tiểu của * n conv * bài toán ( P ) khi và chỉ khi x thỏa mãn đk 1 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 ∇f ( x* ) + ∑ λi ∇gi ( x* ) = 0 (6.5) i =1 iii) λi gi ( 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 L( x, λ1 ,..., λm , µ1 ,..., µ k ) := f ( x) + ∑ λi gi ( x) + ∑ µi h j ( x), i =1 j =1 với các số thực λ1 ≥ 0,..., λm ≥ 0, µ1 ,..., µ k , đgl hàm Lagrange tương ứng với bài toán 1 ( Prb ). Các số λ1 ≥ 0,..., λ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ệu ∇ x 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2