Giáo trình tối ưu phi tuyến

GT.00000 I I

JC VÀ ĐÀO TẠO

941 ] 1ÁI N G U Y Ê N

TRẦN VŨ THIỆU - N G U YỄN THỊ THU THỦY

'ÉN

u

O K I

Q D B H* HQI NHÀ XUẤT BẢN ĐẠI HỌC Q U Ố C GIA HÀ NỘI

BỘ G IÁ O DỤC VÀ Đ À O TẠ O

ĐẠI HỌC THÁI N G U Y Ê N

TRẦN VŨ THIỆU - NGUYỄN THỊ THU THỦY

GIÁO TRÌNH

TỐI 11 PH I TUYẾN

NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI

SÁCH ĐƯỢC XUẤT BẢN BỜI sự TÀI TRỢ CỦA Dự ẤN CIÁO DỤC ĐẠI HỌC 2

MỤC LỤC

T rang

Lời nói đ ầ u ..................................................................................................13

Phán 1. LÝ THUYẾT CHUNG

C hương 1. BÀI TO ÁN T ố i ư u

1.1. Khái niệm và định nghĩa...................................................................17

1.2. Ví dụ .....................................................................................................20

1.3. Phàn loại bài toán tối ưu ..................................................................25

1.4. Sự tồn tại nghiệm tối ư u ...................................................................27

1.4.1. Hàm nửa liên tục dưới ..........................................................28

1.4.2. Điều kiện bức .........................................................................30

Dài t ậ p ..........................................................................................................35

C hương 2. G IẢ I T ÍC H LỚ I

2.1. Tập lồi....................................................................................................37

2 .1 .1. Tập afin và bao afin .............................................................. 37

2.1.2. Tập lồi, nón lồi và bao lồi ....................................................41

2.1.3. Phần trong tương đối và bao lồi dóng ...............................46

2. ỉ .4. Các định lý tách tập lồi .........................................................49

2.1.5. Phương lùi xa và nón lùi xa .................................................55

2.1.6. Siêu phảng tựa, diện, điểm cực biên và phương cực biên.......57

3

2.1.7. Biểu diễn tập lồi qua các điểm cực biên và phương

cực b iê n ....................................................................................59

2.1.8. Tập lồi đa diện ........................................................................ 60

2.2. Hàm lồ i...................................................................................................63

2.2.1. Hàm lồi và hàm lõm .............................................................. 63

2.2.2. Hàm lồi liên t ụ c .......................................................................68

2.2.3. Hàm lồi khả v i.......................................................................... 70

2ắ2.4. Dưới vi phán ............................................................................ 74

2.2.5. Hàm lồi mạnh .......................................................................... 78

Bài tập .......................................................................................................... 80

Chương 3. Đ IỂU K IỆ N T ố i Ư u

3.1. Bài toán tối ưu không ràng buộc......................................................85

3.2. Bài toán tối ưu với ràng buộc tập ....................................................91

3.2.1. Nón chấp nhận được và nón tiếp x ú c .................................92

3.2.2. Điều kiện cần tối ưu cấp 1 và cấp 2 ................................... 94

3.2.3. Điều kiện đủ tối ưu cấp 1 và cấp 2 ..................................... 97

3.2.4. Điều kiện tối ưu cấp 0 dối với bài toán qui hoạch lồ i......100

3.3. Bài toán tối ưu với ràng buộc hiển ......................... 103

3.3.1. Nội dung bài toán ....................................... 103

3.3.2. Điều kiện chính q u i.......................................... Ị04

3.3.3. Điều kiện tối ưu cấp 1 .......................................... J0 7

3.3.4. Điều kiện tối ưu cấp 2 ....................................................... ] Ị J

B ài tậ p .......................................................................................................... 118

4

C hương 4. BÀI TO ÁN Đ ố i NGAU

4.1. Đối ngẫu L ag ran g e ........................................................................ 122

4.1.1. Cặp bài toán đối ngẫu ........................................................122

4.1.2. Đối ngẫu y ế u ........................................................................ 125

4.1.3. Đối ngẫu mạnh ....................................................................126

4.1.4. Ràng buộc đẳng th ứ c ......................................................... 128

4.1.5. Qui hoạch tuyến tính ............................ .............................129

4.1.6. Qui hoạch toàn phương....................................................... 129

4.2. Điểm yên ngựa ............................................................................... 130

4.2.1. Hàm Lagrange và điểm yên ngựa.....................................130

4.2.2. Lời giải tối ưu và điểm yên n g ự a .....................................131

Bài tập .......................................................................................................134

Phần 2ệ PHƯƠNG PHÁP TÌM c ự c TIỂU

