Có Thể Chứng Minh Rằng Hàm F(x) Là Lồi Trên C Khi Và Chỉ Khi - 123doc

1. Trang chủ >
2. Thạc sĩ - Cao học >
3. Sư phạm >

Có thể chứng minh rằng hàm f(x) là lồi trên C khi và chỉ khi

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (138.78 KB, 15 trang )

Hơn nữa, nếu f(x) + với P là ma trận xác định dơng thìC, C là tập giới nội (bị chặn).Điều ngợc lại nói chung không đúng: Một hàm số có mọi tập hợp mức dớilà lồi thì không nhất thiết là một hàm lồi. Ví dụ: Hàm f(x) =x , x |R, có mọitập hợp mức dới lồi, nhng bản thân hàm đó không lồi trên toàn bộ |R. Vì thế, ngời ta mở rộng khái niệm hàm lồi thành hàm tựa lồi, đó là các hàm f : |R n [,+] sao cho các tập mức dới L = {x |Rn : f(x) } là lồi với mọi |R.Hàm f(x) gọi là tựa lõm nếu f(x) là tựa lồi. Tất nhiên hàm lồi (lõm) cũng là tựalồi (tựa lõm), nhng điều ngợc lại nói chung không đúng.Với x, d |Rn cố định, ta ký hiệu () f(x + d). Khi đó ta cóMệnh đề 1.2. Hàm f(x) là lồi khi và chỉ khi hàm một biến () f(x + d)là lồi theo với mọi x, d |Rn.1.2.2. Hàm lồi khả viNếu f(x) là hàm khả vi liên tục trên một tập hợp C |Rn thì với mỗi x Cta xác định véctơ cột n thành phần: f ( x ) f ( x )f ( x ) f ( x ) = ,, ,x 2x n x1Tvà gọi nó là véctơ građiên của hàm f tại điểm x. Véctơ f(x) vuông góc với đờng đồng mức của hàm f đi qua điểm x. Hớng của véctơ này là hớng tăng nhanhnhất của f tại x nên còn đợc gọi là hớng dốc nhất.Ta gọi đạo hàm theo hớng d |Rn của hàm f tại điểm x |Rn là giá trị sốf ( x + d ) f ( x ) f(x, d) = lim+0nếu giới hạn này tồn tại (hữu hạn hay vô hạn). Có thể thấy rằng nếu hàm f khả viliên tục thìf(x, d) = và '() = với mọi x, d |Rn.Hơn nữa, nếu f hai lần khả vi liên tục thì "() = , trong đó10 2f (x )P(x) =x i x jn ìnlà ma trận vuông đối xứng cấp n, gọi là ma trận Hessian của f tại x.Để nhận biết hàm lồi, ngời ta còn sử dụng các tiêu chuẩn sau:Mệnh đề 1.3. Các điều sau đây là tơng đơng:f(x) là hàm lồi trên toàn |Rn.Hàm số '() không giảm theo .f(y) f(x) với mọi x, y |Rn.Ma trận các đạo hàm riêng cấp hai 2f(x) nửa xác định dơng với mọi x,nghĩa là 0 x, d |Rn.Định nghĩa 1.5. Giả sử hàm lồi f(x) xác định tại điểm x 0 và có giá trị hữuhạn. Véctơ g đợc gọi là dới građiên của f tại x0 nếu có bất đẳng thứcf(x) f(x0) với mọi x |Rn.Có thể chứng minh rằng nếu f(x) liên tục tại x0 thì tại đó có tồn tại véctơ dớigrađiên và tập các véctơ dới građiên tại x0 là một tập hợp lồi, đóng và bị chặn.Nếu f(x) khả vi tại x0 thì f(x0) là dới građiên duy nhất của f tại x0. Vì thế, kháiniệm dới građiên là mở rộng của khái niệm đạo hàm (građiên).Với hàm lồi chặt ta cũng có các tính chất tơng tự nh trong Mệnh đề 1.3.Mệnh đề 1.4. Các điều sau đây là tơng đơng:a) f(x) là hàm lồi chặt.b) f(y) f(x) > , x, y |Rn, x y.c) là hàm tăng chặt theo .Hệ quả 1.1. Hàm toàn phơng f(x) + ẵ là lồi khi vàchỉ khi ma trận C nửa xác định dơng. (Do 2f(x) C x).1.2.3. Hàm lồi mạnh và tính chất11Định nghĩa 1.6. Hàm f(x) xác định trên tập lồi C |Rn đợc gọi là lồimạnh, nếu tồn tại hằng số > 0 (hằng số lồi mạnh) sao cho với mọi x, y C vàmọi [0, 1] ta có bất đẳng thức:f[x + (1 )y] f(x) + (1 )f(y) (1 ) x y 2.(1.1)Có thể chứng minh rằng hàm f(x) lồi mạnh khi và chỉ khi hàm f(x) .||x||2là lồi. Rõ ràng hàm lồi mạnh thì lồi chặt, nhng điều ngợc lại không chắc đúng.Các hàm lồi mạnh có vai trò đặc biệt quan trọng trong nghiên cứu các bàitoán tối u. Sau đây sẽ xét các hàm lồi mạnh hai lần khả vi liên tục.Mệnh đề 1.5. Nếu f(x) là hàm hai lần khả vi liên tục thì điều kiện lồi mạnh(1.1) tơng đơng với điều kiện m||d||2, m > 0 với mọi x, d |Rn.(1.2)Hệ quả 1.2. Hàm toàn phơng xác định dơng f(x) = + ẵ làhàm lồi mạnh trên toàn |Rn. Ngợc lại, mọi hàm bậc hai lồi mạnh xác định trêntoàn |Rn là dạng toàn phơng xác định dơng.Tập C |Rn đợc gọi là lồi chặt nếu x, y C, x y, mọi điểmx + (1 )y với 0 < < 1,đều là điểm trong của C.Tập C |Rn gọi là lồi mạnh nếu tồn tại hằng số > 0 sao chox, y C và ||z|| ||x y||2 ẵ (x + y) + z C.Có thể thấy tập lồi mạnh thì lồi chặt, nhng ngợc lại không chắc đúng. Vídụ: tập C = {(x, y) |R2 : y ex} là tập lồi chặt nhng không lồi mạnh.Cho trớc điểm tuỳ ý x0 |Rn. Xét tập mức dới C = {x |Rn: f(x) f(x0)}.Mệnh đề 1.6. Nếu f(x) là một hàm lồi mạnh hai lần khả vi liên tục thì C làmột tập hợp lồi mạnh, đóng và bị chặn.Mệnh đề 1.7. Nếu ma trận 2f(x) thoả mãn điều kiện (1.2) thì tồn tại matrận nghịch đảo [2f(x)]1 và 121||d||2.mHơn nữa, nếu ma trận 2f(x) bị chặn, nghĩa là M.||d||2.thì m||d||2.M21.2.4. Cực trị của hàm lồiCho hàm số thực f(x) xác định trên một tập khác rỗng C |Rn. Ta nói x0 C là điểm cực tiểu địa phơng của f trên C nếu tồn tại số > 0 sao cho f(x0) f(x) với mọi x C thoả mãn ||x x0|| < . Ta nói x0 C là điểm cực tiểu toàncục của f trên C nếu f(x0) f(x) với mọi x C.Các khái niệm cực đại địa phơng, cực đại toàn cục đợc định nghĩa tơngtự. Mệnh đề sau đây nêu một tính chất rất đáng chú ý của hàm lồi:Mệnh đề 1.8. Cho f(x) là một hàm lồi xác định trên tập lồi C. Nếu x0 Clà một điểm cực tiểu địa phơng của f trên C thì x0 cũng là điểm cực tiểu toàn cụccủa f trên C.Hơn nữa: x0 C là điểm cực tiểu của f trên C khi và chỉ khi 0 với mọi x C. Hàm lồi chặt có nhiều nhất một điểm cực tiểu.Mệnh đề 1.9. Cho f(x) là một hàm khả vi liên tục trên một tập mở chứa C.Nêú C là tập lồi đóng, khác rỗng và f lồi mạnh trên C (nói riêng, f là dạng toànphơng xác định dơng) thì f có duy nhất một cực tiểu trên C.1.3. Chỉ số điều kiện của ma trậnXét hệ tuyến tính Ax = b, với A là ma trận vuông cấp n không suy biến và blà véctơ trong |Rn, b 0. Hệ đợc gọi là đặt không chỉnh nếu những nhiễu nhỏtrong hệ gây nên những thay đổi tơng đối lớn trong lời giải đúng của hệ. Ngợclại, hệ đợc gọi là đặt chỉnh.Ví dụ 1.1. Xét hệ phơng trình tuyến tính sau đây:0,835x + 0,667y = 0,168 b1,130,333x + 0,266y = 0,067 b2.Nghiệm đúng của hệ là x* = 1 và y* = - 1. Nếu thay b 2 = 0,067 bằng 0,066thì lời giải trở thành x* = - 666 và y* = 834!!!Tình huống này có thể xẩy ra, chẳng hạn khi các số b 1 và b2 là các kết quảcủa một thí nghiệm và đợc đọc từ mặt số đồng hồ của một dụng cụ đo. Giả sửđồng hồ đợc đọc với sai số cho phép là 0,001.Bây giờ vấn đề là làm thế nào đo đợc mức không chỉnh này. Muốn thế, taký hiệu x* là lời giải của hệ tuyến tính Ax = b và ta thay b thành b + b. Khi đó,lời giải mới có thể viết thành x* + x. Ta có A(x* + x) = b + b = Ax* + bsao cho Ax = b và x = A-1b. Vì thế||x|| ||A-1||.||b||.(1.3)Do Ax* = b nên ta có ||b|| = ||Ax*|| ||A||.||x*||, từ đó1/ ||x*|| ||A||/ ||b||.(1.4)Khi đó, từ (1.3) và (1.4) ta rút ra||x||/ ||x*|| ||A||.||A-1||.||b||/ ||b||.Tơng tự, nếu ta thay A bởi A và nếu x là lời giải mới thì||x||/ ||x|| ||A||.||A-1||.||A||/ ||A||.Trong cả hai trờng hợp ta thấy sự thay đổi tơng đối của x bị chặn bởi thayđổi tơng đối của dữ liệu, nhân với ||A||.||A -1||. Tích ||A||.||A-1|| càng lớn thì sự thayđổi tơng đối càng rộng.Định nghĩa 1.7. Cho A là một ma trận vuông cấp n không suy biến. Giá trịcủa tích ||A||.||A-1|| đợc gọi là chỉ số điều kiện của A và ký hiệu là cond(A).Để ý rằng chỉ số điều kiện của A luôn luôn lớn hơn hay bằng 1. Thật vậy,1 = ||AA-1|| ||A||.||A-1|| = cond(A).Với hệ tuyến tính cho ở ví dụ 1.1 chỉ số điều kiện của A là||A||.||A-1|| = 1,502 ì 1.168.000 1,7 ì 106.Mệnh đề 1.10. Cho A là ma trận đối xứng (cấp n) xác định dơng. Khi đó,14cond(A) = 1(A)/ n(A),trong đó 1(A) và n(A) lần lợt là giá trị riêng lớn nhất và nhỏ nhất của A.1.4. Bài toán tối u phi tuyến:Xét bài toán tối u phi tuyến(P)min {f(x) : hi(x) = 0, i = 1, , m; gj(x) 0, j = 1, , p},trong đó f, hi, i = 1, , m, và gj, j = 1, , p, là các hàm hai lần khả vi liên tục(thuộc lớp C2). Ký hiệu h(x) = (h1(x), , hm(x))T |Rm và g(x) = (g1(x), ,gp(x))T |Rp. Điểm x thoả mãn h(x) = 0 và g(x) 0 gọi là một điểm (lời giải)chấp nhận hay một phơng án của bài toán (P). Tập các phơng ánD = {x |Rn : h(x) = 0, g(x) 0}gọi là miền ràng buộc của bài toán. Đó là một tập hợp lồi khi h i (i = 1, , m) làcác hàm afin và gj (j = 1, . , p) là các hàm lồi. Giả thiết D khác rỗng. Một phơng án đạt cực tiểu của hàm f đợc gọi là một phơng án (lời giải) tối u.Khi đó, ta nói mỗi phơng trình hi(x) = 0 là một ràng buộc đẳng thức, mỗibất phơng trình gj(x) 0 là một ràng buộc bất đẳng thức.Hàm Lagrange tơng ứng với bài toán (P) đợc xác định nh sau:L(x, à, ) = f(x) + h(x)Tà + g(x) T.trong đó x |Rn, à |Rm và |Rp, 0.Giả sử x* là một điểm chấp nhận của (P), ta ký hiệuI(x*) = {j : 1 j p, gj(x*) = 0}.Bài toán (P) đợc gọi là chính qui tại điểm x* (hay x* là điểm chính quicủa (P)) nếu hệ {h1(x*), , hm(x*) và gj(x*), j I(x*)} độc lập tuyến tính.Điều kiện cần tối u (Định lý Karush - Kuhn - Tucker). Giả sử x* D là điểm cực tiểu địa phơng của f trên D và x* là điểm chính qui của (P).Khi đó, có những nhân tử à* |Rm và * |Rp thoả mãn:f(x*) + h(x*)Tà* + g(x*)T* = 0,15

Xem Thêm

Tài liệu liên quan

• Luận văn:PHƯƠNG PHÁP HÀM CHẮN VÀ PHƯƠNG PHÁP HÀM PHẠT trong các bài toán tối ưu Chương 1
  • 15
  • 861
  • 2
• day truc tuyen Lacture Maker.ppt
  • 2
  • 174
  • 0
• BIEU THUC CO CHUA 2 CHU
  • 13
  • 489
  • 1

Tải bản đầy đủ (.doc) (15 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(137.5 KB) - Luận văn:PHƯƠNG PHÁP HÀM CHẮN VÀ PHƯƠNG PHÁP HÀM PHẠT trong các bài toán tối ưu Chương 1-15 (trang) Tải bản đầy đủ ngay ×