Gradient suy rộng và ứng dụng vào bài toán tối ưu không trơn

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

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

ĐẶNG HIẾU TRỌNG

GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN

TỐI ƯU KHÔNG TRƠN

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

THÁI NGUYÊN - NĂM 2010

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

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

ĐẶNG HIẾU TRỌNG

GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN

TỐI ƯU KHÔNG TRƠN

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

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

Mã số: 60.46.36

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

GS. TS. TRẦN VŨ THIỆU

THÁI NGUYÊN - NĂM 2010

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

Mục lục

Mở đầu 1

1 Gradient suy rộng 3

1.1 Định nghĩa và ký hiệu . . . . . . . . . . . . . . . . . . . 3

1.2 Một số tính chất cơ bản của gradient suy rộng . . . . . . 8

2 Một số phương pháp giải bài toán tối ưu không trơn 11

2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Một số phương pháp giải bài toán tối ưu không trơn . . . 18

2.3.1 Phương pháp dưới gradient . . . . . . . . . . . . 18

2.3.2 Phương pháp siêu phẳng cắt . . . . . . . . . . . . 25

2.3.3 Phương pháp bó . . . . . . . . . . . . . . . . . . 27

2.3.4 Phương pháp miền tin cậy đối với hàm hợp không

trơn . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3.5 Phương pháp Newton không trơn . . . . . . . . . 38

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . 47

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ii

Lời cảm ơn

Bả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 dưới sự hướng dẫn trực tiếp của GS.TS. Trần Vũ

Thiệu Viện toán học - Viện KHCN Việt Nam. Tác giả xin bày tỏ lòng

kính trọng và biết ơn sâu sắc tới Thầy về sự hướng dẫn tận tình trong

suốt thời gian tác giả làm luận văn.

Tác giả xin bày tỏ lòng biết ơn tới các Thầy Cô ở Viện toán học - Viện

KHCN Việt Nam, Viện công nghệ thông tin, Khoa công nghệ thông tin,

Khoa toán và Phòng đào tạo sau đại học trường Đại học Khoa Học -

Đại học Thái Nguyên đã tận tình giảng dạy và tạo mọi điều kiện thuận

lợi cho tác giả trong quá trình học tập tại trường.

Tác giả xin gửi lời cảm ơn tới Ban giám đốc trung tâm Giáo dục

thường xuyên Hưng Hà - Thái Bình và các Thầy Cô trong trung tâm đã

tạo điều kiện giúp đỡ tác giả trong suốt thời gian học.

Xin chân thành cảm ơn anh chị em học viên lớp cao học và các bạn

bè đồng nghiệp về những đóng góp quý báu, sự giúp đỡ tận tình và sự

cổ vũ hết sức to lớn trong suốt quá trình học tập, nghiên cứu và làm

luận văn.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1

Mở đầu

Hàm không trơn được hiểu là những hàm không khả vi. Vì thế những

hàm này còn được gọi là những hàm không khả vi.

Bài toán quy hoạch phi tuyến

min{f(x) : gi(x) = 0, i = 1, ..., p, gi(x) ≤ 0, i = p + 1, ..., m}

được gọi là bài toán tối ưu không trơn nếu hàm mục tiêu f(x) hay một

trong các hàm ràng buộc gi(x) là một hàm không trơn.

Như chúng ta đã biết với bài toán tối ưu trơn, do các hàm khả vi có

rất nhiều tính chất đẹp, do đó các phương pháp giải đối với bài toán

này đã được xây dựng và phát triển khá hoàn thiện. Nhưng với bài toán

tối ưu không trơn thì việc xây dựng các phương pháp giải gặp rất nhiều

khó khăn, ngay cả những bài toán trong R

1 việc giải cũng không đơn

giản. Tuy nhiên, bài toán tối ưu không trơn có tính ứng dụng thực tiễn

rất cao. Vì vậy, xây dựng phương pháp giải cho bài toán tối ưu không

trơn thu hút rất nhiều người làm toán quan tâm. Chính vì lẽ đó mà tác

giả đã chọn đề tài "Gradient suy rộng và ứng dụng vào bài toán tối ưu

không trơn".

Mục đích của luận văn này là trình bày những kiến thức ban đầu về

tối ưu không trơn, đề cập tới điều kiên tối ưu không trơn và giới thiệu

một số phương pháp bằng số giải bài toán tối ưu không trơn.

Luận văn được chia làm hai chương.

Chương 1: Gradient suy rộng

Trong chương này, tác giả trình bày một số khái niệm về hàm Lipschitz,

đạo hàm theo hướng, đạo hàm theo hướng Dini trên, đạo hàm suy rộng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn