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.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Tối ưu: Chương 4 - ThS. Trần Thị Thùy Nương
- 10/6/2010 MaMH C02012 Chương 4: QHPT có ràng buộc 1
- 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
- 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
- − 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
- 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
- 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
- Đị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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Đị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
- Đị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
- Đị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
- 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
- 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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
