ĐẠ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 . . . . . . 1.2 Tập a-phin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3
1.3 Định lí tách các tập lồi . 1.4 Bao lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 10
1.5 Hàm lồi và cực trị của hàm lồi . . . . . .
. 1.5.1 Cực tiểu hàm lồi (cực đại hàm lõm) . . . . . . . . . . . . . . . . . . . . 11 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 . . .
. 2.1.1 Bài toán và định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18
2.1.2 2.1.3 Điều kiện tối ưu . Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 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ó . 2.3.2 Các khía cạnh và kết quả tính toán . 27 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 tọa độ thứ i của x tích vô hướng của hai vectơ x và y chuẩn của vectơ x đoạn thẳng đóng nối x và y đoạn thẳng mở nối x và y bao đóng của A bao lồi của A tập hợp các điểm trong của A tập hợp các điểm trong tương đối của A tập hợp các điểm cực biên(đỉnh) của A hàm bao đóng của hàm f bao lồi của P tập hữu dụng của f trên đồ thị của f dưới vi phân của f tại x đạo hàm của f tại x đạo hàm theo phương d của f tại x xi (cid:104)x, y(cid:105) (cid:107)x(cid:107) [x, y] (x, y) A coA intA riA V (A) f convP dom f epi f ∂ f (x) ∇ f (x) ∇ f (x, d)
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à:
(1.1) x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λ x + (1 − λ ) y ∈ C.
Ta nói x là tổ hợp lồi của các điểm x1, ..., xk nếu
k ∑ j=1
x = λ jx j, λ j ≥ 0, ∀ j = 1..z..k
k ∑ j=1
và λ 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 ∑ j=1
k ∑ j=1
λ j = 1, ∀x1, ..., xk ∈ C ⇒ λ jx j ∈ C. ∀k ∈ N, ∀λ1, ..., λk > 0 : x =
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 ∑ j=1
k ∑ j=1
x = λ jx j, λ j > 0, ∀ j = 1....k , λ j = 1.
k−1 ∑ j=1
Đặt ξ = λ j, khi đó 0 < ξ < 1 và
λ j ξ x j + xkλk,
k−1 ∑ j=1
k−1 ∑ j=1
λ j
x = λ jx j + λkxk = ξ
ξ = 1 và λ j
k−1 ∑ j=1
do
λ j ξ ∈ C.
ξ > 0, ∀ j = 1, ..., k − 1, k−1 ∑ j=1
nên theo giả thiết qui nạp, điểm y =
k ∑ j=1
λi = 1 nên x là một tập Ta có: x = ξ y + λkxk, do ξ > 0, λk > 0 và ξ + λk =
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:
(1.2) ∀x, y ∈ C, ∀λ ∈ R ⇒ λ x + (1 − λ ) ∀y ∈ C.
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
(cid:12)aT x = α (cid:9), trong đó a ∈ R là một véc tơ khác 0 và α ∈ R.
Đị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: (cid:8)x ∈ Rn (cid:12) 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
(cid:8)x (cid:12) (cid:12)aT x ≥ α (cid:9) ,
trong đó a (cid:54)= 0 và a ∈ R. Tập (cid:8)x (cid:12) (cid:12)aT x > α (cid:9) 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 := (cid:8)x ∈ Rn (cid:12) (cid:10)a j, x(cid:11) ≤ b j, j = 1, ..., m(cid:9) , (cid:12)
ở đó 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: (cid:104)a, x(cid:105) = b có thể viết một cách tương đương dưới dạng hai bất phương trình: (cid:104)a, x(cid:105) ≤ b và (cid:104)−a, x(cid:105) ≤ 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
aT y. aT x < α < inf y∈D sup x∈C
Đị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 (cid:54)= ∅ (không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt
(cid:107)x − y.(cid:107) dC(y) := inf 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) = (cid:107)π − y(cid:107), 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. (iii) Nếu y /∈ C, thì (cid:104)PC(y) − y, x − PC(y)(cid:105) = 0 là siêu phẳng tựa của PC(y) và
tách hẳn khỏi C, tức là
(cid:104)PC(y) − y, x − PC(y)(cid:105) ≥ 0 ∀C
và
(cid:104)PC(y) − y, y − PC(y)(cid:105) < 0.
(iv) Ánh xạ y (cid:55)→ PC(y) có các tính chất sau: a) (cid:107)PC(x) − PC(y)(cid:107) ≤ (cid:107)x − y(cid:107) ∀x, y ∈ Rn (tính không giãn) b) (cid:107)PC(x) − PC(y), x − y(cid:107) ≤ (cid:107)PC(x) − PC(y)(cid:107) 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 (cid:107)x − y(cid:107) ≤ (cid:107)y − xλ (cid:107). Hay
(cid:107)π − y(cid:107)2 ≤ (cid:107)λ (x − π) + (π − y)(cid:107)2.
Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có
λ (cid:107)π − y(cid:107)2 + 2 (cid:104)x − π, π − y(cid:105) ≥ 0.
Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ → 0, ta được
(cid:104)π − y, x − π(cid:105) ≥ 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 + π)
= (cid:107)y − π(cid:107)2 + (y − π)T (x − y) .
Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có:
(cid:107)y − π(cid:107)2 ≤ (y − π)T (y − x) ≤ (cid:107)y − π(cid:107) . (cid:107)y − x(cid:107) .
7
Suy ra (cid:107)y − π(cid:107) ≤ (cid:107)y − x(cid:107) ∀x ∈ C và do đó π = PC(y).
(cid:107)x − y(cid:107) nên theo định nghĩa của cận dưới đúng, tồn tại
(ii) Do dC(y) = inf x∈C một dãy (cid:8)xk(cid:9) ⊂ C sao cho
(cid:13)xk − y(cid:13) (cid:13) (cid:13) = dC(y) < +∞. lim k→+∞
Vậy dãy (cid:8)xk(cid:9) bị chặn, do đó nó có một dãy con (cid:8)xk j(cid:9) hội tụ đến điểm π nào đó. Do C đóng nên π ∈ C. Vậy
(cid:13)xk − y(cid:13) (cid:13) (cid:13) = dC(y). (cid:13)xk j − y(cid:13) (cid:13) (cid:107)π − y(cid:107) = lim j→+∞ (cid:13) = lim 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à
(cid:10)π − y, π l − π(cid:11) ≥ 0 và (cid:10)π l − y, π − π l(cid:11) ≥ 0.
Cộng hai bất đẳng thức này ta suy ra (cid:13) (cid:13)π − π l(cid:13) (cid:13) ≤ 0 và do đó π = π l.
(iii) Theo phần (ii) ánh xạ x (cid:55)→ 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ó
(cid:104)x − PC(x), PC(y) − PC(x)(cid:105) ≤ 0
và
(cid:104)x − PC(y), PC(x) − PC(y)(cid:105) ≤ 0.
Cộng hai bất đẳng thức trên ta được
(cid:104)PC(y) − PC(x), PC(y) − PC(x) + x − y(cid:105) ≤ 0.
Từ đây và theo bất đẳng thức Cauchy-Schwarz suy ra
(cid:107)PC(x) − PC(y)(cid:107) ≤ (cid:107)x − y(cid:107).
Để 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ó
8
(cid:104)PC(x) − x, PC(x) − PC(y)(cid:105) ≤ 0,
(cid:104)y − PC(y), PC(x) − PC(y)(cid:105) ≤ 0.
Cộng hai bất đẳng thức ta được
(cid:104)PC(x) − PC(y) + y − x, PC(x) − PC(y)(cid:105) ≤ 0
⇔ (cid:104)PC(x) − PC(y), y − x(cid:105) + (cid:107)PC(x) − PC(y)(cid:107) 2 ≤ 0 ⇔ (cid:104)PC(x) − PC(y), x − y(cid:105) ≥ (cid:107)PC(x) − PC(y)(cid:107) 2.
Đây chính là tính đồng bức cần được chứng minh.
Mệnh đề 1.3.9. Cho C là một tập lồi khác rỗng và x0 /∈ riC. Khi đó tồn tại siêu phẳng tựa của C tại hình chiếu của x0 trên C.
Chứng minh. Gọi hình chiếu của x0 trên C là p(x0). Trước hết ta xét trường hợp intC (cid:54)= ∅.
Vậy x0 /∈ intC. Phân biệt hai trường hợp:
a) x0 /∈ C. Do C lồi, đóng nên theo (iii) của Mệnh đề 1.3.8, siêu phẳng (cid:10)p(x0) − x0, x(cid:11) = (cid:10)p(x0) − x0, p(x0)(cid:11)
là siêu phẳng tựa của C tại p(x0) và tách hẳn C và x0.
b) x0 ∈ C. Khi đó do x0 /∈ intC, nên x0 ∈ Rn\C. Vậy tồn tại dãy xk → x0 với xk /∈ C với mọi k. Do C lồi, đóng, nên lại áp dụng (iii) của Mệnh đề 1.3.8, tồn tại siêu phẳng tựa của C tại p(xk). Tức là tồn tại π k (cid:54)= 0 thỏa mãn
(cid:10)π k, x(cid:11) ≤ (cid:10)π k, p(xk)(cid:11) ∀x ∈ C. Bằng cách chuẩn hóa π k, ta có thể coi (cid:13) (cid:13)π k(cid:13) (cid:13) = 1, và do đó có thể giả sử π k → π 0. Do ánh xạ chiếu liên tục, nên từ bất đẳng thức trên, qua giới hạn và chú ý là p(x0) = x0 (vì x0 ∈ C), ta có:
(cid:10)π 0, x(cid:11) ≤ (cid:10)π 0, p(x0)(cid:11) = (cid:10)π 0, x0(cid:11) ∀x /∈ C.
Vậy (cid:10)π 0, x(cid:11) = (cid:10)π 0, x0(cid:11) là siêu phẳng tựa của C tại x0.
Trong trường hợp intC = ∅, thì dimC < n. Vậy C bị chứa trong một siêu phẳng H chứa affC. Gọi w là véc-tơ pháp tuyến của H. Khi đó tồn tại số thực α sao cho H = {x ∈ Rn|wT x = α}. Do C ⊆ C ⊆ H nên suy ra H là siêu phẳng tựa của cả C và C.
9
Định lý 1.3.10. (Định lí tách 1). Cho C và D là hai tập lồi khác rỗng trong Rn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D.
Định lí tách vừa nêu có thể suy ra ngay từ Bổ đề 1.3.11 dưới đây, chính là
định lí tách một tập lồi và một phần tử không thuộc nó.
Bổ đề 1.3.11. (Bổ đề liên thuộc). Cho C ⊂ Rn là một tập lồi khác rỗng. Giả sử x0 /∈ C. Khi đó tồn tại t ∈ Rn thỏa mãn (cid:104)t, x(cid:105) ≥ (cid:10)t, x0(cid:11) ∀x ∈ C.
Chứng minh bổ đề: Do x0 /∈ riC, nên tồn tại siêu phẳng tách trong bổ đề, được suy ra từ Mệnh
đề 1.3.9.
Chứng minh Định lí tách 1. Do C và D là lồi, nên C − D cũng lồi. Hơn nữa 0 ∈ C − D, vì C ∩ D = (cid:11). Theo Bổ đề 1.3.9 áp dụng với x0 = 0, tồn tại véc-tơ t ∈ Rn, t (cid:54)= 0 sao cho (cid:104)t, z(cid:105) ≥ 0 với mọi z ∈ C − D. Vì z = x − y với x ∈ C, y ∈ D, nên ta có
(cid:104)t, x(cid:105) ≥ (cid:104)t, y(cid:105) ∀x ∈ C, y ∈ D.
(cid:104)t, y(cid:105), tách C và D. Lấy α := sup y∈D (cid:104)t, y(cid:105), khi đó siêu phẳng α := sup y∈D
Định lý 1.3.12. (Định lí tách 2) Cho C và D là hai tập lồi đóng khác rỗng sao cho C ∩ D = ∅. . Giả sử có ít nhất một tập là compact. Khi đó hai tập này có thể tách mạnh bởi một siêu phẳng.
Cũng như trên, Định lý tách 2 được dễ dàng suy ra từ Bổ đề 1.3.13 dưới đây,
nói về sự tách mạnh giữa một tập lồi đóng và một điểm bên ngoài tập này.
Bổ đề 1.3.13. Cho C ⊂ Rn là một tập lồi đóng khác rỗng sao cho 0 /∈ C. Khi đó tồn tại một véc-tơ t ∈ Rn, t (cid:54)= 0 và α > 0, sao cho
(cid:104)t, x(cid:105) ≥ α > 0 ∀x ∈ C.
Theo Bổ đề này, thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi siêu
phẳng (cid:104)t, x(cid:105) = α 2 .
Chứng minh Bổ đề: Do C đóng và 0 /∈ C, Ω\C mở, nên tồn tại quả cầu B ⊂ Ω\C, tâm ở gốc, bán kính r > 0 sao cho B ∩C = ∅. Áp dụng Định lý tách 1 cho hai tập C và B, ta có t ∈ Rn\ {0} và α ∈ R, sao cho
10
(cid:104)t, x(cid:105) ≥ α ≥ (cid:104)t, y(cid:105) ∀x ∈ C, ∀y ∈ B.
Bằng cách chuẩn hóa ta có thể xem (cid:104)t, x(cid:105) ≥ α ≥ (cid:104)t, y(cid:105) ∀x ∈ C, ∀y ∈ B và do
đó khoảng cách từ gốc đến siêu phẳng ít nhất là bằng α ≥ r. Vậy thì
(cid:104)t, x(cid:105) ≥ α ≥ r > 0.
Chứng minh định lý tách 2: Giả sử C là tập compact. Ta chỉ ra tập C −D đóng. Thật vậy, giả sử zk ∈ C −D và zk → z. Ta có zk = xk − yk với xk ∈ C, yk ∈ D. Vì tập C compact, nên có một dãy con xk j → x khi j → +∞. Vậy yk j = zk j − xk j → z − x ∈ D. Do vậy z = x − y ∈ C − D . Chứng tỏ C − D là tập đóng. Do 0 /∈ C − D, nên theo Bổ đề trên, tồn tại t (cid:54)= 0, sao cho (cid:104)t, x − y(cid:105) ≥ α > 0 với mọi x ∈ C, y ∈ D. Vậy
(cid:104)t, y(cid:105) + . (cid:104)t, x(cid:105) − inf x∈C α 2 α 2 ≥ sup y∈D
Chứng tỏ C và D có thể tách mạnh.
1.4 Bao lồi
Định nghĩa 1.4.1. Cho P là tập hữu hạn k- điểm trong Rn, giao của tất cả các tập lồi chưa P được gọi là bao lồi của P. Ta kí hiệu bao lồi của P là conv(P).
(cid:41)
k ∑ i=1
. conv(P) := θixi/xi ∈ P, θi ≥ 0, i = 1, ..., k, θi = 1 (cid:40) k ∑ i=1
Nhận xét 1.4.2. Bao lồi của tập P là tập lồi nhỏ nhất chứa P. Bao lồi của một tập hữu hạn điểm P ⊂ Rn là một đa diện lồi trong Rn.
Định nghĩa 1.4.3. Véc-tơ x = λixi gọi là tổ hợp a-phin của
n ∑ i=1 x1, x2, ..., xn ∈ Rn nếu λi ∈ Rn ∀i,
n ∑ i=1
λi = 1.
Định lý 1.4.4. Tập X là tập a-phin nếu và chỉ nếu nó đóng với phép toán tổ hợp a-phin.
11
Định nghĩa 1.4.5. Số chiều của tập a-phin X là số m nhỏ nhất để tồn tại m + 1 véc-tơ x0,x1, ..., xm sao cho X = Aff {x0, x1, ..., xm}. Các véctơ x0,x1, ..., xm này gọi là cơ sở a-phin của X. Kí hiệu số chiều của X là dim X.
Định lý 1.4.6. (Định lí Caratheodory). Nếu dimX = m thì mọi điểm x ∈ convX có thể biểu diễn bằng tổ hợp lồi của không quá m + 1 điểm thuộc X. Chứng minh.
Xét x ∈ convX và giả sử tổ hợp lồi:
k ∑ i=1
k ∑ i=1
x = λixi, λi = 1, λi > 0, xi ∈ X,
k ∑ i=2
γi ta γi(xi − x1) = 0. Nếu đặt y = − tồn tại bộ số {γ2, ..., γk} (cid:54)= 0 sao cho: là tổ hợp lồi có số véc-tơ k nhỏ nhất có thể được của x. Ta sẽ chứng minh k (cid:54) m + 1. Thật vậy, giả sử ngược lại, k > m + 1, các véc-tơ {x1, x2, ..., xk} không thể độc lập a-phin vì dimX = m. Như vậy, các véc-tơ {x2 − x1, .., xk − x1} không thể độc lập tuyến tính. Tức là, k ∑ i=2
k ∑ i=2
k ∑ i=2
có γixi = 0, γi = 0, (γ1, ..., γk) (cid:54)= 0, thì x có thể viết lại như sau:
k ∑ i=1
k ∑ i=1
k ∑ i=1
x = λixi = (λi + tγi)xi = λi(t)xi.
Rõ ràng, với t đủ nhỏ, biểu thức trên vẫn là tổ hợp lồi của x. Tuy nhiên nếu λi ta chọn t = min |γi|, thì hệ số dương trong tổ hợp lồi sẽ ít hơn số hệ số dương γi<0
Lưu ý: chắc chắn tồn tại I, γi < 0 vì γi = 0, (γ1, ..., γk) (cid:54)= 0. trongtổ hợp lồi ban đầu, mâu thuẫn với giả thiết k là nhỏ nhất có thể được. k ∑ i=2
1.5 Hàm lồi và cực trị của hàm lồi
Cho C ⊆ Rn là tập lồi và f : C → R. Ta sẽ kí hiệu
dom f := {x ∈ C | f (x) < +∞} ,
12
tập dom f được gọi là miền hữu dụng của f . Tập
epi f := {(x, µ) ∈ C × R | f (x) ≤ µ } ,
được gọi là trên đồ thị của hàm f .
Định nghĩa 1.5.1. Cho hàm f xác định trên tập lồi C ⊆ Rn.
Hàm f được gọi là hàm lồi trên C nếu
(1.3) f (λ x + (1 − λ )y) ≤ λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1).
Hàm f được gọi là hàm lồi chặt trên C nếu
(1.4) f (λ x + (1 − λ )y) < λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1).
Hàm f được gọi là hàm lồi mạnh trên C với hệ số ρ > 0 nếu
(1.5) λ (1 − λ )(cid:107)x − y(cid:107)2 f (λ x + (1 − λ )y) ≤ λ f (x) + (1 − λ ) f (y) − ρ 2
∀x, y ∈ C, ∀λ ∈ (0, 1).
Bổ đề 1.5.2.
(i) Cho véc-tơ a cố định, a ∈ Rn, hàm f (x) := (cid:107)x − a(cid:107)2 là lồi mạnh với hệ số
ρ = 1 trên toàn không gian Rn.
(ii) Cho J là tập chỉ số hữu hạn khác rỗng, X là tập lồi và g j là hàm lồi mạnh trên X với hệ số ρ j với mọi j ∈ J. Khi đó, hàm g = max j∈Jg j là lồi mạnh trên X với hệ số r = min j∈Jr j.
Định nghĩa 1.5.3. Cho f : Rn → Rn ∪ {+∞} là hàm lồi. Véc-tơ v được gọi là dưới đạo hàm của f tại x nếu với mọi y ∈ Rn ta có: (cid:104)v, y − x(cid:105) ≤ f (y) − f (x).
Tập dưới đạo hàm của f tại x được gọi là dưới vi phân của f tại x và dược kí
hiệu bởi ∂ f (x).
Hàm f được gọi là khả dưới vi phân tại x nếu dom∂ f (cid:54)= ∅, f được gọi là
khả dưới vi phân trên C nếu nó khả dưới vi phân tại mọi điểm x ∈ C.
Ví dụ:
13
1. f (x) = (cid:107)x(cid:107) , x ∈ Rn. Tại điểm x = 0, hàm này không khả vi, nhưng nó khả
dưới vi phân và
∂ f (0) = {x∗ |(cid:104)x∗, x(cid:105) ≤ (cid:107)x(cid:107) ∀x} .
2. f = δC là hàm chỉ của một tập lồi C (cid:54)= ∅. Khi đó với x0 ∈ C,
∂ δC(x0) = (cid:8)x∗ (cid:12) (cid:10)x∗, x − x0(cid:11) ≤ δC(x) ∀x(cid:9) . (cid:12)
Với x0 /∈ C, thì δC(x) = + ∞, nên bất đẳng thức này luôn đúng. Vậy
∂ δC(x0) = (cid:8)x∗ (cid:12) (cid:10)x∗, x − x0(cid:11) ≤ 0 ∀x ∈ C (cid:9) = NC(x0). (cid:12)
Vậy dưới vi phân của hàm chỉ của tập lồi C khác rỗng tại một điểm x0 ∈ C
chính là nón pháp tuyến ngoài của C tại x0.
Định nghĩa 1.5.4. Một hàm lồi f : Rn → Rn ∪ {+∞} được gọi là hàm lồi chính thường nếu dom f (cid:54)= ∅.
Định nghĩa 1.5.5. Cho X là một tập lồi trong Rn. Điểm x ∈ X được gọi là điểm cực biên của X nếu không tồn tại y, z ∈ X, y (cid:54)= zsao cho: x = (1 − λ )y + λ z với 0 < λ < 1. Khi X là một tập lồi đa diện, điểm cực biên của nó còn được gọi là đỉnh.
Bổ đề 1.5.6. Gọi fi : Rn → R (i ∈ I := {1, ..., m)} là các hàm lồi trên Rn và f (x) = max { fi(x)| x ∈ I}. Khi đó f là một hàm lồi khả dưới vi phân trên Rn. Hơn nữa
∂ f (x) = conv (cid:0)∪i∈I(x)∂ fi(x)(cid:1) ,
với I(x) := {i ∈ I| f (x) = fi(x)}.
Định nghĩa 1.5.7. Gọi A là một tập lồi đóng khác rỗng của Rn và x là một điểm bất kì thuộc Rn. Điểm x ∈ A được gọi là hình chiếu khoảng cách của x trên A nếu:
(cid:107)x − x(cid:107) ≤ (cid:107)x − y(cid:107) ∀y ∈ A.
Kí hiệu PA(x) là hình chiếu của x trên A. Với mọi x thì hình chiếu PA(x) tồn
tại duy nhất. Hơn nữa ta có
14
x = PA(x) ⇔ x ∈ A và (cid:104)x − x, y − y(cid:105) ≤ 0 ∀y ∈ A.
1.5.1 Cực tiểu hàm lồi (cực đại hàm lõm)
Định lý 1.5.8. Cho f : Rn → Rn là hàm lồi và C là tập lồi, khác rỗng trong Rn. Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực tiểu toàn cục.
Tập các điểm cực tiểu là tập lồi của C. Chứng minh.
Gọi x0 ∈ C là điểm cực tiểu địa phương, suy ra tồn tại các lân cận U(x0) sao
cho f (x0) ≤ f (x), ∀x ∈ C ∩U(x0). Lấy x ∈ C bất kỳ:
1. Nếu x ∈ U(x0) thì hiển nhiên f (x0) ≤ f (x). 2. Nếu x /∈ U(x0), ta lấy xλ = λ x + (1 − λ )x0 sao cho xλ ∈ U(x0), λ ∈ (0, 1). Do f là hàm lồi nên f (xλ ) ≤ λ f (x) + (1 − λ ) f (x0), mà f (xλ ) ≥ f (x0) nên f (x0) ≤ λ f (x) + (1 − λ ) f (x0). Suy ra f (x0) ≤ f (x).
Từ Định lí này suy ra bất cứ điểm cực đại địa phương nào của một hàm lõm trên một tập lồi cũng là điểm cực đại toàn cục. Tập tất cả các điểm cực đại của
hàm lõm trên tập lồi là lồi.
Mệnh đề 1.5.9. Giả sử f là hàm lồi khả vi liên tục, xác định trên tập lồi C và giả sử x0 ∈ C. Khi đó, f (cid:0)x0(cid:1) ≤ f (x), x ∈ C (nghĩa là x0 là điểm cực tiểu của hàm f (x) trên C) khi và chỉ khi (cid:10)∇ f (x0), x − x0(cid:11) ≥ 0 ∀x ∈ C. Chứng minh.
Do f là hàm lồi khả vi tại x0 nên
(cid:10)∇ f (x0), x − x0(cid:11) ≤ f (x) − f (x0) ∀x ⇔ f (x0) ≤ f (x) ⇔ (cid:10)∇ f (x0), x − x0(cid:11) ≥ 0.
Hệ quả 1.5.10. Với các giả thiết như trong Mệnh đề 1.5.9, điểm trong x0 ∈ intC là điểm cực tiểu khi và chỉ khi 0 ∈ ∂ f (x0). Mệnh đề 1.5.11. Giả sử C ⊂ R là tập compact khác rỗng, f : C → Rn là một hàm lồi. Khi đó, mỗi điểm cực đại toàn cục của f trên C cũng là một điểm cực đại của f trên convC. Chứng minh.
15
x = λ jx j, Ta gọi V (C) là tập hợp các điểm cực biên của C. Do C compact, nên mọi điểm x ∈ convC đều biểu diễn bằng tổ hợp lồi của C, tức là với mọi x ∈ C ta có: k ∑ j=1
k ∑ j=1 Khi đó do f lồi, nên
λ j = 1 và x j ∈ V (C) ( chú ý là k phụ thuộc vào điểm x). trong đó λ j > 0,
k ∑ j=1
f (x) ≤ λ j f (x j) ≤ max (cid:8) f (x j) : j = 1, ..., k(cid:9) = f (v),
với v là một điểm cực biên trong số các điểm (cid:8)x1, ..., xk(cid:9). Tuy nhiên, do mỗi điểm cực biên của C đều thuộc bao lồi của C và do C ⊆ convC, nên
max { f (x) : x ∈ C} = max { f (x) : x ∈ V (C)} .
Mệnh đề 1.5.12. Cho C là tập lồi đóng, f là hàm lồi khả vi trên C, điều kiện cần và đủ để x∗ ∈ C là điểm cực tiểu của f trên C là x∗ = PC (y∗), trong đó y∗ = x∗ − α∇ f (x∗), α > 0 là một số bất kỳ. Chứng minh.
Theo định nghĩa hình chiếu
x∗ = PC(y∗) ⇔ (cid:104)y∗ − x∗, x − x∗(cid:105) ≤ 0 ∀x ∈ C.
Thay y∗ = x∗ − α∇ f (x∗), ta được
(cid:104)−α∇ f (x∗), x − x∗(cid:105) ≤ 0 ⇔ (cid:104)∇ f (x∗), x − x∗(cid:105) ≥ 0 (do α > 0).
Do f là hàm lồi nên
(cid:104)∇ f (x∗), x − x∗(cid:105) ≤ f (x) − f (x∗).
1.5.2 Cực tiểu của hàm lồi mạnh
Sau đây ta xét một lớp hàm luôn có cực tiểu trên mọi tập lồi đóng khác rỗng.
Hơn nữa, giống như hàm lồi chặt, cực tiểu này là duy nhất.
16
Ta nhắc lại rằng hàm f xác định trên tập lồi C ⊂ R được gọi là lồi mạnh nếu tồn tại hằng số ρ > 0 đủ nhỏ (hằng số lồi mạnh) sao cho với mọi x, y và mọi λ ∈ [0, 1] ta có bất đẳng thức
≥ (cid:107)x − y(cid:107)2 . (1.6) f [λ x + (1 − λ )y] ≤ λ f (x) + (1 − λ ) f (y) − λ (1 − λ ) ρ 2
Có thể chứng minh rằng hàm f lồi mạnh trên C khi và chỉ khi hàm
f (.) − ρ(cid:107).(cid:107)2
là lồi trên C. Rõ ràng một hàm lồi mạnh thì lồi chặt, nhưng điều ngược lại chưa chắc đã đúng (chẳng hạn, hàm ex ∀x ∈ R lồi chặt nhưng không lồi mạnh trên R.
Mệnh đề 1.5.13. Nếu hàm f là hàm lồi mạnh và khả vi trên tập lồi đóng C thì: i) Tồn tại duy nhất điểm x∗ ∈ C,sao cho f (x∗) = min { f (x) : x ∈ C}; ii) (cid:104)∇ f (x) − ∇ f (y), x − y(cid:105) ≥ ρ(cid:107)x − y(cid:107)2, ∀x, y ∈ C.; iii) Với bất kỳ x0 ∈ C tập mức dưới C0 = (cid:8)x ∈ C : f (x) ≤ f (x0)(cid:9) bị chặn. Chứng minh.
(i) Áp dụng Bổ đề 11.2 trong [2], ta có hàm f thỏa mãn điều kiện bức, tức là f (x) → +∞ khi (cid:107)x(cid:107) → +∞. Do đó bài toán min { f (x) : x ∈ C} có nghiệm. Tính duy nhất nghiệm là do tính lồi mạnh.
(ii) Áp dụng tính lồi mạnh của f nên hàm g(x) := f (x) − ρ(cid:107)x(cid:107)2 là hàm lồi. Khi đó tính đạo hàm của hàm g và áp dụng tính chất đạo hàm của hàm lồi, ta suy ra (ii).
(iii) Do f lồi mạnh nên lại theo Bổ đề 11.2 trong [2], hàm f thỏa mãn điều
kiện bức, do đó tập (cid:8)x ∈ C : f (x) ≤ f (x0)(cid:9) phải bị chặn.
Mệnh đề 1.5.14. Giả sử f (x) lồi mạnh trên tập lồi đóng C và x0 là điểm cực tiểu của f trên C. Khi đó, với mọi x ∈ C ta có
(cid:2) f (x) − f (x0)(cid:3) , ≤ (1.7) (cid:13)x − x0(cid:13) (cid:13) 2 (cid:13) 2 ρ
hơn nữa, nếu f (x) khả vi thì
≤ (1.8) (cid:107)∇ f (x)(cid:107) (cid:13)x − x0(cid:13) (cid:13) 2 (cid:13) 1 ρ
17
ρ (cid:107)∇ f (x)(cid:107)2.
và 0 ≤ f (x) − f (x0) ≤ 1
Hệ quả 1.5.15. Hàm lồi thực f trên tập lồi đa diện D, không chứa đường thẳng nào, hoặc không bị chặn trên trên một cạnh vô hạn nào đó của D, hoặc đạt cực đại tại một đỉnh của D.
Hệ quả 1.5.16. Hàm lồi trên tập lồi compact C đạt cực đại tại một điểm cực biên của C.
18
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. Các kết quả trình bày trong chương này được tổng hợp từ các
tài liệu: [1], [2], [4], [5] và [8].
2.1 Về bài toán quy hoạch lồi
2.1.1 Bài toán và định nghĩa
Cho D ⊂ Rn và f : Rn → R. Xét bài toán qui hoạch toán học:
(P) min { f (x) : x ∈ D} ,
trong đó D là tập lồi đóng trong Rn và f là hàm xác định trên D. Điểm x∗ được gọi là một phương án chấp nhận được của bài toán (P). Tập D được gọi là miền (tập) chấp nhận được, f được gọi là hàm mục tiêu của bài toán (P). Thông thường tập D được cho như là tập nghiệm của một hệ bất đẳng thức hoặc đẳng thức có dạng:
(2.1) D := (cid:8)x ∈ X : g j(x) ≤ 0, hi(x) = 0, j = 1, ..., m, i = 1, ..., p(cid:9) ,
trong đó ∅ (cid:54)= X ⊆ Rn và g j, hi : Rn → R ( j = 1, ..., m, i = 1, ..., p).
19
Bài toán (P) với D cho bởi (2.1) được gọi là trơn nếu cả hàm mục tiêu và
các ràng buộc đều trơn ( khả vi).
Bài toán (P) có nhiều ứng dụng trong các lĩnh vực khác nhau.
Định nghĩa 2.1.1. Giả sử f : Rn → Rn ∪ {+∞} là hàm tùy ý và C ⊆ Rn là tập tùy ý.
Điểm x0 ∈ C được gọi là điểm cực tiểu toàn cục của f trên C nếu với mọi
x ∈ C ta có f (x0) ≤ f (x).
Nếu tồn tại lân cận U(x0) của x0 sao cho f (x0) ≤ f (x) với mọi x0 ∈ C ∩
U(x0) thì x0 ∈ C được gọi là điểm cực tiểu địa phương của f trên C.
Các khái niệm cực đại địa phương và cực đại toàn cục được định nghĩa tương tự. Ta kí hiệu tập tất cả các điểm cực tiểu (cực đại) toàn cục của f trên C là Argminx∈C f (x), (Argmaxx∈C f (x) ).
Do min { f (x) : x ∈ C} = − max {− f (x) : x ∈ C} nên lý thuyết cực tiểu (hay
cực đại) hàm lồi cũng chính là lý thuyết cực đại (hay cực tiểu) hàm lõm.
Định nghĩa 2.1.2. Điểm x∗ ∈ U được gọi là lời giải tối ưu địa phương của bài toán (P) nếu tồn tại một lân cận I của x∗ sao cho: f (x∗) (cid:54) f (x) ∀x ∈ U ∩ D, và x∗ ∈ D là lời giải tối ưu toàn cục của (P) nếu: f (x∗) ≤ f (x) ∀x ∈ D.
2.1.2 Sự tồn tại nghiệm tối ưu
Xét bài toán tối ưu toàn cục (P). Có 4 trường hợp tồn tại nghiệm tối ưu của
bài toán này.
f (x) → −∞).
(i) D = ∅, không có nghiệm. (ii) f không bị chặn dưới trên D( inf x∈D f (x) < ∞ nhưng giá trị cực tiểu không đạt được trên D.
f (x). (ii) inf x∈D (iv) Tồn tại x∗ ∈ D sao cho f (x∗) = min x∈D
(D) := {t ∈ R : f (x) ≤ t, x ∈ D} đóng và bị chặn dưới.
Định lý 2.1.3. Để bài toán (P) tồn tại nghiệm tối ưu toàn cục thì điều kiện cần và đủ là: F +
Định lý 2.1.4. (Weierstrass). Nếu D là tập compact và f nửa liên tục dưới trên D thì bài toán (P) có nghiệm tối ưu.
20
Định lý 2.1.5. Nếu f nửa liên tục dưới trên D và thỏa mãn điều kiện:
f (x) → +∞ khi x ∈ D, (cid:107)x(cid:107) → +∞,
thì f có điểm cực tiểu trên D.
2.1.3 Điều kiện tối ưu
Xét bài toán (P) định nghĩa bởi: min f (x) với điều kiện
x ∈ D := (cid:8)x ∈ X : g j(x) ≤ 0, hi(x) = 0, j = 1, ..., m, i = 1, ..., k(cid:9) ,
trong đó ∅ (cid:54)= X ⊆ Rn và f , g j, hi: Rn → R (∀ j, i). Ta gọi bài toán (P) là bài toán lồi nếu X là tập lồi và các hàm f, g j là hàm lồi, hi là hàm a-phin.
j ( j = 1, ..., k) không đồng thời bằng 0 sao cho
Định lý 2.1.6. (Karush - Kuhn - Tucker). Giả sử (P) là bài toán lồi. Nếu x∗ là một nghiệm tối ưu của bài toán (P) thì tồn tại λ ∗ i ≥ 0 (i = 0, 1, ..., m) và µ ∗
L(x∗, λ ∗, µ ∗), L(x∗, λ ∗, µ ∗) = min x∈X
i gi(x∗) = 0 (i = 1, ..., m), λ ∗
(điều kiện đạo hàm triệt tiêu) và
(điều kiện độ lệch bù). Hơn nữa, nếu intX = ∅ và điều kiện Slater ∃x0 ∈ D : gi(x0) < 0 (i = 1, ..., m) được thỏa mãn và các hàm a-phin hi (i = 1, . . . , k) độc lập tuyến tính trên X thì λ ∗ 0 > 0 và các điều kiện đạo hàm triệt tiêu và điều kiện bù là điều kiện đủ để điểm chấp nhận được x∗ là nghiệm tối ưu của bài toàn (P).
Chứng minh. Giả sử x∗ là nghiệm tối ưu của bài toán P. Đặt
C := {(λ0, λ1, ..., λm, µ1, µ2, ...µk)| ∃x ∈ X} f (x) − f (x∗) < λ0, gi(x) ≤ λi, i = 1, ..., m, h j(x) = µ j, i = 1, ..., k.
Do X (cid:54)= (cid:11) lồi, f , gi là các hàm lồi và h j là hàm affin trên X nên C là một tập lồi đóng, khác rỗng trong Rm+k+1. Hơn nữa, 0 /∈ C, thật vậy, vì nếu trái lại
21
0 ∈ C thì tồn tại một điểm chấp nhận được x thỏa mãn f (x) < f (x∗). Điều này mâu thuẫn với giả thiết x∗ là nghiệm tối ưu của bài toán (P).
i (i =
Khi đó theo Định lí tách 1, có thể tách tập C và 0, tức là tồn tại λ ∗
i (i = 1, 2, ...k) không đồng thời bằng 0 sao cho
0, 1, ...m), µ ∗
j µ j ≥ 0, ∀ (λ0, ..., λm, µ1, ..., µk) ∈ C.
m ∑ i=0
k ∑ j=1
(1) µ ∗ λ ∗ i λi+
1 ..., λ ∗
0 , λ ∗
của C ta chỉ lấy x = x∗. Từ chú ý này ta suy ra ngay tất cả các λ ∗ Chú ý rằng nếu λ0, ..., λm > 0 thì (λ0, ..., λm, 0, ..., 0) ∈ C, vì theo định nghĩa m ≥ 0.
Hơn nữa, với mọi ε > 0, x ∈ X, ta lấy
λ0 = f (x) − f (x∗) + ε, λi = gi(x) (i = 1, ..., m), µ j( j = 1, ..., k)
rồi thay vào (1) và cho ε → 0, sẽ được
j h j(x) ≥
m ∑ i=1
k ∑ j=1
µ ∗ λ ∗ i gi(x) + λ ∗ 0 f (x) +
j h j(x∗) ∀x ∈ X. µ ∗
i gi(x∗) + λ ∗
0 f (x∗) + λ ∗
k ∑ j=1
m ∑ i=1
(2)
Hay
L(x∗, λ ∗, µ ∗) ≤ L(x, λ ∗, µ ∗) ∀x ∈ X.
Đây chính là điều kiện đạo hàm triệt tiêu. Để chứng minh điều kiện bù, ta chú ý rằng do x∗ là điểm chấp nhận được, nên gi(x∗) (cid:54) 0 với mọi i. Nếu tồn tại một i nào đó mà gi(x∗) = ξ < 0, thì với mọi ε > 0, ta có
i ≥ 0. Nhưng vì ξ < 0 nên λ ∗
i ≤ 0. Do
(ε, ..., ξ , ε, ..., ε, 0, ..., 0) ∈ C (ξ ở vị trí i + 1).
0 > 0. Thật vậy, nếu
đó λ ∗
i gi(x∗)+ λ ∗
j h j(x) ∀x ∈ X.
k ∑ j=1
m k m ∑ ∑ ∑ j=1 i=1 i=1 Do λ ∗ 0 = 0 nên xảy ra 2 trường hợp:
0 = (3) µ ∗ Thay vào (1) và cho ε → 0, ta có λ ∗ i = 0. Bây giờ ta chứng minh điều kiện đủ. Trước hết, ta có λ ∗ λ ∗ 0 = 0, do điều kiện đạo hàm triệt tiêu và điều kiện bù, ta có j h j(x∗) ≤ µ ∗ λ ∗ i gi(x)+
22
i > 0. Khi đó thay thế x = x0 vào
Trường hợp 1: Tồn tại chỉ số i sao cho λ ∗
bất đẳng thức (3) ta được
i gi(x∗)+ λ ∗
j h j(x∗) ≤ µ ∗
j h j(x0) < 0 (vô lý).
m ∑ i=1
k ∑ j=1
k ∑ j=1
m ∑ i=1
0 = µ ∗ λ ∗ i gi(x0)+
i = 0 với mọi i và tồn tại j sao cho µ ∗
j > 0, ta có
Trường hợp 2: λ ∗
j h j(x) ∀x ∈ X.
j h j(x∗) ≤ µ ∗
k ∑ j=0
k ∑ j=0
0 = µ ∗
Do intX (cid:54)= 0 và hi là hàm a-phin với mọi j nên ta có
j h j(x) > 0 ∀x ∈ X.
k ∑ j=0
µ ∗
j = 0 ∀ j. Điều j không đồng thời bằng 0. Do đó λ ∗ 0 > 0 và 0 > 0, ta có thể sử dụng hàm Lagrange của bài toán
Theo giả thiết, các hàm h j độc lập tuyến tính trên X, nên µ ∗ i và µ ∗
này mâu thuẫn với giả thiết λ ∗ chia cả 2 vế của (2) cho λ ∗ có (P) dạng
j h j(x).
i gi(x∗)+ λ ∗
k ∑ j=1
m ∑ i=1
µ ∗ L(x, λ , µ) = f (x) +
Sử dụng điều kiện đạo hàm triệt tiêu và điều kiện độ lệch bù, với mọi nghiệm
chấp nhận được x∗, ta có
j h j(x∗) µ ∗
k ∑ j=1
f (x∗) = f0(x∗) +
j h j(x) ≤ f (x).
m ∑ i=1 m ∑ i=1
i gi(x∗)+ λ ∗ k ∑ j=1
µ ∗ ≤ f0(x) + λ ∗ i gi(x)+
Điều này chứng tỏ x∗ là một nghiệm tối ưu của bài toán (P).
Chú ý rằng, nếu X là tập mở (hơn nữa X là toàn bộ không gian) thì theo
Moreau-Rockfellar (trong [3]), điều kiện đạo hàm triệt tiêu kéo theo
j ∂ g j(x∗)+ λ ∗
i ∇hi(x∗). µ ∗
m ∑ j=1
k ∑ i=1
0 ∈ ∂ f (x∗) +
23
Ví dụ 2.1.7. Áp dụng định lí cho bài toán sau:
2, 1 2
(cid:3) .
2
(cid:3) Giả min (cid:8) f (x)| g j(x) ≤ 0, (i = 1, 2), x ∈ X(cid:9) , trong đó f (x) = x2, g1(x) = x2 − x, g2(x) = −x, X = (cid:2)− 1 Giải: Ta có miền chấp nhận được D = {x ∈ X| gi(x) ≤ 0 (i = 1, 2)} = (cid:2)0, 1
i ≥ 0(i = 0, 1, 2) không đồng thời bằng 0 sao cho
sử tồn tại λ ∗
1) L(x∗, λ ∗) = min L(x, λ ∗). i gi(x∗) = 0, i = 1, 2. 2) λ ∗ 3) λ ∗ 0 > 0. Từ Định lí 2.1.5 suy ra x∗ là nghiệm tối ưu của bài toán (P) đang xét
⇔ f (x∗) ≤ f (x), ∀x ∈ D ⇔ (x∗)2 ≤ x2, ∀x ∈ D ⇔ x∗ = 0.
Ngược lại, nếu x∗ = 0 là nghiệm của bài toán (P) thì từ Định lí 2.1.5, suy ra
i ≥ 0(i = 0, 1, 2) không đồng thời bằng 0 sao cho:
tồn tại λ ∗
1) L(x∗, λ ∗) = min L(x, λ ∗). 2) λ ∗ i gi(x∗) = 0, i = 1, 2. Ta có L(x∗, λ ∗) = min L(x, λ ∗).
⇔ L(x, λ ∗) ≥ L(x∗, λ ∗), ∀x ∈ X.
i gi(x) ≥λ ∗ λ ∗
i gi(x∗) ∀x ∈ X. λ ∗
0 f (x∗) +
⇔ λ ∗
0 f (x) + 0 x2 + λ ∗
2 ∑ i=1 1 (x2 − x) − λ ∗
2 ∑ i=1 2 x ≥ 0 ∀x ∈ X.
⇔ λ ∗
i gi(x∗) = 0, (i = 1, 2) λ ∗ ⇔ λ ∗ i .0 = 0, (i = 1, 2) ⇔ λ ∗ i ≥ 0, (i = 1, 2).
i ≥ 0, i = 0, 1, 2 không đồng thời bằng 0 nên ta có thể:
Ta có
1 = λ ∗
1 (x2 − x) − λ ∗
2 x ≥ 0 ∀x ∈ X
2 = 0. Ta có 0 x2 + λ ∗ λ ∗ ⇔ λ ∗ ⇔ λ ∗ ⇒ λ ∗
0 x2 ≥ 0 ∀x ∈ X. 0 > 0. 0 = 1.
Do λ ∗ + Chọn λ ∗
24
1 = λ ∗
2 = 1. Ta có
1 (x2 − x) − λ ∗
2 x ≥ 0 ∀x ∈ X
0 x2 + λ ∗ λ ∗ ⇔ (λ ∗
0 + 1)x2 − 2x ≥ 0 ∀x ∈ X
+ Chọn λ ∗
2 x ≥ 0 ∀x ∈ X
0 x2 + λ ∗ λ ∗ ⇔ λ ∗
1 (x2 − x) − λ ∗ 0 x2 − x ≥ 0 ∀x ∈ X,
suy ra không tông tại λ ∗ 0 . 1 = 0, λ ∗ . Chọn λ ∗ 2 = 1. Ta có
1 (x2 − x) − λ ∗
2 x ≥ 0 ∀x ∈ X
suy ra không tông tại λ ∗ 0 . 1 = 1, λ ∗ . Chọn λ ∗ 2 = 0. Ta có
0 + 1)x2 − x ≥ 0 ∀x ∈ X,
λ ∗ 0 x2 + λ ∗ ⇔ (λ ∗
0 = 1, λ ∗
1 = λ ∗
2 = 0 là các nhân
suy ra không tông tại λ ∗ 0 . Vậy x∗ là nghiệm tối ưu của bài toán (P) và λ ∗
tử Lagrange tương ứng.
2.2 Bài toán định vị với hàm mục tiêu lồi
Bài toán định vị xét trong chương này có thể mô tả như sau: Giả sử trong không gian Rn cho tập C gồm N điểm a1, a2, ..., aN. Bài toán
yêu cầu tìm một điểm x∗ trong tập C sao cho:
f (x∗) ≤ f (x) ∀x ∈ C,
trong đó f ký hiệu hàm khoảng cách (theo một nghĩa nào đó).
Khoảng cách ở đây lấy theo chuẩn Euclid hoặc có thể được định nghĩa một
cách tổng quát phù hợp với yêu cầu cụ thể của từng bài toán. Chẳng hạn:
N ∑ i
f (x) = (cid:13)x − ai(cid:13) (cid:13) 2 (cid:13)
25
2(cid:41)
hoặc
, (cid:13)x − ai(cid:13) (cid:13) (cid:13) f (x) = max i=1,N (cid:40) N ∑ i
trong nhiều trường hợp người ta có thể thay khoảng cách bằng một hàm chi phí
nào đó phụ thuộc vào điểm cần tìm.
Một trường hợp riêng được xét là tổng khoảng cách từ điểm cần tìm đến các
điểm khác là nhỏ nhất.
Một trường hợp riêng khác là khoảng cách xa nhất từ điểm cần tìm đến các
điểm khác là nhỏ nhất.
Gọi c(x, v) là khoảng cách liên quan đến điểm x,v. Khi đó mô hình toán học cho bài toán tìm vị trí x ∈ D sao cho tổng chi phí là nhỏ nhất. Cụ thể, bài toán có thể viết dưới dạng bài toán tối ưu như sau:
(cid:40) (cid:41)
p ∑ j=1
, min f (x) := c (cid:0)x, v j(cid:1) : x ∈ D (2.2)
người ta có thể thay hàm mục tiêu bằng chi phí bởi những hàm mục tiêu khác tùy thuộc vào yêu cầu cụ thể của từng bài toán. Một trường hợp hay được sử dụng là lấy hàm mục tiêu minmax. Tức là
f1(x) = max (cid:8)x(c, v j) : j = 1, ..., p(cid:9) .
(cid:13)x − v j(cid:13) (cid:13) thì hàm f1(x) = max (cid:8)(cid:13) (cid:13)x − v j(cid:13) (cid:13) : j = 1, ..., p(cid:9),
Ví dụ: Khi c(x, v j) = (cid:13) khi đó bài toán có dạng:
(2.3) min { f1(x) : x ∈ D}
có nghĩa là từ một điểm x∗ ∈ D sao cho khoảng cách xa nhất từ x∗ đến các điểm đã cho là gần nhất. Hay nói cách khác, bài toán (2.3) là bài toán định vị, dạng: Tìm x∗ ∈ D sao cho: f1(x∗) (cid:54) f1(x) ∀x ∈ D.
26
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
Ở phần này, sẽ trình bày một thuật toán toán sau đây có thể được xem như là
một sự cải biên của thuật toán dưới đạo hàm được xét trong tài liệu [8] cho bài toán định vị với hàm mục tiêu minmax.
Như đã đề cập ở phần giới thiệu, để giải bài toán, chúng ta cần tìm một điểm x trong một tập lồi D cho trước sao cho khoảng cách lớn nhất từ x đến các điểm trong một tập hữu hạn đã biết C là ngắn nhất.
Định nghĩa 2.3.1. Khoảng cách cực đại từ một điểm x tới một tập C được nghĩa bởi
d(x,C) := maxy∈C(cid:107)x − y(cid:107)2.
Khi đó bài toán tối ưu phải giải là:
d(x,C). min x∈D
(cid:111) (cid:110) . (cid:107)x − y(cid:107)2(cid:12) (cid:12) (cid:12) y ∈ VC
Bổ đề 2.3.2. Gọi VC là tập các đỉnh của convC. Khi đó ta có (i) VC ⊆ C (ii) d (x,C) = max Chứng minh. Ta thấy (i) được suy ra từ định nghĩa tập VC. Từ (ii), ta có
y∈conv(C)
(cid:107)x − y(cid:107)2, (cid:107)x − y(cid:107)2 = max d(x,C) = max y∈C (cid:107)x − y(cid:107)2 = max y∈VC
trong đó đẳng thức sau là giá trị lớn nhất của một hàm lồi trên tập lồi đạt được
tại điểm cực biên của nó.
Bổ đề 2.3.3. Đặt v1, . . . , vm là các phần tử của VC . Khi đó ta có: (i) d(x,C) lồi mạnh với hệ số 2; (ii) ∂ d(.,C)(x) = conv(∪ j∈ j(x)∂ d j(.,C)(x)), trong đó ∂ d j(. ,C)(x) là dưới vi phân của hàm lồi d j(. ,C) tại x và
J(x) = (cid:8) j ∈ J| d(x,C) = d j(x,C)(cid:9) .
27
Chứng minh. Từ Bổ đề 1.5.2(i) suy ra
d j(x,C). (cid:13)x − v j(cid:13) (cid:13) 2 (cid:13) d(x,C) = max j∈J = max j∈J
Theo Bổ đề 1.5.2(i), với mỗi j ∈ J hàm d j(x,C) = (cid:13)
(cid:13)x − v j(cid:13) 2 lồi mạnh với (cid:13) hệ số bằng 2. Do đó khẳng định (i) nhận được từ (ii) của Bổ đề 1.5.2, trong khi khẳng định (ii) tuân theo d(x,C).
Từ khía cạnh tính toán, việc tính giá trị hàm mục tiêu d(x,C) tại mỗi điểm của C sẽ rất tốn kém nếu số điểm trong C quá nhiều. May thay, nhờ có Bổ đề 2.3.2(i), để cực tiểu hàm d(x,C), ta chỉ cần phải xét trong đỉnh của bao lồi C. Ta sẽ chứng minh Bổ đề sau để chứng minh sự hội tụ của thuật toán.
Bổ đề 2.3.4. Giả sử {ξk} là một dãy số dương thỏa mãn điều kiện
ξk+1 ≤ ξk + βk ∀k ∈ N,
∞ ∑ k=0
βk < +∞, thì dãy {ξk} hội tụ. trong đó βk ≥ 0 và
2.3.1 Thuật toán và sự hội tụ của nó
Bằng Bổ đề 2.3.2(ii), bài toán cần giải có dạng
(cid:107)x − v(cid:107)2, (P(cid:48)) min x∈D d(x,C) = min x∈D max v∈VC
Giả sử D là một tập lồi đóng (không nhất thiết phải bị chặn). Do d(x, C) lồi
mạnh trên D, bài toán (P’) luôn luôn có một nghiệm tối ưu duy nhất.
Thuật toán sau đây có thể được xem như là một sự cải biên của thuật toán
dưới đạo hàm cho bài toán tối ưu hóa lồi không trơn không bị ràng buộc.
Thuật toán Khởi tạo. Chọn x0 ∈ D, tham số ρ > 0 cố định và chọn một dãy các số dương
{βk} thỏa mãn điều kiện
∞ ∑ k=0
∞ ∑ k=0
(2.4) βk = +∞, β 2 k < ∞.
28
Cho k := 0 Bước 1. Tìm vk ∈ C sao cho
2(cid:12) (cid:110)(cid:13) (cid:13)xk − v(cid:13) (cid:12) (cid:12) v ∈ VC (cid:13)
(cid:111) . vk= argmax
tại vk. (cid:13)vk − xk(cid:13) 2 (cid:13)
Bước 2. Lấy gk := 2 (cid:0)vk − xk(cid:1), tức là đạo hàm của (cid:13) Trường hợp (2a): Nếu gk = 0, thì kết thúc thuật toán, xk là nghiệm tối ưu của bài toán (P(cid:48)). Trường hợp (2b): Nếu gk (cid:54)= 0, thì tính
αk := βk max {ρ, (cid:107)gk(cid:107)}
và
, xk+1 := PD xk − αkgk(cid:17) (cid:16)
trong đó PD là hình chiếu Euclid lên tập D. Bước 3. Nếu xk+1 = xk, thì kết thúc thuật toán,xk là nghiệm tối ưu của (P’). Ngược lại, cho k := k + 1 và quay lại Bước 1.
Định lý 2.3.5.
(i) Nếu Thuật toán 2.1 kết thúc tại bước lặp k, thì xk là nghiệm tối ưu cho bài
toán (P’).
(ii) Nếu Thuật toán 2.1 không dừng lại, thì dãy {xk} hội tụ đến nghiệm x∗
của bài toán (P’). Chứng minh. (i) Nếu Thuật toán 2.1 kết thúc tại bước lặp k, thì
hoặc gk = 0 hoặc xk = PD(xk − αkgk).
Trong trường hợp đầu tiên,gk = 0 ∈ ∂ d(xk,C) , theo định nghĩa dưới vi phân, nó có nghĩa là (cid:10)0, x − xk(cid:11) + d(xk,C) ≤ d(x,C) ∀x ∈ D. Do đó
d(xk,C) ≤ d(x,C) ∀x ∈ D, (2.5)
nghĩa là xk cực tiểu hóa hàm d(xk,C) trên D. Ở trường hợp thứ hai,xk = xk+1 = PD(xk − αkgk), dùng tính chất của phép chiếu
29
metric ta có:
(2.6)
(cid:10)(xk − αkgk) − xk, x − xk(cid:11) ≤ 0 (cid:10)gk, x − xk(cid:11) ≤ 0 ⇔ −αk ⇔ (cid:10)gk, x − xk(cid:11) ≥ 0.
Do gk ∈ ∂ d (cid:0)xk,C(cid:1) nên ta có (cid:10)gk, x − xk(cid:11) + d(xk,C) ≤ d(x,C). Kết hợp với bất đẳng thức (2.6) thu được d(xk,C) ≤ d(x,C) ∀x ∈ D. Do đó xk là nghiệm tối ưu của bài toán (P’). (ii) Giờ giả sử Thuật toán không kết thúc. Gọi x∗ là nghiệm của bài toán (P(cid:48)). Ta sẽ chứng minh rằng khẳng định (ii) qua một số Bổ đề sau:
Bổ đề 2.3.6. Ta có
(cid:13)xk+1 − xk(cid:13) (cid:13) (cid:13) ≤ βk ∀k ∈ N
Chứng minh. Theo định nghĩa của αk, ta có
βk(cid:107)gk(cid:107) max{ρ,(cid:107)gk(cid:107)}
≤ βk. αk (cid:13)gk(cid:13) (cid:13) (cid:13) =
Do xk+1 = PD(xk − αkgk, lại dùng tính chất của phép chiếu metric, ta có
(2.7) ≤ 0 ∀x ∈ D. (xk − αkgk − xk+1, x − xk+1(cid:69) (cid:68)
Thay x bởi xk ta có
2 (cid:13) (cid:13)
(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) ≤ ≤ αk αkgk, xk − xk+1(cid:69) (cid:68) (cid:13)gk(cid:13) (cid:13) (cid:13) (cid:13)xk − xk+1(cid:13) (cid:13) (cid:13) ≤ βk (cid:13)xk − xk+1(cid:13) (cid:13) (cid:13) (2.8)
2(cid:111)
(cid:13)xk − xk+1(cid:13) có nghĩa là (cid:13) (cid:13)xk+1 − xk(cid:13) (cid:13) ≤ βk.
hội tụ. (cid:110)(cid:13) (cid:13)xk − x∗(cid:13) (cid:13)
2 = (cid:13) (cid:13)xk − x∗(cid:13) (cid:13) (cid:13)
Bổ đề 2.3.7. Với mỗi giá trị k, dãy Chứng minh. Dùng định nghĩa về chuẩn Euclid, ta có thể viết
(cid:13)xk+1 − xk(cid:13) 2 − 2 (cid:10)xk − xk+1, x∗ − xk+1(cid:11) + (cid:13) (cid:13) (cid:13)xk+1 − x∗(cid:13) 2. (cid:13)
Do vậy
2 (cid:13) (cid:13)
2 (cid:13) (cid:13)
2 (cid:13) (cid:13)
(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) = − (cid:68) xk − xk+1, x∗ − xk+1(cid:69) . + 2 (2.9) (cid:13)xk+1 − x∗(cid:13) (cid:13)xk − x∗(cid:13) (cid:13)xk+1 − xk(cid:13)
30
Chú ý rằng từ (2.8) ta có
(cid:13) (cid:13) (2.10) (cid:104)αkgk, xk − xk+1(cid:105) ≤ βk (cid:13)xk − xk+1(cid:13) (cid:13) ≤ β 2 (cid:13) k ,
theo (2.9) và (2.10), ta có
(2.11)
(cid:13)xk+1 − x∗(cid:13) 2 ≤ (cid:13) (cid:13) 2 − (cid:13) (cid:13)xk − x∗(cid:13) (cid:13)xk+1 − xk(cid:13) 2 + 2 (cid:10)αkgk, x∗ − xk+1(cid:11) (cid:13) (cid:13) (cid:13) (cid:13)xk − x∗(cid:13) ≤ (cid:13) 2 + 2 (cid:10)αkgk, x∗ − xk+1(cid:11) (cid:13) (cid:13)xk − x∗(cid:13) = (cid:13) 2 + 2 (cid:10)αkgk, x∗ − xk(cid:11) + 2 (cid:10)αkgk, xk − xk+1(cid:11) (cid:13) (cid:13)xk − x∗(cid:13) ≤ (cid:13) 2 + 2αk (cid:13) (cid:10)gk, x∗ − xk(cid:11) + 2β 2 k .
Từ [gk ∈ ∂ d(xk,C), ta có
gk, x∗ − xk(cid:69) (cid:68) ≤ d(x∗,C) − d(xk,C). (2.12)
Cộng (2.12) vào (2.11) để được
2 (cid:13) (cid:13)
2 (cid:13) (cid:13)
(cid:13) (cid:13) (cid:13) (cid:13) (cid:17) (cid:16) d(x∗,C) − d(xk,C) ≤ (2.13) + 2αk + 2β 2 k . (cid:13)xk+1 − x∗(cid:13) (cid:13)xk − x∗(cid:13)
Vì x∗ là một nghiệm tối ưu, d (cid:0)xk,C(cid:1) ≥ d (x∗,C), và vì vậy từ (2.13) ta có
2 (cid:13) (cid:13)
2 (cid:13) (cid:13)
2(cid:111)
(cid:13) (cid:13) (cid:13) (cid:13) ≤ + 2β 2 k , (cid:13)xk+1 − x∗(cid:13) (cid:13)xk − x∗(cid:13)
∞ ∑ k=0
từ đây, theo giả thuyết (cid:110)(cid:13) (cid:13)xk − x∗(cid:13) (cid:13) β 2 k < +∞ và từ Bổ đề 2.3 ta được dãy
là hội tụ.
Bổ đề 2.3.8. Ta có
(cid:17) (cid:16) d (cid:16) xk,C (cid:17) − d (x∗,C) = 0. sup (2.14) lim k→+∞
Chứng minh. Từ (2.13), ta có thể viết
2 (cid:13) (cid:13)
2 (cid:13) (cid:13)
(cid:13) (cid:13) (cid:13) (cid:13) − (cid:17) (cid:16) d(xk,C) − d(x∗,C) ≤ (2.15) 0 ≤ 2αk + 2β 2 k . (cid:13)xk+1 − x∗(cid:13) (cid:13)xk − x∗(cid:13)
31
Cộng hai vế của bất đẳng thức trên, ta được
(cid:0)d (cid:0)xk,C(cid:1)(cid:1) − d (x∗,C) 0 ≤ 2
m ∑ k=0
(cid:13)xm+1 − x∗(cid:13) 2 + 2 (cid:13) β 2 k
m αk ∑ k=0 (cid:13)x0 − x∗(cid:13) 2 − (cid:13) (cid:13) (cid:13)x0 − x∗(cid:13) (cid:13) .
≤ (cid:13) ≤ (cid:13)
,
Cho m → ∞ ta có
+∞ ∑ k=0
+∞ ∑ k=0
(cid:17) (cid:16) d(xk,C) − d(x∗,C) ≤ (cid:13) (2.16) 0 ≤ 2 αk (cid:13)x0 − x∗(cid:13) (cid:13) + 2 β 2 k .
+∞ ∑ k=0
Vì β 2 k < +∞, ta có
+∞ ∑ k=0
(2.17) αk(d(xk,C)−d(x∗,C)) ≤ +∞,
mặt khác, vì dãy (cid:8)xk(cid:9) bị chặn, nên dãy (cid:8)gk(cid:9) cũng bị chặn. Vì vậy, tồn tại L > 0 (cid:13)gk(cid:13) sao cho (cid:13) (cid:13) ≤ L < ∞, với k ∈ N. Cho L0 := max {ρ, L}, khi đó, theo định nghĩa của αk, ta có
≥ , (2.18) αk = βk max {ρ, (cid:107)gk(cid:107)} βk L0
điều này cùng với (2.16) ta được
+∞ ∑ k=0
+∞ ∑ k=0
(cid:17) (cid:16) d(xk,C) − d(x∗,C) (cid:17) (cid:16) d(xk,C) − d(x∗,C) ≤ (2.19) < +∞. αk βk 1 L0
+∞ ∑ k=0
Vì βk = +∞, ta có thể kết luận rằng
(cid:17) (cid:16) d(xk,C) − d(x∗,C) = 0. sup (2.20) lim k→+∞
Bây giờ dùng Bổ đề vừa chứng minh, ta có thể chứng minh khẳng định (ii) của
32
Định lí 2.3.5. Thật vậy, theo định nghĩa của lim sup, tồn tại một dãy con (cid:8)xk j(cid:9) thuộc dãy (cid:8)xk(cid:9) sao cho
(cid:17) (cid:17) (cid:16) d (cid:16) d (cid:16) xk j,C (cid:17) − d (x∗,C) (cid:16) xk,C (cid:17) − d (x∗,C) sup = 0. lim j→+∞ = lim k→+∞
Vì (cid:8)xk j(cid:9) bị chặn, ta có thể giả sử rằng
xk j = x. lim j→+∞
Ta có:
(cid:0)d (x∗,C) − d (cid:0)xk j,C(cid:1)(cid:1)
d(x∗,C) − d(x,C) = lim j→∞ (cid:0)d (cid:0)xk j,C(cid:1) − d (x∗,C)(cid:1) (cid:0)d (cid:0)xk,C(cid:1) − d (x∗,C)(cid:1) = − lim j→∞ = − lim j→∞
= 0.
Điều này cho thấy x cũng là một nghiệm tối ưu. Nhớ rằng x∗ là nghiệm duy nhất cho bài toán (P), do vậy x∗ = x, Vì dãy (cid:8)(cid:13) (cid:13)xk − x∗(cid:13) (cid:9) hội tụ và dãy con (cid:8)xk j(cid:9) (cid:13) của (cid:8)xk(cid:9) hội tụ đến x∗, ta có
xk j = x∗. xk j = lim j→+∞ lim k→+∞
Vì vậy, toàn bộ dãy (cid:8)xk(cid:9) phải hội tụ đến x∗.
Nhận xét 2.3.9. Như ta đã thấy, nếu gk = 0 hoặc xk+1 = xk, thì xk là một nghiệm chính xác. Trong tính toán, để có nghiệm xấp xỉ, ta có thể dừng thuật toán nếu (cid:13)xk, 1(cid:13) (cid:13)gk(cid:13) (cid:13) (cid:9) ε, với [ε > 0 cho trước. (cid:13) (cid:13) ≤ ε hoặc (cid:13) (cid:13)xk+1 − xk(cid:13) (cid:13) ≤ max (cid:8)(cid:13)
2.3.2 Các khía cạnh và kết quả tính toán
Trong phần này chúng ta xem xét các thực nghiệm và các kết quả tính toán
trên một mô hình trong không gian hai chiều.
Giả sử rằng số phần tử của tập hợp C, của người sử dụng là rất lớn (thường
xuất hiện trong mô hình thực tế) và tập hợp D mà chúng ta muốn xác định vị trí
33
của cơ sở là một tập hợp lồi đa diện được cho như dưới đây
D = (cid:8)x ∈ R2(cid:12) (cid:12) Ax ≤ b(cid:9) .
Với S là một ma trận mx2 đủ bậc, b là một vec-tơ thuộc Rn.
Như đã trình bày ở trên, để cực tiểu hàm d(x,C) ta chỉ cần biết đỉnh bao lồi
của C (hình vẽ dưới).
Để xác định bao lồi của C, đã có một số thuật toán hiệu quả trong không gian hai chiều, như: thuật toán Quickhull (QH) và thuật toán Quickhull mới (NQH).
Thuật toán trên đã được thử nghiệm trên nhiều tập được tạo ngẫu nhiên và
được thử nghiệm với hai tập D1 và D2 cho bởi
(cid:34) (cid:35)
A1 = 8 0 5 1 −3 14 −15 −7 4
−1 −10 1 b1 = (103, 11, 17, 142, 155, 133)T
Kết quả tính toán công bố ở tài liệu [8], được cho ở bảng dưới đây.
34
35
Kết luận
Bài toán định vị được nhiều nhà toán học quan tâm, nghiên cứu và có một
lịch sử phát triển lâu dài vì tính thực tế của nó.
Luận văn đã trình bày một số vấn đề sau: Các khái niện cơ bản và kết quả của giải túch lồi như: Tập lồi, tập a-fin, hàm
lồi, bài toán qui hoạch lồi.
Giới thiệu về bài toán định vị với mục tiêu hàm lồi, đó là bài toán tìm một vị
trí trong miền xác định sao cho khoảng cách từ vị trí đó đến các điểm cho trước là nhỏ nhất.
Tiếp đến trình bày một thuật toán dựa trên phương pháp dưới đạo hàm để
giải một bài toán định vị. Sự hội tụ của thuật toán cũng đã được chứng minh chi tiết trong luận văn.
36
Tài liệu tham khảo
Tiếng Việt
[1] Lê Dũng Mưu (1998), Giáo trình các phương pháp tối ưu, Nhà xuất bản
Khoa học và Kĩ thuật, Hà Nội.
[2] Nguyễn Văn Hiền, Lê Dũng Mưu và Nguyễn Hữu Điển (2008), Nhập môn
giải tích lồi, Nhà xuất bản Đại học quốc gia Hà Nội.
[3] Đỗ Văn Lưu và Phan Huy Khải (1998), Giải tích lồi, Nhà xuất bản Khoa
học và Kĩ thuật, Hà Nội.
[4] Nguyễn Thị Bạch Kim (2008), Giáo trình Các phương pháp tối ưu - Lý
thuyết và thuật toán, Nhà xuất bản Bách khoa và kĩ thuật.
[5] Trần Vũ Thiệu và Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi
tuyến, NXB Đại học Quốc gia Hà Nội.
Tiếng Anh
[6] D. Bertsekas (2004), Nonlinear Programming, Athena Sicentific.
[7] Hoang Tuy (2016), Convex Analysís and Global Optimization, Springer.
[8] Nguyen Kieu Linh, Le Dung Muu (2015), "A convex hull algorithm for solving a location problem". RAIRO - Operations Research 49, pp. 589–600.
