Luận văn Thạc sĩ Toán học: Phân tích không âm của ma trận

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

30
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài đã hệ thống một số kiến thức cơ sở trong đại số tuyến tính và lý thuyết tối ưu; phát biểu bài toán phân tích không âm của ma trận, nêu các ứng dụng trong phân tích dữ liệu, điều kiện cần tối ưu, trình bày thuật toán bình phương tối thiểu luân phiên, thuật toán Lee và Seung để giải bài toán phân tích không âm của ma trận và thử nghiệm số với bài toán nhận diện khuôn mặt.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phân tích không âm của ma trận

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------- Đoàn Thị Như Xuân PHÂN TÍCH KHÔNG ÂM CỦA MA TRẬN LUẬN VĂN THẠC SỸ TOÁN HỌC Hà Nội - 2019
BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------- Đoàn Thị Như Xuân PHÂN TÍCH KHÔNG ÂM CỦA MA TRẬN Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SỸ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ HẢI YẾN Hà Nội – 2019
Lời cam đoan Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, nghiên cứu của bản thân và sự hướng dẫn tận tình của cô giáo TS. Lê Hải Yến. Mọi kết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kỳ một hội đồng bảo vệ luận văn thạc sỹ nào và cũng chưa hề được công bố trên bất kỳ một phương tiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan trên. Hà Nội, ngày 28 tháng 06 năm 2019 Người cam đoan Đoàn Thị Như Xuân
Lời cảm ơn Trước khi trình bày nội dung chính của luận văn, tôi xin bày tỏ lòng biết ơn sâu sắc tới cô giáo TS. Lê Hải Yến, người đã dành nhiều thời gian, công sức để hướng dẫn và tận tình chỉ bảo tôi trong suốt quá trình thực hiện luận văn. Nhân đây tôi xin được gửi lời cảm ơn đến ban lãnh đạo và các thầy cô giáo, các cán bộ Học viện Khoa học và công nghệ nói chung và Viện Toán nói riêng đã tạo điều kiện thuận lợi nhất, giúp đỡ tôi trong thời gian học tập và nghiên cứu tại viện. Tôi xin cảm ơn các bạn trong chuyên ngành Toán ứng dụng đã động viên và có những ý kiến trao đổi quý báu trong thời gian qua. Cuối cùng tôi xin bày tỏ lòng biết ơn gia đình, người thân và các bạn đồng nghiệp đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và hoàn thành những công việc của mình. Hà Nội, ngày 28 tháng 06 năm 2019 Học viên Đoàn Thị Như Xuân
Mục lục Danh mục ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 MỞ ĐẦU 2 1 MỘT SỐ KIẾN THỨC CƠ SỞ 4 1.1 ĐẠI SỐ TUYẾN TÍNH . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Một số ma trận cơ bản, tích trong và tích Hadamard . . 4 1.1.2 Chuẩn . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Ma trận không âm . . . . . . . . . . . . . . . . . . . . 9 1.2 LÝ THUYẾT TỐI ƯU . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Điều kiện Kuhn-Tucker . . . . . . . . . . . . . . . . . 13 2 PHÂN TÍCH KHÔNG ÂM CỦA MA TRẬN 15 2.1 PHÁT BIỂU BÀI TOÁN . . . . . . . . . . . . . . . . . . . . 15 2.2 ỨNG DỤNG TRONG PHÂN TÍCH DỮ LIỆU . . . . . . . . . 17 2.2.1 Xử lý ảnh - Trích xuất đặc điểm khuôn mặt . . . . . . . 18 2.2.2 Khai thác văn bản - Khôi phục chủ đề và tài liệu . . . . 19 2.3 ĐIỀU KIỆN CẦN TỐI ƯU . . . . . . . . . . . . . . . . . . . 20 2.3.1 Hàm Lagrange . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Điều kiện cần tối ưu . . . . . . . . . . . . . . . . . . . 21 2.3.3 Đặc trưng của cực tiểu địa phương . . . . . . . . . . . 23
3 THUẬT TOÁN VÀ THỬ NGHIỆM SỐ 25 3.1 THUẬT TOÁN BÌNH PHƯƠNG TỐI THIỂU LUÂN PHIÊN . 25 3.2 THUẬT TOÁN LEE VÀ SEUNG . . . . . . . . . . . . . . . . 26 3.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.2 Định lí hội tụ . . . . . . . . . . . . . . . . . . . . . . 27 3.3 THỬ NGHIỆM SỐ VỚI BÀI TOÁN NHẬN DIỆN KHUÔN MẶT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 KẾT LUẬN 40
1 Danh mục ký hiệu R tập hợp các số thực Rn tập hợp các vector n chiều Rm×n tập hợp các ma trận cỡ m × n Rm×n + tập hợp các ma trận không âm cỡ m × n Ai: dòng thứ i của ma trận A A:j cột thứ j của ma trận A AT ma trận chuyển vị của ma trận A In ma trận đơn vị cấp n trace(A) vết của ma trận vuông A span(V ) không gian vector sinh bởi V rank(A) hạng của ma trận A kxk chuẩn Euclide của vector x kAkF chuẩn Frobenius của ma trận A hA, Bi tích trong của hai ma trận cùng cỡ A và B A◦B tích Hadamard của hai ma trận cùng cỡ A và B ∇f gradient của hàm f arg min f (x) tập nghiệm của bài toán min f (x) x ∈X x ∈X
2 MỞ ĐẦU Trong thời đại hiện nay, dữ liệu chiếm một vai trò vô cùng quan trọng. Cứ mỗi giây trôi qua, những người sử dụng internet tạo ra và chia sẻ hàng tỉ các thông tin khác nhau: hình ảnh, video, kinh nghiệm du lịch, mua sắm, ... Việc khai thác và sử dụng những thông tin hay dữ liệu này trở thành một vấn đề thu hút được sự quan tâm của rất nhiều người. Một trong những phương pháp khai thác dữ liệu là giảm độ phức tạp của dữ liệu trong khi vẫn giữ được những yếu tố cần thiết. Bên cạnh đó, để nghiên cứu các loại dữ liệu khác nhau, người ta cũng cần các mô hình khác nhau để thu được các thông tin riêng của dữ liệu. Luận văn nghiên cứu bài toán phân tích một ma trận không âm cho trước thành tích của hai ma trận không âm khác: Cho một ma trận không âm A cỡ m × n (tức là aij ≥ 0) và số nguyên dương r (r ≤ min(m, n)). Tìm hai ma m×r trận không âm U ∈ R+ và V ∈ Rn×r T + sao cho U V xấp xỉ ma trận A. Người ta có thể dùng nhiều cách để đo sự khác nhau giữa ma trận dữ liệu A và ma trận mô hình U V T . Nhưng phương pháp được dùng nhiều nhất là chuẩn Frobenius. Khi đó, bài toán phân tích ma trận không âm (viết tắt là NMF) được phát biểu lại như sau: Cho một ma trận không âm A cỡ m × n và một số nguyên dương r < min(m, n), giải bài toán 1 A − U V T 2 . min m×r n×r 2 F U ∈R+ V ∈R+ Bài toán phân tích ma trận không âm được phát biểu và nghiên cứu lần đầu tiên vào năm 1994 bởi Pateero và Tapper [5]. Từ đó đến nay, các nhà toán học đã đưa ra nhiều thuật toán tìm phân tích không âm của ma trận. Trong đó, phải kể đến thuật toán bình phương tối thiểu luân phiên [4] và thuật toán của Lee và Seung [6]. Bài toán này có ứng dụng trong nhiều lĩnh vực như nhận diện khuôn mặt, khai thác dữ liệu văn bản, phân loại ung thư, ... Trong nhận diện khuôn mặt, mỗi cột của ma trận dữ liệu A thường được cho tương ứng với một bức ảnh khuôn mặt (A(i, j) là cường độ của điểm ảnh thứ i trong bức ảnh khuôn mặt thứ j ). Khai triển NMF sinh ra hai ma trận (U, V ) trong đó mỗi cột của U tương ứng với một đặc điểm nào đó của khuôn mặt như mắt, mũi, miệng... và
3 các phần tử của V thể hiện tầm quan trọng của đặc điểm đó trong từng bức ảnh. Trong khai thác văn bản, mỗi cột của ma trận không âm A tương ứng với một tài liệu và mỗi hàng ứng với một từ. Phần tử (i, j) của ma trận A có thể bằng số lần xuất hiện của từ thứ i trong tài liệu thứ j . Khai triển NMF có thể giúp ta cho ta biết các chủ đề xuất hiện trong toàn bộ dữ liệu đồng thời phân loại các tài liệu theo chủ đề. Cấu trúc của luận văn gồm có ba chương: Chương 1. Một số kiến thức cơ sở: Nội dung của chương bao gồm một số kiến thức đại số tuyến tính và lý thuyết tối ưu nhằm phục vụ cho các chương sau. Chương 2. Phân tích không âm của ma trận: Trong chương này, chúng tôi trình bày nội dung bài toán phân tích không âm của ma trận, các ứng dụng trong phân tích dữ liệu. Chúng tôi cũng phát biểu điều kiện cần tối ưu cho bài toán. Chương 3. Thuật toán và thử nghiệm số: Hai thuật toán được trình bày trong chương này là thuật toán bình phương tối thiểu luân phiên và quy tắc nhân của Lee và Seung. Chúng tôi nghiên cứu bài toán nhận diện khuôn mặt và ứng dụng kĩ thuật phân tích không âm của ma trận vào bài toán cụ thể này.
4 CHƯƠNG 1 MỘT SỐ KIẾN THỨC CƠ SỞ Chương này trình bày lại một số khái niệm của đại số tuyến tính như tích trong, tích Hadamard, chuẩn của vector, chuẩn của ma trận, ma trận không âm. Bên cạnh đó, chúng tôi cũng trình bày một số khái niệm và kết quả cơ bản trong Lý thuyết tối ưu để phục vụ các chương sau như tập lồi và hàm lồi, điều kiện tối ưu, điều kiện Kuhn-Tucker. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1],[2],[4]. 1.1 ĐẠI SỐ TUYẾN TÍNH 1.1.1 Một số ma trận cơ bản, tích trong và tích Hadamard Cho A là một ma trận cỡ m × n với các phần tử ở hàng thứ i cột thứ j là aij . Khi đó, ta viết: A = (aij )m×n , trong đó: i = 1, 2, ..., m; j = 1, 2, ..., n. Ta kí hiệu dòng thứ i của ma trận A bởi Ai: và cột thứ j của ma trận A bởi A:j . Ma trận chuyển vị của ma trận vuông A được kí hiệu là AT ; A được gọi là đối xứng nếu A = AT . Ma trận vuông A cấp n được gọi là ma trận trực giao nếu AT A = In . D là ma trận đường chéo nếu D là ma trận vuông có aij = 0 với mọi i 6= j . Với x = (x1 , x2 , ..., xn ) ∈ Rn , Dx là ma trận đường chéo với các phần tử trên đường chéo là x1 , x2 , ..., xn . Ma trận A vuông cấp n được gọi là nửa xác định dương nếu xT Ax ≥ 0 ∀x ∈ Rn . A được gọi là xác định dương nếu xT Ax > 0 với mọi x ∈ Rn , x 6= 0. Nếu A đối xứng và nửa xác định dương thì tất cả các giá trị riêng của A đều không âm.
5 Vector hóa của ma trận A ∈ Rm×n là:   A  .:1  mn .   . ∈R . vec(A) =  A:n ! a b Ví dụ 1.1.1. Cho ma trận A = . c d   a   c Vector hóa ma trận A là: vec(A) =  b .    d Bằng cách vector hóa ma trận, ta có thể xem một ma trận tổng quát A cỡ m × n như một vector: vec(A) với m × n thành phần và có thể xác định tích trong của hai ma trận thực cùng cỡ như sau: X hA, Bi = vec(A)T vec(B) = aij bij = trace AT B . ij Ở đó, vết của ma trận vuông A (được kí hiệu trace(A)) là tổng của tất cả các phần tử đường chéo của ma trận A. Điều này suy ra một mối quan hệ mà chúng ta sẽ dùng ở chương sau: Mệnh đề 1.1.1. hI, ABCi = AT , BC = B T AT , C = C T B T AT , I = trace (ABC) . Chứng minh. Ta có: hI, ABCi = vec(I)T vec(ABC) = trace (IABC) = trace (ABC) . (1.1) T T A , BC = vec AT vec(BC) = trace (ABC) . (1.2) T T T B A , C = vec B T AT vec(C) = trace (B T AT )T C
6 = trace (AT )T (B T )T C = trace (ABC) . (1.3) T T T T C B A , I = vec C T B T AT vec(I) = trace (C T B T AT )T I = trace (AT )T (C T B T )T I = trace A(B T )T (C T )T = trace (ABC) . (1.4) Vậy từ (1.1),(1.2),(1.3),(1.4) ta có điều phải chứng minh. Tích Hadamard của hai ma trận A và B cùng cỡ m × n (kí hiệu A ◦ B ) là một ma trận cùng cỡ C với cij = aij bij .     1 2 3 4 1 1     Ví dụ 1.1.2. Cho hai ma trận A = 4 3 0  và B = 5 4 3.   2 1 5 0 1 2   4 2 3   Ta có: A ◦ B = 20 12 0  .  0 1 10 Mệnh đề 1.1.2. Với A, B, C là các ma trận cỡ m × n, ta có: (i) A ◦ B = B ◦ A ; (ii) A ◦ (B ◦ C) = (A ◦ B) ◦ C ; (iii) A ◦ (B + C) = (A ◦ B) + (A ◦ C); (iv) AT ◦ B T = (A ◦ B)T . Chứng minh. (i) A ◦ B = (aij bij )m×n = (bij aij )m×n = B ◦ A. (ii) A ◦ (B ◦ C) = (aij (bij cij ))m×n = ((aij bij )cij )m×n = (A ◦ B) ◦ C . (iii) A ◦ (B + C) = (aij (bij + cij ))m×n = (aij bij )m×n + (aij cij )m×n = (A ◦ B) + (A ◦ C). (iv) AT ◦ B T = (aji bji )m×n = (aij bij )Tm×n = (A ◦ B)T .
7 1.1.2 Chuẩn Định nghĩa 1.1.1. Một chuẩn vector trên Rn là một hàm f : Rn → R thỏa mãn các tính chất sau: (i) f (x) ≥ 0, ∀x ∈ Rn ; f (x) = 0 ⇔ x = 0; (ii) f (x + y) ≤ f (x) + f (y), ∀x, y ∈ Rn ; (iii) f (αx) = |α| f (x), ∀α ∈ R, ∀x ∈ Rn . Chuẩn của x thường được ký hiệu là kxk Cho vector x = (x1 , x2 , ..., xn )T , một số chuẩn vector thông dụng là: • Chuẩn p (p ≥ 1) 1 kxkp = (|x1 |p + ... + |xn |p ) p . • Chuẩn 1 (p = 1) kxk1 = |x1 | + ... + |xn |. • Chuẩn 2 (p = 2) hay gọi là chuẩn Euclide 1 12 2 2 2 T kxk = |x1 | + ... + |xn | = x x . • Chuẩn ∞ (p = ∞) kxk∞ = max (|x1 | , |x2 | , ..., |xn |) . Ví dụ 1.1.3. Cho vector x = (1, 2, 4)T . Chuẩn 1 của vector x là: kxk1 = 1 + 2 + 4 = 7. 21 √ Chuẩn Euclide của vector x là: kxk = 12 + 22 + 42 = 21. Chuẩn ∞ của vector x là: kxk∞ = max (1, 2, 4) = 4. Định nghĩa 1.1.2. Chuẩn ma trận trên Rm×n là hàm số f : Rm×n → R thỏa mãn các tính chất sau: (i) f (A) ≥ 0, ∀A ∈ Rm×n ; f (A) = 0 ⇔ A = 0.
8 (ii) f (A + B) ≤ f (A) + f (B), ∀A, B ∈ Rm×n ; (iii) f (αA) = |α| f (A), ∀α ∈ R, ∀A ∈ Rm×n . Kí hiệu: f (A) = kAk . Cho ma trận A = (aij )m×n , một số chuẩn ma trận thông dụng là: • Chuẩn 1 (chuẩn cực đại theo cột) m X kAk1 = max |aij |. 1≤j≤n i=1 • Chuẩn Frobenius. Kí hiệu:kAkF v u m X n uX kAkF = t |aij |2 . i=1 j=1 • Chuẩn ∞ (chuẩn cực đại theo hàng) n X kAk∞ = max |aij |. 1≤i≤m j=1 Ví dụ 1.1.4. Cho ma trận   4 2 3   A= −1 3 −2   0 1 5 a) Chuẩn 1 của ma trận A là: P3 kAk1 = max |aij | = max (|a1j | + |a2j | + |a3j |) 1≤j≤3 i=1 1≤j≤3 = max (|a11 | + |a21 | + |a31 | ; |a12 | + |a22 | + |a32 | ; |a13 | + |a23 | + |a33 | ) = max (4 + 1 + 0; 2 + 3 + 1; 3 + 2 + 5) = max(5; 6; 10) = 10. Frobenius của ma trận A là: b) Chuẩn s 3 P3 |aij |2 P kAkF = i=1 j=1 21 2 2 2 2 2 2 2 2 2 = |4| + |2| + |3| + |−1| + |3| + |−2| + |0| + |1| + |5| √ = 69.
9 c) Chuẩn ∞ của ma trận A là: P3 kAk∞ = max |aij | = max (|ai1 | + |ai2 | + |ai3 |) 1≤i≤3 j=1 1≤i≤3 = max (|a11 | + |a12 | + |a13 | ; |a21 | + |a22 | + |a23 | ; |a31 | + |a32 | + |a33 | ) = max (4 + 2 + 3; 1 + 3 + 2; 0 + 1 + 5) = max(9; 6; 6) = 9. 1.1.3 Ma trận không âm Định nghĩa 1.1.3. Ma trận A có tất cả các phần tử không âm được gọi là ma trận không âm. Kí hiệu: A ≥ 0. Rm×n + là tập hợp các ma trận không âm cỡ m × n. Chúng ta viết: A ≥ 0 nếu aij ≥ 0 ∀ i, j ; A > 0 nếu aij > 0 ∀ i, j . Một ma trận không âm gọi là chấp nhận được theo hàng nếu nó không có hàng bằng không. Tương tự, một ma trận không âm gọi là chấp nhận được theo cột nếu nó không có cột bằng không. Một ma trận không âm gọi là ngẫu nhiên cột (hàng) nếu tất cả các tổng cột (hàng) bằng một. Một trong những kết quả quan trọng liên quan đến ma trận không âm được trình bày sau đây: Định lý 1.1.1. Cho A là một ma trận vuông, không âm. Giá trị riêng lớn nhất của A là không âm và tồn tại một vector riêng không âm tương ứng với nó. Vector này thường gọi là vector Perron của ma trận không âm. Cho một tập con V ⊂ Rm×n và ma trận A ∈ Rm×n , phần tử gần nhất của V đến A (tương ứng với khoảng cách) được gọi là hình chiếu của A trên V , kí hiệu bởi PV (A). Nếu ta xét V là tập các ma trận không âm và khoảng cách xem xét là khoảng cách Euclide (chuẩn Frobenius), hình chiếu của A được kí hiệu là [A]+ và được cho bởi: ( aij khi aij > 0 [A]+ ij = = max(0, aij ). 0 khi aij ≤ 0
10 ! 1 0 Ví dụ 1.1.5. Cho ma trận A = . −2 3 ! 1 0 Hình chiếu của ma trận A lên R2×2 + là: [A]+ = . 0 3 1.2 LÝ THUYẾT TỐI ƯU 1.2.1 Tập lồi và hàm lồi Định nghĩa 1.2.1. Một tập con C ⊂ Rn được gọi là tập lồi nếu ∀x1 , x2 ∈ C; ∀λ ∈ [0, 1] ta có: λx1 + (1 − λ)x2 ∈ C. Ví dụ 1.2.1. Các nửa không gian là các tập lồi. Các tam giác và các hình tròn trong mặt phẳng là tập lồi. Tập hợp các ma trận không âm cỡ m × n ( Rm×n + ) cũng là một tập lồi. m×n Tập R+ là một trong những đối tượng chính được sử dụng trong luận văn này. Định nghĩa 1.2.2. Một tập C ⊂ Rn được gọi là nón lồi nếu nó đóng với phép cộng và phép nhân với một số không âm. u, v ∈ C ⇒ u + v ∈ C, u ∈ C, α ≥ 0 ⇒ αu ∈ C. Ví dụ 1.2.2. Rn+ là nón lồi. Định nghĩa 1.2.3. Một nón đa diện là một nón lồi được sinh bởi một tập các vector V = {v1 , v2 , ..., vk } ∈ Rn tức là: ( k ) X C= αi vi |αi ∈ R+ . i=1
11 Định nghĩa 1.2.4. Giả sử tập C ⊂ Rn là tập lồi. Hàm số f : C → R. Hàm f được gọi là hàm lồi trên C nếu ∀x1 , x2 ∈ C; ∀λ ∈ [0, 1] ta có: f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ) f (x2 ). Hàm f được gọi là hàm lồi chặt trên C nếu ∀λ ∈ (0, 1); ∀x1 6= x2 ∈ C ta có: f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ) f (x2 ). Mệnh đề 1.2.1. Cho k . k là một chuẩn tương ứng với tích vô hướng h., .i trên Rn . Khi đó: (i) k . k là hàm lồi trên Rn . (ii) k . k2 là hàm lồi trên Rn . Chứng minh. (i) Với mọi x, y ∈ Rn , λ ∈ [0, 1], ta có: kλx + (1 − λ)yk ≤ kλxk + k(1 − λ)yk = λ kxk + (1 − λ) kyk . (ii) Với mọi x, y ∈ Rn , λ ∈ [0, 1], ta có: kλx + (1 − λ)yk2 = hλx + (1 − λ)y, λx + (1 − λ)y i = λ2 kxk2 + 2λ(1 − λ) hx, yi + (1 − λ)2 kyk2 = λkxk + (1 − λ)kyk + (λ − λ)kxk + (1 − λ) − (1 − λ) kyk2 2 2 2 2 2 + 2λ(1 − λ) hx, yi Khai triển và giản ước ta được kết quả sau: λkxk2 + (1 − λ)kyk2 + λ(λ − 1)kxk2 + λ(λ − 1)kyk2 − 2λ(λ − 1) hx, yi = λkxk2 + (1 − λ)kyk2 + λ(λ − 1)kx − yk2 ≤ λkxk2 + (1 − λ)kyk2 . 1.2.2 Điều kiện tối ưu Xét bài toán: min f (x) (1.5) x∈C với C ⊂ Rn , f : C → R.
12 Định nghĩa 1.2.5. Điểm x∗ ∈ C được gọi là cực tiểu địa phương của bài toán (1.5) nếu ∃ε > 0 sao cho ∀x ∈ C ∩ B(x∗ , ε) ta có: f (x) ≥ f (x∗ ). Điểm x∗ ∈ C được gọi là cực tiểu địa phương ngặt của bài toán (1.5) nếu ∀x ∈ C ∩ B(x∗ , ε) và x 6= x∗ ta có: f (x) > f (x∗ ). Định nghĩa 1.2.6. Điểm x∗ ∈ C được gọi là cực tiểu toàn cục của bài toán (1.5) nếu ∀x ∈ C ta có: f (x) ≥ f (x∗ ). Điểm x∗ ∈ C được gọi là cực tiểu toàn cục ngặt của bài toán (1.5) nếu ∀x ∈ C , x 6= x∗ ta có: f (x) > f (x∗ ). Tập các hướng chấp nhận được tại x∗ ∈ C là: Z(x∗ ) = {d ∈ Rn |∃λ∗ > 0 : x∗ + λd ∈ C, ∀ 0 ≤ λ ≤ λ∗ } . Định lý 1.2.1. Giả sử tập C ⊂ Rn và f là một hàm khả vi trên C . Nếu x∗ là cực tiểu địa phương của f trên C thì: dT ∇f (x∗ ) ≥ 0, ∀d ∈ Z(x∗ ). Chứng minh. Lấy d ∈ Z(x∗ ) . Khi đó, tồn tại λ∗ sao cho ∀λ : 0 ≤ λ ≤ λ∗ thì x∗ + λd ∈ C. x∗ là cực tiểu địa phương có nghĩa là tồn tại ε > 0 sao cho: ∀x ∈ C ∩ B(x∗ , ε) thì f (x) ≥ f (x∗ ). ∗ ε Lấy λ1 = min λ , kdk Khi đó, ∀ 0 ≤ λ ≤ λ1 ta có: ( x∗ + λd ∈ C x∗ + λd ∈ B(x∗ , ε). Nên f (x∗ + λd) ≥ f (x∗ ), ∀0 ≤ λ ≤ λ1 (1.6) ∗ +td)−f (x∗ ) Ta lại có: dT ∇f (x∗ ) = lim+ f (x t ≥ 0 (do (1.6)). t→0 Định nghĩa 1.2.7. Điểm x∗ ∈ C thỏa mãn: dT ∇f (x∗ ) ≥ 0, ∀d ∈ Z(x∗ ) được gọi là điểm dừng của bài toán (1.5).
13 Mệnh đề 1.2.2. Giả sử x∗ ∈ int(C) và x∗ là điểm dừng của bài toán (1.5). Khi đó: Z(x∗ ) = Rn và ∇f (x∗ ) = 0. Chứng minh. Mệnh đề này được suy ra trực tiếp từ Định lý 1.2.1. Định lý 1.2.2. Giả sử C ⊂ Rn là tập lồi và f là hàm lồi. Khi đó, mọi cực tiểu địa phương của bài toán (1.5) cũng là cực tiểu toàn cục. Chứng minh. Giả sử x∗ ∈ C là cực tiểu địa phương của bài toán (1.5). Theo định nghĩa, tồn tại ε > 0 sao cho với mọi y ∈ B(x∗ , ε) ∩ C ta có: f (y) ≥ f (x∗ ). Với mọi x ∈ C , đặt d = x − x∗ . Khi đó tồn tại λ ∈ [0, 1] sao cho x∗ + λd ∈ B(x∗ , ε) ∩ C . Nên f (x∗ + λd) ≥ f (x∗ ). Lại có x∗ + λd = x∗ + λ(x − x∗ ) = λx + (1 − λ)x∗ . Do f lồi trên C nên f (x∗ +λd) = f (λx+(1−λ)x∗ ) ≤ λf (x)+(1−λ)f (x∗ ). Mà f (x∗ +λd) ≥ f (x∗ ) nên f (x∗ ) ≤ λf (x)+(1−λ)f (x∗ ) ⇔ f (x∗ ) ≤ f (x). Điều này đúng với mọi x ∈ C . Vậy x∗ là cực tiểu toàn cục của bài toán (1.5). 1.2.3 Điều kiện Kuhn-Tucker Xét bài toán tối ưu min f (x) (1.7) x∈C với C = {x : hi (x) = 0, gj (x) ≤ 0}. Trong đó: hi (x) = 0 (i = 1, 2, ..., k) là k ràng buộc đẳng thức và gj (x) ≤ 0 (j = 1, 2, ..., m) là m ràng buộc bất đẳng thức. Ràng buộc của bài toán này được viết trong hàm Lagrange như sau: k X m X L(x, µ1 , ..., µk , λ1 , ..., λm ) = f (x) + µi hi (x) + λj gj (x) i=1 j=1 Trong đó µi (i = 1, ..., k) và λj ≥ 0 (j = 1, ..., m) gọi là nhân tử Lagrange. Định lý 1.2.3. Cho x∗ là cực tiểu địa phương của bài toán (1.7). Giả sử rằng f, hi , gj : Rn → R là các hàm khả vi liên tục; ∇hi (x∗ ) và ∇gj (x∗ ) là độc lập
14 tuyến tính. Khi đó tồn tại µi (i = 1, ..., k) và λj (j = 1, ..., m) thỏa mãn các điều kiện sau: k m (i) ∇f (x∗ ) + µi ∇hi (x∗ ) + λj ∇gj (x∗ ) = 0, P P i=1 j=1 (ii) λj ≥ 0 (j = 1, ..., m), (iii) λj gj (x∗ ) = 0 (j = 1, ..., m). Các điều kiện (i) − (iii) được gọi là điều kiện Kuhn - Tucker (KT) của bài toán (1.7).