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

R

n 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

domf 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