Tài liệu Phương pháp nón pháp tuyến giải bài toán tối ưu hóa đa mục tiêu và bài toán quy hoạch tích 272050

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - ĐỖ XUÂN HƯNG PHƯƠNG PHÁP NÓN PHÁP TUYẾN GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ BÀI TOÁN QUI HOẠCH TÍCH LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: TOÁN TIN Hà Nội - 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - ĐỖ XUÂN HƯNG PHƯƠNG PHÁP NÓN PHÁP TUYẾN GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ BÀI TOÁN QUI HOẠCH TÍCH Chuyên ngành: Toán Tin LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH: TOÁN TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. NGUYỄN THỊ BẠCH KIM Hà Nội - 2013 Mục lục Lời cảm ơn iii Lời mở đầu iv Danh mục các kí hiệu và chữ viết tắt ix 1 Nón pháp tuyến của tập lồi 1 1.1 Nón pháp tuyến của tập lồi . . . . . . . . . . . . . . . . 1 1.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Mối quan hệ giữa nón pháp tuyến và tập lồi đa diện 9 1.2 Điểm hữu hiệu và điểm hữu hiệu yếu của một tập . . . . 15 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Điều kiện hữu hiệu theo nón pháp tuyến . . . . . 19 2 Bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính 21 2.1 Bài toán qui hoạch lồi đa mục tiêu . . . . . . . . . . . . 22 2.2 Thuật toán nón pháp tuyến giải bài toán qui hoạch tuyến tính đa mục tiêu . . . . . . . . . . . . . 29 2.2.1 29 Cơ sở lý thuyết của thuật toán . . . . . . . . . . i 2.2.2 Thuật toán . . . . . . . . . . . . . . . . . . . . . 34 2.2.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . 42 3 Bài toán qui hoạch tích các hàm tuyến tính trên tập lồi 46 3.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . . 47 3.2 Cơ sở lý thuyết của thuật toán giải bài toán (MP Y ) . . 50 3.3 Thuật toán giải bài toán (MP Y ) . . . . . . . . . . . . . 58 Tài liệu tham khảo 71 Phụ lục 76 ii Lời cảm ơn Đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS.TS. Nguyễn Thị Bạch Kim, người đã tận tình, nghiêm khắc hướng dẫn, chỉ bảo để luận văn này được hoàn thành, cũng như giúp tôi tăng trưởng niềm đam mê nghiên cứu khoa học. Tôi xin chân thành cảm ơn Viện Toán ứng dụng và Tin học, Viện Đào tạo Sau Đại học, trường Đại học Bách khoa Hà Nội, đã tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu tại trường. Tôi xin được cảm ơn sự dạy dỗ, chỉ bảo và quan tâm của các thầy cô của Viện Toán ứng dụng và Tin học trong suốt thời gian tôi theo học và nghiên cứu. Tôi xin chân thành cảm ơn Phòng Giải tích số và Tính toán khoa học, Viện Toán học, nơi tôi đang công tác, đã tạo điều kiện thuận lợi cho tôi có cơ hội học tập. Tôi xin chân thành cảm ơn ThS. Trần Ngọc Thăng về việc hợp tác nghiên cứu và những trao đổi hữu ích giúp cho luận văn được hoàn thiện hơn. Cuối cùng, tôi muốn gửi lời cảm ơn chân thành tới gia đình bạn bè và đồng nghiệp, những người luôn động viên khích lệ giúp tôi hoàn thành luận văn này. Xin chân thành cảm ơn. Học viên: Đỗ Xuân Hưng Lớp: 11BTT-KH iii Lời mở đầu Bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính, kí hiệu là (MOP ), là bài toán tối ưu đồng thời p ≥ 2 hàm mục tiêu tuyến tính fj (x) = hcj , xi, cj ∈ Rn , i = 1, . . . , p, trên một tập lồi đóng khác rỗng X ⊂ Rn . Mô hình toán học của bài toán này là Min Cx với điều kiện x ∈ X, (MOP ) trong đó C là ma trận cấp p × n với các hàng c1 , . . . , cp. Trường hợp đặc biệt, khi tập chấp nhận được X là tập lồi đa diện, bài toán (MOP ) trở thành bài toán qui hoạch tuyến tính đa mục tiêu và kí hiệu là (MOLP ). Đây là trường hợp đơn giản nhất của tối ưu đa mục tiêu. Như đã biết, tuy tập nghiệm hữu hiệu XE và tập nghiệm hữu hiệu yếu XW E của bài toán qui hoạch tuyến tính đa mục tiêu (MOLP ) là các tập liên thông đường gấp khúc, bao gồm một số hữu hạn diện đóng của tập chấp nhận được X, nhưng nói chung, chúng là các tập không lồi và có cấu trúc phức tạp. Bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính có ý nghĩa ứng dụng quan trọng trong thực tế đặc biệt là trong lý thuyết quyết định, kinh tế, quản lý, công nghiệp, tài chính. . . Vì vậy, nó đã dành được sự quan tâm nghiên cứu của nhiều nhà toán học, chẳng hạn xem [3-4], [8], [15] và danh mục tài liệu tham khảo kèm theo. iv Một bài toán tối ưu toàn cục nảy sinh trong nhiều lĩnh vực thực tế khác nhau như kinh tế, tài chính, thiết kế chip điện tử. . . và liên quan gần gũi với bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính là bài toán qui hoạch tích các hàm tuyến tính trên tập lồi, kí hiệu là (MP X). Đó là bài toán cực tiểu một hàm mục tiêu là tích của p ≥ 2 hàm tuyến tính fj (x) = hcj , xi, cj ∈ Rn , i = 1, . . . , p, trên một tập lồi X khác rỗng trong Rn . Cho đến nay, đã có nhiều thuật toán đưa ra để giải bài toán này, chẳng hạn xem [5-7], [12], [14-16], [21], [22], [26] và danh mục tham khảo kèm theo. Mục đích của luận văn là nghiên cứu bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính và bài toán qui hoạch tích các hàm tuyến tính trên tập lồi. Do nhu cầu ứng dụng, việc nghiên cứu để đề xuất các thuật toán mới giải quyết hai bài toán này luôn là vấn đề có ý nghĩa khoa học và tính thời sự. Chúng tôi nghiên cứu các điều kiện hữu hiệu của bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính thông qua nón pháp tuyến của tập lồi chấp nhận được và giới thiệu thuật toán nón pháp tuyến [15] do N.T.B. Kim và Đ.T. Lục đề xuất năm 2000 để giải bài toán qui hoạch tuyến tính đa mục tiêu trong Chương 2. Chương 3 đề xuất một thuật toán trên không gian ảnh để giải bài toán qui hoạch tích các hàm tuyến tính trên tập lồi. Kết quả này đã được báo cáo tại Hội thảo Tối ưu và Tính toán khoa học lần thứ 11, tổ chức tại Ba Vì, ngày 24 - 27/04/2013. v Nội dung chính của Luận văn được trình bày trong ba chương. Cụ thể: Chương 1: Nón pháp tuyến của tập lồi. Chương này dành để nghiên cứu về nón pháp tuyến của tập lồi và điều kiện nhận biết một điểm hữu hiệu, hữu hiệu yếu của một tập lồi thông qua nón pháp tuyến của nó. Như đã biết, công thức tường minh để tính nón pháp tuyến của một tập lồi đa diện đã được biết đến, chẳng hạn xem [15] và [24]. Chúng tôi không tìm được công thức tính nón pháp tuyến của tập lồi trong bất kỳ tài liệu nào. Ở đây, công thức này đã được đưa ra trong Mệnh đề 1.1. Đây là cơ sở để chứng minh điều kiện hữu hiệu của bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính được đề xuất ở Chương 2 (Mệnh đề 2.2). Chương 2: Bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính. Mục đích của chương này là: i) Nghiên cứu về bài toán qui hoạch lồi đa mục tiêu với các hàm mục tiêu tuyến tính và đưa ra điều kiện nhận biết nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán này thông qua nón pháp tuyến của tập lồi chấp nhận được; ii) Giới thiệu thuật toán nón pháp tuyến [15] do N.T.B. Kim và Đ.T. Lục đề xuất năm 2000 để xác định toàn bộ tập nghiệm hữu hiệu của bài toán qui hoạch tuyến tính đa mục tiêu. Như đã biết, nếu đã biết toàn bộ tập đỉnh hữu hiệu của bài toán qui hoạch tuyến tính đa mục tiêu thì việc giải bài toán qui hoạch tích các hàm tuyến tính trên tập lồi đa diện tương ứng với nó (trường hợp đặc biệt của bài toán (MP X)) chỉ đơn giản là việc so sánh giá trị hàm mục tiêu tại các đỉnh hữu hiệu (Nhận vi xét 3.2). Tuy nhiên, do cấu trúc phức tạp của tập nghiệm hữu hiệu của bài toán (MOLP ) nên khối lượng tính toán để xác định toàn bộ tập đỉnh hữu hiệu của bài toán này tăng rất nhanh khi kích thước bài toán (tức số biến n, số hàm mục tiêu p, số ràng buộc của tập lồi đa diện chấp nhận được) tăng. Chương 3: Bài toán qui hoạch tích các hàm tuyến tính trên tập lồi. Trong chương này, chúng tôi nghiên cứu bài toán qui hoạch tích các hàm tuyến tính trên tập lồi (MP X) và đề xuất thuật toán với kỹ thuật xấp xỉ ngoài để giải bài toán trên không gian ảnh (MP Y ) tương ứng với nó. Thuật toán này được xây dựng dựa vào mối quan hệ giữa nghiệm tối ưu của bài toán (MP Y ) và điểm hữu hiệu của tập ảnh Y = C(X), trong đó C là ma trận cấp p × n với các hàng c1 , . . . , cp. Khi thuật toán kết thúc, ta nhận được nghiệm tối ưu của cả hai bài toán (MP X) và (MP Y ). Do p ≪ n nên thuật toán có thể cho phép tiết kiệm thời gian cũng như khối lượng tính toán. Thuật toán được chứng minh là hội tụ (Mệnh đề 3.10) và đã được lập trình tính toán thử nghiệm. Kết quả tính toán đã chứng tỏ tính hữu hiệu của thuật toán. Phụ lục của Luận án giới thiệu chương trình giải bài toán (MP X). Chương trình được viết trên ngôn ngữ lập trình MATLAB R2009a chạy trên môi trường Win 7. vii Luận văn được hoàn thành tại Viện Toán ứng dụng và Tin học, trường Đại học Bách khoa Hà Nội, dưới sự hướng dẫn của PGS.TS. Nguyễn Thị Bạch Kim. Mặc dù đã rất cố gắng, song luận văn không tránh khỏi thiếu sót. Rất mong nhận được sự góp ý của các thầy cô và các bạn. Xin chân thành cảm ơn. Hà Nội, ngày 26 tháng 05 năm 2013 viii Danh mục các kí hiệu và chữ viết tắt R tập số thực Rn không gian Euclid n chiều ∅ tập rỗng x∈M x thuộc tập M x∈ /M x không thuộc tập M ∀x ∈ M với mọi x thuộc tập M ∃x tồn tại x M ∩N giao của hai tập hợp M và N M ∪N hợp của hai tập hợp M và N M \N hiệu của hai tập hợp M và N M ⊂N M là một tập con thực sự của N M ⊆N M là một tập con của N |I| số phần tử của tập I [x1, x2] đoạn thẳng nối hai điểm x1 và x2 affX bao afin của tập X intX phần trong của tập X riX phần trong tương đối của tập X recX nón lùi xa của tập X cone{v 1, . . . , v k } nón sinh bởi các véc tơ v 1 , . . . , v k ∇g(x) véc tơ gradient của hàm g tại điểm x kxk chuẩn của x |x| giá trị tuyệt đối của x CT ma trận chuyển vị của ma trận C ix ha, xi tích vô hướng của hai véc tơ a và x Argmin(P ) tập nghiệm của bài toán (P ) v.đ.k. viết tắt của cụm từ "với điều kiện" KKT viết tắt của cụm từ "Karush Kuhn Tucker" x Chương 1 Nón pháp tuyến của tập lồi Chương này trình bày một số khái niệm và kết quả về nón pháp tuyến của tập lồi cần sử dụng trong các chương sau. Mục 1.1 trình bày khái niệm nón pháp tuyến, mối quan hệ giữa nón pháp tuyến và tập lồi đa diện đồng thời đề xuất công thức tính nón pháp tuyến của tập lồi. Khái niệm điểm hữu hiệu, điểm hữu hiệu yếu của một tập và điều kiện hữu hiệu theo nón pháp tuyến được trình bày ở Mục 1.2. Nội dung chính của chương được tham khảo trong [1], [15] và [19]. 1.1 1.1.1 Nón pháp tuyến của tập lồi Định nghĩa Cho tập lồi khác rỗng X ⊂ Rn và một điểm x0 ∈ X. Nón pháp tuyến trong (inner normal cone) của X tại x0 , kí hiệu là NX (x0), được xác định bởi NX (x0) = {v ∈ Rn |hv, x0i ≤ hv, xi, ∀x ∈ X}. 1 Để đơn giản, trong luận văn này ta gọi "nón pháp tuyến trong" là "nón pháp tuyến". Xem minh họa về nón pháp tuyến ở Hình 1.1. x0 X X 0 x b) a) Hình 1.1: Nón pháp tuyến của tập lồi X tại x0 . Dễ thấy rằng, véc tơ v ∗ ∈ NX (x0) khi và chỉ khi v ∗ là véc tơ pháp tuyến của một siêu phẳng tựa với tập X tại x0, hay điểm x0 là nghiệm tối ưu của bài toán qui hoạch lồi với hàm mục tiêu tuyến tính min hv ∗ , xi v.đ.k. x ∈ X. Nhắc lại rằng, siêu phẳng H = {x ∈ Rn |ha, xi = α, a ∈ Rn \ {0}, α ∈ R}, được gọi là siêu phẳng tựa (supporting hyperplane) với một tập Q ⊂ Rn tại điểm q 0 ∈ Q nếu hai điều kiện sau được thỏa mãn  i) q 0 ∈ H, tức là a, q 0 = α, ii) ha, qi ≥ α ∀q ∈ Q. Tập X ⊆ Rn được gọi là tập lồi (convex set) nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Nói cách khác, X ⊆ Rn là tập lồi nếu với mọi x1, x2 ∈ X và α bất kỳ thuộc đoạn [0, 1] thì ta có αx1 + (1 − α)x2 ∈ X. Hiển nhiên rằng, giao của một họ các tập lồi là tập lồi tuy nhiên hợp của một họ các tập lồi chưa chắc là tập lồi. 2 Một tập con lồi F ⊆ X được gọi là một diện (face) của X nếu nó chứa một điểm trong tương đối của một đoạn thẳng nào đó thuộc X thì nó chứa trọn cả đoạn thẳng đó, nói cách khác tập lồi con khác rỗng F ⊆ X là diện của X nếu x, y ∈ X, z = λx + (1 − λ)y ∈ F với 0 < λ < 1 ⇒ x, y ∈ F. Hàm số f xác định trên tập lồi X ⊆ Rn được gọi là hàm lồi (convex function) nếu f (λx1 + (1 − λ)x2) ≤ λf (x1) + (1 − λ)f (x2), ∀x1 , x2 ∈ X, 0 ≤ λ ≤ 1. Như đã biết (xem Mệnh đề 1.11, [1]), nếu f là hàm lồi xác định trên Rn thì với mỗi α ∈ R tập mức dưới Lα f = {x ∈ Rn |f (x) ≤ α} là tập lồi. Thông thường, tập lồi X ⊂ Rn được cho dưới dạng tập nghiệm của một hệ hữu hạn các bất phương trình gi(x) ≤ 0, i = 1, . . . , m, (1.1) ở đây gi(x), i = 1, . . . , m, là các hàm lồi khả vi liên tục trong Rn . Hình 1.2 minh họa tập lồi X ⊂ R2 là giao của 4 tập mức dưới L0gi = {x ∈ R2 |gi (x) ≤ 0}, i = 1, . . . , 4, trong đó gi : R2 → R, i = 1, . . . , 4, là các hàm lồi. Trường hợp đặc biệt, nếu tập lồi X ⊂ Rn được xác định bởi (1.1) với gi (x) là các hàm afin với mọi i = 1, . . . , m, thì X được gọi là tập lồi đa diện. Theo định nghĩa, tập lồi đa diện luôn là tập đóng. Nếu tập lồi đa diện bị chặn thì được gọi là đa diện. 3 g4 (x) g1 (x) g3 (x) X g2 (x) Hình 1.2: Tập lồi. Mỗi bất đẳng thức gi (x) ≤ 0, i ∈ {1, . . . , m}, được gọi là một ràng buộc của tập lồi X. Ràng buộc thứ i0, gi0 (x) ≤ 0, được gọi là thừa nếu {x ∈ Rn |gi (x) ≤ 0, i = 1, . . . , m} = {x ∈ Rn |gi (x) ≤ 0, i ∈ {1, . . . , m}\{i0}}. Cho X xác định bởi (1.1) và điểm x0 ∈ X. Nếu gi0 (x0) = 0, i0 ∈ {1, . . . , m}, thì ta nói ràng buộc thứ i0 được thỏa mãn chặt tại x0. Tập tất cả các chỉ số của các ràng buộc được thỏa mãn chặt tại x0 được kí hiệu là I(x0), I(x0) = {i0 ∈ {1, . . . , m}|gi0 (x0) = 0}. Tập khác rỗng K ⊆ Rn được gọi là một nón (cone) nếu với mỗi v ∈ K và t ≥ 0 thì ta có tv ∈ K. Tập K vừa là nón, vừa là tập lồi đa diện thì K được gọi là nón lồi đa diện. Cho v 1 , . . . , v k ∈ Rn . Nón sinh bởi các véc tơ v 1, . . . , v k , kí hiệu là cone{v 1, . . . , v k }, được xác định bởi 1 k n cone{v , . . . , v } = {v ∈ R |v = k X i=1 4 λi v i , λi ≥ 0, i = 1, . . . , k}. Nhận xét: Từ định nghĩa, dễ thấy, nếu x0 ∈ intX thì NX (x0) = {0}. Ở đây, intX là kí hiệu phần trong của tập X. Như đã biết, khái niệm nón pháp tuyến đóng vai trò quan trọng trong việc xây dựng các điều kiện tối ưu trong các bài toán qui hoạch toán học. Công thức tường minh tính nón pháp tuyến của tập lồi đa diện tại một điểm đã được đưa ra, chẳng hạn xem [15] và [24]. Theo hiểu biết của chúng tôi, chưa có công trình nào đề xuất công thức tính nón pháp tuyến của tập lồi tại một điểm. Công thức này được đưa ra và chứng minh trong kết quả sau đây. Mệnh đề 1.1. Cho tập lồi X xác định bởi (1.1) và một điểm xk ∈ X. Giả sử điều kiện Slater được thỏa mãn, tức ∃x̄ ∈ Rn sao cho gi (x̄) < 0 với mọi i = 1, . . . , m. Khi đó, nón pháp tuyến của X tại xk được tính theo công thức NX (xk ) = cone{−∇gi (xk ), i ∈ I(xk )}, trong đó ∇gi (xk ) là véc tơ gradient của hàm gi (x) tại điểm xk . Chứng minh: Lấy tùy ý v ∗ ∈ NX (xk ). Theo định nghĩa, xk ∈ X là nghiệm tối ưu của bài toán qui hoạch lồi thỏa mãn điều kiện Slater sau min hv ∗, xi v.đ.k. gi (x) ≤ 0, i = 1, . . . , m. (Pv∗ ) Theo Định lý Karush Kuhn Tucker (Định lý 6.13, [1]), xk là nghiệm tối 5 ưu của bài toán (Pv∗ ) khi và chỉ khi hệ sau có nghiệm  m P ∗  µi ∇gi(xk ) = 0 v +    i=1   µi gi(xk ) = 0, i = 1, . . . , m       µi ≥ 0, i = 1, . . . , m. Với mỗi i ∈ / I(xk ), ta có µi = 0 do gi (xk ) 6= 0. Do đó v∗ = − X µi ∇gi(xk ), trong đó µi ≥ 0, i ∈ I(xk ). i∈I(xk ) Điều này đồng nghĩa với v ∗ ∈ cone{−∇gi(xk ), i ∈ I(xk )}. Ngược lại, lấy tùy ý v ∗ ∈ cone{−∇gi(xk ), i ∈ I(xk )}. Theo định nghĩa P µi ∇gi(xk ). tồn tại µi ≥ 0, i ∈ I(xk ) sao cho v ∗ = − i∈I(xk ) Đặt µi = 0 với mọi i ∈ / I(xk ). Khi đó, hệ sau được thỏa mãn  m P ∗  µi ∇gi(xk ) = 0 v +    i=1   µi gi(xk ) = 0, i = 1, . . . , m       µi ≥ 0, i = 1, . . . , m. Theo Định lý Karush Kuhn Tucker, ta có xk là nghiệm tối ưu của bài toán (Pv∗ ). Do đó, v ∗ ∈ NX (xk ).  Công thức tính nón pháp tuyến của tập lồi đa diện tại một điểm có thể xem là hệ quả trực tiếp của Mệnh đề 1.1. Cụ thể, xét tập lồi đa diện P ⊂ Rn xác định bởi hệ hữu hạn các bất đẳng thức tuyến tính hai , xi − bi ≤ 0, i = 1, 2, . . . , m, trong đó a1 , . . . , am ∈ Rn , b1, . . . , bm ∈ R. Khi đó ta có kết quả sau. 6 (1.2) Hệ quả 1.2. (xem Bổ đề 3.1, [15] và Định lý 6.46, [24] ) Cho P ⊂ Rn là tập lồi đa diện xác định bởi hệ (1.2) và xk ∈ P . Khi đó, nón pháp tuyến của P tại xk ∈ P được xác định bởi NP (xk ) = cone{−ai , i ∈ I(xk )}, trong đó I(xk ) = {i ∈ {1, . . . , m}|hai , xk i − bi = 0}. Dưới đây là ví dụ minh họa cho công thức tính nón pháp tuyến. Ví dụ 1.1. Xét tập lồi X ⊂ Rn xác định bởi X = {x ∈ R2 |(x1 − 5)2 + (x2 − 5)2 − 9 ≤ 0, (x1 − 2)2 + (x2 − 2)2 − 9 ≤ 0} và điểm x0 = (5, 2)T ∈ X. Ta có g1 (x) = (x1 − 5)2 + (x2 − 5)2 − 9, g2 (x) = (x1 − 2)2 + (x2 − 2)2 − 9. Dễ thấy g1 , g2 : R2 → R là các hàm lồi và điều kiện Slater thỏa mãn. Ta có  ∇g1(x) =  2(x1 − 5) 2(x2 − 5)    , ∇g2 (x) =  2(x1 − 2) 2(x2 − 2) và I(x0) = {1, 2}.  ∇g1(x0) =  0 −6    , ∇g2(x0) =  7 6 0  .  , Suy ra NX (x0) = cone{−∇gi(x0), i ∈ I(x0)} = cone{(0, 6)T , (−6, 0)T }, hay NX (x0) = {v ∈ R2 |v = t1 (0, 6)T − t2 (6, 0)T , t1, t2 ≥ 0}, đây chính là góc phần tư thứ hai trong R2 . Xem Hình 1.3.  X x0 Hình 1.3: Nón pháp tuyến của X tại x0 . Ví dụ 1.2. Xét tập lồi đa diện P cho bởi P = {x ∈ R2 |x1 + x2 − 5 ≤ 0, −x1 ≤ 0, −x2 ≤ 0}, điểm x0 = (2, 3)T ∈ P và x1 = (0, 5)T . Ta có  a1 =  1 1    , a2 =  −1 0    , a3 =  0 −1  . Tại điểm x0 = (2, 3)T ta có I(x0) = {1}. Do đó NP (x0) = cone{−a1 } = cone{−(1, 1)T } = {v ∈ R2 |v = −λ(1, 1)T , λ ≥ 0}. 8