zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Thạc sĩ - Tiến sĩ - Cao học

Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cho bài toán quy hoạch toán học tựa khả vi

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

Báo xấu

46
lượt xem 5
download

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

Luận văn Thạc sĩ Toán học "Điều kiện tối ưu cho bài toán quy hoạch toán học tựa khả vi" trình bày các nội dung chính sau: Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi; Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cho bài toán quy hoạch toán học tựa khả vi

VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC ———————o0o——————– ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN QUY HOẠCH TOÁN HỌC TỰA KHẢ VI Phạm Thanh Nghị LUẬN VĂN THẠC SĨ Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 Người hướng dẫn khoa học: PGS. TS. Đỗ Văn Lưu HÀ NỘI - 2013
Mục lục Lời cảm ơn 2 Mở đầu 3 1 Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi 5 1.1 Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Điều kiện chính quy hàm lùi xa . . . . . . . . . . . . . . . . 8 1.3 Điều kiện cần tối ưu . . . . . . . . . . . . . . . . . . . . . . 11 2 Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi 15 2.1 Các khái niệm và kết quả bổ trợ . . . . . . . . . . . . . . . 15 2.2 Định lí tách phi tuyến và các quy tắc tựa nhân tử Lagrange 19 2.3 Trường hợp dimX < ∞ . . . . . . . . . . . . . . . . . . . . 34 Kết luận 38 Tài liệu tham khảo 39 1
Lời cảm ơn Luận văn này được hoàn thành với một phần nỗ lực của bản thân và sự hướng dẫn của PGS. TS. Đỗ Văn Lưu, Viện Toán học. Tôi xin tỏ lòng biết ơn chân thành tới thầy hướng dẫn. Với tinh thần làm việc nghiêm túc, thầy đã tận tình giúp tôi trong suốt quá trình xây dựng đề cương cũng như hoàn thành luận văn. Tôi cũng xin bày tỏ lòng cảm ơn sâu sắc tới các thầy cô giáo của Viện Toán học, những người đã tận tình giảng dạy và khích lệ, động viên tôi vượt qua những khó khăn trong học tập. Tôi xin cảm ơn Ban lãnh đạo Viện toán học, trung tâm đào tạo sau đại học Viện Toán học, sở GD - ĐT Lạng Sơn và trường THPT Văn Lãng đã tạo mọi điều kiện thuận lợi, giúp đỡ tôi trong suốt thời gian tôi học tập. Cuối cùng, tôi xin chân thành cảm ơn gia đình, người thân, bạn bè đã giúp đỡ tôi cả về vật chất và tinh thần để tôi có thể hoàn thành bản luận văn cũng như khóa học của mình. 2
Mở đầu Lớp các bài toán tối ưu tựa khả vi là một bộ phận quan trọng của lớp các bài toán tối ưu không trơn. Lý thuyết tựa vi phân của Demyanov- Rubinov là công cụ hữu hiệu để nghiên cứu lớp các bài toán này (xem [3]-[5]). Hàm f : X → R (X-không gian Banach thực) được gọi là tựa khả vi ¯ ∈ X nếu tồn tại các tập lồi compact yếu* ∂f (¯ tại x ¯ (¯ x) và ∂f x) sao cho f 0 (¯ x; y) = max hv, yi + min hw, yi . v∈∂f (¯ x) ¯ (¯ w∈∂f x) Cặp [∂f (¯ ¯ (¯ x) , ∂f x)] được gọi là tựa vi phân của f tại x¯. Bởi vì tựa vi phân của một hàm tựa khả vi là không duy nhất, cho nên việc nghiên cứu các điều kiện tối ưu không phụ thuộc cách chọn tựa vi phân được nhiều tác giả quan tâm nghiên cứu. V.F. Demyanov và A.M. Rubinov [3] đã đưa ra điều kiện chính quy cặp tựa vi phân ở vị trí tổng quát. D.E. Ward [10] đã đưa ra điều kiện chính quy dưới ngôn ngữ hàm lùi xa của đạo hàm theo phương của hàm ràng buộc. Điều kiện chính quy của Ward kéo theo điều kiện vị trí tổng quát của Demyanov-Rubinov. Bằng phương pháp không gian ảnh, A.Uderzo [9] đã thiết lập một định lí tách phi tuyến và từ đó dẫn các điều kiện cần tối ưu cho bài toán tối ưu tựa khả vi. Luận văn trình bầy các điều kiện cần tối ưu cho bài toán quy hoạch 3
Mở đầu toán học tựa khả vi với hữu hạn ràng buộc bất đẳng thức của D.E. Ward [10] với điều kiện chính quy dưới ngôn ngữ hàm lùi xa của đạo hàm theo phương của hàm ràng buộc và các điều kiện cần tối ưu cho bài toán tựa khả vi của A.Uderzo [9] trên cơ sở thiết lập một định lí tách phi tuyến. Luân văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán tựa khả vi. Trình bầy các kết quả của D.E. Ward [10] về điều kiện tối ưu cho bài toán quy hoạch toán học tựa khả vi với hữu hạn ràng buộc bất đẳng thức. Điều kiện chính quy được phát biểu dưới ngôn ngữ hàm lùi xa của đạo hàm theo phương của hàm ràng buộc. Điều kiện này kéo theo điều kiện vị trí tổng quát của Demyanov-Rubinov [3]. Các điều kiện Kuhn-Tucker được trình bầy với điều kiện chính quy đó. Chương 2. Quy tắc nhân tử Lagrange cho bài toán tối ưu tựa khả vi của Uderzo. Trình bầy phương pháp không gian ảnh của A.Uderzo [9] để thiết lập các quy tắc nhân tử Lagrange cho bài toán tối ưu tựa khả vi với hữu hạn ràng buộc bất đẳng thức. Chương này trình bầy định lí tách phi tuyến của Uderzo, và từ đó dẫn các quy tắc nhân tử Lagrange cho bài toán tựa khả vi, trong đó các tựa nhân tử Lagrange (các phiếm hàm dưới tuyến tính, đơn điệu) thay thế cho các nhân tử Lagrange thông thường. Hà Nội, ngày 08 tháng 08 năm 2013 Tác giả Phạm Thanh Nghị 4
Chương 1 Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Chương 1 trình bầy các kết quả của Ward [10] về điều kiện chính quy và điều kiện cần Kuhn-Tucker cho bài toán tựa khả vi với hữu hạn ràng buộc bất đẳng thức. Điều kiện chính quy của Ward được phát biểu dưới ngôn ngữ hàm lùi xa của đạo hàm theo phương của hàm ràng buộc và mạnh hơn điều kiện vị trí tổng quát của Demyanov-Rubinov [3]. 1.1 Các khái niệm Định nghĩa 1.1.1 Hàm số f : Rn → R được gọi là hàm khả vi theo phương tại x ∈ Rn nếu đạo hàm theo phương f (x + ty) − f (x) f 0 (x; y) = lim+ t→0 t tồn tại và hữu hạn với mọi y ∈ Rn . Nếu tồn tại các tập compact lồi khác ¯ (x) sao cho rỗng ∂f (x) và ∂f f 0 (x; y) = max hv, yi + min hw, yi v∈∂f (x) ¯ (x) w∈∂f 5
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi ¯ (x)] được gọi ∀y ∈ Rn , thì f được gọi là tựa khả vi tại x và cặp [∂f (x), ∂f là tựa vi phân của f tại x. ¯ (x) trong Định nghĩa 1.1.1 Việc sử dụng kí hiệu dưới gradient ∂f (x) và ∂f là do sự kiện tập dưới gradient ∂p(0) := {v ∈ Rn | hv, yi ≤ p(y)} của hàm tựa p(y) := max hv; yi bằng ∂f (x) (xem [3]).Tương tự, với hàm v∈∂f (x) ¯ (x). q(y) := max hw, yi, ta có ∂q(0) = −∂f ¯ (x) w∈∂f ¯ (x)] là một tựa vi phân của f tại x và Chú ý rằng nếu [∂f (x), ∂f ¯ (x) − C] cũng là C ⊂ Rn , C 6= φ, C compact, lồi thì cặp [∂f (x) + C, ∂f một tựa vi phân của f tại x. Như vậy, một hàm tựa khả vi có nhiều tựa vi phân. Khi đó, một câu hỏi nẩy sinh trong tối ưu tựa khả vi là: Với điều kiện nào thì điều kiện tối ưu không phụ thuộc vào cách lựa chọn các tựa vi phân? Câu trả lời đã được Demyanov và Rubinov cho trong [3]. Trước hết ta sử dụng lại khái niệm cặp tập lồi compact ở vi trí tổng quát. Định nghĩa 1.1.2 a) Giả sử V ⊂ Rn là tập lồi compact khác rỗng. Mặt max của V được sinh ra bởi x là tập hợp sau đây Gx (V ) := v ∈ V | hv; xi = max hw, xi . w∈V b) Giả sử V , W là các tập lồi compact khác rỗng của Rn . Cặp [V, W ] được gọi là ở vị trí tổng quát( in a general position ) nếu không tồn tại x ∈ Rn sao cho Gx (W) ⊂ Gx (V ). 6
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Nhận xét 1.1.3 a) Nếu V và W là rời nhau thì cặp [V, W ] ở vị trí tổng quát. Mặt khác, nếu W ⊂ V thì [V, W ] không ở vị trí tông quát, bởi vì G0 (W) = W ⊂ V = G0 (V ). b) Demyanov-Rubinov [3] chỉ ra rằng nếu f là tựa khả vi tại x, thì tính ¯ (x)] ở vị trí tổng quát không phụ thuộc vào cách chất cặp [∂f (x), −∂f chọn tựa vi phân. Mệnh đề 15.3 [3] chứng minh rằng nếu g : Rn → R là tựa khả vi tại ¯ x ∈ g −1 (0) và [∂g(x), −∂g(x)] ở vị trí tổng quát, thì {y|g 0 (x; y) ≤ 0} = cl {y|g 0 (x; y) < 0} (ở đây ”cl” kí hiệu bao đóng của một tập). Sự kiện này sẽ được sử dụng để dẫn các điều kiện tối ưu cho bài toán quy hoạch toán học có ràng buộc bất đẳng thức min {f (x)|g(x) ≤ 0} . (1.1) Định lí 1.1.4 [3] Giả sử f, g : Rn → R là tựa khả vi tại x và x là một điểm cực tiểu của ¯ bài toán (1.1). Giả sử g(x) = 0 và [∂g(x), −∂g(x)] ở vị trí tổng quát. Khi đó, với bất kì cách chọn các tựa vi phân của f, g , ta có \ ¯ (x) ⊂ −∂f [∂f (x) + clcone(∂g(x) + w)] , (1.2) ¯ w∈∂g(x) trong đó cone (∂g(x) + w) := {λ(v + w)|λ ≥ 0, v ∈ ∂g(x)} . 7
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi 1.2 Điều kiện chính quy hàm lùi xa Giả sử g : Rn → R là khả vi theo phương tại x ∈ Rn . Điều kiện chính quy bao gồm hàm lùi xa ( recession funtion ) của g 0 được xác định bởi công thức: ∞ (g 0 ) (x; y) := sup {g 0 (x; d + y) − g 0 (x; d)} . d∈Rn Các hàm lùi xa của các đạo hàm theo phương khác nhau đã được nghiên cứu trong [7]. Chúng ta trình bày một số tính chất cơ bản của hàm lùi xa. Mệnh đề 1.2.1 [7] Giả sử g khả vi theo phương tại x. Khi đó, (a) (g 0 )∞ (x; .) là hàm dưới tuyến tính; (b) g 0 (x; .) ≤ (g 0 )∞ (x; .) ; (c) Nếu g 0 (x; .) là lồi, thì g 0 (x; .) = (g 0 )∞ (x; .) . Nhận xét 1.2.2 Ta có (xem [10]) ∞ g(x + td + ty) − g(x + td) (g 0 ) (x; y) = sup limsup . (1.3) d∈Rn t→0+ t Vế phải của (1.3) là đạo hàm theo phương của Michel-Penot. Nếu g là tựa khả vi tại x, thì điều kiện ∞ y| (g 0 ) (x; y) < 0 6= φ (1.4) kéo theo giả thiết vị trí tổng quát của Định lí 1.1.4. 8
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Định lí 1.2.3 Giả sử g : Rn → R là tựa khả vi tại x, và giả sử (1.4) đúng. Khi đó, cặp ¯ [∂g(x), −∂g(x)] ở vị trí tổng quát. ¯ Chứng minh. Ta giả sử rằng cặp [∂g(x), −∂g(x)] không ở vị trí tổng quát và ta sẽ chỉ ra một mâu thuẫn. Đặt h(.) := g 0 (x; .). Khi đó, h(.) = p(.) − q(.), trong đó p(y) := max hv, yi và q(y) := max hv, yi. Bởi v∈∂g(x) ¯ v∈−∂g(x) vì p và q nhận giá trị hữu hạn và dưới tuyến tính, h là khả vi theo phương trên Rn với ∀z, y ∈ Rn , ta có h0 (z; y) = p0 (z; y) − q 0 (z; y) = max hv, yi − max hv, yi , v∈Gz (∂g(x)) ¯ v∈Gz (−∂g(x)) ( do Định lí 2.3.4 [8] ). ¯ Bởi vì [∂g(x), −∂g(x)] không ở vị tri tổng quát, cho nên ∃w ∈ Rn sao cho ¯ Gw (−∂g(x)) ⊂ Gw (∂g(x)). Với w này, h0 (w, y) ≥ 0,∀y ∈ Rn . y k = 1 và (g 0 )∞ (x; yˆ) = α < 0 khi đó Bây giờ ta giả sử yˆ ∈ Rn mà kˆ ∀t > 0, y ) − h(d) 1 0 ∞ h(d + tˆ ∞ sup y ) = (g 0 ) (x; yˆ) = α. = (g ) (x; tˆ d∈Rn t t Do đó h0 (d; yˆ) ≤ α < 0, ∀d ∈ Rn . Nói riêng, h0 (w, y ˆ) < 0 và ta có mâu thuẫn. Ví dụ 1.2.4 Phần ngược của Định lí 1.2.3 không đúng. Chẳng hạn hàm g : R → R được xác định theo công thức g(x) = − |x|. Tại x = 0, cặp [{0} , [−1, 1]] là ở vị trí tổng quát. Tuy nhiên, (g 0 )∞ (0; y) = |y|, cho nên (1.4) không đúng tại x = 0. Khái niệm sau đây là rất hữu ích cho việc dẫn điều kiện tối ưu cho bài toán quy hoạch toán học tựa khả vi. 9
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Định nghĩa 1.2.5 Giả sử g : Rn → R có đạo hàm theo phương tại x. Hàm dưới tuyến tính h : Rn → R được gọi là xấp xỉ lồi trên ( upper convex approximate ) của g tại x, nếu g0 (x;.) ≤ h(.). Ta kí hiệu lớp các xấp xỉ lồi trên của g tai x là U CA(g, x). Bổ đề kĩ thuật sau đây sẽ đóng một vai trò cốt lõi trong chứng minh các điều kiện tối ưu, trong chứng minh ta sẽ sử dụng kí hiệu epif để chỉ trên đồ thị của hàm f và coC để chỉ bao lồi của tập C. Bổ đề 1.2.6 Cho g có đạo hàm theo phương tại x. Nếu p ∈ U CA(g, x) thì tồn tại h ∈ U CA(g, x) sao cho ∞ h(.) ≤ min p(.), (g 0 ) (x; .) . Chứng minh. Cho p ∈ U CA(g, x). Ta lấy h là bao lồi của p và q (.) := (g 0 )∞ (x; .), tức là hàm mà trên đồ thị của nó là co [epi p ∪ epi q]. Rõ ràng h thoả mãn định lí (1.2.3). Bởi vì epi p và epi q là các nón lồi chứa 0, cho nên epi h = epi p + epi q ( [8], Định lí 3.8 ) và vì vậy, h là dưới tuyến tính. Bởi vì epi q là nón lùi xa của epi g 0 (x; .), ta có epi h = epip + epiq ⊂ epig 0 (x; .) + epiq ⊂ epi g 0 (x; .). Do đó h(.) ≥ g 0 (x; .) và ta suy ra h ∈ U CA(g, x) 10
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi 1.3 Điều kiện cần tối ưu Xét bài toán quy hoạch toán học có ràng buộc bất đẳng thức min {f (x)|gi (x) ≤ 0, i ∈ J} (1.5) trong đó f, gi : Rn → R và J là tập chỉ số hữu hạn. Với x ∈ Rn , ta định nghiã I(x) := {i ∈ J|gi (x) = 0} . Trong phần này thiết lập được điều kiện cần tối ưu Kuhn-Tucker cho (1.5) với giả thiết f, gi là tựa khả vi và \ {y|(gi0 )∞ (x0 ; y) < 0} = 6 φ (1.6) I(x0 ) tại một điểm cực tiểu địa phương x0 . Để chứng minh ta dùng Bổ đề 1.2.6 và lí luận tách thông thường. Định lí 1.3.1 Giả sử f và gi , i ∈ J là tựa khả vi tại x0 , x0 là một điểm cực tiểu địa phương của bài toán (1.5). Giả sử gi là liên tục tại x0 với mỗi i ∈ J\I(x0 ) và (1.6) đúng. Khi đó, với bấy kì cách chọn tựa vi phân của f và gi , i ∈ J(x0 ), ta có   \ X ¯ (x0 ) ⊂ −∂f ∂f (x0 ) + cone (∂gi (x0 ) + wi ). (1.7) ¯ i (x0 ) wi ∈∂g I(x0 ) i∈I(x0 ) ¯ (x0 ), wi ∈ ∂g Chứng minh. Giả sử w ∈ ∂f ¯ i (x0 ), i ∈ I(x0 ). Ta định nghĩa p(y) = max hv, yi , pi (y) = max hv, yi . v∈∂f (x0 ) v∈∂gi (x0 ) 11
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Khi đó, p + w ∈ U CA(f, x0 ), pi + wi ∈ U CA(gi , x0 ) với mỗi i ∈ I(x0 ). Theo theo Bổ đề 1.2.6 tồn tại hi ∈ U CA(gi , x0 ) sao cho ∀y ∈ Rn , ∞ hi (y) ≤ min pi (y) + hwi , yi , (gi0 ) (x0 ; y) . (1.8) Đặt F (x) := max {f (x) − f (x0 ), max gi (x0 )} Bởi vì f và gi là khả vi theo phương tại x0 , nên F cũng là khả vi theo phương tại x0 . Chú ý rằng x0 là một cực tiểu địa phương của F . Vì vậy ∀y ∈ Rn từ phép tính đạo hàm theo phương, ta có     0 0 0 0 ≤ F (x0 ; y) = max f (x0 ; y) , max gi (x0 ; y)  I(x0 )    (1.9)   ≤ max p(y) + hw, yi , max hi (y) .  I(x0 )  Ta gọi m := |I(x0 )| + 1, và đặt S1 := {z ∈ Rm |z ≤ 0} và S2 := {z ∈ Rm |(p(y) + hw, yi , ...hi (y)...) ≤ z} với y nào đó y ∈ Rn Trong đó ≤ là kí hiệu thứ tự nhỏ hơn theo từng toạ độ trên Rm Do (1.9), suy ra intS1 ∩ S2 = φ. Kết hợp điều này với sự kiện S1 và S2 là nón lồi khác rỗng, cho nên ta có thể tách chúng bằng một siêu phẳng. Vì vậy ∃λi ∈ R, i ∈ I(x0 ) ∪ {0}, với ít nhất một trong các λi 6= 0 hay không đồng thời bằng 0, sao cho ∀z ≤ 0, z ∈ Rm và y ∈ Rm , ta có X X λi zi ≤ 0 ≤ λ0 (p(y) + hw, yi) + λi hi (y). (1.10) i∈I(x0 )∪{0} I(x0 ) 12
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi Từ bất đẳng thức (1.10) suy ra mỗi λi ≥ 0. Nếu λi = 0 thì theo (1.10) và (1,8) ta có X X 0≤ λi hi (.) ≤ λi (gi0 )∞ (x0 ; .) . (1.11) I(x0 ) I(x0 ) Bởi vì (1.6) đúng cho nên (1.11) chỉ đúng nếu mỗi λi = 0. Điều này mâu thuẫn với sự kiện ít nhất một λi > 0. Vì vậy, λ0 > 0. Không mất tính tổng quát ta có thể giả sử λ0 = 1 theo (1.10) X h−w, yi ≤ p(y) + λi hi (y), ∀y ∈ Rn . I(x0 ) Vì vậy, ! P −w ∈ ∂ p(.)+ λi hi (.) (0) I(x0 ) P P = ∂p (0) + λi ∂hi (0) ⊂ ∂p (0) + λi (∂pi (0) + wi ) I(x0 ) I(x0 ) P = ∂f (x0 ) + λi (∂gi (x0 ) + wi ). I(x0 ) Theo Định lí 23.8 [8] và (1.8). Bởi vì w được chọn tuỳ ý, cho nên   X −∂f¯ (x0 ) ⊂ ∂f (x0 ) + cone(∂gi (x0 ) + wi ) . I(x0 ) Và cuối cùng, bởi vì wi là tuỳ ý nên (1.7) đúng. Định lí 1.3.1 chỉ ra rằng điều kiện (1.4) là điều kiện đủ cho phép bỏ được 00 cl00 ở (1.2). Ví dụ sau đây chỉ ra rằng nói chung là không bỏ được. Ví dụ 1.3.2 Xét (1.1) với  1  x + x2 + y 2 /2 − y ;  if y ≥ 0, g (x, y) := 1  x + x2 + y 2 /2 ,  if y < 0 13
Chương 1. Điều kiện chính quy cho bài toán quy hoạch toán học tựa khả vi và f (x, y) := y ¯ (0) = {(0, 0)} Điểm gốc là một cực tiểu. Chọn ∂f (0) = {(0, 1)} , ∂f n o ∂g(0) = V = (v1 , v2 ) | (v1 − 1)2 + v22 ≤ 1 , và ¯ ∂g(0) = W := {(w1 , w2 ) |w1 = 0, −1 ≤ w2 ≤ 0}. Ta có thể kiểm chứng rằng [V, −W ] ở vị trí tổng quát. Vì vậy điều kiện cần (1.2) đúng. Tuy nhiên, (1.4) không thoả mãn, cho nên Định lí 1.3.1 là không áp dụng được. Vì vậy, trong ví dụ này 00 cl00 không thể bỏ được trong (1.2), bởi vì (0, −1) ∈ / coneV . 14
Chương 2 Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi Chương 2 trình bày phương pháp không gian ảnh của Uderzo [9] để thiết lập các quy tắc tựa nhân tử Lagrange cho bài toán tối ưu tựa khả vi với hữu hạn ràng buộc bất đẳng thức. Trong chương này chúng tôi trình bày định lí tách phi tuyến và từ đó dẫn các quy tắc tựa nhân tử Lagrange cho bài toán tựa khả vi, trong đó các tựa nhân tử Lagrange ( phiếm hàm dưới tuyến tính đơn điệu ) thay thế cho các nhân tử Lagrange thông thường. 2.1 Các khái niệm và kết quả bổ trợ Xét bài toán tối ưu có ràng buộc sau đây minf(x) ,Ω= {x ∈ X : G(x) ∈ Rm −} , (P) x∈Ω trong đó (X. ||.| |) là không gian Banach thực Rm m m + := {y = (y1 , y2 , ..., ym ) : yi ≥ 0, ∀i = 1, ..., m} , R− = −R+ f :X→R 15
Chương 2. Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi và G : X → Rm được cho bởi G(x) := (g1 (x), g2 (x), ..., gm (x)). (X ∗ , k.k) kí hiệu không gian đối ngẫu tô pô của không gian Banach thực (X, k.k), 0∗ là điểm không của không gian X ∗ . h., .i kí hiệu cặp đối ngẫu chính tắc của chúng. Kí hiệu coS, int S, cl S, clco S lần lượt là bao lồi, phần trong, bao đóng, bao lồi đóng của S . Nón sinh bởi một tập S được kí hiệu là cone S . Kí hiệu cl∗ co S là bao lồi đóng theo tôpô yếu* của tập S trong không gian tôpô đối ngẫu, S 0 và S ⊥ là nón cực âm và tập trực giao của S . Hơn nữa, cho tập S ⊆ X ∗ hàm tựa của S kí hiệu là σ (.|S), nghĩa là σ (x|S) = supx∗ ∈S hx∗ , xi. Cho một hàm f : X → R và một ánh xạ G : X → Y Kí hiệu f 0 (¯ x, z) và G0 (¯ x, z) là đạo hàm theo phương của các hàm f, G tại x¯ ⊂ X theo phương z . Hàm f và ánh xạ G gọi là khả vi theo phương tại x nếu f, G có đạo hàm theo phương bất kì tại điểm đó. Giả sử f : X → R là hàm liên tục dưới tuyến tính (trên tuyến tính). Tập compact yếu* ∂h = {x∗ ∈ X ∗ : hx∗ , xi ≤ h(x), ∀x ∈ X} ¯ = {x∗ ∈ X ∗ : hx∗ , xi ≥ h(x), ∀x ∈ X} được gọi là dưới vi ( tương ứng ∂h phân ( tương ứng trên vi phân) của h. Định nghĩa 2.1.1 Hàm f : X → R được gọi là tựa khả vi tại x ¯ ∈ X nếu nó khả vi theo ¯ và tồn tại hàm liên tục dưới tuyến tính f x¯ : X → R và hàm phương tại x liên tục trên tuyến tính f¯x¯ : X → R sao cho. x, z) = f x¯ (z) + f¯x¯ (z), ∀z ∈ X. f 0 (¯ 16
Chương 2. Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi Nhận xét 2.1.2 Theo tính đối ngẫu Minkowski-Hormander thì đẳng thức sau đúng f x¯ (z) = max hx∗ , zi , f¯x¯ (z) = min hx∗ , zi , ∀z ∈ X ∗ x ∈∂f x¯ x∗ ∈∂¯f¯x¯ cho nên đạo hàm theo phương của hàm tựa khả vi có thể biểu diễn dưới dạng f 0 (¯ x, z) = max ∗ hx∗1 , zi + min hx∗2 , zi x1 ∈∂f x¯ x∗2 ∈∂¯f¯x¯ ∗ = min σ z|∂f x¯ + hx2 , zi . x∗2 ∈∂¯f¯x¯ Cặp [∂f x¯ , ∂¯f¯x¯ ] có thể biểu diễn đối ngẫu f 0 (¯ x, .) được gọi là tựa vi phân của f tại x ¯. Sau đây những cặp như vậy sẽ được kí hiệu là Df (¯ x) = [∂f (¯ ¯ (¯ x), ∂f x)]. Các phép tính cho tựa vi phân được phát triển trong [3]. Thực ra tựa vi phân của f tại x ¯ biểu diễn bằng các cặp, các tập lồi compact yếu* khác nhau. Với tập lồi compact yếu* tập bất kì C, cặp x) + C, ∂¯f¯(¯ [∂f (¯ x) − C] cũng biểu diễn Df 0 (¯ x). Bài toán (P) được gọi là bài toán tựa khả vi nếu f và G là tựa khả vi. Bổ đề 2.1.3 ¯ ∈ Ω là nghiệm địa phương của bài toán (P) với f và G khả vi Giả sử x theo phương tại x ¯. Khi đó hệ sau đây là không tương thích:   f 0 (¯ x, z) < 0, z∈X (S) 0 m  G(¯ x) + G (¯ x; z) ∈ intR . − Chứng minh. Giả sử ngược lại hệ (S) là tương thích, nghĩa là tồn tại zˆ ∈ X khác không, sao cho   f 0 (¯ x, zˆ) < 0,  G(¯ x) + G0 (¯ x, zˆ) ∈ intRm . − 17
Chương 2. Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi Khi đó, ta có G0 (¯ x, zˆ) ∈ intRm x) = int [Rm − − G(¯ − − G(¯ x)] . Bởi vì −1 Rm m x) − α−1 G(¯ − − G(¯ x ) = R− + α − 1 G(¯ x) −1 ⊆ Rm − − α G(¯ x), ∀α ∈ ]0; 1] , cho nên G0 (¯ x; zˆ) ∈ [intRm − G(¯ x)] ⊆ Rm − − G(¯ x) −1 ⊆ Rm − − α G(¯ x), ∀α ∈ ]0; 1] . Điều này có nghĩa là tồn tại ρ > 0 không phụ thuộc vào tham số α ∈ ]0; 1] sao cho tồn tại hình cầu Bρ (0Y ) tâm 0Y , bán kính ρ sau cho G0 (¯ x; zˆ) + Bρ (0Y ) ⊆ Rm − − G(¯ x) −1 ⊆ Rm − − α G(¯ x), ∀α ∈ ]0; 1] . Vì vậy, do tính chất thuần nhất dương của G0 (¯ x; .), ta có x) + G0 (¯ G(¯ z ) + αBρ (0Y ) ⊆ Rm x; αˆ − , ∀α ∈ ]0; 1] . (2.1) ¯, tồn tại α0 ∈ ]0; 1] sao Do tính chất khả vi theo phương của f và G tại x cho f (¯ x + αˆ x) − f 0 (¯ z ) − f (¯ x; αˆ z) < −f 0 (¯ x, zˆ) , ∀α ∈ ]0; α0 ] , α và kG(¯ z ) − G(¯ x + αˆ x) − G0 (¯ x; αˆ z )k < ρ, ∀α ∈ ]0; α0 ] . α Từ đó ta nhận được f (¯ x + αˆ x), ∀α ∈ ]0; α0 ] , z ) < f (¯ (2.2) 18
Chương 2. Quy tắc tựa nhân tử Lagrange của Uderzo cho bài toán tối ưu tựa khả vi và α−1 [G(¯ x + αˆ x) − G0 (¯ z ) − G(¯ z )] ∈ Bρ (0Y ) , ∀α ∈ ]0; α0 ] . x; αˆ Sử dụng bao hàm thức (2.1) ta có G(¯ z ) ∈ Rm x + αˆ − , ∀α ∈ ]0; α0 ] . (2.3) ¯ ∈ X . Do đó ta nhận được (2.2) và (2.3) mâu thuẫn với tính tối ưu của x điều phải chứng minh. Bổ đề 2.1.4 Giả sử G : X → Rm là ánh xạ khả vi theo phương tại x ¯ ∈ X và p : Rm → R là hàm dưới tuyến tính. Khi đó, p ◦ G : X → R khả vi theo phương tại x ¯ và (p ◦ G)0 (¯ x; z) = p0 (G(¯ x); G0 (¯ x; z)) , ∀z ∈ X. Nếu G(¯ x) = 0 ta có (p ◦ G)0 (¯ x; z) = p (G0 (¯ x; z)) , ∀z ∈ X. 2.2 Định lí tách phi tuyến và các quy tắc tựa nhân tử Lagrange Trong không gian R × Rm ta xét tập: H = intR1+m − và K = {w = (r, y) ∈ R1+m : ∃z ∈ X : z ∈ X : r = f x¯ (z) + f¯x¯ (z) , 19

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng

172 tài liệu

841 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.