Tài liệu Phương pháp chiếu giải bài toán tối ưu (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ NGHĨA PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN TỐI ƯU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN – 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ NGHĨA PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN TỐI ƯU Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS. TSKH. LÊ DŨNG MƯU THÁI NGUYÊN – 2015 i Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Phát biểu bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. Một số ví dụ điển hình về bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1. Bài toán thể tích lớn nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2. Bài toán lập kế hoạch sản xuất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3. Bài toán định vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4. Bài toán phân việc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 8 8 1.4. Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1. Tối ưu không ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2. Tối ưu có ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3. Điều kiện tối ưu Kuhn - Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 15 18 20 Chương 2. Phương pháp chiếu giải bài toán tối ưu . . . . . . . . . . 23 2.1. Toán tử chiếu lên tập lồi đóng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Một thuật toán chiếu giải bài toán tối ưu lồi. . . . . . . . . . . . . . . . . . . . 2.2.1. Thuật toán chiếu dưới đạo hàm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Thuật toán hàm phạt điểm trong . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 27 32 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1 Mở đầu Toán học nảy sinh từ thực tiễn và đã được ứng dụng rộng rãi trong thực tế. Lí thuyết tối ưu là một ngành toán học được ứng dụng trong rất nhiều lĩnh vực của khoa học tự nhiên, xã hội, công nghệ, kinh tế... Bài toán tối ưu đóng vai trò quan trọng trong lý thuyết tối ưu, có hai yếu tố quan trọng trong bài toán tối ưu là tập chấp nhận được (tập ràng buộc) và hàm mục tiêu xác định trên tập đó. Để chứng minh sự tồn tại nghiệm và xây dựng phương pháp giải, người ta thường phân loại các bài toán theo cấu trúc của tập chấp nhận được và tính chất hàm mục tiêu. Mục đích của luận văn này là tổng hợp lại kiến thức cơ bản của bài toán tối ưu. Đặc biệt luận văn đi sâu trình bày thuật toán chiếu giải bài toán tối ưu không đòi hỏi tính khả vi của hàm mục tiêu. Luận văn được chia làm 2 chương Chương 1: Bài toán tối ưu Chương này trình bày một số kiến thức cơ bản về giải tích lồi, phát biểu bài toán tối ưu, một số ví dụ điển hình về bài toán tối ưu, sự tồn tại nghiệm và điều kiên tối ưu. Chương 2: Phương pháp chiếu giải bài toán tối ưu. Chương này trình bày chi tiết về toán tử chiếu lên tập lồi đóng và tính chất của toán tử chiếu. Thuật toán chiếu để giải bài toán tối ưu lồi đợc giới thiệu ở đây là thuật toán chiếu dưới đạo hàm. Cuối chương là thuật toán hàm phạt điểm trong là một kỹ thuật cho phép đưa việc giải bài toán tối ưu có ràng buộc về việc giải các bài toán không có ràng buộc qua đó cho phép tránh phải tính hình chiếu vì rất nhiều trường hợp tính hình chiếu rất khó, thậm trí không thực hiện được. Nhân dịp này, tôi xin bày tỏ lòng biết ơn sâu sắc tới GS. TSKH. Lê Dũng Mưu, người thầy đã tận tâm, nhiệt tình hướng dẫn, cung cấp tài liệu, truyền đạt cho tôi kiến thức trong quá trình học tập và luôn giúp đỡ, động viên tôi 2 hoàn thành luận văn. Tôi xin trân trọng cảm ơn ban giám hiệu, phòng Đào Tạo, Khoa Toán Tin trường Đại học Khoa học, Đại học Thái Nguyên cùng các thầy, cô giáo tham gia giảng dạy cao học khóa 2013 - 2015 đã quan tâm và giúp đỡ tôi trong suốt quá trình học tập tại trường. Tôi xin cảm ơn trường THPT Hùng An, Bắc Quang, Hà Giang và gia đình đã tạo điều kiện tốt nhất cho việc học tập của tôi. Cảm ơn bạn bè và đồng nghiệp đã hỗ trợ tôi trong việc hoàn thành luận văn này. Thái Nguyên, tháng 05 năm 2015 Học viên Bùi Thị Nghĩa 3 Chương 1 Bài toán tối ưu Chương này trình bày một số kiến thức cơ bản về giải tích lồi, giới thiệu bài toán tối ưu và một số ví dụ điển hình về bài toán tối ưu. Tiếp đến trình bày sự tồn tại nghiệm tối ưu, điều kiện tối ưu như tối ưu không ràng buộc, tối ưu có ràng buộc và điều kiện tối ưu Kuhn - Tucker. Nội dung của chương được trích dẫn chủ yếu từ tài liệu tham khảo [1]; [2]; [3] và [4]. 1.1. Kiến thức chuẩn bị Để thuận tiện cho người đọc, trong phần này ta xét một số khái niệm và kết quả sẽ được sử dụng trong phần tiếp theo. Cho hai điểm a, b ∈ Rn . Tập tất cả các điểm: x = (1 − λ)a + λb với 0 ≤ λ ≤ 1, gọi là đoạn thẳng nối a và b, được kí hiệu là [a, b]. Định nghĩa 1.1. Tập C ⊂ Rn được gọi là một tập lồi nếu nó chứa đoạn thẳng nối hai điểm bất kì thuộc nó, nói cách khác nếu (1 − λ)a + λb, ∀a, b ∈ C, 0 ≤ λ ≤ 1. Định nghĩa 1.2. Cho f : Rd → R ∪ {+∞} là một hàm lồi. Một véc tơ v được gọi là dưới đạo hàm của hàm f tại x nếu với mọi y ∈ Rd ta có hv, y − xi ≤ f (x) − f (y). Tập các dưới đạo hàm của hàm f được gọi là khả dưới vi phân của hàm f tại x, được kí hiệu bởi ∂f (x). Hàm f được gọi là khả dưới vi phân tại x nếu 4 ∂f (x) 6= 0. Hàm f được gọi là khả dưới vi phân nếu nó khả dưới vi phân tại mọi x ∈ domf , trong đó domf = {x ∈ Rd : f (x) < +∞}. Định lí 1.1. (Moreau - Rockafellar) Cho f1 , f2 , ..., fn : X → R ∪ {∞} là các hàm lồi, trên C = Domfi , i = 1, n thì: ∂f1 (x) + ∂f2 (x) + ... + ∂f1 (x) ⊂ ∂(f1 + f2 + ... + fn )(x), ∀x ∈ X. Giả sử C là họ các tập lồi của X , X chứa các điểm trong và các hàm fi , giả sử x∗ là liên tục trên C thì: ∂(f1 + f2 + ... + fn )(x) = ∂f1 (x) + ∂f2 (x) + ... + ∂f1 (x), ∀x ∈ X. Định nghĩa 1.3. Cho f : Rn −→ R ∪ +∞ ta nói hàm f là lồi trên một tập C nếu ∀x, y ∈ C, ∀λ ∈ [0, 1]: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)(bất đẳng thức Jensen) Định nghĩa 1.4. Hàm f : C → R gọi là hàm nửa liên tục dưới tại điểm x ∈ C nếu với mỗi ε > 0 có một δ > 0 sao cho f (x) − ε ≤ f (x) với mọi x thuộc C, kx − xk ≤ δ . Hàm f gọi là nửa liên tục dưới trên C nếu f nửa liên tục dưới tại mọi điểm x ∈ C . Định nghĩa trên tương đương với limx∈C,x→x f (x) ≥ f (x). Định nghĩa 1.5. Hàm f : C → R gọi là hàm nửa liên tục trên tại điểm x ∈ C nếu với mỗi ε > 0 có một δ > 0 sao cho f (x) ≤ f (x) + ε với mọi x thuộc C, kx − xk ≤ δ . Hàm f gọi là nửa liên tục trên trên C nếu f nửa liên tục trên tại mọi điểm x ∈ C . Định nghĩa trên tương đương với limx∈C,x→x f (x) ≤ f (x). Định nghĩa 1.6. Hàm f gọi là liên tục nếu nó vừa là nửa liên tục dưới vừa là nửa liên tục trên Bổ đề 1.1. Giả sử rằng {ξk } là một dãy các số dương thỏa mãn ξk+1 ≤ ξk + βk ∀k ∈ N, trong đó βk ≥ 0 và P∞ k=0 βk < +∞. Thì dãy {ξk } là chuỗi hội tụ. 5 1.2. Phát biểu bài toán tối ưu Trong không gian véc tơ Rn , cho C ⊆ Rn là một tập khác rỗng và hàm số thực f : C → R tùy ý. Bài toán tối ưu có dạng min{f (x) : x ∈ C}. (P) là bài toán tìm véc tơ (điểm) x∗ ∈ C sao cho f (x∗ ) ≤ f (x) với mọi x ∈ C Hàm f gọi là hàm mục tiêu hay hàm chi phí, tập C gọi là tập ràng buộc hay miền chấp nhận được. Một véc tơ (điểm) x ∈ C gọi là phương án (lời giải hay nghiệm) chấp nhận được. Véc tơ x∗ ∈ C sao cho f (x∗ ) ≤ f (x) với mọi x ∈ C được gọi là một phương án (lời giải hay nghiệm) tối ưu của bài toán và f (x∗ ) gọi là giá trị cực tiểu hay giá trị tối ưu của f trên C , thường được kí hiệu là fmin . Trường hợp C = Rn ta có bài toán tối ưu không ràng buộc: min{f (x) : x ∈ Rn } hay minn f (x). x∈R Trái lại (P ) là bài toán tối ưu có ràng buộc. Thông thường tập C được cho bởi C = {x ∈ Rn : gi (x) ≤ 0, i = 1, ..., m, hj (x) = 0, j = 1, 2, ..., p}, (1.1) với gi , hj : Rn → R là các hàm số cho trước, gọi là các hàm ràng buộc, và bài toán (P ) có thể viết dưới dạng (gọi là bài toán dạng chuẩn): f (x) → min với điều kiện: gi (x) ≤ 0, i = 1, ..., m, (1.2) hj (x) = 0, j = 1, 2, ..., p. (1.3) Các hệ thức gi ≤ 0 gọi là các ràng buộc bất đẳng thức, các hệ thức hi = 0 gọi là các ràng buộc đẳng thức. Ràng buộc bất đẳng thức dạng xj ≥ 0 (−xj ≤ 0) gọi là ràng buộc không âm hay ràng buộc về dấu. Nhận xét 1.1. Ràng buộc về bất đẳng thức có thể biến đổi thành ràng buộc đẳng thức và ngược lại. Thật vậy, các ràng buộc (1.2) có thể được biểu diễn nhờ hệ thức gi (x) + yi = 0, i = 1, ..., m, 6 với yi là các số thực, gọi là các biến bù. Ngược lại mỗi ràng buộc đẳng thức (1.3) tương đương với hai ràng buộc bất đẳng thức: hj (x) ≤ 0, −hj (x) ≤ 0, j = 1, 2, ..., p. Với nhận xét vừa nêu không giảm tính tổng quát đôi khi ta xét bài toán tối ưu chỉ với ràng buộc đẳng thức hoặc chỉ với ràng buộc bất đẳng thức. Nhận xét 1.2. Do min{f (x) : x ∈ C} = −max{−f (x) : x ∈ C} nên bài toán cực tiểu được đưa về bài toán cực đại và ngược lại. Nếu f (x∗ ) ≥ f (x) với mọi x ∈ C thì f (x∗ ) là giá trị cực đại của hàm f trên C và thường được kí hiệu là fmax . 1.3. Một số ví dụ điển hình về bài toán tối ưu Trước hết ta nêu một số ví dụ quen thuộc trong nhiều giáo trình về bài toán tối ưu 1.3.1. Bài toán thể tích lớn nhất Tìm cách dựng một hộp bìa các tông có thể tích lớn nhất với điều kiện diện tích toàn phần của hộp là một số c (cho trước)? Kí hiệu kích thước hộp là x, y, z . Bài toán có thể diễn đạt thành V (x, y, z) = xyz → max với điều kiện 2(xy + yz + zx) = c, x ≥ 0, y ≥ 0, z ≥ 0. 1.3.2. Bài toán lập kế hoạch sản xuất Ví dụ 1.1. Có một loại sản phẩm được chế tạo từ m loại vật liệu khác nhau. Hàm sản xuất f (x1 , x2 , ..., xm ) cho biết số lượng sản phẩm sản xuất được khi sử dụng kết hợp xj đơn vị vật liệu j, j = 1, 2, ..., m. Giá một đơn vị sản phẩm là q và giá trị một đơn vị các loại vật liệu lần lượt là p1 , p2 , ..., pm . Để đạt lợi nhuận tối đa, nhà sản xuất cần giải bài toán tối ưu không ràng buộc: qf (x1 , x2 , ..., xm ) − (p1 x1 + p2 x2 + ... + pm xm ) → max. 7 Ví dụ 1.2. Một cơ sở sản xuất dự định sản xuất hai loại sản phẩm A và B . Các sản phẩm này được chế tạo từ ba loại nguyên liệu I, II, III. Số lượng đơn vị dự trữ của từng loại nguyên liệu và số lượng đơn vị từ loại nguyên liệu cần dùng để sản xuất ra một đơn vị sản phẩm mỗi loại được cho trong bảng dưới đây: Hãy lập kế hoạch sản xuất, tức là tính xem cần sản xuất bao Loại nguyên liệu I II III Nguyên liệu dự trữ 18 30 25 Số lượng đơn vị nguyên liệu cần dùng cho việc sản xuất một đơn vị sản phẩm A B 2 3 5 4 1 6 nhiêu đơn vị sản phẩm mỗi loại để tiền lãi thu được là lớn nhất, biết rằng bán một đơn vị sản phẩm A thu lãi 3 trăm ngàn đồng, bán một đơn vị sản phẩm B thu lãi 2 trăm ngàn đồng. Ta xây dựng mô hình toán học cho bài toán trên: Gọi x và y theo thứ tự là số lượng đơn vị sản phẩm A và B cần sản xuất theo kế hoạch. Khi đó tiền lãi thu được sẽ là: z = 3x + 2y Do nguyên liệu dự trữ có hạn nên x và y phải chịu những ràng buộc nào đó, cụ thể là: 2x + 3y ≤ 18 (ràng buộc về nguyên liệu I); 5x + 4y ≤ 30 (ràng buộc về nguyên liệu II); x + 6y ≤ 25 (ràng buộc về nguyên liệu III). Ngoài ra còn các ràng buộc rất tự nhiên nữa là x ≥ 0, y ≥ 0 vì số đơn vị sản phẩm không thể âm. Bằng ngôn ngữ toán học, bài toán trên có thể phát biểu như sau: Tìm x và y sao cho tại đó biểu thức z = 3x + 2y đạt giá trị lớn nhất với các ràng buộc:  2x + 3y ≤ 18;    5x + 4y ≤ 30; x + 6y ≤ 25;    x ≥ 0, y ≥ 0. 8 Bài toán lập kế hoạch sản xuất tổng quát có thể phát biểu dưới dạng: Hãy tìm véc tơ x = (x1 , x2 , ..., xn ) sao cho tại đó hàm f (x) = n X cj xj , j=1 đạt giá trị lớn nhất với các ràng buộc: n X aij xj ≤ bi , xj ≥ 0; i = 1, 2, ..., m; j = 1, 2, ..., n. j=1 1.3.3. Bài toán định vị Cho A1 , A2 , ..., An ∈ Rn , cho trước một tập C ⊆ Rn , tìm x∗ ∈ C sao cho: n X ||x∗ − Aj || j=1 đạt cực tiểu (hay tổng độ dài từ điểm x∗ đến j điểm A1 , A2 , ..., Aj là nhỏ nhất). Ta có bài toán tối ưu: ( ) n X M in f (x) := ||x − Aj || : x ∈ C . j=1 Nhận thấy rằng nếu bài toán trên chỉ dừng lại ở 3 điểm đầu tiên, ta có bài toán phổ thông quen thuộc: Cho A1 , A2 , A3 tạo thành một tam giác, tìm điểm x∗ thuộc tam giác sao cho tổng khoảng cách từ điểm x∗ đến các điểm A1 , A2 , A3 là nhỏ nhất. 1.3.4. Bài toán phân việc Ví dụ 1.3. Có n công việc phân cho n người sao cho có lợi nhất • cij : lợi ích nhận được nếu người i nhận được công việc j ; • xij (các biến được xác định);  1 nếu công việc i phân cho người j; xij = 0 trong các trường hợp còn lại. 9 Mô hình toán học max n X cij xij , i,j=1 sao cho: xij ∈ {0, 1}; n X xij = 1, ∀i; i,j=1 n X xij = 1, ∀j. i,j=1 1.4. Sự tồn tại nghiệm tối ưu Xét bài toán min{f (x) : x ∈ C}, (P) trong đó C ⊆ X(X ≡ Rn ), f : X → R ∪ {∞}. Có 4 trường hợp để tồn tại nghiệm tối ưu (toàn cục): ∗ C = φ (không có điểm chấp nhận); ∗ C 6= φ, hàm mục tiêu f không bị chặn dưới trên C tức: inf f (x) = −∞; x∈C ∗ C 6= φ, inf x∈C f (x) < ∞ nhưng không đạt cực tiểu trên C ; ∗ Tồn tại x∗ ∈ C sao cho f (x∗ ) ≤ f (x), ∀x ∈ C . Câu hỏi đặt ra là làm thế nào để kiểm tra khả năng tồn tại nghiệm? Có hay không một nghiệm tối ưu (cực tiểu hay cực đại toàn cục)? Một định lý quen thuộc trong giải tích là định lý Weierstrass: Nếu hàm f liên tục và tập C compact, khác rỗng, thì bài toán có nghiệm tối ưu. Ta xét một số điều kiện mở rộng đảm bảo cho bài toán có nghiệm tối ưu. Định lí 1.2. Để bài toán (P) có nghiệm cực tiểu, điều kiện cần và đủ là tập f (C)+ = {α ∈ R : f (x) ≤ α với x ∈ C}, đóng và có một cận dưới hữu hạn Chứng minh. Trước hết ta giả sử x∗ là một nghiệm của bài toán (P). Khi đó f (x∗ ) = min f (x) và f (C)+ = [f (x∗ ), +∞]. x∈C Rõ ràng f (C)+ là một tập đóng và f (x∗ ) là một cận dưới hữu hạn của f (C)+ . 10 Ngược lại, nếu tập f (C)+ có một cận dưới hữu hạn thì cận dưới lớn nhất của f (C)+ cũng hữu hạn. Ta kí hiệu tập dưới lớn nhất (hay infimum) của f (C)+ là α∗ . • Theo định nghĩa infimum, α∗ ≤ α với mọi α ∈ f (C)+ và tồn tại dãy số {αk } ⊂ f (C)+ hội tụ đến α∗ . • Do f (C)+ là tập đóng nên α∗ ∈ f (C)+ . • Theo định nghĩa của f (C)+ tồn tại x∗ ∈ C sao cho f (x∗ ) ≤ α∗ . Ta có f (x∗ ) ∈ f (C)+ và do x∗ là cận dưới lớn nhất của f (C)+ nên α∗ ≤ f (x∗ ). Vì thế α∗ = f (x∗ ). Điều này chứng tỏ x∗ là một nghiệm cực tiểu của bài toán (P). Sau đây là một ví dụ cho thấy định lý trên không còn đúng nếu thiếu giả thiết về tính đóng của tập f (C)+ . Ví dụ 1.4. Cho hàm f (x) = ex , x ∈ C = R. Do ex > 0 với mọi x ∈ R nên: f (C)+ = (0, +∞). Tập f (C)+ có cận dưới hữu hạn 0, nhưng do nó là tập không đóng nên hàm f (x) = ex không đạt cực tiểu trên C = R. Định lí 1.3. ( Weierstrass) Nếu C là compact và f là nửa liên tục trên trên C thì (P) có nghiệm tối ưu (đạt cực đại trên C). Định lí 1.4. Nếu C là compact và f là nửa liên tục dưới trên C thì (P) có nghiệm tối ưu (đạt cực tiểu trên C). Hệ quả 1.1. Nếu f là nửa liên tục dưới trên C và thỏa mãn các điều kiện sau: f (x) → +∞ khi x ∈ C, kxk → +∞, thì f có cực tiểu trên C . Chứng minh. Xét: C(a) = {x ∈ C : f (x) ≤ f (a)}, a ∈ C. Ta có C(a) đóng và bị chặn. Vậy f có một điểm cực tiểu trên C(a) và cũng là một điểm cực tiểu của f trên C . 11 Hệ quả 1.2. Nếu f là nửa liên tục trên trên C và thỏa mãn các điều kiện sau: f (x) → −∞ khi x ∈ C, kxk → +∞, thì f có cực đại trên C . Chú ý 1.1. Nếu f là nửa liên tục dưới trên C , hàm f được gọi là bức (coercive) trên C , nghĩa là: f (x) → +∞ khi x ∈ C, kxk → +∞, Nếu f là nửa liên tục trên trên C hàm −f được gọi là bức (coercive) trên C , nghĩa là: f (x) → −∞ khi x ∈ C, kxk → +∞. Ví dụ 1.5. Hàm f (x) = x2 với mọi x 6= 0 và f (0) = −1 nửa liên tục dưới trên R. Hàm f (x) = ex với mọi x 6= 0 và f (0) = 2 nửa liên tục trên trên R. Tuy nhiên các hàm này không liên tục trên toàn bộ R. Ví dụ 1.6. a) Cho hàm một biến số  f (x) = x2 khi |x| > 1; 2 khi −1 ≤ |x| ≤ 1. Dễ thấy hàm f nửa liên tục trên do: f (x) → ∞ khi x ∈ C, |x| → ∞ nhưng không nửa liên tục dưới. Vì thế giá trị cực tiểu toàn cục của hàm không đạt được. b) Xét hàm f (x) ≡ 1 với mọi x ∈ R. Khi đó x ∈ R đều là cực tiểu toàn cục của f , nhưng f (x) 9 +∞ khi |x| −→ +∞. Nhận xét 1.3. Qua ví dụ (1.6), ví dụ này cho thấy rằng hai hệ quả (1.1) và (1.2) không thể thiếu giả thiết nửa liên tục dưới và điều kiện bức chỉ là điều kiện đủ chứ không phải là điều kiện cần. 12 1 T x Ax + bT x với A ∈ Rn×n đối xứng, 2 b ∈ Rn là bức khi và chỉ khi A xác định dương. Định lí 1.5. Hàm bậc hai f (x) = Chứng minh. Giả sử A xác định dương. Nếu f không bức thì có một dãy x1 , x2 , ..., xk , ... với kxk k → +∞ nhưng f (xk ) ≤ α với α ∈ R, nghĩa là 1 f (x) = (xk )T Ax + bT xk ≤ α, 2 ∀k. (1.4) xk Đặt y = , ta có ky k k = 1. Mọi y 1 , y 2 , ... đều nằm trên biên của hình k kx k cầu đóng B(0, 1) tâm 0 bán kính 1. Do biên này là một tập đóng và bị chặn nên có thể xem rằng y k hội tụ đến một điểm duy nhất w với kwk = 1. Từ (1.4) cho thấy !T ! 1 xk Axk bT xk α + ≤ , ∀k = 1, 2, ... 2 kxk k kxk k kxk k2 kxk k2 k k Khi k → ∞ thì kx k → ∞ và ta nhận được lim k→∞ 1 k T k (y ) Ay 2  ! +0≤0 ⇒ xk  thay y = k kx k k 1 T w Aw ≤ 0, 2 trái lại với A xác định dương. Ngược lại giả sử f bức nhưng A không xác định dương. Khi đó tồn tại phần tử w ∈ Rn (w 6= 0) sao cho wT Aw ≤ 0. Với x = t.w ta có 1 f (x) = t2 (wT Aw) + t.bT w. 2 bT w là một hằng số và wT Aw ≤ 0 nên khi t → ±∞ (nếu b 6= 0, chọn t trái dấu với bT w), f (x) → 0 hoặc −∞, tức là f không bức. Vậy f bức thì A phải xác định dương. Ví dụ 1.7. Hàm toàn phương nào sau đây là bức? Vì sao? a)L1 (x) = L1 (x1 , x2 , x3 ) = x21 + 4x22 + 3x23 + 2x1 x2 . b)L2 (x) = L2 (x1 , x2 , x3 ) = 2x21 + 3x22 − 1x23 + 4x1 x2 − 6x1 x3 + 10x2 x3 . Giải 13 a)L1 (x) = L1 (x1 , x2 , x3 ) = x21 + 4x22 + 3x23 + 2x1 x2 . Ta có: ! 1 1 0 A= 1 4 0 0 0 3 Xét các định thức con chính:   1 1    |1| = 1 > 0; 1 4 = 4 − 1 = 3 > 0;   1 1 0   1 4 0 = 12 − 3 = 9 > 0. 0 0 3 Do đó A là ma trận xác định dương nên hàm L1 (x) là bức. b)L2 (x) = L2 (x1 , x2 , x3 ) = 2x21 + 3x22 − 1x23 + 4x1 x2 − 6x1 x3 + 10x2 x3 . Ta có ! 2 2 −3 B= 2 3 5 −3 5 −1 Xét các định thức con  2  |2| = 2 > 0; 2 chính:  2 3 = 6 − 4 = 2 > 0;    2 2 −3    2 3 5  = −139 < 0. −3 5 −1 Do đó B không là ma trận xác định dương nên hàm L2 (x) không bức. Ví dụ 1.8. Các bài toán sau có nghiệm tối ưu hay không? vì sao? a) min{x21 + x22 + ... + x2n : a1 x1 + a2 x2 + ... + an xn = b, b, ai 6= 0 ∀i.} b) min{x1 + 2x2 − x3 : 3x1 − x2 + 2x3 = 4}. Giải a) Đây là bài toán tối ưu dạng min{f (x) = x21 + x22 + ... + x2n : x ∈ C} Hàm f (x) liên tục và bức vì: f (x) = kx2 k nên khi kxk → ∞ thì f (x) → ∞. Tập C = {∀x ∈ Rn : a1 x1 + a2 x2 + ... + an xn = b} có một dạng siêu phẳng trong Rn nên C là một tập đóng. Dễ thấy C khác rỗng vì: x1 = b ; x1 = x2 = ... = xn = 0, a1 thỏa mãn: a1 x1 + a2 x2 + ... + an xn = b. 14 Vậy bài toán có điểm cực tiểu toàn cục (nghiệm tối ưu). b) Đây là bài toán cực tiểu hàm tuyến tính f (x) = x1 + 2x2 − x3 trên tập affine C = {∀x ∈ R3 : 3x1 − x2 + 2x3 = 4} (C là một tập nghiệm của một phương trình tuyến tính). Ta có: a(1, 1, 1)T , b(0, 0, 2)T ∈ C và f (a) = 2 6= f (b) = −2. Khi đó hàm f không bị chặn dưới trên C , do đó bài toán không có nghiệm cực tiểu (inf {f (x) : x ∈ C} = −∞). 1.5. Điều kiện tối ưu Một vấn đề được đặt ra là: Nếu x∗ là một nghiệm tối ưu (địa phương hoặc toàn cục) thì điều gì xảy ra với x∗ ? Định nghĩa 1.7. (Hướng chấp nhận được) Một véc tơ d 6= 0 được gọi là hướng chấp nhận được của C tại x∗ ∈ C nếu x∗ + λd ∈ C, với mọi λ > 0 đủ nhỏ. Ta định nghĩa C(x∗ ) là tập tất cả các hướng chấp nhận được của C tại x∗ . Định lí 1.6. Nếu (P) là bài toán quy hoạch lồi (C là tập lồi và f là hàm lồi trên C ), f khả dưới vi phân thì điều kiện cần và đủ để x∗ là nghiệm tối ưu của bài toán (P): 0 ∈ ∂f (x∗ ) + NC (x∗ ), trong đó NC (x∗ ) là nón pháp tuyến của C . Tức là NC (x∗ ) = {x∗ ∈ X ∗ : hx∗ , x − xi ≤ 0, ∀x ∈ C}, với x∗ ∈ X ∗ được gọi là véc tơ pháp tuyến của tập lồi C tại x ∈ C Chứng minh. Xét hàm chỉ  δC (x) = 0 nếu x ∈ C, +∞ nếu x ∈ / C. 15 Do C lồi suy ra δC (x) lồi và ∂δC (x∗ ) = NC (x∗ ). Bài toán (P) được viết lại thành bài toán không ràng buộc: min{f (x) + δC (x), x ∈ Rn }. (UP) Khi đó x∗ là nghiệm tối ưu của bài toán (UP) khi và chỉ khi 0 ∈ ∂(f (x∗ ) + δC (x∗ )). Theo định lý Moreau - Rockafellar, ta có: 0 ∈ ∂f (x∗ ) + ∂δC (x∗ ). Từ 0 ∈ ∂δC (x∗ ) = NC (x∗ ) = {w : hw, x − x∗ i ≤ 0, ∀x ∈ C}. Do vậy 0 ∈ ∂f (x∗ ) + NC (x∗ ). Hệ quả 1.3. Nếu x∗ ∈ intC và x∗ ∈ S(C, f ) (tập nghiệm tối ưu của (P)) thì 0 ∈ ∂f (x∗ ). Đặc biệt, nếu f là khả vi và C là toàn bộ không gian thì 0 = 5f (x∗ ). 1.5.1. Tối ưu không ràng buộc Xét bài toán tối ưu không ràng buộc có dạng: min{f (x) : x ∈ Rn } (M) trong đó f : Rn → R là một hàm phi tuyến cho trước. Định lí 1.7. Nếu x ∈ Rn là một cực tiểu địa phương của một hàm f (x) khả vi trên Rn thì Of (x) = 0 và nếu f (x) hai lần khả vi thì O2 f (x) ≥ 0 (ma trận O2 nửa xác định dương). Ngược lại, nếu x ∈ Rn là điểm tại đó f (x) hai lần khả vi và Of (x) = 0, O2 f (x) > 0 (ma trận O2 xác định dương), thì x ∈ Rn là một cực tiểu địa phương chặt của f (x) trên Rn , nghĩa là có một số ε > 0 sao cho f (x) < f (x) với mọi x ∈ Rn , x 6= x và kx − xk < ε. 16 Chứng minh. Vì x là cực tiểu địa phương nên với |t| đủ nhỏ và d ∈ Rn ta có f (x + td) − f (x) ≥ 0, do đó với t > 0 suy ra f (x + td) − f (x) ≥ 0. t  Cho qua giới hạn khi t → 0+ ta được Of (x), d ≥ 0.  Tương tự khi t < 0 và t → 0− ta có Of (x), d = 0. Với mọi d ∈ Rn , suy ra Of (x)d = 0. Nếu f (x) khả vi hai lần thì chú ý rằng Of (x) = 0 ta có  t2 d, O2 f (x)d + 0(t2 ), 0 ≤ f (x + td) − f (x) = 2  vì thế d, O2 f (x)d ≥ 0 với mọi d ∈ Rn , tức là O2 f (x) ≥ 0. Ngược lại, nếu O2 f (x) > 0 thì lấy λ > 0 là giá trị riêng nhỏ nhất của O2 f (x), ta có  d, O2 f (x)d ≥ λkdk2 với mọi d ∈ Rn . Do Of (x) = 0 nên với t đủ nhỏ và d ∈ Rn ta có  t2 d, O2 f (x)d + 0(t2 ). f (x + td) = f (x) + 2 Vì thế f (x + td) − f (x) λ||d||2 0(t2 ) ≥ + 2 , t2 2 t f (x + td) − f (x) do đó khi |t| đủ nhỏ > 0 với mọi 0 6= d ∈ Rn , vậy x là cực 2 t tiểu địa phương chặt của f (x) trên Rn . Do max{f (x) : x ∈ Rn } = −min{−f (x) : x ∈ Rn } khi đó ta có hệ quả sau Hệ quả 1.4. Giả sử f (x) khả vi hai lần trên Rn a) Nếu x̃ ∈ Rn là một cực đại địa phương của f (x) trên Rn thì Of (x̃) = 0 và O2 f (x̃) ≤ 0, (O2 f (x̃) (nửa xác định âm)). b) Ngược lại, nếu x̃ ∈ Rn thỏa mãn Of (x̃) = 0 và O2 f (x̃) < 0, (O2 f (x̃) (nửa xác định âm)). thì x̃ ∈ Rn là một cực đại địa phương chặt của f (x) trên Rn 17 Ví dụ 1.9. Tìm nghiệm cực tiểu và cực đại của hàm một biến f (x) = x5 − 5x. Giải Ta thấy x → +∞ thì x5 − 5x → +∞. Khi x → −∞ thì x5 − 5x → +∞. Vì thế, f (x) = x5 − 5x không có cực tiểu và cực đại toàn cục. 0 Ta có f (x) = 5x4 − 5 = 0 tức x4 = 1, ta được hai điểm dừng x2 = 1, x1 = −1. Để biết x1 , x2 là cực tiểu hay cực đại địa phương, ta tính 00 f (x) = 20x3 00 f (x1 ) = 20 > 0 00 f (x2 ) = −20 < 0 nên x1 = 1 là nghiệm cực tiểu địa phương với f (x1 ) = −4. x2 = −1 là nghiệm cực đại địa phương với f (x2 ) = 4. Ví dụ 1.10. Tìm cực đại cực tiểu của hàm hai biến 1 f (x1 , x2 ) = (x41 − 4x1 x2 + x42 ). 4 Giải Ta có: 5f (x) = x31 − x2 −x1 + x32 ! và 52 f (x) = 3x21 ! −1 . −1 3x22 Giải hệ phương trình  5f (x) = 0 ⇔ x31 − x2 = 0 −x1 + x32 = 0 " x1 = 0 → x2 = 0; ⇔ x1 = 1 → x2 = 1; x1 = −1 → x2 = −1. Vậy có ba điểm dừng là x1 = (0, 0)T ; x2 = (1, 1)T ; x3 = (−1, −1)T . Ta có: ! ! 0 −1 3 −1 52 f (x1 ) = −1 0 , 52 f (x2 ) = 52 f (x3 ) = −1 3 .