Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi

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

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

VŨ THỊ NGỌC BÍCH

MỘT PHƯƠNG PHÁP QUI HOẠCH LỒI

GIẢI BÀI TOÁN CHẤP NHẬN LỒI

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

Thái Nguyên - 2018

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

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

VŨ THỊ NGỌC BÍCH

MỘT PHƯƠNG PHÁP QUI HOẠCH LỒI

GIẢI BÀI TOÁN CHẤP NHẬN LỒI

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

Mã số: 84 60 112

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

i

Mục lục

Mở đầu 1

Chương 1 Bài toán qui hoạch lồi 3

1.1 Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

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

1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Bài toán qui hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . 16

Chương 2 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi 24

2.1 Bài toán chấp nhận lồi và ví dụ . . . . . . . . . . . . . . . . . . . . 24

2.1.1 Bài toán chấp nhận lồi . . . . . . . . . . . . . . . . . . . . 24

2.1.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Một phương pháp qui hoạch lồi giải bài toán chấp nhận lồi . . . . . 25

2.2.1 Tóm tắt hai phương pháp cơ bản: chiếu lần lượt và chiếu song

song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2.2 Thuật toán đạo hàm giải bài toán qui hoạch lồi . . . . . . . . 29

2.2.3 Phương pháp chuyển về bài toán qui hoạch lồi . . . . . . . . 32

Kết luận 41

Tài liệu tham khảo 42

1

Mở đầu

Tối ưu hóa được khởi nguồn như một ngành của Toán học, có rất nhiều ứng dụng

trong quy hoạch tài nguyên, thiết kế chế tạo máy, điều khiển tự động, quản trị kinh

doanh... trong việc tạo nên các hệ hỗ trợ ra quyết định trong quản lý và phát triển các

hệ thống lớn.

Chính vì vậy, các lĩnh vực của tối ưu hóa ngày càng trở nên đa dạng mang nhiều

tên gọi khác nhau như Quy hoạch toán học, Điều khiển tối ưu, Vận trù học, Lý thuyết

trò chơi... Hiện nay môn học Tối ưu hóa được đưa vào giảng dạy trong nhiều chương

trình đào tạo đại học cho các ngành khoa học cơ bản. Một trong những bài toán quan

trọng của Tối ưu hóa là bài toán qui hoạch lồi.

Nhiều bài toán quan trọng trong lĩnh vực toán học hoặc trong thực tế có thể

chuyển về bài toán qui hoạch lồi (tìm cực tiểu của một hàm lồi trên một tập lồi). Đối

với lớp bài toán này có nhiều phương pháp giải hiệu quả, ví dụ như phương pháp đạo

hàm, phương pháp dưới đạo hàm, phương pháp điểm trong,. . . Bài toán chấp nhận

lồi là bài toán tìm một điểm chung của một số hữu hạn hoặc vô hạn các tập lồi. Bài

toán này rất quan trọng vì nhiều bài toán trong toán học cũng như trong các lĩnh vực

thực tế khác đều có thể chuyển về bài toán chấp nhận lồi. Ví dụ như bài toán giải hệ

phương trình, bài toán tìm nghiệm chung của các bài toán tối ưu, bất đẳng thức biến

phân,. . .

Chính vì vậy chúng tôi chọn đề tài: "Một phương pháp qui hoạch lồi giải bài toán

chấp nhận lồi". Luận văn nghiên cứu về bài toán chấp nhận lồi và giới thiệu một vài

phương pháp giải bài toán này, đặc biệt đi sâu vào phương pháp chuyển bài toán chấp

nhận lồi về qui hoạch lồi. Nội dung luận văn gồm hai chương:

Chương 1. "Bài toán qui hoạch lồi” giới thiệu các kiến thức cơ bản nhất về giải