intTypePromotion=1

Giáo trình Tối ưu phi tuyến: Phần 1 - Trần Vũ Thiệu, Nguyễn Thị Thu Thủy

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:183

0
326
lượt xem
108
download

Giáo trình Tối ưu phi tuyến: Phần 1 - Trần Vũ Thiệu, Nguyễn Thị Thu Thủy

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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, cho sinh viên toán học, tin học, kinh tế và kỹ thuật. Phần 1 cuốn giáo trình "Tối ưu phi tuyến" giới thiệu tới người học các lý thuyết chung về bài toán tối ưu hóa. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Giáo trình Tối ưu phi tuyến: Phần 1 - Trần Vũ Thiệu, Nguyễn Thị Thu Thủy

  1. JC VÀ ĐÀO TẠO I I G T.00000 941 ] 1ÁI N G U Y Ê N T R Ầ N VŨ T H IỆ U - N G U Y Ễ N T H Ị T H U T H Ủ Y 'ÉN u OKI QDB H* HQI NHÀ XUẤT BẢN ĐẠI H Ọ C Q U Ố C GIA HÀ NỘI
  2. 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 Q U Ố C G IA HÀ NỘI
  3. 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
  4. 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
  5. 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 C hư ơ ng 3. Đ IỂ U K IỆ N T ố i Ư u 3.1. Bài toán tối ưu không ràng b u ộ 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
  6. C hư ơ ng 4. BÀI T O Á N Đ ố i NGAU 4.1. Đối ngẫu L a g ra n 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 t i 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 e w 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
  7. 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 P H Á P K H Ô N G D Ù NG Đ Ạ O H À M 6.1. Phương pháp H ooke - J e e v e s ........................................................ 167 6.2. Phương pháp N elder - M e a d ......................................................... 173 B ài t ậ p .........................................................................................................181 C hư ơ ng 7. P H Ư Ơ N G P H Á P G R A D IE N 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 ra d 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 e w 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 New ton suy rộng .............. 197 7.2.3. Cải biên phương pháp N ew ton suy r ộ n g ........................ 200 7.3. Phương pháp tựa N e w 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
  8. 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 P H Á 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 ag rran g e................................................. 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. P H Ư Ơ N G P H Á P TU Y Ê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 t i ê u ................................................................263 9.2.1. Bài toán và các giả t h i ế t ..................................................... 263 9.2.2. Thuật toán Frank - W olfe ................................................. 264 9.2.3. V í dụ m inh h ọ a .................................................................... 266 B ài t ậ p ........................................................................................................271 7
  9. 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 t o á n .................................................................................292 10.3.2. M ô tả khái quát thuật t o á n ...............................................292 10.3.3. Thuật toán chi t i ế t .............................................................. 294 B à i tậ p ..........................................................................................................299 C hư ơ ng 11. P H Ư Ơ N G P H Á P P H Ạ 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
  10. 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 k h ảo ...................................................................................341 Các từ k h ó a ...............................................................................................343 9
  11. 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 Xe 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 XD tích của tập c và tập D C uD hợp của tập c và tập D C nD giao của tập c và tập D C cD c là tập con của tập D C cD 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
  12. a ffE 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 in ầm giá trị cực tiểu của hàm f fopl Á 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äi' đạo hàm riêng (cấp m ột) của hàm f theo biến X, 1xi f X' jX j ’, f-ij đạo hàm riêng cấp hai của hàm f theo biến X; và biến X dom f m iền hữu hiệu của hàm f epi f tập trên đồ thị của hàm f h ypo 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
  13. ỗ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 F d( 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), m a trận Hessian của hàm f tại điểm X H f(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à m a 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 m a trận A A-' ma trận nghịch đảo của m a trận A I„ ma trận đơn vị cấp n 12
  14. LỜI NÓI ĐẦU Tối ưu hóa (Optim ization) 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 p h i tuyến (N onlinear O ptim ization) đượ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 N guyên. Đây là một tài liệu tham khảo bàng tiếng V iệ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 N guyên, Trường Đại học Khoa học Tự nhiên - Đại học Q uố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
  15. 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 N hà 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 N elder-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ứ L agrange, 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
  16. Cuối sách liệt kê một số tài liệu tham khảo chính đã sử dụng, trả lời bài tập ở các chương và danh sách các từ khóa để tra cứu. Do số trang hạn chế nên cuốn sách này không trình bày một số nội dung chuyên sâu của tối ưu phi tuyến như tối ưu rời rạc (hay tối ưu tổ hợp), tối ưu toàn cục, tối ưu mạng, tối ưu đa mục tiêuắ.. Các vấn để này là chủ đề trong các tài liệu khác. Sách viết có sử dụng một sô' tài liệu mới in năm 2004 - 2009, bổ sung và làm chính xác một số sự kiện về giải tích lồi mà sách hiện có không nêu rõ hoặc nêu thiếu chính xác (Định lý 1.4, Định lý 2.16 và Hệ quả 2.6, Định lý 2.26 - 2.27 và Hệ quả 2.9); cố gắng đưa ra các chứng minh ngắn gọn, trực tiếp cho nhiều sự kiện quen biết trong lý thuyết tối ưu (Định lý Carathéodory, Định lý tách các tập lồi, các định lý điểu kiện tối ưu cấp 2); đưa vào một số nội dung ít quen biết (điều kiện tối ưu cấp 0, dưới vi phân của hàm lồi và tối ưu với hàm lồi không khả vi ...)• Cách trình bày khá trực quan các kết quả lý thuyết trừu tượng, với nhiều hình vẽ minh họa và nhiều ví dụ số cụ Ihể giúp người đọc dẻ hiểu, dễ vận dụng. Các thuật toán trình bày có kèm theo sơ đồ khối, tiện cho lập trình trên máy tính. Cuối mỗi chương đều có các bài tập với đầy đủ đáp án, nhằm giúp bạn đọc tự ôn luyện và kiểm tra kiến thức đã học. Cũng có thể sử dụng bài tập làm các bài kiểm tra giữa môn hoặc cuối môn học. Có thể dùng sách này làm tài liệu giảng dạy (dùng cho giáo viên), tham khảo và học tập (dùng cho sinh viên và học viên cao học) vể một số môn chuyên đề gần nhau như: Giải tích lồi, Lý thuyết tối ưu, Qui hoạch phi tuyến, Phương pháp giải số bài toán cực trị, v.v... Các tác giả xin chân thành cảm ơn GS.TSKH Lê Dũng Mưu (Viện Toán học) và PGS.TS Nguyễn Thị Bạch Kim (Trường Đại học Bách khoa Hà Nội) đã dành không ít thời gian và công sức đọc kỹ bủn thảo, góp nhiều ý kiến xác đáng và bổ ích, giúp hoàn thiện cuốn 15
  17. sách này. Các tác giả cũng xin chân thành cảm ơn Ban chủ nhiệm Khoa Toán - Tin, Ban lãnh đạo Phòng Đ ào tạo K hoa học và Q uan hệ Quốc tế, Ban giám hiệu Trường Đại học K hoa học - Đại học Thái Nguyên đã nhiệt tình ủng hộ và tạo mọi điểu kiện thuận lợi để các tác giả hoàn thành sách. Lời cảm ơn chân thành cũng xin được gửi tới Ban giám đốc Đại học Thái N guyên đã tận tình giúp đỡ đẽ cuốn sách này sớm được xuất bản. Do thời gian và kinh nghiệm có hạn nên cuốn sách chắc chắn không tránh khỏi những sai sót nhất định. Chúng tôi rất m ong được bạn đọc góp ý và lượng ihứ Tliái Nguyên, Iigày 17 tháng 8 năm 2010 C ác tá c giả 16
  18. Phần I. LÝ T H U Y ẾT CHƯNG Chương I BÀI TOÁN TỐI ƯU 1.1. K H Á I N IỆ M VÀ Đ ỊN H N G H ĨA Trong không gian véctơ K", cho D c K" là một tập khác rỗng và hàm sô' thực f : D —> [R tùy ý. Bài toán tối ưu có dạng min ( f ( x ) : X E D | (P) là bài toán tìm véctơ (điểm) X*E D sao cho f(x*) < f(x) với mọi x e D. Đ ịnh nghĩa 1.1. Hàm f gọi là hàm m ục liêu hay liàm chi phí, tập D gọi là tập ràng buộc hay miền chấp nhận được. M ột véctơ (điểm) X 6 D gọi là một phương án (lời giải hay ngliiệm) chấp nhận dược. V éctơ X* e D sao ch o f(x * ) < f(x) với m ọi X e D gọi là một phương án (lời giải hay nghiệm) tối ưu của bài toán và f(x*) gọi là giá trị cực tiểu hay giá trị tối Iiìt cùa f trên D, thường dược ký hiệu ^ ^mirr Trường hợp D = Kn ta có bài toán tối ưu không ràng buộc: min |f ( x ) : X e IRnỊ hay min f(x). X €R " Trái lại, (P) là bài toán tối ưu có ràng buộc. Khi ấy tập D (hường được cho bởi 17
  19. D = Ịx e R " : g,(x) < 0 , i = 1 , , m, hj(x) = 0, j = 1 , , p i, (1.1) với g;, h j: Rn —» IR là các hàm số cho trước, gọi là các hàm ràng buộc, và bài toán (P) có thể viết dưới dạng (gọi là bài toán dạng chuẩn): f(x) -» min với điều kiện g ,(x )< 0 , i = 1, ... , m, (1.2) hj(x) = 0, j = 1 ,..., p. (1.3) Các hệ thức gi(x) < 0 gọi là các ràng buộc b ất đẳng thúc, các hệ thức hj(x) = 0 gọi là các ràng buộc dẳng thức. R àng buộc bất đẳng thức dạng Xj > 0 (- Xj < 0 ) g ọ i là rà n g b u ộ c không âm hay ràng buộc v ề dấu. N hận xét l . l ế Ràng buộc bất đẳng thức có thể biến đổi thành ràng buộc đẳng thức và ngược lại. Thật vậy, các ràng buộc (1.2) có thể được biểu diễn nhờ hệ thức g;(x) + y f = 0, i = 1, ..., m với y, là các số thực, gọi là các biến bù. Nguợc lại, mỗi ràng buộc đằng thức (1.3) tương đương với hai ràng buộc bất đảng thức hj(x) < 0, - hj(x) < 0, j = 1 ,..., p. Với nhận xét vừa nêu, không giảm tính tổng quát đôi khi ta xét bài toán tối ưu chỉ với ràng buộc đẳng thức hoặc chỉ với ràng buộc bất đẳng thức. N hặn xét 1.2. Do min ( f ( x ) : X e DỊ = - m ax (- f(x) : X e Dị nên bài toán tìm cực tiểu đưa được về bài toán tìm cực đại và ngược lại. Nếu f(x*) > f(x) với mọi X e D thì f(x*) là giá trị cực đại của hàm f trên D và thường được ký hiệu là fmax. Đ ịnh nghĩa 1.2. Điểm X* 6 D được gọi là m ột ngliiệm cực tiểu địa phương của f trẽn D nếu có E > 0 sao cho f(x*) < f(x) với mọi X e D và llx - x*ll < £. 8
  20. N ếu f(x * ) < f(x ) với m ọi X e D, X *■ X* và llx - x*ll < s thì X* được gọi là nghiệm cực tiểu địa phương chặt của f trên D. Đ ịnh nghĩa l ể3. Điểm X* e D được gọi là nghiệm cực tiểu toàn cục của f trên D nếu f(x*) < f(x ) với mọi X 6 D. Nếu f(x*) < f(x) với mọi x e D, X * X* thì X* được gọi là nghiệm cực tiểu toàn cục cliặt của f trên D. Các khái niệm nghiệm cực đại địa phương, cực đại địa phương chặt và nghiệm cực đại toàn cục, cực đại toàn cục chặt được định nghĩa tương tự. Tập D là khoảng đóng [a; + oo) X! điểm cực tiểu toàn cục chặt. (f không có cực đại toàn cục) x2 điểm cực đại địa phương chặt x3 điểm cực tiểu địa phương (không chặt) x4 điểm cực đại địa phương (không chặt) x5 điểm cực tiểu địa phương chặt Hình 1.1. Cực tiểu (cực đại) địa phương (toàn cục) Đối với hàm tùy ý i trên tập D, ta ký hiệu tập tất cả các điểm cực tiểu (cực đại) toàn cục của f trên D là A rgm in xSD f(x) (A rg m a x x g Df(x)). 19
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2