Tài liệu Xấp xỉ nghiệm bài toán bù đơn điệu phi tuyến

.. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KHOA HỌC -ĐẠI HỌC THÁI NGUYÊN NGÔ TRỌNG TOÀN XẤP XỈ NGHIỆM BÀI TOÁN BÙ ĐƠN ĐIỆU PHI TUYẾN LUẬN VĂN THẠC SĨ Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 0112 Giáo viên hướng dẫn: GS.TS NGUYỄN BƯỜNG THÁI NGUYÊN, 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Luận văn được thực hiện và hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn khoa học của GS.TS Nguyễn Bường. Qua đây, tác giả xin được gửi lời cảm ơn sâu sắc đến thầy giáo, người hướng dẫn khoa học của mình, GS.TS. Nguyễn Bường, người đã đưa ra đề tài và tận tình hướng dẫn trong suốt quá trình nghiên cứu của tác giả. Đồng thời tác giả cũng chân thành cảm ơn các thầy cô trong khoa Toán - Tin học trường Đại học Khoa học, Đại học Thái Nguyên, đã tạo mọi điều kiện cho tác giả về tài liệu và thủ tục hành chính để tác giả hoàn thành bản luận văn này. Tác giả cũng gửi lời cảm ơn đến gia đình, BGH trường THPT Yên Thủy B - Hòa Bình và các bạn trong lớp Cao học K4C, đã động viên giúp đỡ tác giả trong quá trình học tập và làm luận văn. 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Mở đầu 2 1 Một số kiến thức cơ sở 1.1 Không gian Hilbert . . . . . . . . . . . . . . . 1.2 Toán tử đơn điệu . . . . . . . . . . . . . . . . 1.3 Phương pháp lặp Newton giải phương trình phi 1.4 Thuật toán giảm cho bài toán phi tuyến . . . . 1.5 Thuật toán Maps . . . . . . . . . . . . . . . . . . . . . . . . tuyến . . . . . . . . 2 Phương pháp giải bài toán bù đơn điệu phi tuyến 2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . 2.2 Định lí tương đương . . . . . . . . . . . . . . . . . 2.3 Tính hội tụ . . . . . . . . . . . . . . . . . . . . . 2.4 Phương pháp giải . . . . . . . . . . . . . . . . . 2.4.1 Phương pháp đường dốc . . . . . . . . . . 2.4.2 Thuật toán . . . . . . . . . . . . . . . . . . 2.4.3 Phép xấp xỉ của Mangasarian và Solodov . 2.5 Một số kết quả thực nghiệm số . . . . . . . . . . . 2.5.1 Phương pháp BFGS (Giới hạn bộ nhớ ) . . 2.5.2 Nhận xét . . . . . . . . . . . . . . . . . . 2.5.3 Nhận xét cuối . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 6 8 9 12 . . . . . . . . . . . 15 15 15 18 20 20 21 22 23 24 25 27 Mở đầu Nhiều vấn đề thuộc lĩnh vực toán học khác nhau như giải tích lồi, phương trình toán lý quy hoạch toán học, lý thuyết trò chơi, mô hình kinh tế ... có thể phát biểu dưới dạng bài toán sau. Xét bài toán bù NCP(F) x ≥ 0, F (x) ≥ 0, xT F (x) = 0, (1) ở đây F : Rn → Rn là một hàm cho trước. Trong nhiều bài báo gần đây, bài toán này xem như là bài toán cực tiểu với mục đích áp dụng phương pháp tối ưu để giải (1). Chẳng hạn, Mangasarian và Solodov [8] giới thiệu bài toán cực tiểu không ràng buộc với tính chất là : Mọi cực tiểu toàn cục của hàm mục tiêu đều là nghiệm của (1). Yamashita và Fukushima [11] chứng minh rằng: Mỗi điểm dừng của hàm Mangasarian và Solodov đều là cực tiểu toàn cục 0 và do đó nó là nghiệm của (1) nếu F khả vi liên tục và F xác định dương ∀x ∈ Rn . Trong luận văn này sử dụng công thức được giới thiệu trong [4] để giải lại (1) như một bài toán tối ưu không ràng buộc. Bố cục luận văn gồm có hai chương : Chương 1: Kiến thức chuẩn bị. Trong chương này, tôi trình bày một số kiến thức cơ bản về giải tích hàm, toán tử đơn điệu,phương pháp lặp New tơn giải phương trình phi tuyến, thuật toán giảm cho bài toán phi tuyến, thuật toán Maps. Chương 2: Bài toán bù đơn điệu phi tuyến. Trong chương này luận văn phát biểu bài toán bù đơn điệu, chứng minh định lý tương đương, trình bày phương pháp xấp xỉ của Mangasasian và Solodov. Phần cuối chúng tôi trình bày một số kết quả thực nghiệm số của bài toán. 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Do thời gian có hạn và khối lượng kiến thức lớn, chắc chắn bản luận văn không thể tránh khỏi những thiếu sót, tác giả rất mong nhận được sự chỉ bảo tận tình của các thầy cô và bạn bè đồng nghiệp, tác giả xin chân thành cảm ơn! 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 Một số kiến thức cơ sở 1.1 Không gian Hilbert Định nghĩa 1.1. Giả sử E là không gian véc tơ trên trường K . Tích vô hướng trên E là ánh xạ ϕ : E × E → K thỏa mãn (i) ϕ(x, x) > 0 nếu x 6= 0; ϕ(x, x) = 0 nếu x = 0. (ii) ϕ(x, y) = ϕ(y, x). (iii) ϕ(λx, y) = λϕ(x, y). (iv) ϕ(x1 + x2 , y) = ϕ(x1 , y) + ϕ(x2 , y). Kí hiệu ϕ(x, y) = hx, xi. Khi đó q ||x|| = hx, xi. Xác định một chuẩn trên E . Định nghĩa 1.2. Không gian véc tơ E cùng với tích vô hướng trên nó gọi là không gian tiền Hilbert. Một không gian tiền Hilbert đủ được gọi là không gian Hilbert. Một không gian tiền Hilbert không đủ bao giờ cũng có thể bổ sung thành một không gian Hilbert. Định nghĩa 1.3. Hai véc tơ x, y ∈ E gọi là trực giao với nhau, kí hiệu x⊥y ,nếu hx, xi = 0. Véc tơ x gọi là trực giao với tập M ⊂ E nếu x trực giao với mọi véc tơ của M . Tập M ⊥ = {x|hx, xi = 0, ∀y ∈ M } gọi là phần bù trực giao của M . Bổ đề 1.1. M ⊥ là không gian đóng của E . 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định nghĩa 1.4. Cho một toán tử tuyến tính liên tục A trong không gian Hilbert E , tồn tại một toán tử duy nhất A∗ để cho < Ax, y >=< x, A∗ y > . Toán tử A∗ gọi là toán tử liên hợp của A. Một số tính chất của toán tử liên hợp : (i) (A∗ )∗ = A . (ii) (A∗ + B ∗ ) = A∗ + B ∗ , (αA)∗ = αA∗ . (iii) (AB)∗ = B ∗ A∗ . ⊥ ⊥ (iv) N (A) = Re (A∗ ) , N (A∗ ) = Re (A) . Định lí 1.1. Cho M là một không gian con đóng của một không gian Hilbert E bất kì phần tử của E cũng biểu diễn duy nhất dưới dạng. x = y + z với y ∈ M, z ∈ M ⊥ , trong đó y là phần tử của M gần x nhất, tức là kx − yk ≤ kx − uk , ∀u ∈ M. Đặt P (x) = y , P gọi là toán tử chiếu lên M . Cho không gian Affine định nghĩa bởi Ax = q, A ∈ Rn×m , q ∈ Rm , chúng ta định nghĩa phép chiếu PA,q bởi x 7→ PA,q x = arg min {kω − xk |Aω = q} , PA = PA,0 . Bổ đề 1.2. Với mọi x ∈ Rn và q ∈ Rm ,thì PA,q x = PA x + PA,q 0. Chứng minh. ω 1 = PA,q1 x1 và ω 2 = PA,q2 x2 . Từ định nghĩa của phép chiếu, ta có Aω i = q i , xi − ω i ⊥N (A), i = 1, 2. Từ đó ta có ∀λ ∈ R, A(ω 1 + λω 2 ) = q 1 + λq 2 và x1 + λx2 − (ω 1 + λω 2 )⊥N (A). Điều đó có nghĩa rằng ω 1 + λω 2 = PA,q1 +λq2 (x1 + λx2 ). Bổ đề 1.3. Giả sử D ∈ Rn sao cho d ∈ D thì d ≈ 1. Khi đó với mọi y ∈ Rn , q ∈ R(A), d ∈ D ta có PAD,q 0 = O(kqk), PAD,q y = O(kqk) + O(kyk), kDPAD Dyk ≈ kPA yk . 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chứng minh. Giả sử A+ là ma trận nghịch đảo của A, nghĩa là A+ là ma trận (n × m) sao cho AA+ q = q, q ∈ R(A). Khi đó ta có min imize {kx − yk |ADz = q} . Suy ra kPAD,q y − yk ≤ D−1 A+ q + kyk . Do đó PAD,q 0 = O(kqk). PAD,q y = O(kqk) + O(kyk). Từ kết quả trên ta cũng có ∀z = Rn , DP ADDz = O(kzk). Lấy z = PA y = y − AT ω, ω ∈ Rm ta được PAD Dz = PAD Dy − PAD DAT ω = PAD Dy, DPAD Dy = O(kPA yk). Bằng cách tương tự, với thay đổi y = Dy , ta có DA y = O(kDPAD Dyk). Vậy kDPAD dyk ≈ kPA yk. 1.2 Toán tử đơn điệu Cho X là không gian Banach phản xạ với không gian liên hợp của nó là X ∗ . Cả hai có chuẩn được ký hiệu là k . k và giá trị của phiếm hàm tuyến tính liên tục x∗ ∈ X ∗ tại điểm x ∈ X được ký hiệu bởi hx∗ , xi. Cho toán tử A với miền xác định là D(A) ⊆ X và miền ảnh R(A) ⊆ X ∗ . Định nghĩa 1.5. Toán tử A được gọi là đơn điệu nếu hA(x) − A(y), x − yi ≥ 0, ∀x, y ∈ D(A). Toán tử A được gọi là đơn điệu chặt nếu dấu bằng chỉ đạt được khi x = y. Ví dụ 1.1. Hàm số f : R → R là đơn điệu nếu nó đồng biến. Định nghĩa 1.6. Tập hợp Gr(A) = {(x, A(x)) : x ∈ X} gọi là đồ thị của toán tử A. 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Khái niệm về toán tử đơn điệu cũng có thể được mô tả dựa trên đồ thị Gr(A) của toán tử A trong không gian tích X × X ∗ . Định nghĩa 1.7. Toán tử A được gọi là đơn điệu nếu hx∗ − y ∗ , x − yi ≥ 0, ∀x, y ∈ X, x∗ ∈ A(x), y ∗ ∈ A(y). Tập Gr(A) được gọi là tập đơn điệu nếu nó thỏa mãn bất đẳng thức trên. Định nghĩa 1.8. Nếu Gr(A) không chứa một tập đơn điệu nào khác trong X × X ∗ thì toán tử A được gọi là toán tử đơn điệu cực đại. Ví dụ 1.2. Toán tử A : R4 → R4 được xác  39 7 32  7 30 34 A =  32 34 58 −20 7 −5 định bởi ma trận  −20 7  −5  26 có định thức khác 0 là đơn điệu. Khi đó, A là toán tử đơn điệu cực đại. Định nghĩa 1.9. Nếu với mọi x ∈ X ta có hAx, xi ≥ 0 thì A được gọi là toán tử xác định không âm, ký hiệu là A ≥ 0. Nhận xét 1.1. Nếu A là một toán tử tuyến tính trong không gian Banach X thì tính đơn điệu tương đương với tính xác định không âm của toán tử. Ví dụ 1.3. Toán tử A : R5 → R5 được xác định  10 4 9 5 28  4 6 5 5 20 A=  9 5 10 4 28 5 5 4 6 20 28 20 28 20 96 bởi ma trận     là xác định không âm. Định nghĩa 1.10. Toán tử A được gọi là d-đơn điệu, nếu tồn tại một hàm không âm d(t), không giảm với t ≥ 0, d(0) = 0 và thỏa mãn tính chất hA(x) − A(y), x − yi ≥ [d(k x k) − d(k y k)](k x k − k y k), ∀x, y ∈ D(A). 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định nghĩa 1.11. Toán tử A được gọi là đơn điệu đều nếu tồn tại một hàm không âm δ(t), không giảm với t ≥ 0, δ(0) = 0 và hA(x) − A(y), x − yi ≥ δ(k x − y k), ∀x, y ∈ D(A). Nếu δ(t) = CA t2 với CA là một hằng số dương thì toán tử A được gọi là đơn điệu mạnh. Nhận xét 1.2. Nếu toán tử A có tính chất tuyến tính thì A được gọi là đơn điệu mạnh nếu hAx, xi ≥ mA k x k2 , mA > 0, ∀x ∈ D(A). Ví dụ 1.4. Hàm số f : R → R được xác định bởi f (x) = 2012x là toán tử tuyến tính đơn điệu mạnh. Cho L là tập con nào đó của N = {1, ..., n}. AL là ma trận đường chéo cấp n.n trong đó các phần tử trên đường chéo được cho bởi   > 0 nếu i ∈ L, aii =  = 0 nếu i ∈ / L. Khi đó AN là một ma trận đường chéo xác định dương. Nếu aii = 1 ∀i thì AN = In là ma trận đơn vị trong Rn . 1.3 Phương pháp lặp Newton giải phương trình phi tuyến Xét hệ phương trình phi tuyến f (x) = 0, ở đây ánh xạ từ Rn vào chính nó. Giả sử f khả vi liên tục. Thuật toán sẽ  sinh ra một dãy lặp xk . Giả sử đã có xk để tìm xk+1 ta giải hệ phương trình tuyến tính f (xk )+∇f (xk )(x−xk ) = 0 . Giả sử rằng ma trận ∇f (xk ) không suy biến. Ta thu được xk+1 bằng cách xk+1 = xk − ∇f (xk )−1 f (xk ). 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định lí 1.2. Giả sử x∗ là nghiệm của hệ phương trình f (x) = 0, f khả vi liên tục trong lân cận của x∗ và ma trận ∇f (x∗ ) không suy biến. Thì tồn tại một lân cận của điểm x∗ sao cho nếu điểm ban đầu x0 được chọn  trong đó thì xk định nghĩa tốt và hội tụ tới x∗ . Hơn nữa, nếu ∇f liên  tục Lipschitz tại x∗ thì xk hội tụ cấp 2. 1.4 Thuật toán giảm cho bài toán phi tuyến Cho Γ ⊂ Rn là một tập mở và f : Γ → Rn là một hàm khả vi với đạo hàm liên tục Lipschitz địa phương x ∈ Γ 7→ ∇f (x). Xét bài toán phi tuyến minimize f (x). x∈Γ Chúng ta sẽ nghiên cứu thuật toán giải cho bài toán này . WHILE ∇f (x) 6= 0 do xk+1 := xk + λk hk k := k + 1 END WHILE Trong đó với mỗi k, h ∈ Rn và λk ∈ (0; +∞) sao cho xk+1 ∈ Γ. Một thuật toán sẽ gọi là thuật toán giảm nếu tồn tại ∆ > 0 sao cho với mọi k ∈ N ta có: (i) hk ≈ ∇f (xk ) ; (ii) f (xk + λk hk ) ≤ f (xk ) − ∇λk hk ∇f (xk ) .  Một dãy xk trong Γ được gọi là compact Γ0 ⊂ Γ, và một điểm x ∈ Γ thì thỏa mãn nếu ∇f (x). Bổ đề sau đây chỉ ra rằng có hai sự lựa chọn cho thuật toán giảm: hoặc bước đủ lớn để tiến tới tập tối ưu và sau đó mọi điểm tụ đều thỏa mãn, hoặc bước ngắn và dãy hội tụ tới điểm không thỏa mãn. Bổ đề 1.4. Giả sử thuật toán giảm ở trên sinh ra một dãy compact vô hạn  k x trong Γ. Khi đó ∞  P (i) Hoặc λk < +∞ và xk hội tụ đến điểm không thỏa mãn hoặc (ii) ∞ P k=0  λk = +∞ và mọi điểm tụ của xk đều thỏa mãn. k=0 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn    Chứng minh. Xét dãy xk , hk , λk sinh ra bởi thuật toán ,và giả sử  rằng xk được chứa trong tập compact Γ0 ∈ Γ. ∞ ∞ P P k (i) Nếu λ < +∞ thì λk hk < +∞. Do hk ≈ k∇f (x)k bị k=0 k=0  chặn trong Γ0 nên xk là dãy Cô si và ta có xk → x với x ∈ Γ0 . Chúng ta phải chứng minh rằng x không thỏa mãn. b = {x ∈ Γ0 |∇f (x) = 0} là các điểm trong thỏa mãn trong Γ0 . Đặt Γ Nếu Γ0 = ∅, thì ta có điều phải chứng minh. Trường hợp ngược lại giả sử L là hằng số Lipschitz toàn cục cho ∇f trong Γ0 . Vì hk ≈ k∇f (x)k , hk ≤ K k∇f (x)k với K > 0 là hằng số. Suy ra k+1 x − xk ≤ λk hk ≤ λk K k∇f (x)k . Sau một bước lặp ta thu được ∇f (xk+1 ) ≥ ∇f (xk ) − L xk+1 − xk ≥ (1 − KLλk ) ∇f (xk ) . Do λk → 0 với k0 đủ lớn 1 − KLλk > 0 và log(1 − KLλk ) ≥ −2KLλk . Vì vậy với k > k0 ta có Y k−1 ∇f (xk ) ≥ ∇f (xk0 ) (1 − KLλj ). j=k0 Và k−1 X k k0 log ∇f (x ) ≥ log ∇f (x ) + (1 − KLλj ) j=k0 k−1 X k ≥ log ∇f (x 0 ) − 2LK λj . j=k0 Suy ra log ∇f (xk ) bị chặn dưới và vì vậy nó bị chặn dưới bởi 0, do đó (i) được chứng minh. P∞ (ii) Giả sử rằng k=0 = +∞. Với ε > 0 tùy ý ta đặt Γε = {x ∈ Γ0 k∇f (x)k > ε} . Vì f bị chặn trong Γ0 và hk ≈ ∇f (xk ) nên ta có ∞ X 2 λk ∇f (xk ) < +∞. k=0 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (1.1)  Ta giả sử (xk ) có điểm tụ x ∈ Γε . Khi đó tập K = k ∈ N |xk ∈ Γε là vô hạn theo (1.1), với ∇f (xk ) ≥ ε với k ∈ K ta có X λk < +∞. (1.2) k∈K và K = N − K cũng là vô hạn. Với mỗi k ∈ K , giả sử k 0 > k là chỉ số đầu tiên trong K . Ta thu được 0 0 −1 kX −1 0 kX k k j j λ h = O( λj ). x − x ≤ j=k (1.3) j=k 0 Sử dụng (1.2) chúng ta có khi k ∈ K tăng thì xk − xk → 0, và như thế   0  0 dãy xk k∈K và dãy xk k∈K có cùng điểm tụ. Nhưng dãy xk k∈K có / Γε . điểm tụ không thỏa mãn k∇f (x)k ≤ ε ⇒ x ∈ Một cách cải biên của thuật toán theo thuật toán trên những bước cho bởi xk+1 := xk + λk hk + η k x0 ∈ Rn , k := 0 WHILE ∇f (x) 6= 0 do xk+1 := xk + λk hk + η k k := k + 1 END WHILE Bổ đề dưới đây chỉ ra rằng, nếu Thuật toán ∞ X k η < ∞ k=0 thì khả năng tìm điểm tụ của thuật toán giảm không ảnh hưởng. Nhưng phần đầu của bổ đề trên sẽ không được đảm bảo vì một hiệu chỉnh thông minh có thể cho ta một điểm thỏa mãn. Bổ đề 1.5. Xét phương pháp giảm với bước hiệu chỉnh ,với dãy hiệu chỉnh k P < ∞, và giả sử rằng nó sinh ra một dãy compact η k sao cho ∞ k=0 η của phép lặp. Thì  k P k (i) ∞ λ < ∞ và x có thể hội tụ đến điểm không thỏa mãn, hoặc  Pk=0 ∞ k (ii) k=0 λ = +∞ và mọi điểm tụ của xk đều thỏa mãn. 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chứng minh. Việc chứng minh theo cách chứng minh của bổ đề trước . Chúng ta sẽ chỉ ra những thay đổi trong quá trình chứng minh. Phần (i) là tầm thường bởi vì dãy kết quả là dãy Cô si. Để chứng minh (ii), ta định nghĩa Γε như trước và chú ý sử dụng điều kiện Lipschitz cho ∇f trong tập compact Γ0 , tồn tại hằng số Lipschitz toàn cục Lf cho f trong Γ0 . Vì vậy ta có f (xk−1 ) = f (xk + λk hk + η k ) ≤ f (xk + λk hk ) + Lf η k ≤ f (xk ) − ∆λk ∇f (xk ) hk + Lf η k . Vì f bị chặn trong Γ0 nên ∞ X (∆λk ∇f (xk ) hk + Lf η k < +∞. k=0 P k 2 k ∇f (x ) λ < +∞. Vì hk ≈ ∇f (xk ) ⇒ ∞ k=0 Phần còn lại được chứng minh giống như bổ đề trước với biểu diễn (1.3) thay bởi 0 0 0 −1 kX −1 kX −1 0 kX k k k j j k j η . x − x ≤ (λ h + η ) = O( λ ) + j=k j=k j=k Một điều rất thú vị là khi λk → 0. Trong trường hợp này, tập các điểm tụ là một tập continuum, và nếu λk vô hạn thì mọi điểm tụ đều thỏa mãn. 1.5 Thuật toán Maps Một hướng giảm cho hàm khả vi tại một điểm là một véc tơ tạo với hướng âm của đạo hàm một góc nhỏ hơn 90 độ. Thuật toán hướng giảm có thể thu được theo nghĩa của ánh xạ mà cho tương ứng mỗi điểm với tập các hướng giảm. x ∈ Γ 7→ H(x) ∈ Rn là ánh xạ từ một tập điểm tới tập các ánh xạ. Định nghĩa 1.12. H(.) gọi là ánh xạ của hướng giảm trong tập Γ0 ∈ Γ nếu tồn tại một hằng số ∆ > 0 sao cho với mỗi x ∈ Γ0 và h ∈ H(x): 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (i) khk ≈ k∇f (x)k, (ii) ∇f (x)T h ≤ −∆ k∇f (x)k khk. Cho ánh xạ của hướng giảm định nghĩa trong Γ0 . Thuật toán giảm được xây dựng lại như sau. x0 ∈ Γ0 , k := 0 WHILE ∇f (x) 6= 0 do Chọn hk ∈ H(xk ) xk+1 := xk + λk hk + η k ∈ Γ0 k := k + 1 END WHILE Trong mỗi bước lặp k , λk ∈ (0; +∞) được chọn sao cho xk+1 ∈ Γ. Bổ đề sau đây chỉ ra rằng nếu λk đủ nhỏ và Γ0 là compact, kết quả của thuật toán này cũng giống như thuật toán giảm, từ đó tính chất hội tụ miêu tả ở trên. Γ0 được xây dựng theo hai hướng như sau:  Hướng thứ nhất là Γ0 = x ∈ Γ|f (x) ≤ f (x0 ) là tập compact, và λk được cho bởi một line search đảm bảo f (xk+1 ) ≤ f (xk ). Hướng thứ hai mà chúng ta quan tâm, ở đây thuật toán sinh ra dãy các phép lặp trong Γε . Bổ đề 1.6. Giả sử H(.) là ánh xạ giảm được định nghĩa trên tập compact Γ0 ∈ Γ. Khi đó tồn tại λ > 0 sao cho với mỗi x ∈ Γ0 , h ∈ H(x) và  λ ∈ 0; λ thỏa mãn f (x + λh) ≤ f (x) − ∆ λ k∇f (x)k khk . 2 Chứng minh. Chúng ta bắt đầu sử dụng điều kiện Lipschitz để chỉ ra rằng
tồn tại λ1 > 0 sao cho với mỗi x ∈ Γ0 , h ∈ H(x) và λ ∈ 0; λ1 : k∇f (x + λh) − ∇f (c)k ≤ λL khk . (1.4) Thật vậy, vì Γ0 là compact và Γ là tập mở, tồn tại ε > 0 sao cho Γ1 = Γ0 + Bε ∈ Γ, Bε = {y ∈ Rn | kyk ≤ ε} . Vì ∇f liên tục Lipschitz trong tập compact Γ1 với hằng số L nên với λh ≤ ε, x ∈ Γ0 ⇒ x + λh ∈ Γ1 và thỏa mãn (1.4). Vì khk ≈ k∇f (x)k và ∇f (x) bị chặn trong Γ0 nên tồn tại K1 > 0 sao cho x ∈ Γ0 , khk ≤ K1 . Chọn λ1 = Kε1 . 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Tiếp theo ta chứng minh bổ đề. Với x ∈ Γ0 , λ ∈ 0; λ1 và h ∈ H(x) thì ta có R1 f (x + λh) = f (x) + λ hT ∇f (x + σλh)dσ 0 R1 = f (x) + λh∇f (x) + λ hT [∇f (x + σλh) − ∇f (x)]dσ 0 2 ≤ f (x) − λδ k∇f (x)k khk + λ2 Lkhk2 . Do H(x) là ánh xạ hướng giảm nên tồn tại K2 > 0 sao cho khk ≤ K2 k∇f (x)k ∀x ∈ Γ0 , h ∈ H(x). o 2 n
1 ∆ Chon λ = min λ , K2 L , λ2 Lkhk2 ≤ λ ∆2 k∇f (x)k khk, với λ ∈ 0; λ . 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 2 Phương pháp giải bài toán bù đơn điệu phi tuyến 2.1 Giới thiệu Xét bài toán bù NCP(F) x ≥ 0, F (x) ≥ 0, xT F (x) = 0, (2.1) ở đây F : Rn → Rn là một hàm cho trước. Trong nhiều bài báo gần đây, bài toán này xem như là bài toán cực tiểu với mục đích áp dụng phương pháp tối ưu để giải (2.1) . Chẳng hạn Mangasarian và Solodov [8] giới thiệu bài toán cực tiểu không ràng buộc với tính chất là: Mọi cực tiểu toàn cục của hàm mục tiêu đều là nghiệm của (2.1). Yamashita và Fukushima [11] chứng minh rằng: Mỗi điểm dừng của hàm Mangasarian và Solodov đều là cực tiểu toàn cục 0 và do đó nó là nghiệm của (2.1) nếu F khả vi liên tục và F xác định dương ∀x ∈ Rn . Trong luận văn này sử dụng công thức được giới thiệu trong [4] để giải lại (2.1) như một bài toán tối ưu không ràng buộc. 2.2 Định lí tương đương Cho ϕF : R2 → R là hàm số xác định bởi √ ϕF (a, b) = a2 + b2 − a − b 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hàm này được gọi là hàm Fischer được giới thiệu gần đây là đặc trưng cho điều kiện Karush-Kuhn-Tucker của một bài toán phi tuyến (xem [1]) và bài toán bù tuyến tính (xem [2]). Ở đây chúng ta quan tâm đến hàm 1 √ ϕ (a, b) : = ( a2 + b2 − a − b)2 . 2 Sau đây là một số tích chất của hàm ϕ(a, b). Bổ đề 2.1. i) ϕ(a, b) = 0 ⇔ a ≥ 0, b ≥ 0, ab = 0. ii) ϕ(a, b) ≥ 0 ∀(a, b)T ∈ R2 . iii) ϕ khả vi liên tục với mọi ∀(a, b)T ∈ R2 , đặc biệt ∇ϕ(0, 0) = (0, 0)T . T ∂ϕ 2 iv) ∂ϕ ∂a (a, b) ∂b (a, b) ≥ 0 , ∀(a, b) ∈ R . ∂ϕ v) ∂ϕ ∂a (a, b) ∂b (a, b) = 0 ⇒ ϕ(a, b) = 0. Bây giờ ta xét bài toán bù phi tuyến (2.1) và bài toán tối ưu không ràng buộc minx∈Rn Ψ(x), (2.2) ở đây Ψ : Rn → R xác định bởi Ψ (x) = n X ϕ (xi , F (x)i ) i=1 trong đó Fi : Rn → R là hàm thành phần thứ i của F . Dựa vào tính chất (i) và (ii) của Bổ đề 2.1 ta có kết quả sau: Bổ đề 2.2. Giả sử bài toán bù (2.1) có ít nhất một nghiệm khi đó x∗ ∈ Rn là nghiệm của (2.1) nếu và chỉ nếu x∗ là nghiệm toàn cục của bài toán (2.2). Sự tương đương nói trong Bổ đề 2.2 không đúng nếu bài toán bù (2.1) không giải được điều này thể hiện ở ví dụ sau. Ví dụ 2.1. Cho n = 1 và F (x) = −x2 − 1 ta có q 2 1 2 2 2 Ψ(x) = ( x + (x + 1) − x + x + 1) . 2 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ψ(x)là liên tục trên tập compact nên nó liên tục trên toàn cục nhưng bài toán bù không có nghiệm. Vấn đề tìm cực tiêu toàn cục trong trường hợp tổng quát rất khó khăn điều ta quan tâm nhất là: Với những điều kiện nào của F thì điểm dừng của Ψ sẽ là cực tiểu toàn cục. Kết quả sau đây thể hiện trong [4]. Định lí 2.1. Giả sử F ∈ C 1 (Rn ) có F 0 (x) xác định dương với ∀x ∈ Rn khi đó x∗ là cực tiểu toàn cục của Ψ nếu và chỉ nếu x∗ là điểm dừng của Ψ. Định lí 2.2. Giả sử F ∈ C 1 (Rn ) là hàm đơn điệu có nghĩa là (x − y)T (F (x) − F (y)) ≥ 0 ∀x, y ∈ Rn , khi đó x∗ ∈ Rn là cực tiểu toàn cục của bài toán tối ưu không ràng buộc (2.2) nếu và chỉ nếu x∗ là điểm dừng của Ψ. Chứng minh. Trước hết giả sử x∗ là cực tiểu toàn cục của Ψ. Do F là khả vi liên tục nên Ψ cũng khả vi lên tục ( theo Bổ đề 2.2 phần (iii)). Vì vậy gradient của Ψ tồn tại và triệt tiêu tai (=0 ) x∗ ( suy ra x∗ là điểm dừng ). Tiếp theo giả sử x∗ là điểm dừng của Ψ nghĩa là: n X ∂ϕ ∂ϕ ∗ ∗ 0 = ∇Ψ(x ) = ( (x∗ , Fi (x∗ ))ei + (x , Fi (x∗ )∇Fi (x∗ ), (2.3) ∂a ∂b i=1 ở đây ei được kí hiệu là véc tơ cột thứ i của ma trận In ta viết tắt: ∂ϕ ∗ ∂ϕ ∗ (..., (x i , Fi (x∗ )), ...) là (x , F (x∗ )), ∂a ∂a ∂ϕ ∗ ∂ϕ ∗ (..., (x i , Fi (x∗ )), ...) là (x , F (x∗ )). ∂b ∂b Điều kiện dừng (2.3) được viết lại là : ∂ϕ ∗ ∂ϕ ∗ 0= (x , F (x∗ )) + F 0 (x∗ )T (x , F (x∗ )). (2.4) ∂a ∂b ∗ ∗ T Nhân vế trái của (2.4) với ∂ϕ ∂b (x , F (x )) ta được n X ∂ϕ ∂ϕ 0 = ( (x∗ i , Fi (x∗ )) (x∗ i , Fi (x∗ ))) ∂a ∂b i=1 + ∂ϕ ∗ ∂ϕ ∗ (x F (x∗ ))T F 0 (x∗ )T (x F (x∗ )). ∂b ∂b 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.5) 0 Do F là đơn điệu nên F (x∗ ) là nửa xác định dương ( xem Ortega và Rheinboldt [10] trang 142 ) sử dụng tính chất (iv) của Bổ đề 2.2, từ (2.5) ta suy ra ∂ϕ ∗ ∂ϕ (x i , Fi (x∗)) (x∗ i , Fi (x∗)) = 0, ∀i = 1...n. ∂a ∂b Bởi (v) của Bổ đề 2.2 ta có ϕ(x∗ i , Fi (x∗)) = 0, ∀i = 1, .., n suy ra Ψ(x∗ ) = 0, tức x∗ là cực tiểu toàn cục suy ra định lí được chứng minh. Từ Bổ đề 2.2 và Định lí 2.2 ta nhận được kết quả sau: Hệ quả 2.1. Cho F ∈ C 1 (Rn ) là hàm đơn điệu . Nếu bài toán bù (2.1) giải được thì x∗ là nghiệm của (2.1) khi và chỉ khi x∗ là điểm dừng của Ψ. 2.3 Tính hội tụ Trước hết chúng ta chứng minh rằng tập mức của bài toán (2.2) bị chặn nếu F là hàm đơn điệu nghiêm ngặt. Nhắc lại F : Rn → Rn được gọi là đơn điệu nghiêm ngặt với modun µ nếu (x − y)T (F (x) − F (y)) ≥ µkx − yk2 , ∀x, y ∈ Rn . (2.6) Chúng ta đã biết rằng với F ∈ C 1 (Rn ), điều kiện (2.6) tương đương với dT F 0 (x) d ≥ µ||d||2 , ∀d ∈ Rn , ∀x ∈ Rn .  Bổ đề 2.3. Cho (ak , bk )k∈N } ⊆ R2 là một dãy bất kỳ thỏa mãn  k  k a  , b  → +∞. Khi đó ϕ(ak , bk ) → ∞, k ∈ N. Chứng minh. Điều này suy ra từ Bổ đề 2.8 trong [5]. Định lí 2.3. Giả sử F liên tục và đơn điệu nghiêm ngặt. Lấy x0 ∈ Rn là  một véc tơ và đặt L(x0 ) = {x ∈ Rn ψ(x) ≤ ψ(x0 ) là một tập mức tương ứng khi đó L(x0 ) là tập compact.  Chứng minh. Giả sử tồn tại một dãy xk }k∈N ⊆ L(x0 ) sao cho   limk→∞ xk = ∞. Xác định tập chỉ số J = i ∈ I  xk i k∈N với dãy 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn