Luận văn Thạc sĩ Toán học: Bài toán định vị với hàm mục tiêu lồi

Chia sẻ: Tri Lễ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

20
lượt xem 2
download

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

Bài luận văn nhằm giới thiệu chi tiết về bài toán định vị, trong đó đi sâu vào các bài toán có hàm mục tiêu lồi. Cụ thể là sẽ trình bày một thuật toán được coi như cải biên của thuật toán dưới vi phân để giải bài toán định vị trong trường hợp số điểm cho trước có thể rất lớn.

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: Bài toán định vị với hàm mục tiêu lồi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM XUÂN HÀ BÀI TOÁN ĐỊNH VỊ VỚI HÀM MỤC TIÊU LỒI Chuyên ngành: Toán ứng dụng Mã số: 62 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Giáo viên hướng dẫn GS. TSKH. LÊ DŨNG MƯU Thái Nguyên - 2017
i Mục lục Bảng ký hiệu 1 Lời nói đầu 2 1 Kiến thức bổ trợ 2 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Tập a-phin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Định lí tách các tập lồi . . . . . . . . . . . . . . . . . . . . . 4 1.4 Bao lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Hàm lồi và cực trị của hàm lồi . . . . . . . . . . . . . . . . . 11 1.5.1 Cực tiểu hàm lồi (cực đại hàm lõm) . . . . . . . . . . 14 1.5.2 Cực tiểu của hàm lồi mạnh . . . . . . . . . . . . . . . 15 2 Bài toán định vị với hàm mục tiêu lồi 18 2.1 Về bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . . 18 2.1.1 Bài toán và định nghĩa . . . . . . . . . . . . . . . . . 18 2.1.2 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . 19 2.1.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . 20 2.2 Bài toán định vị với hàm mục tiêu lồi . . . . . . . . . . . . . . 24 2.3 Thuật toán dưới đạo hàm giải bài toán định vị với hàm mục tiêu mimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.1 Thuật toán và sự hội tụ của nó . . . . . . . . . . . . . 27 2.3.2 Các khía cạnh và kết quả tính toán . . . . . . . . . . . 32 Kết luận 35
ii Tài liệu tham khảo 36
1 Bảng ký hiệu R tập số thực Rn không gian Euclid n-chiều trên trường số thực xi tọa độ thứ i của x hx, yi tích vô hướng của hai vectơ x và y kxk chuẩn của vectơ x [x, y] đoạn thẳng đóng nối x và y (x, y) đoạn thẳng mở nối x và y A bao đóng của A coA bao lồi của A intA tập hợp các điểm trong của A riA tập hợp các điểm trong tương đối của A V (A) tập hợp các điểm cực biên(đỉnh) của A f hàm bao đóng của hàm f convP bao lồi của P dom f tập hữu dụng của f epi f trên đồ thị của f ∂ f (x) dưới vi phân của f tại x ∇ f (x) đạo hàm của f tại x ∇ f (x, d) đạo hàm theo phương d của f tại x
2 Lời nói đầu Một vấn đề quan trọng trong hình học là xác định vị trí của điểm, với những điều kiện nhất định, sao cho đạt được mục tiêu tốt nhất theo một tiêu chuẩn nào đó. Bài toán định vị đơn giản nhất mà ta đã gặp trong chương trình toán phổ thông là bài toán tìm một điểm trong một tam giác đã cho, sao cho tổng khoảng cách từ điểm đó đến ba đỉnh của tam giác là nhỏ nhất. Bài toán định vị có rất nhiều ứng dụng trong thực tế. Ví dụ, khi chúng ta cần xây dựng một bệnh viện, một nhà máy, một trạm xăng, một bến xe, hay một hệ thống giao thông nối các điểm quan trọng với nhau thì câu hỏi đặt ra là vị trí xây dựng như thế nào là tối ưu, thuận tiện nhất sao cho đảm bảo việc thỏa mãn nhu cầu của người sử dụng là tốt nhất để đem lại sự thu hút và lợi ích nhiều nhất. Ví dụ như khi xây dựng một trạm đổ xăng hay bến xe cần tính toán sao cho khoảng cách tới các khu dân cư đông đúc là ngắn nhất, thuận tiện đường nhất, . . . , cũng như vậy khi xây dựng một hệ thống giao thông thì xây dựng thế nào để hệ thống giao thông đó có độ dài ngắn nhất, tiết kiệm chi phí xây dựng, thuận tiện cho việc sử dụng sau này. Một ví dụ quan trọng khác của bài toán định vị, gần đây được nghiên cứu là là xây dựng các trạm phát trong bưu chính viễn thông để bảo đảm tín hiệu tốt nhất. Bài toán định vị thường xuất hiện trong những lĩnh vực thực tế, như trong việc xác định vị trí của một điểm thuộc một miền cho trước sao cho đạt được mục tiêu tốt nhất theo một tiêu chuẩn nào đó. Đây là đề tài đã được nhiều tác giả trong và ngoài nước quan tâm nghiên cứu. Chính vì vậy tác giả chọn đề tài: Bài toán định vị với hàm mục tiêu lồi. Bài luận văn nhằm giới thiệu chi tiết về bài toán định vị, trong đó đi sâu vào
3 các bài toán có hàm mục tiêu lồi. Cụ thể là sẽ trình bày một thuật toán được coi như cải biên của thuật toán dưới vi phân để giải bài toán định vị trong trường hợp số điểm cho trước có thể rất lớn. Luận văn gồm hai chương: Chương 1: Kiến thức bổ trợ Chương này trình bày một số kiến thức của giải tích lồi như tập lồi, hàm lồi, cực trị của hàm lồi, bài toán định vị là những kiến thức nền tảng, cần thiết phục vụ cho việc nghiên cứu và giải quyết đề tài. Chương 2: Bài toán định vị với hàm mục tiêu lồi Chương này trình bày một cách tổng quan hơn về một bài toán định vị với hàm mục tiêu lồi là bài toán tìm một điểm (hay một vị trí) trong một miền xác định sao cho khoảng cách lớn nhất từ điểm (vị trí) đó tới các điểm (vị trí) cho trước là nhỏ nhất. Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS. TSKH. Lê Dũng Mưu. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình. Tác giả luận văn xin cam đoan về tính hợp pháp và tính đúng đắn của luận văn. Luận văn đã tổng hợp các kiến thức lý thuyết và kết quả nghiên cứu mới đây về Bài toán định vị với hàm mục tiêu lồi. Thái Nguyên, ngày 05 tháng 9 năm 2017 Tác giả luận văn Phạm Xuân Hà
2 Chương 1 Kiến thức bổ trợ Chương này trình bày một số kiến thức của giải tích lồi như tập lồi, hàm lồi, cực trị của hàm lồi, bài toán định vị là những kiến thức nền tảng, cần thiết phục vụ cho việc nghiên cứu và giải quyết đề tài. Các kiến thức trong chương được tổng hợp từ các tài liệu [1], [3], [6] và [7]. 1.1 Tập lồi Định nghĩa 1.1.1. Một tập C ⊆ R là một tập lồi nếu C chứa đoạn thẳng đi qua hai điểm bất kỳ x, y ∈ C, tức là: x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λ x + (1 − λ ) y ∈ C. (1.1) Ta nói x là tổ hợp lồi của các điểm x1 , ..., xk nếu k x = ∑ λ j x j , λ j ≥ 0, ∀ j = 1..z..k j=1 k và ∑ λ j = 1. j=1 Mệnh đề 1.1.2. Tập hợp C lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là, C lồi khi và chỉ khi: k k 1 k ∀k ∈ N, ∀λ1 , ..., λk > 0 : x = ∑ λ j = 1, ∀x , ..., x ∈C ⇒ ∑ λ j x j ∈ C. j=1 j=1
3 Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng qui nạp theo số điểm. Với k = 2, từ điều kiện cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k − 1 điểm, ta cần chứng minh mệnh đề đúng với k điểm. Giả sử x1 , ..., xk ∈ C là tổ hợp lồi của k điểm. Tức là: k k x = ∑ λ j x j , λ j > 0, ∀ j = 1....k , ∑ λ j = 1. j=1 j=1 k−1 Đặt ξ = ∑ λ j , khi đó 0 < ξ < 1 và j=1 k−1 k−1 λ x = ∑ λ j x j + λk xk = ξ ∑ ξ j x j + x k λk , j=1 j=1 k−1 λ λj j do ∑ ξ = 1 và ξ > 0, ∀ j = 1, ..., k − 1, j=1 k−1 λ j nên theo giả thiết qui nạp, điểm y = ∑ ξ ∈ C. j=1 k Ta có: x = ξ y + λk xk , do ξ > 0, λk > 0 và ξ + λk = ∑ λi = 1 nên x là một tập j=1 hợp lồi của 2 điểm y và xk đều thuộc C. Vậy x ∈ C. 1.2 Tập a-phin Định nghĩa 1.2.1. Tập C ⊆ R , được gọi là tập a-phin, nếu: ∀x, y ∈ C, ∀λ ∈ R ⇒ λ x + (1 − λ ) ∀y ∈ C. (1.2) Từ định nghĩa cho thấy tập a-phin là một trường hợp riêng của tập lồi. Các không gian con, các siêu phẳng v.v. . . là các trường hợp riêng của tập a-phin. Một ví dụ về tập a-phin là siêu phẳng được định nghĩa dưới dây.
4 Định nghĩa 1.2.2. Siêu phẳng trong không gian Rn là một tập hợp các điểm có
dạng: x ∈ Rn
aT x = α , trong đó a ∈ R là một véc tơ khác 0 và α ∈ R. Véc-tơ a thường được gọi là véc-tơ pháp tuyến của siêu phẳng. Định nghĩa 1.2.3. Bao a-phin của một tập X ⊂ Rn là tập tất cả các tổ hợp a-phin của các điểm thuộc. Kí hiệu bao a-phin của X là affX. 1.3 Định lí tách các tập lồi Định nghĩa 1.3.1. Nửa không gian đóng là một tập hợp có dạng
T x
a x ≥ α , trong đó a 6= 0 và a ∈ R.
Tập x
aT x > α là nửa không gian mở. Định nghĩa 1.3.2. Một tập được gọi là một tập lồi đa diện nếu nó là giao của một số hữu hạn các nửa không gian đóng. Nhận xét 1.3.3. (i) Rn , ∅ là các tập lồi đa diện. (ii) Tập lồi đa diện là tập hợp nghiệm của một hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa diện được cho như sau: D := x ∈ Rn
a j , x ≤ b j , j = 1, ..., m ,
ở đó a j ∈ Rn , j = 1, m, b j ∈ R, j = 1, m. Hoặc nếu ký hiệu A là ma trận có m-hàng là véc-tơ a j với j = 1, . . . , m và véc-tơ bT = (b1 , . . . , bm ), thì hệ trên được viết là D := {x ∈ Rn |Ax ≤ b}. Chú ý rằng, do một phương trình: ha, xi = b có thể viết một cách tương đương dưới dạng hai bất phương trình: ha, xi ≤ b và h−a, xi ≤ b nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương trình cũng là một tập lồi đa diện. Định nghĩa 1.3.4. Cho 2 hai tập C và D khác rỗng. (i) Ta nói siêu phẳng aT x = α tách C và D nếu
5 aT x ≤ α ≤ aT y, ∀x ∈ C, ∀y ∈ D. (ii) Ta nói siêu phẳng aT x = α tách chặt C và D nếu aT x < α < aT y, ∀x ∈ C, ∀y ∈ D. (iii) Ta nói siêu phẳng aT x = α tách mạnh C và D nếu sup aT x < α < inf aT y. x∈C y∈D Định nghĩa 1.3.5. Một điểm a ∈ C được gọi là điểm trong tương đối của C nếu nó là điểm trong của C theo tô-pô cảm sinh bởi affC. Kí hiệu tập các điểm trong tương đối của C là riC. Vậy riC := {a ∈ C| ∃B : (a + B) ∩ affC ⊂ C} , trong đó B là một lân cận mở của gốc. Hiển nhiên riC := {a ∈ affC| ∃B : (a + B) ∩ affC ⊂ C} . Như thường lệ, ta kí hiệu C là bao đóng của C và intC là tập hợp các điểm trong của C. Định nghĩa 1.3.6. Cho x0 ∈ C. Ta nói aT x = α là siêu phẳng tựa của C tại x0 , nếu aT x0 = α, aT x ≥ α ∀x ∈ C. Định nghĩa 1.3.7. Cho C 6= ∅ (không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt dC (y) := inf kx − y.k x∈C Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho dC (y) = kπ − yk, thì ta nói π là hình chiếu (vuông góc) của y trên C và ký hiệu là π = PC (y) Mệnh đề 1.3.8. Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Vơi mọi y ∈ Rn , π ∈ C hai tính chất sau là tương đương:
6 (a) π = PC (y) (b) y − π ∈ NC (π) (ii) Với mọi y ∈ Rn , hình chiếu PC (y) của y trên C luôn tồn tại và duy nhất. / C, thì hPC (y) − y, x − PC (y)i = 0 là siêu phẳng tựa của PC (y) và (iii) Nếu y ∈ tách hẳn khỏi C, tức là hPC (y) − y, x − PC (y)i ≥ 0 ∀C và hPC (y) − y, y − PC (y)i < 0. (iv) Ánh xạ y 7→ PC (y) có các tính chất sau: a) kPC (x) − PC (y)k ≤ kx − yk ∀x, y ∈ Rn (tính không giãn) b) kPC (x) − PC (y), x − yk ≤ kPC (x) − PC (y)k 2 (tính đồng bức). Chứng minh. (i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt xλ := λ x + (1 − λ )π. Do x, π ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do π là hình chiếu của y nên kx − yk ≤ ky − xλ k. Hay kπ − yk2 ≤ kλ (x − π) + (π − y)k2 . Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có λ kπ − yk2 + 2 hx − π, π − yi ≥ 0. Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ → 0, ta được hπ − y, x − πi ≥ 0 ∀x ∈ C. Vậy y − π ∈ NC (π). Bây giờ giả sử có b). Với mọi x ∈ C, ta có 0 ≥ (y − π)T (x − π) = (y − π)T (x + y − y + π) = ky − πk2 + (y − π)T (x − y) . Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có: ky − πk2 ≤ (y − π)T (y − x) ≤ ky − πk . ky − xk .
7 Suy ra ky − πk ≤ ky − xk ∀x ∈ C và do đó π = PC (y). (ii) Do dC (y) = inf kx − yk nên theo định nghĩa của cận dưới đúng, tồn tại k x∈C một dãy x ⊂ C sao cho lim xk − y = dC (y) < +∞. k→+∞ Vậy dãy xk bị chặn, do đó nó có một dãy con xk j hội tụ đến điểm π nào đó. Do C đóng nên π ∈ C. Vậy kπ − yk = lim xk j − y = lim xk − y = dC (y). j→+∞ k→+∞ Chứng tỏ π là hình chiếu của y trên C. Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm π và π l đều là hình chiếu của π trên C thì y − π ∈ NC (π), y − π l ∈ NC (π l ). Tức là π − y, π l − π ≥ 0 và π l − y, π − π l ≥ 0. Cộng hai bất đẳng thức này ta suy ra π − π l ≤ 0 và do đó π = π l . (iii) Theo phần (ii) ánh xạ x 7→ PC (x) xác định khắp nơi. Do z − PC (z) ∈ NC (PC (z)) với mọi z, nên áp dụng z = x và z = y ta có hx − PC (x), PC (y) − PC (x)i ≤ 0 và hx − PC (y), PC (x) − PC (y)i ≤ 0. Cộng hai bất đẳng thức trên ta được hPC (y) − PC (x), PC (y) − PC (x) + x − yi ≤ 0. Từ đây và theo bất đẳng thức Cauchy-Schwarz suy ra kPC (x) − PC (y)k ≤ kx − yk. Để chứng minh tính đồng bức, áp dụng tính chất b) của (i) lần lượt với PC (x) và PC (y), ta có