Tài liệu Bài toán quy hoạch phi tuyến có ràng buộc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA TOÁN - CƠ - TIN HỌC Nguyễn Trường Giang BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: Toán - Giải tích Mã số: 60.46.01.02 Người hướng dẫn: PGS.TS. Nguyễn Hữu Điển Hà Nội - 2014 BẢNG KÝ HIỆU Ký hiệu Ý nghĩa DFP Davidon- Fletcher- Powell QHPT Quy hoạch phi tuyến Rn Không gian thực n chiều ∇ f (x) Gradient của f tại x ∇2 f ( x ) Hessian của f tại x o Vô cùng bé ∆ Số gia 0( x, ε) Lân cận của x với bán kính ε k.k Chuẩn vector AT Ma trận chuyển vị của ma trận A 1 LỜI CẢM ƠN Để hoàn thành bản luận văn này tôi đã nhận được sự giúp đỡ to lớn của Thầy, Cô giáo, gia đình và bạn bè xung quanh. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS Nguyễn Hữu Điển, Khoa Toán- Cơ- Tin học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội. Trong quá trình giảng dạy và hướng dẫn đã ân cần động viên, giúp đỡ chỉ bảo tận tình cho tôi. Tôi cũng gửi lời cảm ơn tới các thầy cô trong Khoa Toán- Cơ- Tin học, Phòng sau đại học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội đã dạy dỗ và giúp đỡ tôi rất nhiều trong suốt quá trình học tập và nghiên cứu luận văn. Đặc biệt là các thầy cô trong Seminar của bộ môn Toán giải tích đã có những ý kiến đóng góp quý báu giúp cho bản luận văn hoàn chỉnh hơn. Cuối cùng tôi cũng xin gửi lời cảm ơn tới gia đình nơi đã sinh thành, nuôi nấng, giúp đỡ, động viên tôi rất nhiều trong suốt thời gian qua. Dù đã cố gắng hết sức nhưng luận văn không thể tránh khỏi những thiếu sót và hạn chế. Mọi ý kiến đóng góp tôi xin được đón nhận với lòng biết ơn và trân trọng sâu sắc. Hà Nội, ngày 29 tháng 10 năm 2014 Học Viên Nguyễn Trường Giang 2 Mục lục LỜI MỞ ĐẦU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chương 1. Một số kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.1. Một số khái niệm cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2. Điều kiện tối ưu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1. Điều kiện cấp 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.2. Điều kiện cấp 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Chương 2. Phương pháp tuyến tính hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1. Tổng quan về quy hoạch phi tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.1. Giới thiệu chung về QHPT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1.2. Bài toán QHPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1.3. Các vấn đề cần giải quyết khi giải bài toán QHPT . . . . . . . . . . . . . . . . . . . . . . . 31 2.2. Tuyến tính hóa ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.1. Bài toán và hướng giải quyết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.2.2. Thuật toán siêu phẳng cắt Kelley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.3. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.5. Chương trình giải ví dụ thuật toán Kelley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3. Tuyến tính hóa mục tiêu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.3.1. Bài toán và hướng giải quyết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.3.2. Thuật toán Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3 2.3.3. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.3.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.3.5. Chương trình giải ví dụ thuật toán Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . . 54 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4 LỜI MỞ ĐẦU Tối ưu hóa là một trong những lĩnh vực kinh điển của toán học, có ảnh hưởng đến hầu hết các lĩnh vực khoa học- công nghệ và kinh tế- xã hội. Trong thực tế, việc tìm giải pháp tối ưu cho một vấn đề nào đó chiếm vai trò rất quan trọng. Phương án tối ưu là phương án hợp lý nhất, tốt nhất, tiết kiệm chi phí, thời gian, tài nguyên, nguồn nhân lực mà lại cho tiệu quả cao. Những năm gần đây nhiều bài toán thực tế được giải quyết bằng phương pháp mô hình hóa toán học rất thành công. Trong số các mô hình toán học được áp dụng có nhiều mô hình tối ưu được giải quyết thông qua các bài toán tối ưu kinh điển. Bài toán tối ưu được phát biểu như sau: Cho D ∈ Rn , D 6= ∅ với Rn là không gian vector và hàm f : D → R tùy ý. Tìm giá trị cực tiểu của hàm f ( x ) khi x ∈ D nghĩa là bài toán tìm vector w thuộc vào tập D sao cho với mọi giá trị của x thuộc D thì f ( w ) ≤ f ( x ). Trong đó • f gọi là hàm mục tiêu. • D được gọi là tập ràng buộc. • x ∈ D là phương án chấp nhận được. • w ∈ D là phương án tối ưu. • f (w) là giá trị tối ưu. Trong trường hợp hàm mục tiêu cũng như tất cả các ràng buộc đều tuyến tính, thì bài toán tối ưu là BTQHTT. BTQHTT có thể được giải bằng một số phương pháp tối ưu quen biết như phương pháp đơn hình, phương pháp đơn hình cải biên và 5 các phương pháp điểm trong. BTQHTT đã và đang được sử dụng rộng rãi trong quy hoạch tài nguyên, quản lý sử dụng đất cũng như nhiều lĩnh vực của quản lý kinh tế và quản trị kinh doanh. Trong trường hợp hoặc là hàm mục tiêu hoặc một trong số các ràng buộc là phi tuyến thì chúng ta có BTQHPT. Cụ thể, trên thực tế có nhiều vấn đề trong kinh tế và trong các hoạt động kinh doanh có những mối liên hệ với nhau không phải tuyến tính mà là phi tuyến. Sự tồn tại các mối quan hệ không theo tỉ lệ như doanh số đạt được không theo tỷ lệ với giá bán (vì giá bán có thể tăng và doanh số có thể giảm). Khi tập ràng buộc D chính là Rn thì ta có bài toán QHPT không ràng buộc. Ngược lại, ta có bài toán QHPT có ràng buộc. Luận văn này trình bày một phần nhỏ lý thuyết tối ưu, đó là tìm hiểu bài toán QHPT có ràng buộc sau đây.  f ( x ) → min với x ∈ D = x ∈ Rn : gi ( x ) ≤ 0, i = 1, m; h j ( x ) = 0, j = 1, p , (1) trong đó f : D → R là hàm tùy ý. Như chúng ta đã biết, có rất nhiều phương pháp giải các lớp bài toán tối ưu phi tuyến riêng biệt , nhưng chưa có phương pháp nào tỏ ra hữu hiệu cho mọi bài toán tối ưu phi tuyến. Do vậy, chúng ta sẽ lần lượt điểm qua một số phương pháp giải BTQHPT có ràng buộc để làm rõ ưu nhược điểm của từng phương pháp cũng như chọn được phương pháp phù hợp cho từng bài toán thực tế. Đầu tiên, phương pháp hình học được coi là phương pháp đơn giản để tìm nghiệm tối ưu cho bài toán cực trị cỡ nhỏ với thuật toán như sau Bước 1. Vẽ miền chấp nhận được D của bài toán (1). Nếu miền D rỗng thì kết luận bài toán (1) vô nghiệm. Bước 2. Vẽ mặt mức f ( x1 , ..., xn ) = α với α ∈ R. Bước 3. Giảm dẫn mức α (tăng dẫn mức α) để xác định mặt mức thấp nhất hay xác lập bài toán không giải được do hàm mục tiêu f giảm vô hạn trện D. 6 Bước 4. Nếu bài toán giải được thì tìm một điểm thuộc D mà mặt mức thấp nhất đi qua nó. Điểm tìm được chính là nghiệm tối ưu của bài toán (1) và tính giá trị hàm mục tiều f tại điểm vừa tìm được ta có f min . Nhóm phương pháp tiếp theo với ý tưởng đưa bài toán quy hoạch có ràng buộc về bài toán quy hoạch không ràng buộc, bằng cách thay t hế hàm mục tiêu ban đầu f ( x ) bởi hàm mục tiêu mở rộng F ( x, r ) chứa thông số r và có tính đến các ràng buộc. Giá trị của hàm mục tiêu mở rộng phải trùng với giá trị hàm mục tiêu ban đầu và khi ra ngoài miền ràng buộc thì giá trị hàm mục tiêu mở rộng khác với giá trị hàm mục tiêu ban đầu. Khi x → w dẫn đến F (w, r ) → f (w). Với mỗi tập ràng buộc khác nhau ta có hàm mục tiêu mở rộng F ( x, r ) được chọn khác nhau, do đó ta cũng có các phương pháp khác nhau. Phương pháp nhân tử Lagrange. Phương pháp này thường được dùng để tìm cực trị của hàm với các ràng buộc đẳng thức và hàm mục tiêu mở rộng cũng được xây dựng bởi hàm Lagrange như sau m L( x, r ) = f ( x ) + ∑ λ j g j ( x ), j =1 với λ j các nhân tử Lagrange, j = 1, 2, ..., m. Điều kiện cần để tồn tại cực trị địa phương của L( x, r ) là  ∂L   = 0; với i = 1, n ∂xi   g ( x ) = 0; với j = 1, m. j Như vậy, ta có (n + m) phương trình để xác định (n + m) ẩn. Phương pháp này có ưu điểm là nó cho phép đưa bài toán cực trị có điều kiện về bài toán cực trị không điều kiện, nhờ đó có thể vận dụng được nhiều phương pháp tìm cực trị khác nhau. Trường hợp ràng buộc đẳng thức thì đưa về giải hệ phương trình tuyến tính đối với bài toán cỡ nhỏ thì phương pháp này được dùng có hiệu quả. Tuy nhiên, muốn nhận biết nghiệm dừng là max hay min ta phải tiếp tục xét đạo hàm cấp hai của L, do đó phức tạp. 7 Phương pháp Carroll. Hàm mục tiêu f ( x ) → min(max), các ràng buộc gi ( x ) ≥ 0; i = 1, 2, ..., m. Hàm mục tiêu mở rộng được xây dựng ở đây m F ( x, r ) = f ( x ) ± rk wj ∑ gj (x) , j =1 • dấu ” + ” khi tìm min f ( x ) • dấu ” − ” khi tìm max f ( x ) • rk nhân tử ở bước lặp thứ k • w j trọng số. Phương pháp Fiacco và Cormick. hàm mục tiêu f ( x ) → min(max) với ràng buộc • gi ( x ) ≥ 0 với i = 1, n. • h j ( x ) = 0 với j = 1, m. Hàm mục tiêu mở rộng được xây dựng có dạng n F ( x, r ) = f ( x ) ± r ∑ i =1 −1 1 ±r 2 gi ( x ) m ∑ h j 2 ( x ). j =1 Phương pháp chọn r0 đối với F ( x, r ) → min . n 1 . i = 1 gi ( x ) không ở gần biên của ràng buộc Đặt p( x ) = ∑ Khi x (0) T −∇ f ( x0 ) p( x0 ) r0 = [∇ p( x0 )] 2 . Khi x0 ở gần biên của ràng buộc s r0 = ∇ f ( x 0 ) H −1 ∇ f ( x 0 ) , ∇ p ( x 0 ) H −1 ∇ p ( x 0 ) trong đó H là ma trận Hessian. Phương pháp Pietrzykoski. Hàm mục tiêu f ( x ) → min(max) với ràng buộc • gi ( x ) ≥ 0 với i = 1.n, 8 • h j ( x ) = 0 với j = 1, m. Hàm mục tiêu mở rộng m n j =1 i =1 F ( x, r ) = r f ( x ) − ∑ h j 2 ( x ) − ∑ wi gi 2 ( x ). Trong đó • wi = 1 đối với gi ( x ) ≥ 0, • wi = 0 đối với gi ( x ) < 0. Tiếp theo là phương pháp Sai lệch linh hoạt. Ý tưởng cơ bản của phương pháp này là mở rộng miền ràng buộc bằng cách đưa hàm T ( x ) là tổ hợp các ràng buộc. Như vậy bài toán (1) được đưa về dạng • Tìm cực tiểu của f ( x ) với x ∈ Rn . • Thỏa mãn ràng buộc φ(k) − T ( x ) ≥ 0. • Sai lệnh này so với ràng buộc ở bước lặp thứ k là   2  r +1  m + 1 ( k ) ( k ) ( k ) ( k − 1 )  φ = min φ , r +1 ∑ x i − x c , i   φ (0) = 2 ( m + 1 ) , trong đó – d là kích thước của đơn hình ban đầu. – xk (k) là điểm thứ i của đơn hình trong Rn . – r = n − m là số bậc tự do của f ( x ). – xc (k) là trọng tâm của đơn hình. Rõ ràng ta luôn có φ(0) ≥ φ(1) ≥ ... ≥ φ(k) ≥ 0 khi dần đến điểm cực tiểu thì kích thước đơn hình dần đến 0 và khi đó φ(k) → 0. tổ hợp ràng buộc là " T (x) = m p i =1 i = m +1 ∑ hi 2 ( x ) + ∑ 9 u i gi 2 ( x ) #1 2 . Trong đó ui = 0 khi gi ( x ) ≤ 0, ngược lại ui = 1. Khi quá trình tìm kiếm gần điểm cực tiểu thì φ(k) → 0 và T ( x ) = 0 hay hi ( x ) = 0 và gi ( x ) ≤ 0. Nhóm phương pháp cuối cùng là phương pháp tuyến tính hóa. Bằng cách thay đổi giả thiết của bài toán (1) thành bài toán tối ưu lồi với hàm mục tiêu tuyến tính.  f ( x ) → min với x ∈ D = x ∈ Rn : gi ( x ) ≤ 0, i = 1, m , (2) trong đó D là một tập lồi compact, khác rỗng và gi ( x ) là các hàm lồi khả vi trên Rn . Để giải bài toán (2) thì năm 1960 Kelley đã đề xuất phương pháp với tên gọi là phương pháp Siêu phẳng cắt Kelley với ý tưởng tuyến tính hóa ràng buộc. Tương tự, thay đổi giả thiết của bài toán (1) thành bài toán tối ưu lồi với ràng buộc tuyến tính như sau f ( x ) → min với x ∈ D = { x ∈ Rn : Ax ≤ b, x ≥ 0} , (3) trong đó • f ( x ) là hàm lồi. • A là ma trận cấp m × n. • b ∈ Rm . Giả thiết rằng • f ( x ) là hàm khả vi liên tục. • ∀ a ∈ D thì hàm tuyến tính x ∇ f ( a) bị chặn dưới trong miền D. Để giải bài toán (3) vào năm 1956 Marguerite Frank và Philip Wolfe đã đề xuất phương pháp tuyến tính hóa hàm mục tiêu có tên là phương pháp Frank- Wolfe. 10 Trên đây là một số phương pháp giải bài toán QHPT có ràng buộc, để vận dụng kiến thuc của QHTT đã được học ở chương trình đại học nên luận văn chọn hai phương pháp Frank- Wolfe và Kelley để tìm hiểu sâu hơn. Nội dung chính của bản luận văn bao gồm các vấn đề sau đây: • Tổng quan về các phương pháp giải bài toán QHPT. • Tóm tắt kiến thức liên quan. • Trình bày cụ thể hai phương pháp. Ví dụ và chạy kết quả bằng Maple. Do thời gian thực hiện khóa luận không nhiều, kiến thức còn hạn chế nên khi làm khóa luận không tránh khỏi những hạn chế và sai sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Xin chân thành cảm ơn! Hà Nội, ngày ... tháng ... năm 2014 Học viên Nguyễn Trường Giang 11 Chương 1 Một số kiến thức chuẩn bị 1.1. Một số khái niệm cơ sở Định nghĩa 1.1. [Tập lồi][9] Tập D ⊂ Rn được gọi là tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Hay nói cách khác D lồi nếu (1 − λ) a + λb ∈ D với mọi a, b ∈ D, 0 ≤ λ ≤ 1. Định nghĩa 1.2. [Tổ hợp lồi][9] Cho x1 , ..., x m là các vector trong không gian vector Rn , gọi m m ∑ λi x , ∑ λi = 1, λ ≥ 0, i i =1 là tổ hợp lồi của các vector i =1 x1 , x2 , ..., x m . Mệnh đề 1.1. Các tính chất của tập lồi • Tổng đại số hữu hạn tập lồi là tập lồi. • Giao của họ các tập lồi là tập lồi. • Tích đề các của các tập lồi là tập lồi. • Ảnh và nghịch ảnh của tập lồi qua ánh xạ tuyến tính cũng là lồi.    m m  • D = x  x = ∑ λi xi , xi ∈ D, ∑ λi = 1, λi ≥ 0, i = 1, 2, ..., m; m ≥ 1 . i =1 i =1 12 Định nghĩa 1.3. [9] Điểm w được gọi là điểm cực biên của tập lồi D nếu không tồn 1 1 tại hai điểm khác nhau x1 , x2 ∈ D sao cho w = x1 + x2 . Điều này tương đương 2 2 1 1 1 2 với việc nếu x , x ∈ D thảo mãn w = x1 + x2 thì w = x1 = x2 . Tập các điểm 2 2 cực biên của tập lồi ký hiệu là Ext( D ). Định nghĩa 1.4. [Bao lồi][9] Cho D là một tập hợp, bao lồi của D là giao của mọi tập lồi chưa D hay nói cách khác bao lồi của D là tập lồi nhỏ nhất chưa D. Bao lồi của D ký hiệu là co ( D ), hoặc conv( D ). Định nghĩa 1.5. [Hàm lồi][9] Hàm f ( x ) xác định trên tập lồi D được gọi là hàm lồi nếu ∀ x, y ∈ D, ∀λ ∈ [0, 1] : f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ) f (y) , nếu bất đẳng thức trên là thực sự thì với ∀λ ∈ [0, 1] thì hàm f được gọi là lồi chặt. Hàm lồi có rất nhiều tính chất giải tích quan trọng, ta quan tâm đến các tính chất tối ưu hóa sau • Cực tiểu địa phương là cực tiểu toàn cục. • Tập mức dưới L(α, f ) = { x ∈ D : f ( x ) ≤ a} là hàm lồi. • Điểm dừng là điểm cực tiểu toàn cục. • Nếu D là tập compact thì hạm đạt cực đại ít nhất một lần ở điểm cực biên. Ví dụ 1.1 (Kiểm tra hàm lồi). Kiểm tra hàm f : D ≡→, x 7→ f ( x ) = x2 là hàm lồi? Thật vậy, dễ thấy D là tập lồi. ∀ x, y ∈ D, ∀λ ∈ [0, 1] thì f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ ) f ( y ) . Định nghĩa 1.6. [Hàm khả vi][10] Giả sử hàm f xác định tại lân cận 0( x, ε) của điểm x. Ta nói hàm f là khả vi tại điểm x nếu tìm được vector f 0 ( x ) ∈ Rn sao cho số gia của hàm số tại x ∆ f ( x ) = f ( x + ∆x ) − f ( x ), k∆x ≤ εk , 13 có thể được viết lại ∆ f ( x ) = h f ( x + ∆x ), f ( x )i + o ( x, ∆x ), trong đó o ( x, ∆x ) là vô cùng bé bậc cao hơn k∆x ≤ εk nghĩa là o ( x, ∆x ) =0 k∆x k→0 k ∆x k lim khi đó f 0 ( x ) được gọi là gradient của hàm f tại x và được ký hiệu là ∇ f ( x ). Định nghĩa 1.7. [Hàm hai lần khả vi][10].Giả sử hàm f xác định tại lân cận 0( x, ε) của điểm x. Ta nói hàm f hai lần khả vi tại điểm x nếu cùng với vector f 0 ( x ), tồn tại ma trận đối xứng f 00 ( x ) ∈ Rn sao cho số gia của hàm số tại điểm x có thể viết dưới dạng  h f 00 ( x ), ∆x i ∆ f ( x ) = f ( x + ∆x ) − f ( x ) = f 0 ( x ), ∆x + + o ( x, ∆x ), 2 khi đó f 00 ( x ) được gọi là ma trận đạo hàm cấp hai hay Hessian của hàm f tại x. Định nghĩa 1.8. [Hàm khả vi liên tục][10].Giả sử hàm f đối xứng trên tập mở X, ta nói hàm f là khả vi liên tục trên tập X nếu f là khả vi tại mọi điểm x ∈ X và 0 f ( x + ∆x ) − f 0 ( x ) → 0 khi k∆x k → 0 với ∀ x, x + ∆x ∈ X. Định nghĩa 1.9. [Hàm hai lần khả vi liên tục][10].Giả sử hàm f xác định trên tập mở X. Ta nói hàm f là hai lần khả vi liên tục trân tập X nếu f là hai lần khả vi tại mọi điểm x ∈ X và 00 f ( x + ∆x ) − f 0 ( x ) → 0 khi k∆x k → 0 với ∀ x, x + ∆x ∈ X. Định nghĩa 1.10. [Ma trận xác định dương][10] Cho ma trận A ∈ Rn×n . Khi đó • A được gọi là nửa xác định dương nếu x t Ax ≥ 0 với mọi vector x ∈ Rn . • A được gọi là xác định dương nếu x t Ax > 0 với mọi vector x ∈ Rn . 14 • A được gọi là nửa xác định âm nếu x t Ax ≤ 0 với mọi vector x ∈ Rn . • A được gọi là xác định âm nếu x t Ax <0 với mọi vector x ∈ Rn .   1  −4 0  Ví dụ 1.2. Kiểm tra tính xác định dương của ma trận   0 − 14 Ta lấy x = [ x1 , x2 ]t ∈ R2 dùng định nghĩa có   −1 0  −1 2  2 n xt  4 −1  x = 4 ( x1 + x2 ) ≤ 0, với ∀ x ∈ R 0 4 Như vậy ma trận đã cho nửa xác định âm. Ngoài ra ta còn có tiêu chuẩn Silvestra để kiểm tra tính xác định dương của ma trận như sau: Ma trận A ∈ Rn×n là xác định dương hay xác định âm khi và chỉ khi tất cả các định thức con của ma trận đó tương ứng là dương hay âm. Định nghĩa 1.11. [Nghiệm cực tiểu địa phương][10]. Cho tập D là một tập con không thực sự của không gian vector Rn khi đó, điểm w ∈ D được gọi là nghiệm cực tiểu địa phương của f trên D nếu có ε > 0 sao cho f (w) ≤ f ( x ) với x ∈ D và k x − wk < ε. Nếu f (w) < f ( x ) với ∀ x ∈ D, x 6= w và k x − wk < ε thì w được gọi là nghiệm cực tiểu địa phương chặt của f trên D. Định nghĩa 1.12. [Nghiệm cực tiểu toàn cục][10]. Không gian vector Rn có tập con không thực sự D. Ký hiệu điểm w thuộc D được gọi là nghiệm cực tiểu toàn cục của hàm f trên D nếu f (w) ≤ f ( x ) với ∀ x ∈ D. Còn nếu f (w) < f ( x ) với mọi x thuộc D sao cho x 6= w thì w được gọi là nghiệm cực tiểu toàn cục chặt của f trên D. Định lý 1.1. (Định lý Weirstrass [Về sự tồn tại nghiệm tối ưu] )[10] Nếu hàm f liên tục, tập D compact và khác rỗng thì bài toán có nghiệm tối ưu. Định nghĩa 1.13. [Tập compact] [8] Tập A ⊂ X được gọi là tập compact nếu mỗi phủ mở của A ta luôn lấy ra được một phủ con hữu hạn. 15 (Tiêu chuẩn compact trên Rn ) Trong không gian Rn , một tập A là tập compact khi va chỉ khi nó đóng và bị chặn. Công thức Taylor. Giả sử X ∈ Rn mở, f : X → R khả vi cấp p − 1, hơn nữa giả sử f khả vi cấp p tại a ∈ X. Khi đó f 0 ( a)( x − a) f 00 ( a)( x − a)2 f (n) ( a)( x − a)n f ( x ) = f ( a) + + + ... + + R n ( x ). 1! 2! n! Công thức số gia hữu hạn. Giả sử hàm f khả vi liên tục trên một tập mở S và x là một vector nào đó trong S. Khi đó với ∀ vector y thỏa mãn x + y ∈ S luôn tìm được số α ∈ [0, 1] sao cho f ( x + y) − f ( x ) = f 0 ( x + αy), y =  Z1  f 0 ( x + ty), y dt. 0 1.2. Điều kiện tối ưu Như chúng ta đã biết thì đối với một bài toán qui hoạch nói chung và bài toán qui hoạch phi tuyến có ràng buộc hiển nói riêng thì việc xét điều kiện để tìm xem bài toán đó có nghiệm hay không được coi là việc đầu tiên trong quá trình giải quyết bài toán đó. Vì thế, việc tìm hiểu về những điều kiện để có nghiệm tối ưu cho bài toán QHPT có ràng buộc là rất quan trọng. Ta xét bài toán sau. Cho không gian vector Rn cho f : D → R là một hàm tùy ý xét bài toán tối ưu ràng buộc hiển sau đây f ( x ) → min, (1.1) gồm các điều kiện    gi ( x ) ≤ 0 với i = 1, m,   h j ( x ) = 0 với j = 1, p. Trước khi xét về các điều kiện tối ưu cho bài toán trên ta có các định nghĩa được bổ sung dưới đây. 16 Định nghĩa 1.14. [Hướng chấp nhận được][9] Trong không gian vector Rn cho tập con không thực sự D và một điểm w0 ∈ D. Một vector d ∈ Rn , d 6= 0 được gọi là hướng chấp nhận được của D tại điểm w0 nếu có một số t0 dương sao cho w0 + td ∈ D với mọi t ∈ [0, t0 ]. Điều này có nghĩa nếu đi từ điểm w0 và dọc theo hương d ta sẽ có tối thiểu một đoạn trong tập D. Định nghĩa 1.15. [Phương tiếp xúc][9] Trong không gian vector Rn cho tập con không thực sự D và một điểm w0 ∈ D. Ta nói rằng vector 0 6= d ∈ Rn là phương  tiếp xúc của D tại điểm w0 nếu có một dãy điểm wk ⊂ D với wk 6= w0 , wk → w0 ( w k − w0 ) và dãy số dương tk & 0 sao cho dk = → d khi k → +∞. tk Định nghĩa 1.16. [Nón tiếp xúc][9]Trong không gian vector Rn cho tập con không thực sự D và một điểm w0 ∈ D. Tập hợp tất các các phương tiếp xúc của D tại w0 cùng với vector 0 gọi là nón tiếp xúc (mũi tại 0) của D tại w0 , ký hiệu là TD (w0 ). Định nghĩa 1.17. [Nón chấp nhận được tuyến tính hóa][9]. Cho tập D là tập con không thực sự trong không gian vector Rn . Lấy một điểm w0 ∈ D. Giả sử rằng các hàm gi (i = 1, m), h j ( j = 1, p) khả vi. Ký hiệu S(w0 ) là tập tất cả các vector d ∈ Rn nghiệm đúng hệ phương trình và bất phương trình tuyến tính    ∇ gi (w0 )d ≤ 0, i ∈ I (w0 ),    ∇hi (w0 )d = 0, j = 1, p,      I ( x 0 ) =  i : g ( w0 ) = 0 . i (1.2) Khi đó, ký hiệu S(w0 ) gọi là nón chấp nhận được tuyến tính hóa. Bổ đề 1.1. Cho tập D là tập con không thực sự trong không gian vector Rn .Lấy điểm w0 ∈ D. Nếu mọi hàm gi và h j khả vi tại x0 và S(w0 ) là nón chấp nhận được tuyến tính hóa thì FD (w0 ) ⊆ TD (w0 ) ⊆ S(w0 ). 17 Chứng minh. Lấy bất kỳ d ∈ TD (w0 ). Nếu d = 0 rõ ràng d ∈ S(w0 ). Giả sử d 6= 0.   Theo định nghĩa (1.2.2) ta có dãy wk ∈ D, wk → w0 và dãy tk & 0 sao cho dk = ( w k − w0 ) tk → d. Do wk = w0 + tk dk ∈ D nên gi (wk ) = gi (w0 + tk dk ) = tk ∇ gi (w0 ) T wk + o (tk ) ≤ 0, i ∈ I (w0 ), h j ( x k ) = h j (w0 + tk dk ) = tk ∇h j (w0 ) T dk + o (tk ) ≤ 0, j = 1, p. Nếu ta đem hai vế của các bất đẳng thức trên chia cho tk > 0 và qua giới hạn khi k → ∞, ta nhận được ∇ gi (w0 ) T d ≤ 0 với mọi i ∈ I (w0 ) và∇h j (w0 ) T d > 0 với mọi j = 1, p nghĩa là d ∈ S(w0 ). Vì d ∈ Td (w0 ) được chọn tùy ý nên TD (w0 ) ⊆ S(w0 ). Hệ quả 1.1. Trong không gian vector Rn lấy tập D ⊆ Rn . Giả sử điểm w ∈ D và f ( x ), gi ( x ) với i = 1, m và h j ( x ) với j = 1, p, khả vi tại w. Nếu ∇ f ( x ∗ )d > 0 với ∀0 6= d ∈ S(w) thì w là cực tiểu địa phương chặt của bài toán (1.1). Ta xét các điều kiện tối ưu sau đây 1.2.1. Điều kiện cấp 1 Trước khi đi vào nội dung của điều kiện cấp 1, ta sẽ đưa ra các định nghĩa và tính chất liên quan tối điểm có cách gọi là điểm chính qui. Định nghĩa 1.18. [Điểm chính qui][10] Một điểm w0 ∈ D với D là một tập con không thực sự trong không gian vector Rn là điểm chính qui nếu TD (w0 ) = S(w0 ). Do vậy, điểm w0 thuộc D là điểm chính qui nếu thỏa mãn một trong điều kiện phát biểu sau • Các hàm ràng buộc gi ( x ), i ∈ I ( x0 ) và h j ( x ), j = 1, p là hàm afin. 18 • Các vector ∇ gi ( x0 ), i ∈ I ( x0 ), h j ( x0 ), j = 1, p là độc lập tuyến tính. • h j ( j = 1, p) là hàm afin và gi (i = 1, m) là hàm lồi và tồn tại điểm v thuộc D sao cho gi (v) < 0 với mọi i mà gi không phải là hàm afin. Bổ đề 1.2. (Bổ đề Farkas) [10] Trong không gian vector Rn cho trước vector p và A là ma trận cấp m × n. Muốn cho py ≥ 0 với mọi y nghiệm đúng Ay ≥ 0 khi và chỉ khi tồn tại vector v ∈ Rm sao cho v ≥ 0 và p = A T v (p biểu diễn được dưới dạng tổ hợp tuyến tính không âm các vector hàng của A). Chứng minh. Ta sẽ lần lượt chúng minh chiều xuôi (điều kiện cần) và chiều ngược (điều kiện đủ). • (Chiều xuôi) Giả sử trong không gian vectorRn cho trước vector p được định nghĩa p = A T v và v ≥ 0. Khi đó, với mọi y thỏa mãn Ay ≥ 0 ta sẽ có py = A T vy = vAy ≥ 0. • (Chiều ngược) Đặt G =  z ∈ Rn : ∃v ≥ 0, z = A T v , ta thấy rằng G là một nón lồi đa diện (z ∈ G ⇒ λz ∈ G, z1 , z2 ∈ G ⇒ z1 + z2 ∈ G ). Giả sử p ∈ /G ta sẽ chỉ ra tồn tại r thỏa mãn Ar ≥ 0 nhưng pr < 0. Thật vậy, nếu gọi q là hình chiếu của p trên G thì q = infc∈G kc − pk (q là điểm thuộc C gần p nhất). Điểm q tồn tại do G lồi đóng. Đặt r = q − p(r 6= 0 do p 6= q) hay p = q − r. ta thấy hai điều như sau Điều 1. r (z − q) ≥ 0. Vì nếu ngược lại thì trên đoạn nối liền z với q sẽ tìm được một điểm nằm gần p hơn q và do điểm này thuộc G nên điều này trái với q là hình chiếu của p (q là điểm thuộc G gần p nhất). Điều 2. r (z − q) = 0, vì nếu ngược lại thì trên đường thẳng nối q với gôc tọa độ tìm được một điểm nằm gần p hơn q và do điểm này thuộc G nên điều này trái với giả thiết q là hình chiếu của p (q là điểm thuộc G gần p nhất). 19