Thuật toán DCA và ứng dụng

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN VĂN HỒNG

THUẬT TOÁN DCA VÀ ỨNG DỤNG

Luận văn Thạc sỹ

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số: 60. 46. 01. 12

Người hướng dẫn khoa học

PGS. TS. PHẠM NGỌC ANH

THÁI NGUYÊN - NĂM 2014

MỤC LỤC

Mục lục 2

Lời cảm ơn 3

Bảng ký hiệu 4

Lời nói đầu 5

1. Một số khái niệm cơ bản 7

1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.2. Phần trong tương đối và bao lồi đóng . . . . . . . . . . . . 9

1.1.3. Phương lùi xa và nón lùi xa. . . . . . . . . . . . . . . . . . . . . . . 10

1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1. Hàm lồi và hàm lõm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.2. Hàm lồi liên tục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.3. Hàm lồi khả vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.4. Dưới vi phân. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3. Hàm D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3.1. Định nghĩa và tính chất của hàm D.C . . . . . . . . . . 16

1.3.2. Bài toán quy hoạch D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4. Bài toán đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.4.1. Điều kiện tối ưu trong bài toán lồi. . . . . . . . . . . . . . . 23

1.4.2. Định lý Karush-Kuhn-Tucker. . . . . . . . . . . . . . . . . . . . . 27

2. Thuật toán DCA 31

2.1. Bài toán D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2

2.2. Thuật toán DCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.3. Sự hội tụ của thuật toán DCA . . . . . . . . . . . . . . . . . . . . . . . 37

3. Ứng dụng thuật toán DCA 47

3.1. Điều kiện tối ưu hóa toàn bộ cho (P1) và (P2) . . . . . . . . 47

3.2. Ứng dụng thuật toán DCA giải bài toán (P1) . . . . . . . . . 48

3.3. Tính hội tụ của DCA đến nghiệm cục bộ của bài toán (P1)

51

3.4. Ứng dụng thuật toán DCA giải bài toán (P2) . . . . . . . . 54

Kết luận 56

Tài liệu tham khảo 57

Lời cảm ơn

Luận văn này được hoàn thành tài trường Đại học Khoa học - Đại

học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS.

Phạm Ngọc Anh (Học viện Công nghệ Bưu chính Viễn thông), thầy đã

trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian

viết luận văn vừa qua.

Xin chân thành cảm ơn các thầy, cô giáo trong Ban chủ nhiệm khoa,

các bạn học viên lớp cao học Toán K6B trường Đại học Khoa học - Đại

học Thái Nguyên và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động

viên tác giả trong quá trình học tập và nghiên cứu tại nhà trường.

Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người

thân luôn khuyến khích, động viên tác giả trong suốt quá trình học tập

và làm luận văn.

Mặc dù có nhiều cố gắng, nhưng luận văn khó tránh khỏi những thiếu

sót và hạn chế. Tác giả rất mong nhận được những ý kiến đóng góp quý

báu của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn.

Xin chân thành cảm ơn!

Thái Nguyên, tháng 6 năm 2014

Tác giả

Nguyễn Văn Hồng

Bảng ký hiệu

R : Tập hợp số thực

R+ : Tập hợp các số trong nửa đoạn [0, +∞)

R

n

: Không gian số thực n - chiều

R

n

+ : Không gian số thực không âm n - chiều

x ∈ C : x thuộc tập C

x 6∈ C : x không thuộc tập C

∀x : Với mọi x

∃x : Tồn tại x

∅ : Tập hợp rỗng

∩ : Phép giao các tập hợp

∪ : Phép hợp các tập hợp

x = y : x được định nghĩa bằng y

hx, yi : Tích vô hướng của x và y

∇x f(x) : Véc tơ đạo hàm của hàm f tại điểm x

x

k * x : Dãy x

k hội tụ yếu tới x

x

k → x : Dãy x

k hội tụ mạnh tới x

I : Ánh xạ đồng nhất

arg min {f (x)|x ∈ C} : Tập các điểm cực tiểu của hàm f trên C

kxk : Chuẩn của véc tơ x.