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

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

Thêm vào BST

Báo xấu

221
lượt xem 59
download

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

Mục tiêu chương 4 Bài toán quy hoạch tuyến tính phi tuyến không ràng buộc thuộc bài giảng Tối ưu trình bày về bài toán quy hoạch tuyến tính phi tuyến không 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 tuyến tính không ràng buộc.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 1
NỘI DUNG 1. Bài toán QHPT không ràng buộc. 2. Điều kiện tối ưu. 3. Một số phương pháp giải bài toán QHPT không ràng buộc. 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 2
Bài toán Quy hoạch phi tuyến không ràng buộc có dạng: (P krb ) min{ f ( x ) : x ∈ ℝ }, n trong đó f :ℝ →ℝ n là hàm phi tuyến. 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 3
I. Điều kiện tối ưu Định lý 1(Điều kiện bậc nhất) Cho hàm f xác định, khả vi trên ℝn . Nếu x ∈ℝ là nghiệm cực tiểu địa phương của * n bài toán thì ∇f ( x* ) = 0. 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 4
Định lý 2 Giả sử f là hàm lồi khả vi trên ℝn . Khi đó, x ∈ℝ là nghiệm cực tiểu toàn cục của bài toán * n ( P ) khi và chỉ khi ∇f ( x* ) = 0. krb 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 5
Định lý 3 (Điều kiện bậc hai) Giả sử hàm f khả vi liên tục hai lần trên ℝn . Khi đó: i) Nếu x* ∈ℝn là điểm cực tiểu địa phương của f trên ℝn thì ∇f ( x ) = 0 và ∇ f ( x ) nửa xác định dương; * 2 * ii) Ngược lại , nếu ∇f ( x ) = 0 và ∇ f ( x ) xác định dương * 2 * * thì x là điểm cực tiểu địa phương chặt của f n trên ℝ . 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 6
Ví dụ1: Cho hàm số f ( x1 , x 2 ) = e 3 x2 − 3 x1 e x2 +x 3 1 Ta có:  −3e + 3x  x2 2 ∇f ( x) =  3 x 1  3e 2 − 3x e x2    1   6x1 −3e  x2 ∇ f (x) =  x 2 x2   −3e 9e − 3x1e  2 3x2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 7
II. Phương pháp hướng giảm 1. Ý tưởng 2. Lược đồ chung 3. Định nghĩa hướng giảm 4. Xác định độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 8
1. Ý tưởng 2. Lược đồ chung 3. Định nghĩa hướng giảm 4. Xác định độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 9
Ý tưởng: Xuất phát từ một điểm bất kỳ x0 ∈ℝn , ta xây 1 2 k dựng một dãy điểm x , x ,..., x ,... sao cho f ( x ) ≥ f ( x ) ≥ f ( x ) ≥ ... ≥ f ( x )... 0 1 2 k và dãy { x } hội tụ đến điểm dừng x* ∈ ℝ n của k hàm f . ( ∇f ( x* ) = 0 ) 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 10
1. Ý tưởng 2. Lược đồ chung 3. Định nghĩa hướng giảm 4. Xác định độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 11
Lược đồ chung của phương pháp hướng giảm Bước khởi đầu. Xuất phát từ một điểm tùy ý x0 ∈ℝn Gán k := 0; Bước lặp k, (k=0,1,2,…) k ( k 1 ) If x thỏa mãn điều kiện dừng Then dừng thuật toán k +1 Else xác định x = x + tk d sao cho k k k +1 f (x ) < f (x ) k ( k 2 ) Gán k := k +1; Quay lại bước lặp k. 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 12
1. Ý tưởng 2. Lược đồ chung 3. Định nghĩa hướng giảm 4. Xác định độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 13
Hướng giảm Định nghĩa: Cho x ∈ℝ . Ta nói d ∈ℝ là hướng 0 n n giảm của hàm f tại x nếu tồn tại ε > 0 sao cho 0 với mọi t thỏa mãn 0 < t < ε ta có f ( x + td ) < f ( x ) 0 0 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 14
Mệnh đề 1. Cho f khả vi trên ℝn , điểm x0 ∈ℝn , và hướng d ∈ℝn Nếu ∇f (x ), d < 0 thì d là hướng giảm của f 0 tại x 0. Mệnh đề 2. Cho hàm lồi f khả vi trên ℝ , điểm x0 ∈ℝn và n hướng d ∈ℝn . Khi đó, ∇f (x0 ), d < 0 khi và chi 0 khi d là hướng giảm của f tại x . 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 15
Hệ quả 1.Cho hàm f khả vi trên ℝ và điểm x0 ∈ℝn n Nếu ∇f (x ) ≠ 0 thì d =−∇f (x ) là một hướng giảm của 0 0 f tại x 0 . Mệnh đề 3. Giả sử hàm f khả vi trên ℝ và ∇f (x0 ) ≠ 0 n 0 .Trong các hướng giảm d của hàm f tại x có d = 1 thì hàm f giảm nhanh nhất theo hướng ∇f ( x 0 ) d =− ∇f ( x 0 ) 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 16
1. Ý tưởng 2. Lược đồ chung 3. Định nghĩa hướng giảm 4. Xác định độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 17
Xác định độ dài bước (tk ) i) Thủ tục tìm chính xác theo tia: tk = arg min{ϕk (t ) := f ( x + td ) :t > 0} k k 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 18
Mệnh đề 4. Cho hàm toàn phương lồi chặt 1 T f (x) = x Ax − b x + c, T 2 trong đó, A n × n đối xứng, xác định dương, b∈ℝn và c∈ℝ. Cho x ∈ℝ và hướng giảm d k của hàm k n f tại x k . Khi đó, độ dài bước chính xác tk được xác định bởi ( Ax − b) d k T k tk = − k T k >0 (d ) Ad 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 19
ii) Thủ tục quay lui k +1 (xác định x khi đã biết d k ) Mệnh đề 5.Cho hàm f khả vi trên ℝ , điểm x ∈ℝ n k n và véctơ d ∈ℝ thỏa mãn ∇f ( xk ), d k < 0 .Cho số k n thực m1 ∈ (0,1) . Khi đó ∃ t0 > 0 : f ( x k + td k ) ≤ f ( x k ) + m1t ∇f ( x k ), d k , ∀t ∈ (0, t0 ]. 10/6/2010 MaMH C02012 Chương 3: QHPT không ràng buộc 20