KHÔNG RÀNG BUỘC

Chương 5. TÌM c ự c TlỂU HÀM MỘT BIẾN

5.1. Phương pháp tìm theo ti a .............................................................. 135

5.1.1. Tìm chính xác và tìm gần đúng theo tia ........................135

5.1.2. Phương pháp lặp N ew to n ...................................................140

5.2. Phương pháp khử liên tiếp ............................................................142

5.2.1. Phương pháp Fibonacci ..................................................... 143

5.2.2. Phương pháp lát cắt v à n g ...................................................148

5.3. Phương pháp nội suy ......................................................................15 4

5

5.3.1. Nội suy bậc hai .....................................................................154

5.3.2. Nội suy bậc ba .....................................................................157

Bài tập .......................................................................................................

C hương 6. PHƯ Ơ N G PH Á P K H Ô N G DÙNG ĐẠO H À M

6.1. Phương pháp Hooke - Je e v e s........................................................167

6.2. Phương pháp Nelder - M e a d ......................................................... 173

Bài t ậ p .........................................................................................................181

C hương 7. PH Ư Ơ N G PH Á P G R A D IEN T

7.1. Phương pháp hướng dốc nhất ....................................................... 183

7.1.1. Nội dung phương pháp ....................................................... 183

7.1.2. Sự hội tụ của phương pháp g rad ie n t................................ 184

7.1.3. Các dạng khác của phương pháp gradient .....................189

7.2. Phương pháp N ew to n ...................................................................... 194

7.2.1. Nội dung phương pháp ....................................................... 194

7.2.2. Sự hội tụ của phương pháp Newton suy rộng .............. 197

7.2.3. Cải biên phương pháp Newton suy r ộ n g ........................ 200

7.3. Phương pháp tựa N ew to n ................................................................201

7.3.1. Nội dung phương pháp ....................................................... 201

7.3.2. Phương pháp Davidon - Fletcher - Powell .....................201

7.4. Phương pháp gradient liên hợp .................... 209

7.4.1. Hướng liên hợp ................................................ 209

7.4.2. Phương pháp Fletcher - Reeves ............................ 212

Bài tập ........................................................................................................222

6

Phần 3ế PHƯƠNG PHÁP TÌM c ự c TIỂU

CÓ RÀNG BUỘC

C hương 8. PHƯ Ơ N G PH Á P TRỰ C T IẾ P

8.1. Phương pháp hình học .................................................................. 224

8.2. Phương pháp nhân tử L agrrange................................................. 229

8.2.1. Ràng buộc đẳng thức.......................................................... 230

8.2.2. Ràng buộc không â m ......................................................... 236

8.3. Phương pháp dùng điều kiện KKT ............................................ 240

8.3.1. Bài to á n ..................................................................................240

8.3.2. Các ví d ụ ............................................................................... 243

8.3.3. Bài toán tối ưu lồi ...............................................................249

Bài tậ p ........................................................................................................ 253

C hương 9. PH Ư Ơ N G PH Á P TUYÊN TÍN H HÓA

9.1. Tuyến tính hóa ràng b u ộ c .............................................................255

9.1.1. Bài toán và ý tưởng phương pháp g iả i............................ 255

9.1.2. Thuật toán siêu phẳng cắt Kelley ................................... 255

9.1.3. Một sô' ví d ụ ..........................................................................258

9.2. Tuyến tính hóa mục tiê u ................................................................263

9.2.1. Bài toán và các giả th iế t.....................................................263

9.2.2. Thuật toán Frank - Wolfe ................................................. 264

9.2.3. Ví dụ minh h ọ a .................................................................... 266

B ài t ậ p ........................................................................................................271

7

Chương 10. PHƯƠNG PHÁP HƯỚNG CHẤP NHẬN Đ ư ợ c

10.1. Ràng buộc phi tu y ế n .....................................................................273

10.1.1. Bài toán và ý tường phương pháp g iả i.......................... 273

10.1.2. Chọn điểm xuất phát và hướng giảm ở mỗi bước .....274

10.1.3. Thuật toán Zoutendijk ......................................................277

10.2. Ràng buộc tuyến tín h ....................................................................282

10.2.1. Bài to á n .................................................................................282

10.2.2. Thuật toán giải bài toán tối ưu với ràng buộc

tuyến tín h ................................................................................. 286

10.3. Phương pháp chiếu Rosen ...........................................................292

10.3.1. Bài to á n .................................................................................292

10.3.2. Mô tả khái quát thuật to á n ...............................................292

10.3.3. Thuật toán chi t i ế t .............................................................. 294

B ài tậ p ..........................................................................................................299

