BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KHOA HỌC -ĐẠI HỌC THÁI NGUN NGƠ TRỌNG TỒ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 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 thực hoàn thành trường Đại học Khoa học - Đại học Thái Nguyên hướng dẫn khoa học GS.TS Nguyễn Bường Qua đây, tác giả xin 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 mình, GS.TS Nguyễn Bường, người đưa đề tài tận tình hướng dẫn suốt trình nghiên cứu tác giả Đồng thời tác giả chân thành cảm ơn thầy khoa Tốn - Tin học trường Đại học Khoa học, Đại học Thái Nguyên, tạo điều kiện cho tác giả tài liệu thủ tục hành để tác giả hoàn thành luận văn Tác giả gửi lời cảm ơn đến gia đình, BGH trường THPT n Thủy B - Hịa Bình bạn lớp Cao học K4C, động viên giúp đỡ tác giả trình học tập làm luận văn Số hóa 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 Một số kiến thứ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 tốn giảm cho toán phi tuyến 1.5 Thuật toán Maps tuyến Phương pháp giả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ỉ Mangasarian Solodov 2.5 Một số kết thực nghiệm số 2.5.1 Phương pháp BFGS (Giới hạn nhớ ) 2.5.2 Nhận xét 2.5.3 Nhận xét cuối Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 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 giải tích lồi, phương trình tốn lý quy hoạch tốn học, lý thuyết trị chơi, mơ hình kinh tế phát biểu dạng tốn sau Xét toán bù NCP(F) x ≥ 0, F (x) ≥ 0, xT F (x) = 0, (1) F : Rn → Rn hàm cho trước Trong nhiều báo gần đây, toán xem tố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 Solodov [8] giới thiệu tốn cực tiểu khơng ràng buộc với tính chất : Mọi cực tiểu toàn cục hàm mục tiêu nghiệm (1) Yamashita Fukushima [11] chứng minh rằng: Mỗi điểm dừng hàm Mangasarian Solodov cực tiểu tồn cục nghiệm (1) F khả vi liên tục F xác định dương ∀x ∈ Rn Trong luận văn sử dụng công thức giới thiệu [4] để giải lại (1) tố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, trình bày số kiến thức giải tích hàm, tố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 tốn giảm cho 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 luận văn phát biểu 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ỉ Mangasasian Solodov Phần cuối chúng tơi trình bày số kết thực nghiệm số toán Số hóa 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 khối lượng kiến thức lớn, chắn luận văn tránh khỏi thiếu sót, tác giả mong nhận bảo tận tình thầy cô bạn bè đồng nghiệp, tác giả xin chân thành cảm ơn! Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương Một số kiến thức sở 1.1 Không gian Hilbert Định nghĩa 1.1 Giả sử E không gian véc tơ trường K Tích vơ hướng E ánh xạ ϕ : E × E → K thỏa mãn (i) ϕ(x, x) > x = 0; ϕ(x, x) = x = (ii) ϕ(x, y) = ϕ(y, x) (iii) ϕ(λx, y) = λϕ(x, y) (iv) ϕ(x1 + x2 , y) = ϕ(x1 , y) + ϕ(x2 , y) Kí hiệu ϕ(x, y) = x, x Khi ||x|| = x, x Xác định chuẩn E Định nghĩa 1.2 Không gian véc tơ E với tích vơ hướng gọi khơng gian tiền Hilbert Một khơng gian tiền Hilbert đủ gọi không gian Hilbert Một khơng gian tiền Hilbert khơng đủ bổ sung thành không gian Hilbert Định nghĩa 1.3 Hai véc tơ x, y ∈ E gọi trực giao với nhau, kí hiệu x⊥y ,nếu x, x = Véc tơ x gọi trực giao với tập M ⊂ E x trực giao với véc tơ M Tập M ⊥ = {x| x, x = 0, ∀y ∈ M } gọi phần bù trực giao M Bổ đề 1.1 M ⊥ khơng gian đóng E Số hóa 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 toán tử tuyến tính liên tục A khơng gian Hilbert E , tồn toán tử A∗ < Ax, y >=< x, A∗ y > Toán tử A∗ gọi toán tử liên hợp A Một số tính chất tố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 khơng gian đóng khơng gian Hilbert E phần tử E biểu diễn dạng x = y + z với y ∈ M, z ∈ M ⊥ , y phần tử M gần x nhất, tức x − y ≤ x − u , ∀u ∈ M Đặt P (x) = y , P gọi toán tử chiếu lên M Cho không gian Affine định nghĩa Ax = q, A ∈ Rn×m , q ∈ Rm , định nghĩa phép chiếu PA,q x → PA,q x = arg { ω − x |Aω = q} , PA = PA,0 Bổ đề 1.2 Với x ∈ Rn q ∈ Rm ,thì PA,q x = PA x + PA,q Chứng minh ω = PA,q1 x1 ω = PA,q2 x2 Từ định nghĩa phép chiếu, ta có Aω i = q i , xi − ω i ⊥N (A), i = 1, Từ ta có ∀λ ∈ R, A(ω + λω ) = q + λq x1 + λx2 − (ω + λω )⊥N (A) Điều có nghĩa ω + λω = PA,q1 +λq2 (x1 + λx2 ) Bổ đề 1.3 Giả sử D ∈ Rn cho d ∈ D d ≈ Khi với y ∈ Rn , q ∈ R(A), d ∈ D ta có PAD,q = O( q ), PAD,q y = O( q ) + O( y ), DPAD Dy ≈ PA y Số hóa 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+ ma trận nghịch đảo A, nghĩa A+ ma trận (n × m) cho AA+ q = q, q ∈ R(A) Khi ta có imize { x − y |ADz = q} Suy PAD,q y − y ≤ D−1 A+ q + y Do PAD,q = O( q ) PAD,q y = O( q ) + O( y ) Từ kết ta có ∀z = Rn , DP ADDz = O( z ) Lấy z = PA y = y − AT ω, ω ∈ Rm ta PAD Dz = PAD Dy − PAD DAT ω = PAD Dy, DPAD Dy = O( PA y ) Bằng cách tương tự, với thay đổi y = Dy , ta có DA y = O( DPAD Dy ) Vậy DPAD dy ≈ PA y 1.2 Toán tử đơn điệu Cho X không gian Banach phản xạ với không gian liên hợp X ∗ Cả hai có chuẩn ký hiệu giá trị phiếm hàm tuyến tính liên tục x∗ ∈ X ∗ điểm x ∈ X ký hiệu x∗ , x Cho toán tử A với miền xác định D(A) ⊆ X miền ảnh R(A) ⊆ X ∗ Định nghĩa 1.5 Toán tử A gọi đơn điệu A(x) − A(y), x − y ≥ 0, ∀x, y ∈ D(A) Toán tử A gọi đơn điệu chặt dấu đạt x = y Ví dụ 1.1 Hàm số f : R → R đơn điệu đồng biến Định nghĩa 1.6 Tập hợp Gr(A) = {(x, A(x)) : x ∈ X} gọi đồ thị tốn tử A Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Khái niệm tốn tử đơn điệu mơ tả dựa đồ thị Gr(A) tốn tử A khơng gian tích X × X ∗ Định nghĩa 1.7 Toán tử A gọi đơn điệu x∗ − y ∗ , x − y ≥ 0, ∀x, y ∈ X, x∗ ∈ A(x), y ∗ ∈ A(y) Tập Gr(A) gọi tập đơn điệu thỏa mãn bất đẳng thức Định nghĩa 1.8 Nếu Gr(A) không chứa tập đơn điệu khác X × X ∗ tốn tử A gọi toán tử đơn điệu cực đại Ví dụ 1.2 Tốn tử A : R4 → R4 xác  39 32  30 34 A =  32 34 58 −20 −5 định ma trận  −20  −5  26 có định thức khác đơn điệu Khi đó, A toán tử đơn điệu cực đại Định nghĩa 1.9 Nếu với x ∈ X ta có Ax, x ≥ A gọi tốn tử xác định không âm, ký hiệu A ≥ Nhận xét 1.1 Nếu A toán tử tuyến tính khơng gian Banach X tính đơn điệu tương đương với tính xác định khơng âm tốn tử Ví dụ 1.3 Tốn tử A : R5 → R5 xác định  10 28  5 20 A=  10 28 5 20 28 20 28 20 96 ma trận     xác định khơng âm Định nghĩa 1.10 Tốn tử A gọi d-đơn điệu, tồn hàm không âm d(t), không giảm với t ≥ 0, d(0) = thỏa mãn tính chất A(x) − A(y), x − y ≥ [d( x ) − d( y )]( x − y ), ∀x, y ∈ D(A) Số hóa 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 gọi đơn điệu tồn hàm không âm δ(t), không giảm với t ≥ 0, δ(0) = A(x) − A(y), x − y ≥ δ( x − y ), ∀x, y ∈ D(A) Nếu δ(t) = CA t2 với CA số dương tốn tử A gọi đơn điệu mạnh Nhận xét 1.2 Nếu tốn tử A có tính chất tuyến tính A gọi đơn điệu mạnh Ax, x ≥ mA x , mA > 0, ∀x ∈ D(A) Ví dụ 1.4 Hàm số f : R → R xác định f (x) = 2012x tốn tử tuyến tính đơn điệu mạnh Cho L tập N = {1, , n} AL ma trận đường chéo cấp n.n phần tử đường chéo cho   > i ∈ L, aii =  = i ∈ / L Khi AN ma trận đường chéo xác định dương Nếu aii = ∀i AN = In ma trận đơn vị 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, ánh xạ từ Rn vào Giả sử f khả vi liên tục Thuật toán sinh 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 ) = Giả sử ma trận ∇f (xk ) không suy biến Ta thu xk+1 cách xk+1 = xk − ∇f (xk )−1 f (xk ) Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hàm gọi hàm Fischer giới thiệu gần đặc trưng cho điều kiện Karush-Kuhn-Tucker toán phi tuyến (xem [1]) tốn bù tuyến tính (xem [2]) Ở quan tâm đến hàm √ ϕ (a, b) : = ( a2 + b2 − a − b)2 Sau số tích chất hàm ϕ(a, b) Bổ đề 2.1 i) ϕ(a, b) = ⇔ a ≥ 0, b ≥ 0, ab = ii) ϕ(a, b) ≥ ∀(a, b)T ∈ R2 iii) ϕ khả vi liên tục với ∀(a, b)T ∈ R2 , đặc biệt ∇ϕ(0, 0) = (0, 0)T T ∂ϕ iv) ∂ϕ ∂a (a, b) ∂b (a, b) ≥ , ∀(a, b) ∈ R ∂ϕ v) ∂ϕ ∂a (a, b) ∂b (a, b) = ⇒ ϕ(a, b) = Bây ta xét toán bù phi tuyến (2.1) toán tối ưu không ràng buộc minx∈Rn Ψ(x), (2.2) Ψ : Rn → R xác định n Ψ (x) = ϕ (xi , F (x)i ) i=1 Fi : Rn → R hàm thành phần thứ i F Dựa vào tính chất (i) (ii) Bổ đề 2.1 ta có kết sau: Bổ đề 2.2 Giả sử toán bù (2.1) có nghiệm x∗ ∈ Rn nghiệm (2.1) x∗ nghiệm tồn cục tốn (2.2) Sự tương đương nói Bổ đề 2.2 khơng tốn bù (2.1) không giải điều thể ví dụ sau Ví dụ 2.1 Cho n = F (x) = −x2 − ta có 2 2 Ψ(x) = ( x + (x + 1) − x + x + 1) 16 Số hóa 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 tập compact nên liên tục tồn cục tốn bù khơng có nghiệm Vấn đề tìm cực tiêu tồn cục trường hợp tổng quát khó khăn điều ta quan tâm là: Với điều kiện F điểm dừng Ψ cực tiểu toàn cục Kết sau thể [4] Định lí 2.1 Giả sử F ∈ C (Rn ) có F (x) xác định dương với ∀x ∈ Rn x∗ cực tiểu tồn cục Ψ x∗ điểm dừng Ψ Định lí 2.2 Giả sử F ∈ C (Rn ) hàm đơn điệu có nghĩa (x − y)T (F (x) − F (y)) ≥ ∀x, y ∈ Rn , x∗ ∈ Rn cực tiểu tồn cục tốn tối ưu không ràng buộc (2.2) x∗ điểm dừng Ψ Chứng minh Trước hết giả sử x∗ cực tiểu toàn cục Ψ Do F khả vi liên tục nên Ψ khả vi lên tục ( theo Bổ đề 2.2 phần (iii)) Vì gradient Ψ tồn triệt tiêu tai (=0 ) x∗ ( suy x∗ điểm dừng ) Tiếp theo giả sử x∗ điểm dừng Ψ nghĩa là: n ∗ = ∇Ψ(x ) = ( i=1 ∂ϕ ∗ ∂ϕ ∗ (x , Fi (x∗ ))ei + (x , Fi (x∗ )∇Fi (x∗ ), ∂a ∂b (2.3) ei kí hiệu véc tơ cột thứ i ma trận In ta viết tắt: ∂ϕ ∗ ∂ϕ ∗ ( , (x i , Fi (x∗ )), ) (x , F (x∗ )), ∂a ∂a ∂ϕ ∗ ∂ϕ ∗ ( , (x i , Fi (x∗ )), ) (x , F (x∗ )) ∂b ∂b Điều kiện dừng (2.3) viết lại : ∂ϕ ∗ ∂ϕ ∗ 0= (x , F (x∗ )) + F (x∗ )T (x , F (x∗ )) (2.4) ∂a ∂b ∗ ∗ T Nhân vế trái (2.4) với ∂ϕ ∂b (x , F (x )) ta n = ( i=1 + ∂ϕ ∗ ∂ϕ (x i , Fi (x∗ )) (x∗ i , Fi (x∗ ))) ∂a ∂b ∂ϕ ∗ ∂ϕ ∗ (x F (x∗ ))T F (x∗ )T (x F (x∗ )) ∂b ∂b 17 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.5) Do F đơn điệu nên F (x∗ ) nửa xác định dương ( xem Ortega Rheinboldt [10] trang 142 ) sử dụng tính chất (iv) Bổ đề 2.2, từ (2.5) ta suy ∂ϕ ∗ ∂ϕ (x i , Fi (x∗)) (x∗ i , Fi (x∗)) = 0, ∀i = n ∂a ∂b Bởi (v) Bổ đề 2.2 ta có ϕ(x∗ i , Fi (x∗)) = 0, ∀i = 1, , n suy Ψ(x∗ ) = 0, tức x∗ cực tiểu toàn cục suy định lí chứng minh Từ Bổ đề 2.2 Định lí 2.2 ta nhận kết sau: Hệ 2.1 Cho F ∈ C (Rn ) hàm đơn điệu Nếu toán bù (2.1) giải x∗ nghiệm (2.1) x∗ điểm dừng Ψ 2.3 Tính hội tụ Trước hết chứng minh tập mức toán (2.2) bị chặn F hàm đơn điệu nghiêm ngặt Nhắc lại F : Rn → Rn gọi đơn điệu nghiêm ngặt với modun µ (x − y)T (F (x) − F (y)) ≥ µ x − y , ∀x, y ∈ Rn (2.6) Chúng ta biết với F ∈ C (Rn ), điều kiện (2.6) tương đương với dT F (x) d ≥ µ||d||2 , ∀d ∈ Rn , ∀x ∈ Rn Bổ đề 2.3 Cho (ak , bk )k∈N } ⊆ R2 dãy thỏa mãn ak , bk → +∞ Khi ϕ(ak , bk ) → ∞, k ∈ N Chứng minh Điều suy từ Bổ đề 2.8 [5] Định lí 2.3 Giả sử F liên tục đơn điệu nghiêm ngặt Lấy x0 ∈ Rn véc tơ đặt L(x0 ) = {x ∈ Rn ψ(x) ≤ ψ(x0 ) tập mức tương ứng L(x0 ) tập compact Chứng minh Giả sử tồn dãy xk }k∈N ⊆ L(x0 ) cho limk→∞ xk = ∞ Xác định tập số J = i ∈ I xk i k∈N 18 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn với dãy xki yk không bị chặn Do điều kiện giả sử nên J khác rỗng Giả sử dãy xác định sau: k∈N k∈N i ∈ J , yik = Từ cách xác định dãy y k xki i = J tính đơn điệu nghiêm ngặt F ta có k∈N (xki ) = µ xk − y k µ (xki − yik )(Fi (xk ) − Fi (y k )) ≤ i∈J xki (Fi (xk ) − Fi (y k )) ≤ = i∈J i∈J Fi (xk ) − Fi (y k ) (xki ) (2.7) i∈J (xki )2 = 0, ∀k ∈ K1 , K1 tập vô hạn N Từ (2.7) ta có Do i∈J Fi (x)k − Fi (y)k , k ∈ K1 (xki ) ≤ µ i∈J i∈ Dựa vào tính bị chặn dãy y k Fi (y)k k∈K1 (2.8) k∈K1 tính liên tục Fi (i ∈ J) ta có bị chặn Do (2.8) có Fi0 (xk ) → ∞ với số i0 ∈ J từ định nghĩa J suy xki0 → ∞, (k ∈ K2 ⊆ K1 ) theo Bổ đề 2.3 ta có ϕ(xki0 , Fi0 (xk )) → ∞, (k ∈ K2 ) Tuy nhiên, điều lại mẫu thuẫn với điều hiển nhiên ϕ(xki0 , Fi0 (xk )) ≤ Ψ(xk ) ≤ Ψ(x0 ), ∀k ∈ N, suy định lí chứng minh Ta thấy Định lí 2.3 với hàm ϕ thỏa mãn điều kiện Bổ đề 2.3 Hơn kết độc lập với giả thiết tính khả vi Kết sau khẳng định ma trận Hessian ψ(x) xác định dương nghiệm x∗ giả thiết cho Kết trường hợp đặc biệt trường hợp chung chứng minh [4] 19 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định lí 2.4 Cho x∗ ∈ Rn nghiệm không tầm thường NCP(F) nghĩa x∗i + Fi (x∗ ) > 0, (i ∈ I) Giả sử F khả vi liên tục tới cấp gradients ∇Fi (x∗ )(i ∈ I ∗ = {x ∈ I |x∗i = 0}) ei (i ∈ I ∗ ) độc lập tuyến tính Khi ma trận Hessian ∇2 ψ(x∗ ) tồn xác định dương 2.4 Phương pháp giải 2.4.1 Phương pháp đường dốc ∂ϕ k k k k Cho điểm lặp xk ∈ Rk , kí hiệu ∂ϕ ∂a (x , F (x )) ∂b (x , F (x )) véc tơ không gian n chiều mà thành phần ma trận thứ i ∂ϕ k ∂ϕ k k k ∂a (xi , Fi (x )) ∂b (xi , Fi (x )) Đặt dk = − ∂ϕ k (x , F (xk )) ∂b (2.9) hướng tìm kiếm Bổ đề sau khẳng định dk hướng tìm kiếm Ψ xk giả thiết đơn điệu Bổ đề 2.4 Giả sử xk ∈ Rn F ∈ C (Rn ) hàm đơn điệu hướng tìm kiếm dk xác định theo (2.9) thỏa mãn điều kiện giảm (điều kiện T độ dốc ) ∇Ψ(xk ) dk < miễn xk nghiệm NCP(F) T F tăng thực với modun η > ∇Ψ(xk ) dk ≤ −η dk Chứng minh Sử dụng biểu diễn (2.3), (2.4) Gradientd ∇Ψ(xk ) định nghĩa dk (2.9) ta nhận k T k ∇Ψ(x ) d n = − i=1 ∂ϕ ∂ϕ k (xi , Fi (xk )) (xki , Fi (xk )) ∂a ∂b T T = −(dk ) F (xk ) dk (2.10) Theo giả thiết ma trận Jacobi F (xk ) nửa xác định dương Từ (2.10) Bổ đề 2.1 (ý iv) ta nhận T ∇Ψ(xk ) dk ≤ T k k ∂ϕ k k Giả sử ∇Ψ(xk ) dk = Khi ∂ϕ ∂a (x , Fi (x )) ∂b (x , Fi (x )) = 0, ∀i ∈ I theo Bổ đề 2.1 (ý (v)) ta có ϕ(xki , Fi (xk )) = 0, ∀i ∈ I nghĩa xk ∈ Rn 20 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nghiệm NCP(F) điều mâu thuẫn với giả thiết Bổ đề 2.4 Nếu F đơn điệu nghiêm ngặt với modun µ > từ (2.14), Bổ đề 2.4 (ý (iv)) ta thu T T ∇Ψ(xk ) dk ≤ −(dk )F (xk ) dk ≤ −µ dk Bổ đề 2.4 cở sở thuật toán sau: 2.4.2 Thuật toán (S.0) Lấy F hàm tăng nghiêm ngặt xác định Ψ : Rn → R Giả sử x0 ∈ Rn , ε > 0, δ ∈ (0, 1) β ∈ (0, 1) Đặt k = (S.1) Nếu Ψ(xk ) < ε dừng: xk nghiệm xấp xỉ NCP(F) k k (S.2) Đặt dk := − ∂ϕ ∂b (x , F (x )) (S.3) Tính độ dài bước tk = β mk với mk số nguyên dương nhỏ thỏa mãn điều kiện Armijo Ψ(xk + β m dk ) ≤ Ψ(xk ) − β m δ dk (S.4) Đặt xk+1 := xk + tk dk ; k := k + quay lại bước (S.1) Định lí hội tụ tồn cục cho thuật tốn Định lí 2.5 Giả sử F ∈ C (Rn ) hàm tăng nghiêm ngặt với modun µ > Nếu x0 ∈ Rn điêm xuất phát đặt L(x0 ) tập mức x0 Giả sử F thỏa mãn điều kiện Lipschitz L(x0 ) Nếu δ < µ dãy xk k∈N tạo thuật toán xác định hội tụ tới nghiệm x0 NCP(F) Chứng minh Điều kiện Lipschitz ∇Ψ L(x0 ) nghĩa ∇Ψ(x) − ∇Ψ(y) ≤ x − y , ∀x, y ∈ L(x0 ) với L > số Sử dụng Bổ đề 2.4 định lý giá trị trung bình nhận T Ψ(xk+1 ) − Ψ(xk ) = ∇Ψ(Φk ) (xk+1 − xk ) T T = t∇Ψ(xk ) dk + t(∇Ψ(Φ) − ∇Ψ(xk )) dk ≤ −tµ dk + tL Φk − xk dk = (−tµ + t2 L) dk , 21 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn với xk+1 = xk + tdk , ≤ t ≤ Φk = xk + vk (xk+1 − xk ), vk ∈ (0; 1) bất đẳng thức Ψ(xk + tdk ) ≤ Ψ(xk ) − δt dk với t mà ≤ t ≤ {1, (µ − δ)/L} suy độ dài bước tk (S.3) thuật toán bị chặn tk ≥ {β, β(µ − δ)/L} (2.11) Đặc biệt với tk > thỏa mãn điều kiện Armijo bước (S.3) ln tìm nghĩa thuật tốn xác định tốt dãy Ψ(xk ) k∈N đơn điệu tăng không âm điều suy từ Ψ(xk+1 ) ≤ Ψ(xk ) − tk δ dk (2.11) suy lim dk k→∞ = Điều dẫn đến ∂ϕ k (x , F (xk )) = ∂b Do từ Bổ đề 2.1 (ý v) ta có điểm tụ dãy xk k∈N nghiệm tốn NCP(F) L(x0 ) Compact nên xk k∈N ln có điểm tụ x∗ Dựa theo điều kiện tụ nghiêm ngặt F , tốn NCP(F) có nghiệm, dãy xk k∈N phải hội tụ tới x∗ lim 2.4.3 Phép xấp xỉ Mangasarian Solodov Chúng ta phải nhắc lại phương pháp đề xuất gần Mangasarian Solodov [8] phân tích sâu Yamashita Fukushima [11] nhiên ý phương pháp khác với phương pháp [8] [11] Mangasarian Solodov giới thiệu hàm (max2 {0, a − αb} − a2 2α + max {0, b − αa} − b2 ) ϕM S (a, b; α) := ab + Và chứng minh kết sau: 22 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.12) Bổ đề 2.5 Với tham số α > ta có : (i) ϕM S (a, b; α) ≥ 0, ∀(a, b)T ∈ R2 (ii) ϕM S (a, b; α) = ⇔ a ≥ 0, b ≥ 0, ab = Trên sở hàm (2.12), xét tốn tối ưu khơng ràng buộc n M (x; α) := x∈Rn ϕM S (xi , F (xi )); α) i=1 Đã xem [8] Dựa vào Bổ đề 2.5 có tương ứng - gữa cực tiểu toàn cục toán nghiệm toán bù NCP(F) Yamashita Fukushima [11] chứng minh điểm dừng M (x; α) nghiệm NCP(F) F khả vi F (x) xác định dương với ∀x ∈ Rn (xem [4]) điều giả sử F mạnh giả sử mà ta dùng Định lý 2.2, đặc biệt Yamashita Fukushima đưa ví dụ chứng tỏ kết họ không trường hợp F đơn điệu ngặt Tuy nhiên Yamashita Fukushima [11] chứng minh kết tương tự Bổ đề 2.4 lần họ cần xác định F (x) để chứng minh ∇M (x; α)T d < d hướng tìm kiếm cho d := −α 2.5 ∂ϕM S (x, F (x); α) ∂b Một số kết thực nghiệm số Trong phần so sánh công thức Mangasarian Solodov [10] toán bù phi tuyến (2.4) cuả tác giả Trước hết ổn định ε = 10−5 , δ = 10−4 , β = 0, véc tơ xuất phát x0 = (0, , 0)T ∈ Rn thuật toán áp dụng với F (x) = M x + q (hàm tuyến tính Affine) M ∈ Rn×n , q ∈Rn , ví dụ1 ta lấy :  −1 · · ·  −1 −1 · · ·    −1  M = , q = (−1, · · · , −1)T     −1 0 −1 Ví dụ thứ với liệu M = diag(1/n, 2/n, , 1), q = (−1, , −1)T 23 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Các kết cho bảng bảng Bảng 1: Số lần lặp cho ví dụ thuật toán 2.4.2 n 16 32 64 128 256 Ψ 35 42 43 43 43 43 M 10 11 12 13 13 14 Bảng Số lần lặp cho ví dụ thuật tốn 2.4.2 n 16 32 64 128 256 Ψ 36 79 165 337 682 1374 M 173 347 696 1395 2791 5584 Thuật toán 2.4.2 áp dụng tốt cho hàm đơn điệu nghiêm ngặt nhiên dựa vào Hệ 2.1 tác giả xét hàm đơn điệu Dưới tác giả mô tả phương pháp giới hạn nhớ BFGS sử dụng g k := ∇Ψ(xk ), sk := xk+1 − xk , y k := g k+1 − g k 2.5.1 Phương pháp BFGS (Giới hạn nhớ ) (S.0) (Dữ liệu đầu) Chọn x0 ∈ Rn , n ∈ N, ε > 0, δ ∈ (0; 1), p ∈ (δ, 1) ma trận đối xứng ,xác định dương H0 ∈ Rn×n , đặt k := (S.1) (Tiêu chuẩn dừng) Nếu Ψ(xk ) < ε dừng: xk nghiệm xấp xỉ (2.1) (S.2) (Tính hướng tìm kiếm) Tính dk := −Hk g k (S.3) (Tính chiều dài bước) Tính tk > thỏa mãn điều kiện Wolfe mạnh T T T Ψ(xk + tk dk ) ≤ Ψ(xk ) + δtk (g k ) dk , ∇Ψ(xk + tk dk ) dk ≤ −ρ(g k ) dk (S.4) (Cập nhật) Đặt xk+1 := xk + tk dk Định nghĩa ρk = T T (y k ) sk Vk := In − ρk y k (sk ) Đặt m ˆ := {k, m − 1} Cập nhật H0 , m ˆ + lần sử dụng cặp j j k (s , y ) j=k−mˆ nghĩa là: T Hk+1 = (VkT Vk− ˆ Vk ) m ˆ )H0 (Vk−m T + ρk−mˆ (VkT Vk− )sk−mˆ (sk−mˆ )(Vk−m+1 Vk ) ˆ m+1 ˆ 24 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn T T ˆ ˆ +ρk−m+1 (VkT Vk− )sk−m+1 (sk−m+1 )(Vk−m+2 Vk ) + + ρk sk (sk ) ˆ ˆ m+2 ˆ (S.5) (Quay vòng) Đặt k := k + quay lại bước (S.1) 2.5.2 Nhận xét a) Trong tính tốn chúng tơi, bước (S.0) chọn ε = 10−5 , δ = 10−4 , ρ = 0, H0 = I b) Chiều dài bước tk > thỏa mãn điều kiện Wolfe tính thuật tốn mơ tả [3] Fletcher (0) (0) c) Có thể ma trận H0 bước (S.4) ma trận Hk , Hk = γk H0 γk hệ số tham số lấy γk theo Liu Nocedal [6], T γk = (y k ) sk ) y k d) Ma trận Hk khơng có cơng thức rõ ràng thay vào m ˆ + véc tơ (sj , y j ) có hướng tìm kiếm tính cách quay vịng hai lần mơ tả [9] Các kết nhận với thuật tốn 6.1 áp dụng cho tốn tóm tắt bảng 3-6 Tác giả nói số lặp kép cho m = m = nhắc lại m ký hiệu số cặp véc tơ(sj , y j ) có phương pháp giới hạn nhớ (BFGS) Tiêu chuẩn dừng thuật tốn 2.5.1 thay đổi sau: Nếu ∇Ψ(xk ) < ε dừng trình lặp Tham số α hàm Mangasarian Solodov α = 1.1 tác giả nhấn mạnh hàm Mangasarian Solodov không trường hợp α = điều dễ dàng thấy, xem Bổ đề 2.1 (trang[7]) ta có hàm hàm lên tục với α > gần tuyến tính với α ≈ áp dụng phương pháp số với α ≈ Bảng : Số lần lặp cho ví dụ HS 34 25 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn m=5 m=5 m=7 m=7 véc tơ xuất phát Ψ M Ψ M (1,1,1,1,1,1,1,1) 114* 101 112 99 (2,2,2,2,2,2,2,2) 107 106 105 94 (1,1,1,0,0,0,0,0) 101 100 102 99 (-1,-1,-1,1,1,1,1,1) 110 98 104 89 (1,1,1,-10,-10,-10,-10,-10) 114 112 113 95 Bảng : Số lần lặp cho ví dụ HS 35 m=5 m=5 m=7 m=7 véc tơ xuất phát Ψ M Ψ M (0.5,0.5,0.5,1) 30 30 27 29 (10,10,10,10) 43 9* 34 9* (100,100,100,100) 44 10* 42 10* (100,10,1,0) 43 14* 40 14* (-1,-10,-100,-1000) 53 17* 48 19 Bảng 5: Số lần lặp cho ví dụ HS 66 m=5 m=5 m=7 m=7 véc tơ xuất phát Ψ M Ψ M (0,1.05,2.9,0,0,0,0,0) 39 35 29 32 (0,0,0,1,1,1,1,1) 64 44 45 29 (-1,-1,-1,1,1,1,1,1) 43 45 46 32 (1,1,1,-1,-1,-1,-1,-1) 61 62 45 41 (-1,-1,-1,0,1,2,3,4) 62 41 52 37 Bảng : Số lần lặp cho ví dụ HS 76 m=5 m=5 m=7 m=7 véc tơ xuất phát Ψ M Ψ M (0.5,0.5,0.5,0.5,0,0,0) 47 42 33 33 (0,0,0,0,0,0,0) 48 33 36 32 (10,10,10,10,10,10,10) 102 27* 73 36 (0,1,0,1,0,1,0) 41 40 34 31 (1,2,3,4,3,2,1) 50 42 39 30 Các kết bảng đến bảng điều sau: Nếu hai phương pháp hội tụ tới nghiệm tốn phương pháp Mangasarian Solodov yếu phương pháp tác giả Tuy nhiên nhiều ví dụ phương pháp hội tụ đến điểm dừng mà điểm dừng nghiệm toán bù tương ứng Trái lại phương pháp tác giả đưa đảm bảo lí thuyết Hệ 2.1 26 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.5.3 Nhận xét cuối Trong luận văn tác giả thiết lập lại công thức cho toán bù phi tuyến tốn tối ưu khơng ràng buộc Điều thể cơng thức tương đương với tốn bù cho hàm đơn điệu F nhiều toán bù đơn điệu thường khơng có Jacobi xác định dương nên tác giả thấy phương pháp xấp xỉ thác triển quan (sự mở rộng quan trọng ) phương pháp Mangasarian Solodov Tuy nhiên báo gần đây, Yamashita Fukushima [12] mở rộng phương pháp xấp xỉ Mangasarian Solodov sang toán tổng quát Tác giả tin mở rộng đơn giản cho phương pháp Tuy nhiên cần nói lại ta chứng minh kết tương tự [12] giả thiết yếu 27 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Kết luận Trong luận văn này, tơi hồn thành cơng việc đọc hiểu trình bày lại số kiến thức giải tích liên quan đến nghiệm tốn bù đơn điệu phi tuyến Ngồi tơi trình bày lại lý thuyết toán bù đơn điệu phi tuyến, số phương pháp giải toán Do thời gian có hạn nên q trình viết luận văn trình bày luận văn chắn khơng tránh khỏi thiếu sót, mong nhận ý kiến đóng góp thầy bạn đọc để tơi hồn thiện luận văn 28 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Tài liệu tham khảo [1] A Fischer(1992): A special Newton-type optimization method Optimization 24,pp.269-284 [2] A Fischer (1994): A globally and Q-quadratically convergent Newtontype method for positive semidefinite linear complementarity problems Journal of Optimization Theory and Applications to appear [3] R Fletcher (1987): Practicarl Methods of Optimization (seconnd edition) John Wiley and Sons, Chichester [4] C.Kanzow (1993) : Nonlinear complementarity as us uncomstrained optimization Preprint 67, Institute of Applied Mathematics , University of Hamburg ,Ham-burg ,Germany (revised February,1994) [5] C.Kanzow (1993) : Global convergence proerties of some iterative methods for linear complementarity problems Peprint 72 ,Institute of Applied Mathemat-ics, University of Hamgurg ,Humgurg ,Germany (revised Jannuary,1994) [6] D.C.Liu and J Nocedal (1989) : On the limted memory BFGS method for large scale optimization Mathematical Programming (Series A) 45,pp.503-528 [7] Z-Q.Luo,O.L.Mangasarian,J.Ren and M.V.Solodov (1994): New er-ror bounds for the linear complementarity Mathematics of Operations Research , to appear [8] O.L Mangasarian and M.V.Solodov (1993): Nonlinear complementarity as unconstrained and constrained minimzation Mathematical Programming (Se-riesB) 62,pp.277-297 29 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn [9] J.Nocedal (1980): Updating quasi-Newton matrices with limited storage Math-ematics of Computation 35,pp.722-782 [10] J.M.Ortega and W C Rheindoldt (1970): Iterative solution of Nonlinear Equations in Several Variables Academic Press ,New York -San Francisco-London [11] N Yamashita and M.Fukushima(1994): On stationary points of the implicit Lagrangian for nonlinear complementarity problems Journal of Optimization Theory and Applications ,to appear [12] N.Yamashita and M.Fukushima (1993) : Implicit Lagrangian for generalized complementarity Technical Report 93010,Nara Institute of Science and Technology ,Ikoma,Nara 630-01, Japan 30 Số hóa Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... tơn giải phương trình phi tuyến, thuật tốn giảm cho 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 luận văn phát biểu toán bù đơn điệu, chứng minh định... lại số kiến thức giải tích liên quan đến nghiệm tốn bù đơn điệu phi tuyến Ngồi tơi trình bày lại lý thuyết toán bù đơn điệu phi tuyến, số phương pháp giải toán Do thời gian có hạn nên q trình viết... giả thiết lập lại cơng thức cho tốn bù phi tuyến tốn tối ưu khơng ràng buộc Điều thể cơng thức tương đương với toán bù cho hàm đơn điệu F nhiều tốn bù đơn điệu thường khơng có Jacobi xác định