Từ bài toán quy hoạch toàn phương đến bất đẳng thức biến phân Affine

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

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

NGUYỄN THỊ SIM

TỪ BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

ĐẾN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2017

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

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

NGUYỄN THỊ SIM

TỪ BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

ĐẾN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE

Chuyên ngành: Toán ứng dụng

Mã số: 60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

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 chuẩn bị 4

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

1.1.1 Tập affine và bao affine . . . . . . . . . . . . . . 4

1.1.2 Tập lồi, nón lồi và bao lồi . . . . . . . . . . . . . 6

1.1.3 Điểm cực biên, phương lùi xa, nón lùi xa và phương

cực biên . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.4 Các định lý tách tập lồi . . . . . . . . . . . . . . . 8

1.1.5 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . 9

1.1.6 Hàm lồi và tính chất . . . . . . . . . . . . . . . . 10

1.2 Hàm toàn phương . . . . . . . . . . . . . . . . . . . . . . 12

1.2.1 Ma trận xác định dương và ma trận nửa xác định

dương . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.2 Hàm toàn phương . . . . . . . . . . . . . . . . . . 13

2 Bài toán quy hoạch toàn phương 15

2.1 Giới thiệu bài toán và sự tồn tại nghiệm . . . . . . . . . . 15

2.1.1 Định nghĩa bài toán quy hoạch toàn phương . . . . 15

2.1.2 Các dạng bài toán quy hoạch toàn phương . . . . . 17

2.1.3 Điều kiện tồn tại nghiệm . . . . . . . . . . . . . . 17

2.2 Điều kiện tối ưu (Điều kiện Karush-Kuhn-Tucker (KKT)) . 29

3 Bài toán bất đẳng thức biến phân affine 31

3.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . . 31

ii

3.1.1 Bất đẳng thức biến phân . . . . . . . . . . . . . . 31

3.1.2 Bất đẳng thức biến phân affine . . . . . . . . . . . 32

3.2 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân affine 36

3.3 Giải bài toán quy hoạch toàn phương bằng cách đưa về bài

toán bất đẳng thức biến phân affine . . . . . . . . . . . . . 40

Kết luận 44

Tài liệu tham khảo 45