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

10/6/2010 1MaMH C02012 Chương 3: QHPT không ràng buộc 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 2MaMH C02012 Chương 3: QHPT không ràng buộc Bài toán Quy hoạch phi tuyến không ràng buộc có dạng: ( ) min{ ( ) : },krb nP f x x∈ℝ trong đó là hàm phi tuyến. : nf →ℝ ℝ 10/6/2010 3MaMH C02012 Chương 3: QHPT không ràng buộc I. Điều kiện tối ưu Định lý 1(Điều kiện bậc nhất) Cho hàm xác định, khả vi trên . Nếu là nghiệm cực tiểu địa phương của f nℝ * nx ∈ℝ bài toán thì *( ) 0.f x∇ = 10/6/2010 4MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 2 Giả sử là hàm lồi khả vi trên . Khi đó, là nghiệm cực tiểu toàn cục của bài toán khi và chỉ khi f nℝ * nx ∈ℝ *( ) 0.f x∇ =( )krbP 10/6/2010 5MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 3 (Điều kiện bậc hai) Giả sử hàm khả vi liên tục hai lần trên . Khi đó: i) Nếu là điểm cực tiểu địa phương của trên thì f nℝ * nx ∈ℝ nℝ f ∇và nửa xác định dương; ii) Ngược lại , nếu và xác định dương thì là điểm cực tiểu địa phương chặt của trên . *( ) 0f x∇ = 2 *( )f x *( ) 0f x∇ = 2 *( )f x∇ *x nℝ f 10/6/2010 6MaMH C02012 Chương 3: QHPT không ràng buộc Ví dụ1: Cho hàm số Ta có: 2 23 3 1 2 1 1( , ) 3x xf x x e x e x= − + 2 2 13 3( ) x e xf x  − +∇ =   2 23 13 3 x x e x e −  2 2 2 2 2 1 3 1 6 3( ) 3 9 3 x x x x x ef x e e x e   −∇ =   − −  10/6/2010 7MaMH C02012 Chương 3: QHPT không ràng buộc 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 8MaMH C02012 Chương 3: QHPT không ràng buộc 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 9MaMH C02012 Chương 3: QHPT không ràng buộc Ý tưởng: Xuất phát từ một điểm bất kỳ , ta xây dựng một dãy điểm sao cho 0 nx ∈ℝ 1 2 , ,..., ,... kx x x 0 1 2( ) ( ) ( ) ... ( )...kf x f x f x f x≥ ≥ ≥ ≥ và dãy hội tụ đến điểm dừng của hàm { }kx * nx ∈ℝ .f ( )*( ) 0f x∇ = 10/6/2010 10MaMH C02012 Chương 3: QHPT không ràng buộc 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 11MaMH C02012 Chương 3: QHPT không ràng buộc 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 ý Gán Bước lặp k, (k=0,1,2,…) If thỏa mãn điều kiện dừng Then 0 nx ∈ℝ : 0;k = 1( )k kx dừng thuật toán Else xác định sao cho Gán Quay lại bước lặp k. 1k k k kx x t d + = + 1( ) ( )k kf x f x+ < 2( )k : 1;k k= + 10/6/2010 12MaMH C02012 Chương 3: QHPT không ràng buộc 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 13MaMH C02012 Chương 3: QHPT không ràng buộc Hướng giảm Định nghĩa: Cho . Ta nói là hướng giảm của hàm tại nếu tồn tại sao cho với mọi t thỏa mãn ta có 0 nx ∈ℝ nd∈ℝ f 0x 0ε > 0 t ε< < 0 0( ) ( )f x td f x+ < 10/6/2010 14MaMH C02012 Chương 3: QHPT không ràng buộc Mệnh đề 1. Cho khả vi trên , điểm , và hướng Nếu thì d là hướng giảm của tại . f nℝ 0 nx ∈ℝ nd∈ℝ 0( ), 0f x d∇ < f 0x Mệnh đề 2. Cho hàm lồi khả vi trên , điểm và hướng . Khi đó, khi và chi khi d là hướng giảm của tại . f nℝ 0 nx ∈ℝ nd∈ℝ 0( ), 0f x d∇ < f 0x 10/6/2010 15MaMH C02012 Chương 3: QHPT không ràng buộc Hệ quả 1.Cho hàm khả vi trên và điểm Nếu thì là một hướng giảm của tại . Mệnh đề 3. Giả sử hàm khả vi trên và f nℝ 0 nx ∈ℝ 0( ) 0f x∇ ≠ 0( )d f x=−∇ f 0x f nℝ 0( ) 0f x∇ ≠ .Trong các hướng giảm d của hàm tại có thì hàm giảm nhanh nhất theo hướng f 0x 1d = f 0 0 ( ) ( ) f xd f x ∇ = − ∇ 10/6/2010 16MaMH C02012 Chương 3: QHPT không ràng buộc 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 17MaMH C02012 Chương 3: QHPT không ràng buộc Xác định độ dài bước i) Thủ tục tìm chính xác theo tia: ( )kt argmin{ ( ) : ( ) : 0}k kk kt t f x td tϕ= = + > 10/6/2010 18MaMH C02012 Chương 3: QHPT không ràng buộc Mệnh đề 4. Cho hàm toàn phương lồi chặt trong đó, đối xứng, xác định dương, và Cho và hướng giảm của hàm 1( ) , 2 T Tf x x Ax b x c= − + n nA × nb∈ℝ .c∈ℝ k nx ∈ℝ kd tại . Khi đó, độ dài bước chính xác được xác định bởi f kx kt ( ) 0( ) k T k k k T k Ax b d t d Ad − = − > 10/6/2010 19MaMH C02012 Chương 3: QHPT không ràng buộc ii) Thủ tục quay lui (xác định khi đã biết ) Mệnh đề 5.Cho hàm khả vi trên , điểm và véctơ thỏa mãn .Cho số 1kx + kd f nℝ k nx ∈ℝ k nd ∈ℝ ( ), 0k kf x d∇ < thực . Khi đó1 (0,1)m ∈ 0 1 00 : ( ) ( ) ( ), , (0, ].k k k k kt f x td f x m t f x d t t∃ > + ≤ + ∇ ∀ ∈ 10/6/2010 20MaMH C02012 Chương 3: QHPT không ràng buộc Thủ tục quay lui (Quy tắc Armijo) Đầu vào: điểm và hướng giảm của hàm tại ; Đầu ra: điểm trên tia thỏa mãn k nx ∈ℝ kd f kx 1kx + , 0k kk kx t d t+ > 1( ) ( )k kf x f x+ < - Bước 1: Tùy chọn và (chẳng hạn ). Đặt - Bước 2: Tính và - Bước 3: If Then dừng thủ tục (ta có ). 1 (0,1)m ∈ (0,1)α∈ 1/2α= : 1;kt = 1 :k k kkx x t d + = + 1( );kf x + 1 1( ) ( ) ( ),k k k kkf x f x m t f x d+ ≤ + ∇ 1kx + 10/6/2010 21MaMH C02012 Chương 3: QHPT không ràng buộc Else và quay về Bước 2.:k kt tα= 10/6/2010 22MaMH C02012 Chương 3: QHPT không ràng buộc 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 23MaMH C02012 Chương 3: QHPT không ràng buộc Tốc độ hội tụ Định nghĩa. Cho dãy hội tụ đến Dãy được gọi là:
Hội tụ đến với tốc độ tuyến tính nếu { }k nx ⊂ℝ * nx ∈ℝ 1 * * 0 00 1 : ; k kk sao cho k k x x x xγ γ+∃ − ≤ − *x { }kx
Hội tụ đến với tốc độ trên tuyến tính nếu và
Hội tụ đến với tốc độ hội tụ bậc hai nếu *x 1 * *: ;k kkk x x c x x +∀ − ≤ − 0 ;kc → *x 21 * * 0 00, : . k kk x x x x k kγ γ+∃ > ∃ − ≤ − ∀ > 10/6/2010 24MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Gradient (tại mỗi bước lặp k, chọn hướng giảm ) Thuật toán 1(TT Gradient với thủ tục tìm chính xác theo tia) Bước khởi đầu. ( )k kd f x= −∇ Chọn trước số đủ nhỏ. Xuất phát từ một điểm tùy ý có ; Đặt Bước lặp k (k=0,1,2,…) Tính trong đó 0ε > 0 nx ∈ℝ 0( ) 0f x∇ ≠ : 0;k = 1( )k 1 : ( ),k k kkx x t f x+ = − ∇ argmin{ ( ) : ( ( )), 0}k kk kt t f x t f x tϕ= = − ∇ > 10/6/2010 25MaMH C02012 Chương 3: QHPT không ràng buộc Tính If Then dừng thuật toán (lấy điểm dừng ) Else, và quay lại Bước lặp k. 2( )k 1( );kf x +∇ 3( )k 1( )kf x ε+∇ ≤ * 1kx x +≈ : 1k k= + 10/6/2010 26MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 4 (Định lý hội tụ) Cho và hàm f khả vi liên tục trên và có tập mức dưới bị chặn. Khi đó, mỗi điểm tụ của dãy được chọn như 0 nx ∈ℝ nℝ 0{ : ( ) ( )}nx f x f x∈ ≤ℝ *x { }kx trong Thuật toán 1 thỏa mãn *( ) 0.f x∇ = 10/6/2010 27MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán 2 (TT Gradient với thủ tục quay lui) Bước khởi đầu. Tùy chọn và . Chọn số thực đủ nhỏ. Xuất phát từ một điểm tùy ý có Đặt 1 (0,1)m ∈ (0,1)α∈ 0ε > 0 nx ∈ℝ 0( ) 0.f x∇ ≠ : 0;k = Bước lặp k ( k=0,1,2,…) Đặt Tính và If 1( )k : 1;kt = 2( )k 1 : ( )k k kkx x t f x+ = − ∇ 1( );kf x + 3( )k 21 1 1( ) ( ) ( , ( ) ( )k k k k kk kf x f x mt f x f x mt f x+ − ≤ ∇ −∇ =− ∇ 10/6/2010 28MaMH C02012 Chương 3: QHPT không ràng buộc Then chuyển sang Bước Else và quay về Bước Tính If Then dừng thuật toán (lấy ) 4( ) ;k :k kt tα= 2( ) ;k 4( )k 1( );kf x +∇ 5( )k 1( )kf x ε+∇ < * 1kx x +≈ Else quay về Bước lặp k.: 1,k k= + 10/6/2010 29MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 5 (Định lý hội tụ) Giả sử hàm f bị chặn dưới , Gradient thỏa mãn điều kiện Lipschitz, tức tồn tại L > 0 sao cho ( )f x∇ ( ) ( ) , , nf x f y L x y x y∇ −∇ ≤ − ∀ ∈ℝ Khi đó, với bất kỳ điểm xuất phát , dãy được chọn như trong Thuật toán 2 có tính chất khi 0x { }kx ( ) 0kf x∇ → .k → ∞ 10/6/2010 30MaMH C02012 Chương 3: QHPT không ràng buộc Ví dụ: Xét bài toán với hàm mục tiêu --------------------------------------------------------------- i) Điều kiện tối ưu; ( )krbP 3 2 1 2 1 2 1 2( , ) 3 2 12f x x x x x x= + − − + ii) Thuật toán Gradient với thủ tục tìm chính xác theo tia ; iii) Thuật toán Gradient với thủ tục quay lui ( )0 (1,2)x = ( )0 (1,2) .x = 10/6/2010 31MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Newton 1. Phương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Phương pháp Newton với bước điều chỉnh 4. Phương pháp tựa Newton 10/6/2010 32MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Newton giải bài toán với hàm mục tiêu phi tuyến f khả vi hai lần trên , chính là giải hệ phương trình ( )krbP min{ ( ) : },nf x x∈ℝ nℝ ( hệ phương trình phi tuyến n ẩn, n phương trình để tìm điểm dừng của hàm f ). ( ) 0f x∇ = 10/6/2010 33MaMH C02012 Chương 3: QHPT không ràng buộc 1. Phương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Phương pháp Newton với bước điều chỉnh 4. Phương pháp tựa Newton 10/6/2010 34MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Newton cổ điển Trường hợp n=1. Xét phương trình một biến số Giả sử nghiệm của phương trình này là . ( ) 0.f x = *x ∈ℝ Thuật toán Newton tìm nghiệm sẽ xuất phát từ một điểm đủ gần và sinh ra một dãy nghiệm xấp xỉ hội tụ đến . Xấp xỉ Taylor bậc nhất của hàm f (x) tại là: , với , đủ bé *x 0x *x 0 1 2 , , ,..., ,... kx x x x *x kx ( ) ( ) ( )k k kf x p f x pf x′+ ≈ + p∈ℝ p 10/6/2010 35MaMH C02012 Chương 3: QHPT không ràng buộc Ta có chính là phương trình tiếp tuyến của hàm số tại điểm Giả sử . Khi đó, phương trình có nghiệm ( ) : ( ) ( )k kd y f x p f x′= + ( )y f x= ( , ( ))k kx f x ( ) 0f x′ ≠ ( ) ( ) 0k kf x p f x′+ = Đặt Ta có . Gán k:=k+1 và lặp lại quá trình tính toán với điểm mới. ( ) / ( )k kp f x f x′= − 1 : ( ) / ( )k k k kx x f x f x+ ′= − 1 ( ) ( )kx d Ox+ = ∩ kx 10/6/2010 36MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 6 (Định lý hội tụ) Giả sử rằng: i) Hàm f (x) khả vi liên tục cấp hai; ii) là nghiệm phương trình , tức iii) *x *( ) 0;f x =( ) 0f x = *( ) 0.f x′ ≠ Khi đó, nếu đủ nhỏ thì dãy xác định bởi hội tụ đến với tốc độ bậc hai và hệ số 0 *x x− { }kx 1 ( ) / ( )k k k kx x f x f x+ ′= − *x * * ( ) .( ) f x f xγ ′′ = ′ 10/6/2010 37MaMH C02012 Chương 3: QHPT không ràng buộc Trường hợp tổng quát (n>1) Xét hàm véctơ : ( )1 2 : ( ) ( ), ( ),..., ( ) n m T m F x F x f x f x f x → = ℝ ℝ ֏ trong đó có các đạo hàm riêng Kí hiệu: là ma trận Jacobi của hàm F tại x. ( ma trận cấp ) : , 1,..., ,nif i m→ =ℝ ℝ ( )DF x m n× 10/6/2010 38MaMH C02012 Chương 3: QHPT không ràng buộc Xét hệ phương trình n ẩn, n phương trình trong đó ( m=n) . Xuất phát: đủ gần nghiệm , xây dựng dãy điểm hội tụ đến . ( ) 0F x = 1 2( ) ( ( ), ( ),..., ( ))nF x f x f x f x= 0x *x { }, 1, 2,...kx k = *x Khai triển Taylor của F tại là trong đó có đủ nhỏ, là vô cùng bé cấp cao hơn so với khi kx ( )( ) ( ) ( ) ,k k kF x p F x DF x p o p+ = + + np∈ℝ p ( )o p p 0.p→ 10/6/2010 39MaMH C02012 Chương 3: QHPT không ràng buộc Khi đó, xấp xỉ Taylor bậc nhất của hàm F tại là Giả sử không suy biến . Hệ phương trình kx ( ( .) ) ( )k k kF x p F x DF x p+ ≈ + ( )kDF x ( ) ( ) 0k kF x DF x p+ = có nghiệm và điểm lặp tiếp theo là Đặt và lặp lại quá trình tính toán với điểm mới. 1[ ( )] ( )k k kp DF x F x−= − 1 1: [ ( )] ( ).k k k k k kx x p x DF x F x+ −= + = − 1:k kx x += kx 10/6/2010 40MaMH C02012 Chương 3: QHPT không ràng buộc 1. Phương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Phương pháp Newton với bước điều chỉnh 4. Phương pháp tựa Newton 10/6/2010 41MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Newton thuần túy Xét bài toán , có thêm giả thiết xác định dương với mỗi Giải hệ n ẩn n phương trình: ( )krbP 2 ( )f x∇ . nx∈ℝ Để tìm điểm dừng của hàm f trên . Ta có: Tại điểm nếu ma trận không suy biến 1 2 ( ) ( ), ( ),..., ( ) 0 T n f f ff x x x x x x x  ∂ ∂ ∂∇ = = ∂ ∂ ∂  nℝ 2( ) ( )D f x f x∇ =∇ kx 2 ( )kf x∇ 10/6/2010 42MaMH C02012 Chương 3: QHPT không ràng buộc thì ta có điểm tiếp theo hay trong đó là nghiệm của hệ phương trình 1 2 1: [ ( )] . ( ).k k k kx x f x f x+ −= − ∇ ∇ 1 :k k kx x p+ = + kp 2[ ( )]. ( )k kf x p f x∇ = −∇ ( hệ phương trình Newton), véctơ được gọi là hướng Newton của hàm f tại . 2 1[ ( )] . ( ).k k kp f x f x−= − ∇ ∇ kx 10/6/2010 43MaMH C02012 Chương 3: QHPT không ràng buộc Mệnh đề 6. Nếu ma trận Hessian xác định dương thì hướng Newton của hàm f tại cũng là hướng giảm của f tại . 2 ( )kf x∇ kp kx kx 10/6/2010 44MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán 3(TT Newton thuần túy giải bt ) Bước khởi đầu. Xuất phát từ một điểm tùy ý đủ gần điểm dừng và Chọn trước số đủ nhỏ. Đặt ( )krbP 0 nx ∈ℝ *x 0( ) 0;f x∇ ≠ 0ε > : 0;k = Bước lặp k ( k =1,2,…) Tính hướng Newton của hàm tại bằng việc giải hệ phương trình tuyến tính 1( )k kp f kx 2[ ( )]. ( )k kf x p f x∇ = −∇ 10/6/2010 45MaMH C02012 Chương 3: QHPT không ràng buộc Xác định và If Then dừng thuật toán (lấy điểm dừng ) Else và quay lại Bước lặp k . 2( )k 1 :k k kx x p+ = + 1( );kf x +∇ 3( )k 1( )kf x ε+∇ ≤ * 1kx x +≈ : 1k k= + 10/6/2010 46MaMH C02012 Chương 3: QHPT không ràng buộc Định lý 7 (Định lý hội tụ) Giả sử : i) Hàm f khả vi hai lần trên ; ii) Hàm là liên tục và Lipschitz trong lân cận của điểm dừng của hàm f , tức tồn tại lân cận và số sao cho nℝ ( )f x∇ *x *( , )B x ε 0L > iii) Ma trận xác định dương tại mọi Khi đó, nếu xuất phát từ một điểm đủ gần thì dãy sinh ra bởi Thuật toán 3 sẽ hội tụ tới theo tốc độ cấp hai. *( ) ( ) , , ( , );f x f y L x y x y B x ε∇ −∇ ≤ − ∀ ∈ 2 ( )f x∇ .nx∈ℝ *x { }kx *x 10/6/2010 47MaMH C02012 Chương 3: QHPT không ràng buộc 1. Phương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Phương pháp Newton với bước điều chỉnh 4. Phương pháp tựa Newton 10/6/2010 48MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp Newton với bước điều chỉnh Xuất phát từ một điểm tùy ý . Tại bước lặp k, điểm được xác định bởi 0 nx ∈ℝ 1kx + 1 : ,k k kkx x t d + = + trong đó vẫn là hướng Newton của hàm f tại tức và độ dài bước được tính theo thủ tục quay lui. kd kx 2 1[ ( )] . ( )k k kd f x f x−= − ∇ ∇ kt 10/6/2010 49MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán 4 ( TT Newton với bước điều chỉnh) Bước khởi đầu Xuất phát từ một điểm tùy ý có Chọn trước số đủ nhỏ. Đặt Bước lặp k (k=1,2,…) 0 nx ∈ℝ 0( ) 0;f x∇ ≠ 0ε > : 0;k = Tính hướng Newton bằng việc giải hệ Tính theo thủ tục quay lui Tính 1( )k kd 2[ ( )] ( )k k kf x d f x∇ = −∇ 2( )k 1 : ,k k kkx x t d+ = + 1( ).kf x +∇ 10/6/2010 50MaMH C02012 Chương 3: QHPT không ràng buộc If Then dừng thuật toán (lấy ) Else và quay lại Bước lặp k. 3( )k 1( )kf x ε+∇ ≤ * 1kx x +≈ : 1k k= + 10/6/2010 51MaMH C02012 Chương 3: QHPT không ràng buộc 1. Phương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Phương pháp Newton với bước điều chỉnh 4. Phương pháp tựa Newton 10/6/2010 52MaMH C02012 Chương 3: QHPT không ràng buộc Phương pháp tựa Newton Tại mỗi bước lặp, thay vì tính hướng Newton , ta tính hướng kp ( ),k kkd H f x= − ∇ trong đó là ma trận không suy biến, đối xứng, xác định dương. kH 10/6/2010 53MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán 5 (Thuật toán D.F.P.) Bước khởi đầu Xuất phát từ một điểm tùy ý có Chọn tùy ý ma trận xác định dương (Thường chọn là ma trận đơn vị I ). 1 nx ∈ℝ 1( ) 0;f x∇ ≠ 1H 1H Đặt Bước lặp k (k=1,2,…) Đặt Tính : 1;k = 1( )k : ( );k kkd H f x= − ∇ 2( )k : argmin{ ( ) : ( ), 0};k kkt t f x td tϕ= = + > 10/6/2010 54MaMH C02012 Chương 3: QHPT không ràng buộc Tính If Then dừng thuật toán Else Chuyển bước ; Tính và 4( )k 3( )k 5( )k 1 1 1: ; : ; ( ).k k k k k k kkx x t d v x x f x+ + += + = − ∇ 1( ) 0kf x +∇ ≈ 5( )k 1: ( ) ( )k k ku f x f x+=∇ −∇ ( )( )( ) k k Tk k T H u H uv v Đặt và quay lại Bước lặp k. 6( )k 1 : ; , , k k k k k k k k k H H u v u H u+ = + − : 1k k= + 10/6/2010 55MaMH C02012 Chương 3: QHPT không ràng buộc III. Phương pháp tìm kiếm trực tiếp Để giải bài toán khi hàm mục tiêu f(x) không khả vi hoặc có khả vi nhưng việc lấy các đạo hàm đạo hàm riêng khó khăn. ( )krbP Xét hai thuật toán: 1. Thuật toán của Hooke và Jeeves 2. Thuật toán tìm kiếm theo đơn hình 10/6/2010 56MaMH C02012 Chương 3: QHPT không ràng buộc 1. Thuật toán của Hooke và Jeeves. 2. Thuật toán tìm kiếm theo đơn hình. 10/6/2010 57MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán của Hooke và Jeeves Thuật toán 6 (Thuật toán giảm theo tọa độ) Bước 0. Xuất phát từ một điểm tùy ý Chọn các véctơ 1 1 2( , ,..., ) .nnx x x x= ∈ℝ trong đó là số cho trước. Chọn trước số đủ nhỏ. (0,..., 0, , 0,..., 0), 1,..., ,i i v i nδ= = 0δ > 0ε > 10/6/2010 58MaMH C02012 Chương 3: QHPT không ràng buộc Bước 1. Đặt Trong ba điểm và chọn một điểm mà tại đó giá trị hàm mục tiêu bé nhất, ký hiệu điểm đó là . Để đơn giản ta viết: Tìm (theo tọa độ thứ nhất); 01 1 .x x= 0 1 x 0 1 1x v± 11x 0 0 01 1 1 11 1 1argmin{ ( ), ( ), ( )}x f x f x v f x v= + − (theo tọa độ thứ hai); (theo tọa độ thứ n); 2 1 1 11 1 1 12 2argmin{ ( ), ( ), ( )}x f x f x v f x v= + − ⋮ 1 1 11 1 1 1argmin{ ( ), ( ), ( )}n n n nn nx f x f x v f x v− − −= + − 10/6/2010 59MaMH C02012 Chương 3: QHPT không ràng buộc Gán Bước 2. If Then Chuyển Bước 3 Else Chuyển Bước 4; Bước 3. If Then Dừng thủ tục ( ) Else Đặt 11 : ;ny x= 1 1x y= δ ε≤ * 1x x≈ và quay lại Bước 1; Bước 4. Đặt và quay lại Bước 1. , 1, ..., 2 i i vv i n= = 2 1 1 1 1 22( ); :x x y x x x= + − = 10/6/2010 60MaMH C02012 Chương 3: QHPT không ràng buộc 1. Thuật toán của Hooke và Jeeves. 2. Thuật toán tìm kiếm theo đơn hình. 10/6/2010 61MaMH C02012 Chương 3: QHPT không ràng buộc Thuật toán tìm kiếm theo đơn hình Thuật toán 7 Bước 1. • Tạo một đơn hình có (n+1) đỉnh • Tính 1 1 ,..., . n nx x + ∈ℝ ( ), 1, ..., 1.if x i n= + Bước 2. Tính Đặt max : ( ) max{ ( ) : 1,..., 1}, {1,..., 1}Mi i Mf f x f x i n i n= = = + ∈ + min : ( ) max{ ( ) : 1,..., 1}, {1,..., 1}mi i mf f x f x i n i n= = = + ∈ + max min: ; : .mM iix x x x= = 10/6/2010 62MaMH C02012 Chương 3: QHPT không ràng buộc Bước 3 ( Tiêu chuẩn tối ưu) If Then Dừng thủ tục ( là nghiệm tối ưu địa phương và là giá trị tối ưu tương ứng) Else Chuyển Bước 4. max minf f ε− ≤ minx minf Bước 4.(Tính điểm trọng tâm) (tổ hợp lồi của ) 1 1 1 1 ( ) ( ) i n S i n ii i f x x x f x + + = = =∑ ∑ , 1, ..., 1ix i n= + 10/6/2010 63MaMH C02012 Chương 3: QHPT không ràng buộc Bước 5. Chiếu đối xứng qua được (tức ) Đặt Bước 6. If Then Chuyển Bước 7 maxx Sx 2( )R max S maxx x x x= + − 1 1 2 2 S max Rx x x= + : ( ).R Rf f x= minRf f≤ Else Chuyển Bước 8. Bước 7. Chiếu đối xứng qua được Đặt If Then Đặt ( ), Sx Rx 2( );E S R Sx x x x= + − : ( ).E Ef f x= minEf f< :Mi Ex x= max : Ex x= 10/6/2010 64MaMH C02012 Chương 3: QHPT không ràng buộc được đơn hình mới và Quay về Bước 2 Else Đặt Quay về Bước 2. Bước 8. (Đã có ) If Then được đơn hình mới và Quay về Bước 2 max: ( : ),Mi R Rx x x x= = minRf f> maxRf f< max: ( : ),Mi R Rx x x x= = Else Chuyển Bước 9. Bước 9. (Đã có ) Tính và maxRf f≥ 1 1 2 2 K max Sx x x= + : ( ).K Kf f x= 10/6/2010 65MaMH C02012 Chương 3: QHPT không ràng buộc If Then được đơn hình mới và Quay về Bước 2 Else Thu hẹp đơn hình theo công thức