C hương 11. PH Ư Ơ N G P H Á P PH Ạ T

11.1. Phương pháp hàm c h ắ n .................................................................301

11.1.1. Bài toán và ý tưởng thuật toán ........................................301

11.1.2. Hàm chắn lôga và hàm chắn nghịch đảo .....................304

11.1.3. Đường trung tâ m .................................................................309

11.1.4. Nhân tử Lagrange .............................................................. 311

11.1.5. Trường hợp bài toán không lồi .......................................316

11.2. Phương pháp hàm phạt .................................................................3 1 5

8

l l ể2.1. Hàm phạt bậc hai ..............................................................317

11.2.2. Hàm phạt chính x á c ......................................................... 323

11.2.3. Hàm phạt Lagrange gia tă n g .......................................... 327

Bài tậ p ........................................................................................................331

Trả lời bài tập ..........................................................................................333

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

Các từ k h ó a ...............................................................................................343

9

MỘT SỐ KÝ HIỆU TOÁN HỌC

R tập số thực (hay đường thẳng thực)

r không gian Euclid n chiều

X e c X thuộc tập c (x là một phần tử của tập C)

x í C X không thuộc tập c (x không phải là phần tử của tập Q

0 tập rỗng (tập không chứa phần tử nào)

C + D tổng của tập c và tập D

C - D hiệu của tập c và tập D

c X D tích của tập c và tập D

C u D hợp của tập c và tập D

C n D giao của tập c và tập D

C c D c là tập con của tập D

C c D c là tập con (có thể bằng) của tập D

ICI số phần tử của tập c

<x, y>, xTy tích vô hướng của X và y (hai véctơ có cùng số chiều)

llxll chuẩn Euclid của véctơ X

các tọa độ của điểm hay thành phần của véctơ X

X |,x 2,....... x„ (dùng chỉ số dưới)

x \ X2, X3, ... liệt kè các véctơ có cùng số chiều (dùng chỉ số trẽn)

[a, b] đoạn thẳng nối hai điểm (véctơ) a và b

B(0,1) hình cầu đơn vị mở (tâm 0, bán kính 1)

B (0 .1) hình cầu đơn vị đóng (tâm 0, bán kính 1)

10

a f f E bao afin của tập E

conv E bao lồi của tập E

conv E bao lồi đóng của tập E

cone E bao nón của tập E

dim c thứ nguyên (hay sô' chiều) của tập c

int c phán trong của tập c

ri c phần trong tương đối của tập c

ÕC biên tương đối của tập c

rec c nón lùi xa của tập c

c bao đóng của tập c

c tập đỉnh của tập lồi đa diện c

fẼmax giá trị cực đại của hàm f

f

ầmin giá trị cực tiểu của hàm f

fÁopl giá trị tối ưu của hàm f

^max điểm (nghiệm, lời giải) cực đại của bài toán tìm cực đại

^min điểm (nghiệm, lời giải) cực tiểu của bài toán tìm cực tiểu

xop. điểm (nghiệm, lời giải) tối ưu của một bài toán tối ưu

f (Xo, d) đạo hàm theo hướng d của hàm f tại điểm Xo

f ' f ' 1xi ’ äi đạo hàm riêng (cấp một) của hàm f theo biến X,

f ' , f- XjXj ’ ij đạo hàm riêng cấp hai của hàm f theo biến X; và biến X

dom f miền hữu hiệu của hàm f

epi f tập trên đồ thị của hàm f

hypo f tập dưới đổ thị của hàm f

ổf(x°) dưới vi phàn của hàm f tại điểm Xo

11

ỗc(x) hàm chỉ của tập lồi c

dc(x) hàm khoảng cách từ điểm X tới tập lồi c

sc(x) hàm tựa của tập lồi c

Fd(x°) nón chấp nhận được của tập D tại điểm x"

T d(xh) nón tiếp xúc với tập D tại điểm x°

S(x°) nón chấp nhận được tuyến tính hóa tại điểm x°

Nc(x°) nón pháp tuyến trong của tập c tại điểm XH

- N c ( x H) nón pháp tuyến ngoài của tập c tại điểm x°

V f(x) véctơ gradient của hàm f tại điểm X

v 2f(x), ma trận Hessian của hàm f tại điểm X

Hf(x)

0 ma trận A xác định dương

A -< 0 ma trận A xác định âm

A > 0 ma trận A nửa xác định dương

A < 0 ma trận A nửa xác định âm

rank A hạng của ma trận A

A e IKmXn A là ma trận m hàng, n cột (m a trận cấp m xn)

At ma trận chuyển vị của ma trận A

A-' ma trận nghịch đảo của ma trận A

I„ ma trận đơn vị cấp n

12

LỜI NÓI ĐẦU

Tối ưu hóa (Optimization) là một môn toán học ứng dụng đã và

đang được nghiên cứu, giảng dạy và học tập ở nhiều trường đại học,

cao đẳng trong nước, từ Bắc tới Nam, cho sinh viên toán học, tin

học, kinh tế và kỹ thuật.

Trong lý Ihuyết tối ưu hóa thì phần quan trọng và được phát

triển hoàn thiện nhất là tối ưu tuyến tính, còn gọi là qui hoạch tuyến

tính. Phần khó hơn và ít được dề cập dến là tối ưu phi tuyến (không

tuyến tính), còn gọi là qui hoạch phi tuyến. Có nhiều sách và giáo

trình viết về qui hoạch tuyến tính, song sách về tối ưu phi tuyến còn

khá khiêm tốn.

Giáo trìnli Tối ưu phi tuyến (Nonlinear Optimization) được viết

theo đề xuất của Khoa Toán - Tin, Trường Đại học Khoa học - Đại

học Thái Nguyên. Đây là một tài liệu tham khảo bàng tiếng Việt về

tối ưu phi tuyến, nhằm góp phần thúc đẩy việc nghiên cứu, giảng

dạy và học tập môn tối ưu hóa nói chung ở Khoa và Trường. Sách

được viết trên cơ sở chỉnh lý, bổ sung và hoàn thiện các bài giáng

về tối ưu do các tác giả đã dùng làm tài liệu giảng dạy trong nhiều

năm cho nhiều đối tượng sinh vién và học viên cao học ờ một số

trường đại học và viện nghiên cứu: Trường Đại học Khoa học

Trường Đại học Sư phạm và Trường Đại học Kỹ thuật Công nghiệp

- Đại học Thái Nguyên, Trường Đại học Khoa học Tự nhiên - Đại

học Quốc gia Hà Nội, Trường Đại học Bách khoa Hà Nội, Trường

Đại học Kinh tế Quốc dân Hà Nội, Viện Toán học, v.v ...

13

Cuốn sách này tập trung trình bày những nội dung cơ bản của lý

thuyết tối ưu phi tuyến và các phương pháp thường dùng đề giải các

bài toán tối ưu phi tuyến có hay không có ràng buộc. Lý thuyết và

phương pháp tối ưu tuyến tính đã được viết trong Giáo trình lối IIÌI

tuyến tính do Nhà xuất bản Đại học Quốc gia Hà Nội in năm 2004.

Nội dung cuốn sách được chia làm ba phần chính, mỗi phần

gồm ba hoặc bốn chương, một sô' chương có thể đọc độc lập với

nhau, tùy theo nhu cầu học tập.

• Phần 1 gồm bốn chương đầu, trình bày lý thuyết chung về

các bài toán tối ưu: nội dung và ý nghĩa bài toán, các định lý về sự

tồn tại nghiệm tối ưu của bài toán, các điểu kiện cần và đù của tối

ưu (điều kiện cấp 0, cấp 1 và cấp 2), các kết quả chính về giải tích

lồi thường dùng trong tôi ưu hóa (tập afin, tập lồi, nón lồi, hàm lồi

và hàm lõm cùng các tính chất cơ bán của chúng). Guối Phần 1 là lý

thuyết đối ngẫu Lagrange.

• Phần 2 gồm ba chương 5, 6 và 7, giới thiệu các phương pháp

tìm cực tiểu không ràng buộc của hàm, bao gồm các phương pháp

tìm cực tiểu của hàm một biến số (phương pháp lập Newton,

Fibonacci, lát cắt vàng, nội suy bậc hai và bậc ba), các phương pháp

không dùng đạo hàm tìm cực tiểu của hàm nhiều biến (phương pháp

Hooke-Jeeves, phương pháp Nelder-M ead) và các phương pháp

gradient đòi hỏi sử dụng các đạo hàm riêng cáp một và cấp hai của

hàm (phương pháp gradient, gradient liên hợp, phương pháp

Newton, tựa Newton).

• Phần 3 gồm bốn chương 8 - 1 1 . trình bày các phương pháp

tìm cực tiểu có ràng buộc của hàm nhiều biến, trong đó có phương

pháp hình học, phương pháp nhân tứ Lagrange, phương pháp dùng

điêu kiện KKT, phương pháp tuyên tính hóa hàm m ục tiêu hay

hùm ràng buộc, các phương pháp hướng chấp nhận được và các

phương pháp phạt điếm trong và điểm ngoài, dùng các hàm chắn

và hàm phạt.

14