Tài liệu Một phương pháp xấp xỉ ngoài tìm nghiệm của hệ bất phương trình tuyến tính và ứng dụng

  • Số trang: 81 |
  • Loại file: PDF |
  • Lượt xem: 48 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ HỒNG MỘT PHƯƠNG PHÁP XẤP XỈ NGOÀI TÌM NGHIỆM CỦA HỆ BẤT PHƯƠNG TRÌNH TUYẾN TÍNH VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC Vũ Thị Hồng MỘT PHƯƠNG PHÁP XẤP XỈ NGOÀI TÌM NGHIỆM CỦA HỆ BẤT PHƯƠNG TRÌNH TUYẾN TÍNH VÀ ỨNG DỤNG 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: TS. NGUYỄN ANH TUẤN Thái Nguyên - 2014 i Mục lục Bảng ký hiệu vi Mở đầu 1 1 Một số khái niệm cơ bản và một số bài toán thực tế đưa về bài toán tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính 4 1.1 Một số khái niệm cơ bản về tập lồi . . . . . . . . . . . . 4 1.2 Một số khái niệm cơ bản liên quan đến hàm số tuyến tính 7 1.3 Khái niệm về miền ràng buộc tuyến tính không bị chặn, phương vô hạn chấp nhận được và hướng tăng, giảm của 1.4 hàm gần lồi - gần lõm . . . . . . . . . . . . . . . . . . . 10 Một số mô hình thực tế . . . . . . . . . . . . . . . . . . 13 1.4.1 Bài toán cái túi . . . . . . . . . . . . . . . . . . 13 1.4.2 Bài toán lập kế hoạch sản xuất (Cực đại tổng lãi 1.4.3 1.5 suất ) . . . . . . . . . . . . . . . . . . . . . . . . 14 Bài toán mua (thuê) máy bay tối ưu . . . . . . . 14 Dạng chuẩn và dạng chính tắc của bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.1 Dạng chuẩn và dạng chính tắc . . . . . . . . . . 15 1.5.2 Đưa bài toán quy hoạch tuyến tính về dạng chuẩn và dạng chính tắc . . . . . . . . . . . . . . . . . 16 ii 1.6 Giới thiệu một số phương pháp giải bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6.1 Giới thiệu phương pháp đơn hình . . . . . . . . . 17 1.6.2 Giới thiệu phương pháp Kamarkar (Điểm trong) 21 2 Quy hoạch tuyến tính dạng chuẩn và phương pháp nón xoay [1] 23 2.1 Bài toán quy hoạch tuyến tính dạng chuẩn tổng quát . . 23 2.2 Khái niệm về nón tuyến tính, cạnh của nón và Nón - min 24 2.2.1 Khái niệm về nón đơn hình tuyến tính . . . . . . 24 2.2.2 Khái niệm về cạnh của nón đơn hình . . . . . . . 24 2.2.3 Khái niệm về nón xoay M(r,s) sinh ra từ nón M . 27 2.2.4 Định nghĩa Nón – min (Nón cực tiểu) . . . . . . 29 Phương pháp nón xoay tuyến tính . . . . . . . . . . . . 33 2.3.1 Thuật toán nón xoay tuyến tính . . . . . . . . . 35 2.3.2 Bảng lặp giải bài toán qui hoạch tuyến tính bởi 2.3 thuật toán nón xoay tuyến tính và ví dụ minh hoạ 37 3 Thuật toán nón xoay cho hệ bất phương trình tuyến tính và ứng dụng 3.1 46 Thuật toán nón xoay tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính với cơ sở xuất phát từ gốc toạ độ là đỉnh của nón Rn+ . . . . . . . . . . . . . . . . . . 3.2 47 Bảng lặp nón xoay tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính với cơ sở xuất phát từ gốc toạ 3.3 độ là đỉnh của nón Rn+ . . . . . . . . . . . . . . . . . . 49 Các ví dụ minh hoạ cho thuật toán BPT 50 . . . . . . . . iii 3.4 Giải bài toán qui hoạch tuyến tính dạng chuẩn từ việc tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính đối ngẫu bởi thuật toán nón xoay bất phương trình (BPT) với cơ sở xuất phát từ gốc toạ độ và ví dụ minh hoạ 56 3.4.1 Đưa bài toán qui hoạch tuyến tính về bài toán tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính với cơ sở xuất phát từ gốc toạ độ . . . . . . 56 3.4.2 Hệ bất phương trình tuyến tính đối ngẫu đối xứng 58 3.4.3 Ví dụ minh hoạ . . . . . . . . . . . . . . . . . . 59 3.5 Thuật toán nón xoay BPT giải ví dụ Klee-Minty . . . . 62 3.6 Vài nét về độ phức tạp tính toán của thuật toán BPT và kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo 69 71 iv Lời cảm ơn Luận văn này được 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 tận tình của Tiến sĩ Nguyễn Anh Tuấn. Tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc về sự tận tâm và nhiệt tình của Thầy trong suốt quá trình tác giả thực hiện luận văn. Trong quá trình học tập và làm luận văn, từ bài giảng của các Giáo sư, Phó Giáo sư tại Viện Toán học, các Thầy Cô trong Đại học Thái Nguyên, tác giả đã trau dồi thêm rất nhiều kiến thức phục vụ cho việc nghiên cứu và công tác của bản thân. Từ đáy lòng mình, tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy Cô. Tác giả xin chân thành cảm ơn Ban Giám hiệu, phòng Đào tạo Khoa học và Quan hệ quốc tế, Khoa Toán - Tin trường Đại học Khoa học, Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tôi xin gửi lời cảm ơn tới gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu. Tác giả Vũ Thị Hồng Bảng ký hiệu ———————————————————————————— v —– vi Bảng ký hiệu φ Tập rỗng 1 Mở đầu Như chúng ta đã biết nhiều bài toán trong lĩnh vực toán học và vật lý như: Lý thuyết xấp xỉ, lý thuyết xử lý số liệu và hình ảnh, ảnh y học, . . . đã dẫn đến việc giải quyết bài toán tìm nghiệm chấp nhận của các bất đẳng thức lồi, cụ thể là tìm một điểm x∗ trong C, với C là giao của hữu hạn các tập lồi đóng Ci trong không gian Hilbert. Bài toán này đã được giải bằng thuật toán hiệu quả là phương pháp chiếu trực giao liên tiếp lên các tập lồi đóng và trong trường hợp riêng khi tất cả các Ci đều là các nửa không gian Affine trong Rn thì ta thu được thuật toán xấp xỉ tìm nghiệm chấp nhận của một hệ bất phương trình tuyến tính (xem[13]). Trong việc giải bài toán quy hoạch tuyến tính bằng thuật toán đơn hình và các thuật toán điểm trong thì đầu tiên chúng ta đều phải giả thiết là biết trước một điểm chấp nhận được của bài toán. Để có được một điểm như vậy chúng ta phải đi giải một bài toán quy hoạch tuyến tính khác hay một bài toán tương đương khác. Chính vì vậy, luận văn này đề nghị một thuật toán trực tiếp tìm nghiệm chấp nhận của một hệ bất phương trình tuyến tính, nói cụ thể chính xác hơn là tìm một điểm cực biên (nếu có) của một hệ ràng buộc ở dạng các bất phương trình tuyến tính. Thuật toán ở đây là một cải tiến trực tiếp từ thuật toán nón xoay tuyến tính giải bài toán quy hoạch tuyến tính dạng chuẩn trình bày trong cuốn sách “Quy hoạch tuyến tính với phương pháp nón xoay”[1]. 2 Thuật toán kết thúc sau hữu hạn bước lặp với điểm xuất phát ban đầu của thuật toán là từ gốc tọa độ của Rn . Việc có được một thuật toán tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính thì điều đó có nghĩa là chúng ta có được một thuật toán giải bài toán quy hoạch tuyến tính. Như vậy mối quan hệ giữa bài toán quy hoạch tuyến tính và bài toán tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính rất gần nhau. Do đó, trong luận văn chương đầu trình bày những bài toán liên quan tới quy hoạch tuyến tinh dạng chuẩn, chương cuối của luận văn trình bày việc đưa bài toán quy hoạch tuyến tính dạng chuẩn bất kỳ về bài toán tìm một nghiệm chấp nhận của hệ bất phương trình dựa trên cơ sở của lý thuyết đối ngẫu trong quy hoạch tuyến tính. Luận văn gồm 3 chương: Chương 1 trình bày một số khái niệm cơ bản liên quan tới hàm gần lồi-gần lõm làm cơ sở khoa học để xây dựng thuật toán nón xoay tuyến tính theo lược đồ xấp xỉ ngoài giải bài toán quy hoạch tuyến tính dạng chuẩn tổng quát, sau một số hữu hạn bước lặp cho ta lời giải của bài toán hoặc phát hiện ra miền ràng buộc của bài toán không có phương án chấp nhận được. Chương 2 trình bày phương pháp nón xoay giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn. Chương 3 với nội dung cải tiến thuật toán nón xoay tuyến tính giải bài toán quy hoạch tuyến tính dạng chuẩn trình bày trong chương 2 trở thành một thuật toán tìm nghiệm chấp nhận được của một hệ bất phương trình tuyến tính với cơ sở xuất phát từ gốc tọa độ và các ví dụ minh họa. Sau đó dựa trên cặp bài toán quy hoạch tuyến tính đối ngẫu đối xứng đưa việc giải bài toán quy hoạch tuyến tính dạng chuẩn bất kỳ về việc giải bài toán tìm nghiệm chấp nhận của một hệ bất phương trình tuyến tính đối ngẫu và ứng dụng nó giải ví dụ Klee-minty với số 3 chiều của bài toán là n bất kỳ vẫn tìm được lời giải của bài toán sau 2 bước lặp ngắn gọn. Thuật toán xấp xỉ ngoài bất phương trình (BPT) tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính đề nghị trong luận văn này được xây dựng chi tiết, các bước của thuật toán được trình bày sao cho chúng ta có thể dễ dàng lập trình chuyển sang các chương trình trên máy tính bằng các ngôn ngữ như Pascal, C, Java, ... Luận văn này hoàn thành dựa trên cuốn sách “Quy hoạch tuyến tính với phương pháp nón xoay” [1] và trên các sách, tài liệu có trong phần tài liệu tham khảo. 4 Chương 1 Một số khái niệm cơ bản và một số bài toán thực tế đưa về bài toán tìm nghiệm chấp nhận của hệ bất phương trình tuyến tính Trong chương này, tôi trình bày một số khái niệm về bài toán tối ưu tổng quát và một số mô hình bài toán thực tế, cũng như một số khái niệm liên quan đến tập lồi đa diện, bài toán quy hoạch tuyến tính. 1.1 Một số khái niệm cơ bản về tập lồi Định nghĩa 1.1.1. Một tập lồi mà là giao của một số hữu hạn nửa không gian đóng gọi là tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính: hai , xi ≤ bi , i = 1, ..., m(ai ∈ Rn , bi ∈ R) (1.1) nghĩa là tập các x nghiệm đúng Ax ≤ b với A là một ma trận cấp mxn và b ∈ Rm . 5 Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên một tập lồi đa diện cũng là tập nghiệm của một hệ các phương trình và bất phương trình tuyến tính : hai , xi = bi , i = 1, ..., p , hai , xi ≤ bi , i = p + 1, ..., m Hạng của hệ bất phương tuyến tính (1.1) được định nghĩa bằng hạng của ma trận A. Nếu hạng của hệ này bằng m thì ta nói hệ độc lập tuyến tính. Một tập lồi đa diện có thể không bị chặn (không giới nội). Một tập lồi đa diện mà đồng thời là một nón lồi (tương ứng với trường hợp b = 0) gọi là một nón lồi đa diện. Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi. Các đa giác lồi theo nghĩa thông thường trong R2 là những ví dụ cụ thể về đa diện lồi. Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh .. của nó. Tập các đỉnh của C ký hiệu là C . Mỗi cạnh vô hạn của một tập lồi đa diện tương ứng với một phương cực biên của nó. Cho tập lồi đa diện D 6= 0 xác định bởi hệ bất phương trình tuyến tính (1.1). Khi đó mỗi bất phương trình (1.1) gọi là một ràng buộc của D. Ta nói điểm x0 ∈ D thoả mãn chặt ràng buộc i nếu hai , x0 i = bi . Với mỗi x ∈ D ký hiệu I(x) = {i : hai , xi = bi } là tập chỉ số của những ràng buộc thoả mãn chặt tại x. Ký hiệu I0 = {i : hai , xi = bi } với mọi x ∈ D. Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của D được cho trong định lý sau : Định lý 1.1.2. Một tập con khác rỗng F ⊂ D là một diện thực sự của D khi và chỉ khi F = {x : hai , xi = b, hai , xi ≤ bi , i ∈ / I} 6 Với I là một tập chỉ số sao cho I0 ⊂ I1 {1, ..., m} (I – tập chỉ số xác định diện F ). Hơn nữa, ta có   dimF = n − rank ai : i ∈ I và dimD = n − rank ai : i ∈ I0 . Hệ quả 1.1.3. Nếu D là một tập lồi đa diện xác định bởi hệ (1.1) thì: a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi  rank ai : i ∈ I(x0 ) = n , nghĩa là X0 thoả mãn chặt n ràng buộc độc lập tuyến tính của hệ (1.1). b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) T ≤ D là một cạnh của D thì T được xác định bởi một tập chỉ số I sao cho  rank ai : i ∈ I(x0 ) = n − 1 Tức là mọi x ∈ T cùng thoả mãn chặt n − 1 ràng buộc độc lập tuyến tính của hệ (1.1). Mỗi tập lồi đa diện chỉ có một sô hữu hạn đỉnh và cạnh (hữu hạn hay vô hạn). Trong Rn một đa diện lồi có k + 1(0 ≤ k ≤ 1) đỉnh độc lập afin gọi là một k – đơn hình. Định lý 1.1.4. a) Mỗi đa diện lồi C bằng bao lồi của tất cả các đỉnh của nó C = convC hay x ∈ C khi và chỉ khi x = λ1 v 1 + λ2 v 2 + ... + λp v p với mọi λi ≥ 0, λ1 + λ2 + ... + λp = 1 và v i (i = 1, ..., p) là các đỉnh của C. b) Với tập lồi đa diện C không giới nội , mỗi x ∈ C có thể biểu diễn dưới dạng một tổ hợp lồi của các đỉnh của C cộng với một tổ hợp tuyến tính không âm của các phương cực biên của C , nghĩa là x ∈ C ⇐⇒ x = λ1 v 1 + λ2 v 2 + ... + λp v p + µ1 u1 + µ2 u2 + ... + µq uq với mọi λi ≥ 0, λ1 + λ2 + ... + λp = 1, µj ≥ 0, p, q ≥ 0 là số nguyên v i là các đỉnh của C(i = 1, ..., p), uj (i = 1, ..., q) là phương của các cạnh 7 vô hạn của C Với tập lồi đa diện C không có đỉnh thì biểu diễn trên chỉ cần các v i ∈ C và các uj ∈ recC (tập các phương lùi xa của C và điểm gốc O tương đương uj ∈ nón lùi xa của C) Định lý trên cho thấy ứng với mỗi tập lồi đa diện C cho trước có hai nhóm hữu hạn véctơ, sao cho tập lồi ấy chính là tập tất cả các điểm có thể biểu diễn thành tổng của một tổ hợp lồi của các véctơ thuộc nhóm thứ nhất và một tổ hợp tuyến tính không âm của các véctơ thuộc nhóm thứ hai. Các véctơ trong nhóm thứ nhất đều thuộc C , các véctơ trong nhóm thứ hai đều là các phương vô hạn của C . Ngược lại, có thể chứng minh được rằng nếu cho trước hai nhóm hữu hạn véctơ thì tập tất cả các điểm có thể biểu diễn như trên xác định một tập lồi đa diện. 1.2 Một số khái niệm cơ bản liên quan đến hàm số tuyến tính Hàm tuyến tính là một hàm gần lồi - gần lõm và không bị chặn trên Rn ([1]). Do đó các kết quả lý thuyết cũng như phương pháp tìm cực tiểu đối với hàm gần lồi - gần lõm đưa ra trong sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính” ([1]) có thể áp dụng đối với hàm tuyến tính. Chính vì vậy, trước khi trình bày bài toán quy hoạch tuyến tính dạng chuẩn và thuật toán nón xoay giải nó, chúng ta nhắc lại một số khái niệm, định nghĩa, các định lý, hệ quả và các tính chất cơ bản của hàm gần lồi - gần lõm đã trình bày trong sách “Quy hoạch gần lồi - gần lõm ứng dụng vào quy hoạch tuyến tính” ([1]). Việc chứng minh các định lý, hệ quả và các tính chất này, chúng ta có thể tìm thấy trong cuốn sách nói trên. Định nghĩa 1.2.1. Hàm f : Rn → Rl là một hàm tựa lõm (quasi - 8 concave) nếu ∀x, y ∈ Rn và ∀α ∈ [0, 1] ta luôn có: f (αx + (1 − α)y) ≥ min{f (x), f (y)} Định nghĩa 1.2.2. Hàm f : Rn → Rl là một hàm tựa lồi (quasi convex) nếu ∀x, y ∈ Rn và ∀α ∈ [0, 1] ta luôn có: f (αx + (1 − α)y) ≤ max{f (x), f (y)} Định nghĩa 1.2.3. Hàm f : Rn → Rl là một hàm gần lõm (almost concave) nếu nó là một hàm tựa lõm và thoả mãn: f (αx + (1 − α)y) > min{f (x), f (y)}, ∀x, y ∈ Rn , f (x) 6= f (y) và ∀α ∈ (0, 1). Định nghĩa 1.2.4. Hàm f : Rn → Rl là một hàm gần lồi (almost convex) nếu nó là một hàm tựa lồi và thoả mãn: f (αx + (1 − α)y) < max{f (x), f (y)}, ∀x, y ∈ Rn , f (x) 6= f (y) và ∀α ∈ (0, 1). Định nghĩa 1.2.5. Hàm f : Rn → Rl là một hàm gần lồi - gần lõm (almost - convex and almost - concave) nếu nó vừa là một hàm gần lồi - vừa là một hàm gần lõm. Từ các định nghĩa trên ta suy ra một số tính chất sau của hàm vừa tựa lồi vừa tựa lõm: Tính chất 1.2.6. min{f (x), f (y)} ≥ f (αx+(1−α)y) ≤ max{f (x), f (y)}, ∀x, y ∈ Rn và ∀α ∈ [0, 1]. Tính chất 1.2.7. Nếu f (x) = f (y) thì f (x) = f (αx+(1−α)y) = f (y), ∀α ∈ [0, 1]. Nếu f là một hàm gần lồi - gần lõm thì nó sẽ thoả mãn các tính chất: Tính chất 1.2.8. Nếu f (x) = f (y) thì f (x) = f (αx+(1−α)y) = f (y), ∀α ∈ Rl . 9 Tính chất 1.2.9. Nếu f (x) 6= f (y) thì min{f (x), f (y)} < f (αx + (1 − α)y) < max{f (x), f (y)}, ∀x, y ∈ Rn và ∀α ∈ (0, 1). Ta có thể chứng minh được rằng nếu f là một hàm gần lồi thì cực tiểu địa phương sẽ là cực tiểu toàn cục. Các định lý sau đây là cơ sở lý luận cho việc xây dựng các thuật toán sau này. Định lý 1.2.10. Nếu f là một hàm gần lồi - tựa lõm, và f (x) ≤ f (y) ∀x 6= y , thì f (x) ≤ f (αx + (1 − α)y), ∀α ≥ 0. Định lý này cho ta kết luận rằng hàm f gần lồi - tựa lõm và ∀x 6= y mà f (x) ≤ f (y) thì x là điểm cực tiểu của f trên tia x + α(y − x) ∀α ≥ 0. Hệ quả 1.2.11. Nếu f là một hàm gần lồi - tựa lõm, và f (x) ≤ f (x+z) ∀x, z 6= 0, thì f (x) ≤ f (x + αz), ∀α ≥ 0. Định lý 1.2.12. Nếu f là một hàm liên tục, gần lồi - tựa lõm, và z là một điểm tuỳ ý thuộc Rn , nếu f (y) ≥ f (x) và f (x + z) ≥ f (x) thì f (y + αz) ≥ f (y) ≥ f (y − αz), ∀α ≥ 0. Định lý 1.2.13. Nếu f là một hàm vừa tựa lồi vừa tựa lõm trên Rn , và z 1 , z 2 ,...,z N là các điểm tuỳ ý thuộc Rn ta luôn có: min{f (z 1 ), ..., f (z N )} ≤ f (α1 z 1 + ... + α1 z N ) ≤ max{f (z 1 ), ..., f (z N )} ∀αi ∈ [0, 1], N P i=1 αi = 1, i = 1, 2..., N 10 1.3 Khái niệm về miền ràng buộc tuyến tính không bị chặn, phương vô hạn chấp nhận được và hướng tăng, giảm của hàm gần lồi - gần lõm Ta gọi P := {x ∈ Rn : Ai , x + bi , i = 1, 2, ..., m} Ai là véc tơ dòng và Ai ∈ Rn , m ≥ n, Ai (a1 , a2 , ..., am ), bi ∈ Rl , i = 1, 2, ..., m Tập P xác định như trên gọi là miền rằng buộc tuyến tính và nó n P xi yi với X := là một miền lồi. Ở đây, chúng ta ký hiệu hX, Y i = X=1 (x1 , x2 , ..., xn ), Y := (y1 , y2 , ..., yn ) Định nghĩa 1.3.1. Miền ràng buộc tuyến tính P được gọi là không bị chặn nếu nó tồn tại một điểm chấp nhận x0 thuộc P và một điểm z 6= 0 sao cho x0 + αz ∈ P , ∀α ≥ 0, khi đó điểm z được gọi là phương vô hạn chấp nhận của P tại x0 . Tập hợp các điểm x = x0 + αz , ∀α ≥ 0 gọi là tia vô hạn chấp nhận được của P. Từ định nghĩa này chúng ta dễ dàng chứng minh được các tính chất sau: Tính chất 1.3.2. z 6= O là một phương vô hạn chấp nhận được tại x0 ∈ P khi và chỉ khi Ai , z ≤ 0, i = 1, 2, ..., m Tính chất 1.3.3. Nếu z là một phương vô hạn chấp nhận được tại x0 ∈ P thì z là phương vô hạn chấp nhận được tại mọi điểm x ∈ P . Định nghĩa 1.3.4. 1. Điểm z 6= 0 được gọi là một hướng tăng từ x0 của hàm gần lồi – gần lõm f nếu f (x0 ) < f (x0 + αz) ∀α > 0, hay ta nói f tăng theo hướng z từ x0 . 11 2. Điểm z 6= 0 được gọi là một hướng giảm từ x0 của hàm gần lồi – gần lõm f nếu f (x0 ) > f (x0 + αz) ∀α > 0, hay ta nói f giảm theo hướng z từ x0 . 3. Điểm z 6= 0 được gọi là một hướng không đổi của f nếu f (x0 ) = f (x0 + αz) ∀α ∈ Rl . Từ các định nghĩa trên ta suy ra một vài tính chất sau: Định lý 1.3.5. Nếu tồn tại α1 > 0 mà f (x) < f (x + α1 z) thì z là một hướng tăng từ x của hàm gần lồi - gần lõm f . Hệ quả 1.3.6. Nếu tồn tại f (x) < f (x + z) thì z là một hướng tăng từ x của hàm gần lồi - gần lõm f . Định lý 1.3.7. Nếu tồn tại α1 > 0 mà f (x) > f (x + α1 z) thì z là một hướng giảm từ x của hàm gần lồi - gần lõm f . Hệ quả 1.3.8. Nếu tồn tại f (x) > f (x + z) thì z là một hướng giảm từ x của hàm gần lồi - gần lõm f . Định nghĩa 1.3.9. Hàm gần lồi – gần lõm f được gọi là không bị chặn trên Rl nếu ∀z 6= 0 và ∀x ∈ Rn ta có: 1. lim f (x + αz) = +∞, với z là hướng tăng từ x của hàm f . α→∞ 2. lim f (x + αz) = +∞, với z là hướng giảm từ x của hàm f . α→∞ Định lý 1.3.10. f : Rn → Rl là một hàm gần lồi - gần lõm, nếu f (x0 ) ≤ f (x0 + z) thì f (x) ≤ f (x + αz), ∀α > 0, ∀x ∈ Rn . Định lý 1.3.10 cho ta kết luận rằng nếu z là một hướng không giảm của f tại x0 thì nó cũng là một hướng không giảm của f tại mọi điểm x thuộc Rn . Do đó ta gọi z là một hướng không giảm của hàm f . Từ Định lý 1.3.10 ta dễ dàng chứng minh được hệ quả sau: Hệ quả 1.3.11. f : Rn → Rl là một hàm gần lồi - gần lõm, nếuf (x0 ) > f (x0 + z) thì z là một hướng giảm của hàm f , ∀x ∈ Rn , tức là f (x) > 12 f (x + αz), ∀α > 0, ∀x ∈ Rn . Và ta gọi z là một hướng giảm của hàm f. Hệ quả 1.3.12. f : Rn → Rl là một hàm gần lồi - gần lõm, z 6= 0 là một hướng tăng của hàm f , khi và chỉ khi f (0) > f (αz), ∀α > 0. Hệ quả 1.3.13. f : Rn → Rl là một hàm gần lồi - gần lõm, nếuf (x0 ) < f (x0 + z) thì z là một hướng tăng của hàm f , ∀x ∈ Rn , tức là f (x) < f (x + αz), ∀α > 0, ∀x ∈ Rn . Và ta gọi z là một hướng giảm của hàm f. Hệ quả 1.3.14. f : Rn → Rl là một hàm gần lồi - gần lõm, z 6= 0 là một hướng tăng của hàm f , khi và chỉ khi f (0) < f (αz), ∀α > 0. Hệ quả 1.3.15. f : Rn → Rl là một hàm gần lồi - gần lõm, và f (x) > f (y) thì z = x − y là một hướng tăng của hàm f và z = y − x là một hướng giảm của hàm f Từ Định lý 1.3.10 và Hệ quả 1.3.11, chúng ta dễ dàng có hệ quả dưới đây: Hệ quả 1.3.16. f : Rn → Rl là một hàm gần lồi - gần lõm, nếu z 6= 0 và f (x0 ) = f (x0 + z) tức z là một hướng không đổi của hàm f tại x0 thì z là một hướng không đổi của hàm f tại mọi điểm x thuộc Rn , tức là f (x) = f (x + αz), ∀α ∈ Rl , ∀x ∈ Rn . Và ta nói z là một hướng không đổi của hàm f Hệ quả 1.3.17. f : Rn → Rl là một hàm gần lồi - gần lõm, nếu z 6= 0 là một hướng không đổi của hàm f , khi và chỉ khi f (0) = f (αz), ∀α ∈ Rl và α 6= 0. Từ Tính chất 1.3.3 và Hệ quả 1.3.16 ta có thể chứng minh dễ dàng hệ quả sau:
- Xem thêm -