Tài liệu Bổ đề s và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 —————— ? —————— HÀ THỊ DUYÊN BỔ ĐỀ S VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC Hà Nội-2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 —————— ? —————— HÀ THỊ DUYÊN BỔ ĐỀ S VÀ ỨNG DỤNG Chuyên ngành: Toán Giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS Nguyễn Năng Tâm Hà Nội-2013 LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học sư phạm Hà Nội 2 dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Tác giả xin bày tỏ lòng biết ơn chân thành, sâu sắc tới PGS.TS Nguyễn Năng Tâm, người đã luôn quan tâm, động viên và tận tình hướng dẫn tác giả trong quá trình thực hiện luận văn. Tác giả xin được gửi lời cảm ơn chân thành Ban giám hiệu trường Đại học sư phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường và các thầy cô giáo dạy cao học chuyên ngành Toán giải tích đã tạo điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Tác giả xin bày tỏ lòng biết ơn tới gia đình, người thân đã động viên và tạo mọi điều kiện để tác giả có thể hoàn thành bản luận văn này. Hà Nội, tháng 07 năm 2013 Tác giả Hà Thị Duyên LỜI CAM ĐOAN Tôi xin cam đoan Luận văn là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn trực tiếp của PGS.TS Nguyễn Năng Tâm. Trong quá trình nghiên cứu, tôi đã kế thừa thành quả khoa học của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 07 năm 2013 Tác giả Hà Thị Duyên v Mục lục Bảng kí hiệu và viết tắt Mở đầu vii ix Nội dung 1 1 Kiến thức chuẩn bị 1 1.1 Không gian véc tơ Ơclit . . . . . . . . . . . . . . . . . . . 1 1.2 Không gian các ma trận . . . . . . . . . . . . . . . . . . . 2 1.3 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Bài toán tối ưu và hàm Lagrange . . . . . . . . . . . . . . 7 1.5 Kết luận chương 1 . . . . . . . . . . . . . . . . . . . . . . 9 2 Bổ đề S 10 2.1 Bổ đề S . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Một số chứng minh khác nhau của bổ đề S . . . . . . . . . 13 2.2.1 Phương pháp cổ điển . . . . . . . . . . . . . . . . . 14 2.2.2 Phương pháp hiện đại . . . . . . . . . . . . . . . . 18 2.2.3 Phương pháp chứng minh thứ ba . . . . . . . . . . 23 Một số trường hợp đặc biệt và phản ví dụ . . . . . . . . . 26 2.3.1 26 2.3 Một số trường hợp đặc biệt . . . . . . . . . . . . . vi 2.3.2 2.4 3 Một số kết quả tổng quát . . . . . . . . . . . . . . 27 Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . . . 34 Một số định lý luân phiên và ứng dụng của bổ đề S 35 3.1 Phân tích ổn định hệ động lực . . . . . . . . . . . . . . . . 35 3.2 Hệ của hai bất đẳng thức toàn phương . . . . . . . . . . . 37 3.2.1 Hệ toàn phương thuần nhất . . . . . . . . . . . . . 38 3.2.2 Hệ không thuần nhất . . . . . . . . . . . . . . . . 43 3.2.3 Điều kiện cần và đủ của tối ưu toàn cục . . . . . . 49 Hệ của ba bất đẳng thức toàn phương . . . . . . . . . . . 52 3.3.1 Hệ toàn phương thuần nhất . . . . . . . . . . . . . 52 3.3.2 Hệ không thuần nhất . . . . . . . . . . . . . . . . . 62 3.3.3 Điều kiện tối ưu đối với bài toán miền tin cậy . . . 65 3.3 3.4 Hệ của hữu hạn bất đẳng thức toàn phương. 3.4.1 69 Điều kiện tối ưu cho quy hoạch toàn phương tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Ứng dụng vào bài toán CDT . . . . . . . . . . . . . 74 Kết luận chương 3 . . . . . . . . . . . . . . . . . . . . . . 78 3.4.2 3.5 . . . . . . . Kết luận 79 Tài liệu tham khảo 80 vii Bảng kí hiệu và viết tắt R : Tập hợp các số thực. Rn : Không gian Euclide n chiều. Rn+ : Tập hợp tất cả các véc tơ không âm của Rn . intRn+ : Phần trong của Rn+ . Y ⊂ X : Y là tập con của X. dim(V ) : Số chiều của không gian V . hx, yi : Tích vô hướng của hai véc tơ x, y. domf : Miền xác định hữu hiệu của f . epif : Đồ thị của hàm f . sup : Cận trên đúng. inf : Cận dưới đúng. Lα f : Tập mức dưới của f . L (x, λ1 , ..., λm ) : Hàm Lagrange. |λ| : Giá trị tuyệt đối của số thực λ. kxk : Chuẩn của phần tử x. Rn×n : Tập các ma trận cấp n × n. viii S n : Không gian các ma trận đối xứng cấp n × n. S+n : Tập hợp các ma trận đối xứng nửa xác định dương cấp n × n. In : Ma trận đồng nhất cấp n × n. P  0 : P là ma trận đối xứng xác định dương. P 0 : P là ma trận đối xứng nửa xác định dương. T rA : Vết của ma trận A. A ∗ B : Vết của ma trận tích AB. rankA : Hạng của ma trận A. x = (x1 , x2 , ..., xn ) : Véc tơ trong không gian Rn . x = (x1 , x2 , ..., xn ) ≥ 0 : Các số xi ≥ 0, i = 1, ..., n. u2:n : Kí hiệu cho véc tơ (u2 , ..., un )T . max : Giá trị lớn nhất. min : Giá trị nhỏ nhất. ix Mở đầu 1. Lí do chọn đề tài Bổ đề S được Yakubovich đưa ra trong [6], là một kết quả nổi tiếng của lý thuyết điều khiển, cho ta một điều kiện tương đương với tính không âm của một hàm toàn phương bất kì f (x) trên một miền D xác định bởi một bất phương trình toàn phương tùy ý g (x) ≤ 0 khi điều
kiện Slater (tồn tại x0 để g x0 < 0) được thỏa mãn. Cụ thể là: Cho f, g : Rn → R là hai hàm toàn phương. Khi đó, nếu tồn tại x0 ∈ Rn sao
cho g x0 < 0 thì [g (x) ≤ 0 ⇒ f (x) ≥ 0] ⇔ [∃µ ≥ 0, ∀x ∈ Rn : f (x) + µg (x) ≥ 0] . Bổ đề S được xem như một khái quát hóa những kết quả trước đó của Hestenes - McShane và Dines [3]. Sau đó Megretsky - Treil mở rộng kết quả cho không gian vô hạn chiều. Bổ đề S có những hệ quả hiệu lực đáng ngạc nhiên trong tối ưu hóa thô (robust optimization) và trong lý thuyết điều khiển, vì nó cho phép thay thế những bài toán tối ưu không lồi cụ thể bằng những bài toán lồi giải được với thời gian đa thức [7]. Về lịch sử và những ứng dụng của Bổ đề S có thể tìm thấy trong bản tổng quan tuyệt vời của Polik - Terlaky [5]. Bổ đề S được chứng minh lần đầu tiên vào năm 1971. Từ đó đến nay, Bổ đề S đã được chứng minh và mở rộng theo nhiều cách khác nhau. Cùng với thời gian, Bổ đề S ngày càng tỏ ra là một công cụ hiệu quả, được sử dụng rộng rãi trong lý thuyết điều khiển, đặc biệt trong phân tích ổn x định những hệ phi tuyến. Bổ đề S cũng có những ứng dụng quan trọng trong Quy hoạch toàn phương. Chính vì thế, Bổ đề S luôn giữ được sự quan tâm trong dạng phát biểu đẹp và đơn giản của nó. Nhiều tác giả trong và ngoài nước đã quan tâm nghiên cứu những khía cạnh khác nhau của Bổ đề S (xem [5], [6] và những tài liệu dẫn trong đó). Sau khi được học những kiến thức về Toán giải tích, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học, mối quan hệ và ứng dụng của chúng, tôi đã chọn đề tài nghiên cứu: " Bổ đề S và ứng dụng". Luận văn bao gồm ba chương: Chương 1: Kiến thức chuẩn bị. Chương 2: Bổ đề S. Chương 3: Một số định lý luân phiên và ứng dụng của bổ đề S. 2. Mục đích nghiên cứu Tìm hiểu về Bổ đề S và những ứng dụng của nó. 3. Nhiệm vụ nghiên cứu Nghiên cứu Bổ đề S cùng một số ứng dụng của nó vào lý thuyết tối ưu. 4. Đối tượng và phạm vi nghiên cứu + Đối tượng: Bổ đề S và ứng dụng vào nghiên cứu điều kiện tối ưu. + Phạm vi: Trong không gian Ơclit. xi 5. Phương pháp nghiên cứu Tổng hợp kiến thức thu thập được qua những tài liệu liên quan đến đề tài, sử dụng các phương pháp nghiên cứu của giải tích hàm. 6. Giả thuyết khoa học + Nghiên cứu và làm rõ được Bổ đề S. + Tổng hợp, hệ thống một số kết quả đã được các nhà khoa học nghiên cứu và công bố về Bổ đề S và ứng dụng. 1 Chương 1 Kiến thức chuẩn bị Chương này trình bày những kiến thức cơ bản, được áp dụng cho chương sau nên các kết quả không chứng minh. Các kết quả này được lấy từ [2]. 1.1 Không gian véc tơ Ơclit Dưới đây là các định nghĩa và tính chất về không gian véc tơ Ơclit và các kiến thức có liên quan như tích vô hướng, góc giữa hai véc tơ,. . . Định nghĩa 1.1.1. Cho V là không gian véc tơ thực, tích vô hướng của hai véc tơ x, y là một số thực , ký hiệu hx, yi thỏa mãn các tính chất sau: 1. hx, yi = hy, xi ∀x, y ∈ V 2. hλx, yi = λ hx, yi ∀x, y ∈ V    3. x1 + x2 , y = x1 , y + x2 , y ∀x1 , x2 , y ∈ V 4. hx, xi ≥ 0, hx, xi = 0 ⇔ x = 0 ∀x, y ∈ V Không gian véc tơ thực hữu hạn chiều V trên đó xác định một tích vô hướng gọi là không gian Ơclit, ký hiệu là E. 2 Định nghĩa 1.1.2. (Độ dài của một véc tơ) Giả sử E là một không gian Ơclit. Khi đó chuẩn hay độ dài của một véc tơ x ∈ E là đại lượng p kxk := hx, xi. Nhận xét 1.1.1. Trong Rn ta định nghĩa tích vô hướng như sau: hx, yi = n X xi yi , x = (x1 , ..., xn ), y = (y1 , ..., yn ). i=1 Định nghĩa 1.1.3. (Góc giữa hai véc tơ) Giả sử E là một không gian Euclid. Với mọi véc tơ x, y 6= 0 của E, ta gọi góc giữa x và y là góc α với 0 ≤ α ≤ π sao cho cosα = hx, yi . kxk . kyk Khái niệm trên phù hợp với khái niệm góc thông thường trong hình học. Theo định nghĩa trên hai véc tơ x, y vuông góc với nhau khi và chỉ khi hx, yi = 0. Định nghĩa 1.1.4. Giả sử S1 , S2 là hai tập hợp các véc tơ trong E. Ta gọi S1 trực giao (vuông góc) với S2 nếu hx, yi = 0 với mọi véc tơ x ∈ S1 , y ∈ S2 . 1.2 Không gian các ma trận Phần này trình bày về các ma trận thường gặp và các phép toán trên ma trận. Định nghĩa 1.2.1. Cho m và n là hai số tự nhiên. Một m × n ma trận là một bảng số hình chữ nhật gồm m dòng và n cột. Kí hiệu (aij ), trong đó aij ký hiệu số ở dòng i cột j (i = 1, ..., m, j = 1, ..., n). Các số aij được gọi là các phần tử của ma trận. 3 Định nghĩa 1.2.2. (Ma trận vuông) Một ma trận vuông A = (aij ) là ma trận có số dòng bằng số cột. Số dòng của ma trận vuông gọi là cấp của ma trận đó. Hệ các phần tử aii của A có cùng chỉ số dòng và cột được gọi là đường chéo chính của A. Định nghĩa 1.2.3. Ma trận vuông I = (aij ) cấp n mà aij = 1 nếu i = j, và aij = 0 nếu i 6= j được gọi là ma trận đơn vị cấp n. Sau đây ta chỉ xét các ma trận có phần tử trong một trường số thực R. Định nghĩa 1.2.4. Cho A = (aij ), B = (bij ) và c ∈ R ta có thể định nghĩa phép cộng A + B và phép nhân vô hướng cA như sau: A + B = (aij + bij ) , cA = (caij ). Ta kí hiệu L(m, n) là tập hợp tất cả các m × n ma trận. Mệnh đề 1.2.1. L(m, n) là một không gian véctơ với dim L(m, n) = mn. Chứng minh. Ta có thể coi các m × n ma trận như là các bộ gồm m × n phần tử của R. Khi đó L(m, n) chính là không gian véc tơ Rmn . Định nghĩa 1.2.5. Giả sử A = (aij ) là một m × n ma trận và B = (bjk ) là một n × p ma trận. Ma trận tích AB là m × p ma trận (dik ) với dik = ai1 b1k + ai2 b2k + ... + ain bnk . Phép nhân hai ma trận chỉ có thể thực hiện được khi ma trận thứ nhất có số cột bằng số dòng của ma trận thứ hai. 4 Định nghĩa 1.2.6. Ma trận nhận được từ một ma trận A bằng việc đổi các dòng thành các cột được gọi là ma trận chuyển vị của A, kí hiệu là AT . Nếu A = (aij ) là một m × n ma trận thì AT = (a0 ji ) là một n × m ma trận với a0 ji = aij (i = 1, ..., m, j = 1, ..., n). Nhận xét 1.2.2. Phép chuyển vị có những tính chất sau:
T AT = A, (A + B)T = AT + B T ,
(cA)T = c AT . Các tính chất này cho thấy ánh xạ A → AT là một đẳng cấu giữa hai không gian véc tơ L(m, n) và L(n, m). Định nghĩa 1.2.7. Cho A là một ma trận vuông cấp n. Một ma trận vuông B cấp n được gọi là ma trận nghịch đảo của A nếu AB = BA = I. Nếu A có ma trận nghịch đảo thì A được gọi là khả nghịch. Nếu A là khả nghịch thì A có duy nhất một ma trận nghịch đảo. Định nghĩa 1.2.8. Một ma trận vuông A = (aij ) được gọi là ma trận đường chéo nếu aij = 0 với mọi i 6= j, có nghĩa là tất cả các phần tử nằm ngoài đường chéo chính của A đều bằng 0. Định nghĩa 1.2.9. Một ma trận vuông A = (aij ) được gọi là ma trận đối xứng nếu aij = aji với mọi chỉ số i, j. Điều này có nghĩa là AT = A. Ma trận A được gọi là một ma trận đối xứng lệch nếu aij = −aji với mọi chỉ số i, j. Điều này có nghĩa là AT = −A. 5 Định nghĩa 1.2.10. Cho A, B là hai ma trận vuông cấp n. Khi đó tích vô hướng của hai ma trận A và B được xác định bởi A ∗ B = T r(AB) = Pn Pn i=1 j=1 aij bji , trong đó aij là phần tử (i, j) của A, bji là phần tử (j, i) của B. Nhận xét 1.2.3. Cho A, B là hai ma trận vuông cấp n. Khi đó ta có một số tính chất : 1. A ∗ B = T r(AB) = T r(BA).
2. A ∗ xxT = xT Ax với mọi x ∈ Rn và a ∈ S n . 3. Nếu A và B là hai ma trận nửa xác định dương thì A ∗ B ≥ 0. 1.3 Tập lồi và hàm lồi 1.3.1 Tập lồi Định nghĩa 1.3.1. Tập hợp C ⊂ X được gọi là lồi nếu với mọi cặp điểm x, y ∈ C ta có (x, y) ⊂ C. Trong đó (x, y) = {λx + (1 − λ) y |λ ∈ [0, 1]}. Nhận xét 1.3.1. Giao của một họ các tập lồi là lồi. Nếu A và B là các tập lồi và α ∈ R, thì các tập A + B, αA cũng lồi. Định nghĩa 1.3.2. (Nón lồi) Một tập K ⊂ X được gọi là nón nếu mọi điểm k ∈ K và λ > 0 ta có λk ∈ K. Hơn nữa nếu K là tập lồi thì nó sẽ P được gọi là nón lồi. Một tổ hợp tuyến tính m i=1 λi ai sẽ được gọi là một tổ hợp dương nếu λi ≥ 0 với mọi i là tổ hợp dương không tầm thường nếu tồn tại ít nhất một hệ số λi dương chặt. Nhận xét 1.3.2. Giao của một họ bất kỳ các nón lồi là một nón lồi. 6 Định lí 1.3.3. (Định lý Caratheodory) Giả sử dim X = n < ∞và A ⊂ X. Lúc đó, với mọi X ∈ coA, x là một tổ hợp lồi của một họ không quá n + 1 véc tơ thuộc A. Tức là tồn tại hệ {a0 , a1 , ..., am } ⊂ A và các số λ0 , ..., λm ≥ 0, với m ≤ n, sao cho m P 0 λi = 1 và x = m P λi ai . 0 Định lí 1.3.4. (Định lý tách tập lồi) Cho A và B là hai tập con của không gian véc tơ X. Một phiếm hàm tuyến tính f ∈ X ∗ | {0} được gọi là tách A và B nếu f (a) ≤ f (b) (hoặc f (a) ≥ f (b)); a ∈ A, b ∈ B. Điều này tương đương với tồn tại một số α ∈ R sao cho f (a) ≤ α ≤ f (b) ∀a ∈ A, b ∈ B. Lúc đó, ta nói siêu phẳng H (f ; α) = f −1 (α) = {x ∈ X| f (x) = α}, tách A và B. Trường hợp B là tập một điểm B = {x0 }, ta nói đơn giản H (f ; α) tách A và x0 . Rõ ràng siêu phẳng tách hai tập, nếu có là không duy nhất. Định lí 1.3.5. (Định lý tách cơ bản) Cho A và B là hai tập lồi khác rỗng, coreA 6= ∅ và A ∩ B = ∅. Lúc đó tồn tại siêu phẳng tách A và B. 1.3.2 Hàm lồi Định nghĩa 1.3.3. Hàm f : X → R được gọi là thuần nhất dương nếu f (λx) = λf (x) ; ∀x ∈ X, ∀λ > 0. 7 Định nghĩa 1.3.4. (Hàm lồi) Cho hàm f : X → R ∪ {−∞, ∞} thì domf := {x ∈ X/f (x) < ∞} là miền xác định hữu hiệu và epif := {(α, x) ∈ R × X/f (x) 6 α} là đồ thị (epigraph) của f . Hàm f được gọi là thật nếu domf 6= ∅ và f (x) > −∞ với mọi x ∈ X. Hàm f là một hàm lồi nếu epif là một tập lồi trong R × X. Mệnh đề 1.3.6. Cho f : X → R lồi khi và chỉ khi f (λx1 + (1 − λ) x2 ) 6 λf (x1 ) + (1 − λ) f (x2 ) , ∀x1 , x2 ∈ X, λ ∈ [0, 1] . Định lí sau đây đưa ra một số tính chất quan trọng của hàm lồi đối với bài toán cực trị. Định lí 1.3.7. Chof : X → R là một hàm lồi thật. (i) Mọi tập mức dưới Lα f := {x ∈ X/f (x) 6 α} (1.1) là lồi (∀α ∈ R). (ii) Mỗi điểm cực tiểu địa phương của f là một điểm cực tiểu toàn cục. (iii) Mỗi điểm dừng của f là một điểm cực tiểu toàn cục. 1.4 Bài toán tối ưu và hàm Lagrange Định nghĩa 1.4.1. (Bài toán tối ưu) Bài toán tối ưu tổng quát được phát biểu như sau: min f (x) với điều kiện x ∈ D, (P 1) 8 hoặc max f (x) với điều kiện x ∈ D, (P 2) trong đó D ⊆ Rn được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và f : D → R là hàm mục tiêu. Mỗi điểm x ∈ D được gọi là một nghiệm chấp nhận được hay một phương án chấp nhận được ( gọi tắt là một phương án). Điểm x∗ ∈ D mà f (x∗ ) 6 f (x) ∀x ∈ D được gọi là nghiệm tối ưu, hoặc nghiệm tối ưu toàn cục, hoặc nghiệm cực tiểu toàn cục, hoặc là nghiệm của bài toán (P1).Người ta còn gọi một nghiệm tối ưu là một phương án tối ưu hay lời giải của bài toán đã cho. Điểm x∗ ∈ D được gọi là nghiệm cực tiểu toàn cục chặt nếu f (x∗ ) < f (x) ∀x ∈ D và x 6= x∗ . Không phải bài toán (P1) nào cũng có nghiệm cực tiểu toàn cục nếu bài toán có nghiệm cực tiểu toàn cục thì cũng chưa chắc có nghiệm cực tiểu toàn cục chặt. Giá trị tối ưu (hay giá trị cực tiểu) của bài toán (P1) được kí hiệu là min f (x) hoặc min {f (x) |x ∈ D } . x∈D Nếu bài toán (P1) có nghiệm tối ưu là x∗ thì f (x∗ ) = min {f (x) |x ∈ D } . Ta kí hiệu Arg min {f (x) |x ∈ D } là tập nghiệm tối ưu của bài toán (P1). Nếu bài toán chỉ có một nghiệm tối ưu x∗ thì có thể viết x∗ = arg min {f (x) |x ∈ D }. Tương tự đối với bài toán (P2), ta cũng có các khái niệm như trên. 9 Định nghĩa 1.4.2. (Hàm Lagrange) Cho C là tập khác rỗng trong Rn , fi : C → R, bi ∈ R, i = 0, 1, ..., m là những hàm xác định trên C. Xét bài toán tối ưu : min {f0 (x) : x ∈ D} , (Q) trong đó D = {x ∈ Rn : x ∈ C, fi (x) 6 bi , i = 1, ..., m} là miền ràng buộc của bài toán. Để nghiên cứu điều kiện tối ưu của bài toán trên người ta quan tâm đến hàm Lagrange L (x, λ) := L (x, λ1 , ..., λm ) := f0 (x) + m X λi (fi (x) − bi ) i=1 xác định trên C × Rm + , trong đó bộ số λ = (λ1 , ..., λm ) gọi là các nhân tử Lagrange. 1.5 Kết luận chương 1 Trong chương này ta đã trình bày định nghĩa, một số tính chất cơ bản của không gian véc tơ Ơclit, không gian các ma trận, tập lồi và hàm lồi, bài toán tối ưu và hàm Lagrange. Chương tiếp theo ta sẽ trình bày về bổ đề S, các cách chứng minh bổ đề S.