Một phương pháp tách giải một lớp bài toán tối ưu lồi mạnh

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

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

-------------------------------

NGUYỄN VĂN MẠNH

MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP

BÀI TOÁN TỐI ƯU LỒI MẠNH

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

THÁI NGUYÊN - 2016

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

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

-------------------------------

NGUYỄN VĂN MẠNH

MỘT PHƯƠNG PHÁP TÁCH GIẢI MỘT LỚP

BÀI TOÁN TỐI ƯU LỒI MẠNH

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 - 2016

Mục lục

Mở đầu 1

1 Bài toán tối ưu lồi 3

1.1 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . 3

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

1.3 Bài toán tối ưu lồi . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Các khái niệm . . . . . . . . . . . . . . . . . . . 12

1.3.2 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . 13

1.3.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . 15

1.4 Tối ưu có ràng buộc . . . . . . . . . . . . . . . . . . . 16

1.4.1 Đối ngẫu . . . . . . . . . . . . . . . . . . . . . . 16

1.4.2 Điều kiện tối ưu có ràng buộc . . . . . . . . . . 20

2 Một thuật toán tách giải bài toán tối ưu lồi mạnh 26

2.1 Toán tử chiếu lên tập lồi đóng . . . . . . . . . . . . . . 26

2.2 Một thuật toán chiếu giải bài toán tối ưu lồi . . . . . . 30

2.2.1 Thuật toán chiếu dưới đạo hàm . . . . . . . . . 30

2.2.2 Một thuật toán tách giải bài toán tối ưu lồi mạnh 35

Kết luận 42

Tài liệu tham khảo 43

DANH MỤC CÁC KÍ HIỆU

Kí hiệu Ý nghĩa

R

n Không gian Euclide n - chiều trên trường số thực;

N Tập số tự nhiên;

xi Tọa độ thứ i của x;

x

T Véctơ hàng (chuyển vị của x);

< x; y >= x

T

y Tích vô hướng của 2 vectơ x và y;

||x|| Chuẩn Euclide của x;

∇f(x) Đạo hàm của f theo x;

∂f(x) Dưới vi phân của f theo x;

∂εf(x) ε - dưới vi phân của f theo x.