Tài liệu Bài toán quy hoạch phi tuyến không ràng buộc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA TOÁN - CƠ - TIN HỌC Lê Hồng Nguyên BÀI TOÁN QUY HOẠCH PHI TUYẾN KHÔNG RÀNG BUỘC LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: Toán - Giải tích Mã số: 60.46.01.02 Người hướng dẫn: PGS.TS. Nguyễn Hữu Điển Hà Nội - 2014 LỜI CẢM ƠN Để hoàn thành bản luận văn này tôi đã nhận được sự giúp đỡ to lớn của Thầy, Cô giáo, gia đình và bạn bè xung quanh. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS Nguyễn Hữu Điển, Khoa Toán- Cơ- Tin học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội. Trong quá trình giảng dạy và hướng dẫn đã ân cần động viên, giúp đỡ chỉ bảo tận tình cho tôi. Tôi cũng gửi lời cảm ơn tới các thầy cô trong Khoa Toán- Cơ- Tin học, Phòng sau đại học, Trường Đại học khoa học tự nhiên, ĐHQG Hà Nội đã dạy dỗ và giúp đỡ tôi rất nhiều trong suốt quá trình học tập và nghiên cứu luận văn. Đặc biệt là các thầy cô trong Seminar của bộ môn Toán giải tích đã có những ý kiến đóng góp quý báu giúp cho bản luận văn hoàn chỉnh hơn. Ngoài ra tôi cũng gửi lời cám ơn chân thành tới bạn bè, đồng nghiệp đã giúp đỡ rất nhiều, tạo điều kiện tốt nhất cho tôi có thời gian để hoàn thành luận văn. Cuối cùng tôi cũng xin gửi lời cảm ơn tới gia đình nơi đã sinh thành, nuôi nấng, giúp đỡ, động viên tôi rất nhiều trong suốt thời gian qua. Dù đã cố gắng hết sức nhưng luận văn không thể tránh khỏi những thiếu sót và hạn chế. Mọi ý kiến đóng góp tôi xin được đón nhận với lòng biết ơn và trân trọng sâu sắc. Hà Nội, ngày 14 tháng 10 năm 2014 Học Viên Lê Hồng Nguyên 1 BẢNG KÝ HIỆU Ký hiệu Ý nghĩa DFP Davidon- Fletcher- Powell QHPT Quy hoạch phi tuyến Rn Không gian thực n chiều ∇ f (x) Gradient của f tại x ∇2 f ( x ) Hessian của f tại x o Vô cùng bé ∆ Số gia 0( x, ε) Lân cận của x với bán kính ε k.k Chuẩn vector AT Ma trận chuyển vị của ma trận A 2 Mục lục Lời mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chương 1. Một số kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1. Một số khái niệm giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2. Một số khái niệm từ giải tích . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Tốc độ hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4. Điều kiện tối ưu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chương 2. Phương pháp Davidon- Fletcher- Powell . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Nội dung của phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3. Sự hội tụ của phương pháp DFP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5. Chương trình giải ví dụ thuật toán DFP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chương 3. Phương pháp Hooke- Jewes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.1. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2. Sự hội tụ của thuật toán Hooke- Jewes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3. Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.4. Chương trình giải ví dụ thuật toán Hooke- Jeeves . . . . . . . . . . . . . . . . . . . . 51 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 LỜI MỞ ĐẦU Như L.Euler đã viết: "Vì thế giới được thiết lập một cách hoàn hảo nhất, và vì nó là sản phẩm của đấng sáng tạo tinh thông nhất, nên không thể tìm thấy cái gì mà không mang theo tính chất cực đại hay cực tiểu nào đó". Vấn đề đặt ra ở đây là, các trạng thái của vật thể trong tự nhiên hoạt động tuân theo những quy luật như thế nào. Như chúng ta đã biết, thực tế bài toán quy hoạch đã xuất hiện từ khi con người biết lao động, biết suy nghĩ để tìm ra cách làm nhanh và hiệu quả nhất. Tuy nhiên các hành động này thay đổi liên tục và buộc con người ta phải tìm cách thích ứng. Và ngày nay, mô hình tối ưu hóa được sử dụng trong nhiều lĩnh vực như: Quản lý kinh tế và tài chính, nghiên cứu khoa học và cả trong các lĩnh vực kỹ thuật... cũng được thừa hưởng từ các thành quả ở trên với nguồn tài nguyên vô cùng vô tận và các cơ sở kỹ thuật hiện đại. Để giải quyết các vấn đề trên ta nghiên cứu bài toán quy hoạch phi tuyến không ràng buộc có dạng min { f ( x ) : x ∈ Rn } , trong đó Rn là một không gian vector , f : Rn → R là một hàm phi tuyến cho trước và được gọi là hàm mục tiêu. Tập nguồn Rn ứng với bài toán tối ưu không ràng buộc. Mục đích của khóa luận này là nhằm tìm hiểu một số phương pháp đặc trưng để giải các bài toán quy hoạch phi tuyến không ràng buộc. Như chúng ta đã biết tìm kiếm theo tia (line search) hay còn gọi là tìm kiếm một chiều (one dimensional search) là mấu chốt của nhiều thuật toán để giải các bài toán quy hoạch phi tuyến. Nội dung chính của chiến lược tìm theo tia như sau : Xuất phát từ một điểm x0 và một hướng d ∈ Rn cho trước, tìm một khoảng ban đầu mà nó chứa điểm cực tiểu, sau đó dùng kỹ thuật chia nhỏ hay nội suy để thu hẹp dần các khoảng chứa nghiệm cho tới khi độ dài của khoảng nhỏ hơn một mức dung sai định trước. 4 Phương đơn giản để tìm khoảng ban đầu là phương pháp tiến và lùi (forwardbackward method). Ý tưởng chính của phương pháp này là: Cho trước một điểm ban đầu và một độ dài bước ban đầu, ta thử tìm ba điểm ứng với ba giá trị mục tiêu dạng "cao-thấp-cao". Nếu đi theo chiều tiến (nghĩa là điểm sau ở bên phải điểm trước) không đạt kết quả thì sẽ đi lùi lại (tức là điểm sau ở bên trái điểm trước). Tiếp tục quá trình như thế, ta sẽ nhận được khoảng ban đầu mà nó chứa điểm cực tiểu cần tìm. Thứ hai là phương pháp khử liên tiếp với hai phương pháp quen thuộc để tìm cực tiểu của hàm đơn mốt: Phương pháp Fibonaci và phương pháp lát cắt vàng (golden section method). Ở phương pháp này cho phép ta thu hẹp dần khoảng chứa điểm cực tiểu bằng cách tính giá trị hàm tại những điểm chọn trong khoảng này, tuy nhiên phương pháp lát cắt vàng có ưu điểm là một trong hai điểm chia đoạn mới trùng với một điểm chia cũ, do đó ở mỗi bước lặp chỉ cần tính thêm một giá trị hàm ứng với điểm chia mới, nhờ đó tiết kiệm được thời gian tính toán. Tiếp theo là phương pháp nội suy, phương pháp này dùng giá trị của hàm cần tìm cực tiểu tại những điểm nhất định để xấp xỉ các hàm đó bởi các đa thức: Tam thức bậc hai (phương pháp Powell) và đa thức bậc ba (phương pháp Davidon), sau đó điểm cực tiểu của hàm ban đầu được thay thế bằng điểm cực tiểu của đa thức xấp xỉ mà nó được tìm đơn giản hơn. Trên đây là một số phương pháp tìm cực tiểu hàm một biến. Chúng ta cũng có thể dùng bất kỳ phương pháp tìm cực tiểu một biến này để tìm cực tiểu dọc theo các trục tọa độ đối với hàm hai biến cũng như hàm nhiều biến. Tuy nhiên các phương pháp được giới thiệu ở trên chỉ có hiệu quả trong trường hợp cực tiểu của hàm là duy nhất. Song trên thực tế nó tỏ ra ít hiệu quả. Vì thế, người ta đã đề ra nhiều phương pháp khác cho phép khai thác nhiều thông tin hơn dựa trên các giá trị hàm đã nhận được, và chúng được chia thành hai nhóm đó là: Phương pháp tìm trực tiếp (chỉ dùng giá trị của hàm) và phương pháp gradient (sử dụng đạo hàm của hàm). 5 Một trong hai phương pháp tìm kiếm trực tiếp là phương pháp Hooke- Jeeves do Hooke- Jeeves đề ra năm 1961. Với nội dung : Xuất phát từ một điểm cơ sở tùy ý, việc tìm kiếm bao gồm một dãy bước tìm theo tọa độ quanh điểm cơ sở nhằm đạt tới điểm có giá trị hàm nhỏ hơn (điểm tốt hơn). Nếu thành công sẽ chuyển cơ sở tới điểm mới tốt hơn vừa tìm được và tiếp tục di chuyển theo hướng đó đến một điểm gọi là điểm mẫu. Tiến hành tìm theo tọa độ quanh điểm mẫu. Nếu tìm được điểm tốt hơn thì tiếp tục dò tìm quanh điểm mẫu mới, nếu không thành công sẽ quay trở lại điểm cơ sở trước đó hoặc giảm độ dài bước dò tìm. Thứ hai là phương pháp Neldel- Mead (1965) còn được gọi là phương pháp tìm kiếm theo đơn hình biến thiên được Neldel- Mead đề nghị cải tiến từ phương pháp đơn hình đều SpendleyHext- Himsworth để có thể sử dụng cho các đơn hình không đều. Từ ý tưởng chính của phương pháp Spendley- Hext- Himsworth là so sánh giá trị hàm tại tất cả các đỉnh của đơn hình đều và dịch chuyển đơn hình về hướng điểm tối ưu nhờ một thủ tục lặp. Và ở phương pháp Neldel- Mead thì cụ thể đơn hình được dịch chuyển nhờ ba thao tác cơ bản: Phép phản xạ, phép dãn và phép co. Đây là một phương pháp tìm trực tiếp đáng tin cậy và là một trong các phương pháp tìm cực tiểu tự do hiệu quả nhất đối với không gian có số chiều nhỏ hơn 7. Hai phương pháp này đặc biệt thích hợp để tìm cực tiểu của những hàm có cấu trúc phức tạp, thường không khả vi hoặc khó tính đạo hàm. Tuy nhiên các phương pháp này nói chung chậm hội tụ hơn so với phương pháp dùng đạo hàm. Cuối cùng là các phương pháp sử dụng đạo hàm của hàm. Các phương pháp này đòi hỏi sử dụng tới các đạo hàm riêng bậc nhất hoặc bậc hai của hàm. Khoảng những năm 70 của thế kỷ XX, các phương pháp gradient được nghiên cứu rất mạnh và đã thu được những thành tựu đáng kể. Nhiều công trình nghiên cứu đã được công bố. Có một phương pháp thông dụng để tìm cực tiểu, nó rất đơn giản và có thể áp dụng cho nhiều lớp hàm rộng, đó chính là phương pháp hướng dốc nhất (Steepest Descent Method) với nội dung như sau: Ta xây dựng một dãy điểm 6 x k hội tụ tới điểm z khi k → ∞ với đặc điểm giá trị hàm của chúng giảm dần và ∇ f (z) = 0. Giả sử ta có điểm x k nằm trong lân cận của điểm z, khi đó để giảm hàm mục tiêu ta sẽ dịch chuyển từ x k theo hướng dk tạo với vector gradient ∇ f (z) một góc tù, với độ dài bước αk xác định. Việc lựa chọn hướng dịch chuyển và độ dài bước khác nhau sẽ cho ta phương pháp gradient khác nhau. Và ở phương pháp này ta chọn hướng dk = −∇ f ( x k ) với mọi k. Phương pháp gradient chỉ sử dụng xấp xỉ thô của hàm cần tìm cực tiểu (nghĩa là chỉ có số hạng tuyến tính ở khai triển f ( x ) thành chuỗi Taylor được dùng để chọn hướng dịch chuyển). Trong khi đó, không giống như phương pháp gradient thông thường, phương pháp Newton có hướng tìm riêng, gọi là hướng Newton, đã dùng đến các đạo hàm riêng cấp hai của hàm f ( x ) vì thế nó đòi hỏi hàm f ( x ) hai lần khả vi liên tục và hướng của nó được xác định như sau dk = −[∇ f ( x k )]−1 ∇ f ( x k ). Công việc tính ma trận nghịch đảo [∇ f ( x k )]−1 ở mỗi bước là một công việc khó khăn. Vì thế, phương pháp Newton ít được sử dụng trong thực tiễn khi n > 1, mặc dầu phương pháp có tốc độ hội tụ bậc hai. Bằng cách sử dụng công thức lặp và thay đổi độ dài bước bởi các phương pháp tìm kiếm một chiều theo hướng mới đã cải tiến phép lặp của phương pháp Newton thành phương pháp Newton suy rộng. Phương pháp này có tốc độ hội tụ của điểm cũng như hội tụ của hàm nhanh hơn so với phương pháp gradient, cụ thể chúng ta sẽ xét kỹ hơn phương pháp Davidon- Fletcher- Powell ở chương sau. Và đặc biệt khi độ dài bước αk = 1 thì ta có phương pháp Newton. Cuối cùng là phương pháp gradient liên hợp Fletcher- Reeves tìm cực tiểu tự do của hàm toàn phương ( hàm lồi bậc hai )bằng phương pháp lặp. Như vậy, các phương pháp sử dụng đạo hàm có ưu điểm là hội tụ nhanh, nhưng khi số biến lớn thì gặp khó khăn trong việc tính đạo hàm, mặt khác việc chuẩn bị bài toán để giải tốn nhiều thời gian. Tóm lại không có phương pháp chung nào có hiệu quả để giải bài toán quy hoạch nói chung và quy hoạch phi tuyến nói riêng. Mỗi phương pháp đều có 7 những ưu, nhược điểm riêng. Nên luận văn chỉ tìm hiểu sâu về thuật toán, sự hội tụ cũng như các ví dụ để làm rõ hai phương pháp: Phương pháp chỉ sử dụng giá trị của hàm Hooke- Jeeves và phương pháp sử dụng đạo hàm của hàm DavidonFletcher-Powell thuộc lớp chung của phương pháp Newton, trong việc giải quyết các bài toán tối ưu không ràng buộc. Nội dung chính của bản luận văn bao gồm các vấn đề sau đây: • Tổng quan về các phương pháp tìm cực tiểu tự do. • Tóm tắt kiến thức liên quan. • Trình bày cụ thể hai phương pháp. Ví dụ minh họa và chạy kiểm tra kết quả bằng Maple. Do thời gian thực hiện khóa luận không nhiều, kiến thức còn hạn chế nên khi làm khóa luận không tránh khỏi những hạn chế và sai sót. Tác giả mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Xin chân thành cảm ơn! Hà Nội, ngày ... tháng ... năm 2014 Học viên Lê Hồng Nguyên 8 Chương 1 Một số kiến thức chuẩn bị 1.1. Một số khái niệm giải tích lồi Định nghĩa 1.1. [Đoạn thẳng][8]. Tập tất cả các điểm x = (1 − λ) a + λb với 0 ≤ λ ≤ 1, a, b ∈ Rn được gọi là đoạn thẳng nối hai điểm a và b. Ký kiệu [ a, b] . Định nghĩa 1.2. [Tập lồi][8]. Tập D ⊂ Rn được gọi là tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Hay nói cách khác D là tập lồi nếu (1 − λ) a + λb ∈ D với mọi a, b ∈ D, 0 ≤ λ ≤ 1. Ví dụ 1.1. Hình 1.1: Tập lồi :a, b, tập không lồi :c. Các tính chất của tập lồi • Tổng đại số hữu hạn tập lồi là tập lồi. • Giao của họ các tập lồi là tập lồi. 9 • Tích đề các của các tập lồi là tập lồi. Định nghĩa 1.3. [Hàm lồi][8]. Hàm f ( x ) xác định trên tập lồi D được gọi là hàm lồi nếu ∀ x, y ∈ D, ∀λ ∈ [0, 1] : f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ) f (y) . Ví dụ 1.2. Kiểm tra hàm f : D → R, x 7→ f ( x ) = x2 là hàm lồi? Thật vậy, dễ thấy D là tập lồi. ∀ x, y ∈ D, ∀λ ∈ [0, 1] thì f (λx + (1 − λ) y) ≤ λ f ( x ) + (1 − λ ) f ( y ) . Định nghĩa 1.4. Ta nói hai tập lỗi khác rỗng C, D trong Rn tách được bởi siêu phẳng H = { x ∈ Rn : tx = α} với t ∈ Rn \ {0} và α ∈ R, nếu inf tx ≥ α ≥ sup ty. x ∈C (a) y∈ D Định lý 1.1. [Định lý tách 1][8] Hai tập lồi C và D trong Rn khác rỗng, không có điểm chung có thể tách được bởi một siêu phẳng, nghĩa là tồn tại vector t ∈ Rn với t 6= 0 và một số α ∈ R sao cho ( a) thỏa mãn. Chứng minh. Ta có tập C − D là tập lồi và thỏa mãn không chứa 0 vì thế tồn tại t ∈ Rn \ {0} sao cho t( x − y) ≥ 0 với mọi x ∈ C và y ∈ D. Khi đó, ( a) đúng với α = inf tx. x ∈C Định lý 1.2. [Định lý tách 2][8] Hai tập lồi đóng C và D trong Rn khác rỗng, không cắt nhau và ít nhất một trong hai tập này là compact (có thể tách hẳn bởi một siêu phẳng) nghĩa là tồn tại một vector t ∈ Rn với t 6= 0 và một số α ∈ R sao cho inf t T x > α > sup t T y. x ∈C y∈ D Chứng minh. Trong không gian vector Rn giả thiết rằng C compact. Xét tập lồi C − D. Nếu zk = x k − yk → z với x k ∈ C và yk ∈ D thì do C compact nên tồn tại n o dãy con x kq sao cho x kq → x ∈ C. Theo giả thiết thì D đóng nên ykq = x kq − zkq → x − z ∈ D. 10 Suy ra z = x − y với x ∈ C và y ∈ D. Từ đó, C − D đóng. Do 0 ∈ / C − D nên tồn tại vector t ∈ Rn \ {0} và một số η sao cho t( x − y) > η > 0 với mọi x ∈ C, y ∈ D. Khi đó thì inf tx − x ∈C Nếu như đặt α = inf tx − x ∈C η η ≥ sup ty + . 2 2 y∈ D η thì ta nhận được 2 inf tx > α > sup ty. x ∈C 1.2. y∈ D Một số khái niệm từ giải tích Định nghĩa 1.5. [Hàm khả vi][8]. Giả sử hàm f xác định tại lân cận 0( x, ε) của điểm x. Ta nói hàm f là khả vi tại điểm x nếu tìm được vector f 0 ( x ) ∈ Rn sao cho số gia của hàm số tại x ∆ f ( x ) = f ( x + ∆x ) − f ( x ), k∆x ≤ εk , có thể được viết lại ∆ f ( x ) = f ( x + ∆x ) T f ( x ) + o ( x, ∆x ), trong đó o ( x, ∆x ) là vô cùng bé bậc cao hơn k∆x ≤ εk nghĩa là o ( x, ∆x ) = 0, k∆x k→0 k ∆x k lim khi đó f 0 ( x ) được gọi là gradient của hàm f tại x và được ký hiệu là ∇ f ( x ). Định nghĩa 1.6. [Hàm hai lần khả vi][8] Giả sử hàm f xác định tại lân cận 0( x, ε) của điểm x. Ta nói hàm f hai lần khả vi tại điểm x nếu cùng với vector ∇ f ( x ), tồn tại ma trận đối xứng ∇2 f ( x ) ∈ Rn sao cho số gia của hàm số tại điểm x có thể viết dưới dạng ∇2 f ( x )T ∆x ∆ f ( x ) = f ( x + ∆x ) − f ( x ) = ∇ f ( x ) ∆x + + o ( x, ∆x ), 2 T 11 khi đó ∇2 f ( x ) được gọi là ma trận đạo hàm cấp hai hay Hessian của hàm f tại x. Định nghĩa 1.7. [Hàm khả vi liên tục][8] Giả sử hàm f đối xứng trên tập mở X, ta nói hàm f là khả vi liên tục trên tập X nếu f là khả vi tại mọi điểm x ∈ X và k∇ f ( x + ∆x ) − ∇ f ( x )k → 0 khi k∆x k → 0 với ∀ x, x + ∆x ∈ X. Định nghĩa 1.8. [Hàm hai lần khả vi liên tục][8] Giả sử hàm f xác định trên tập mở X. Ta nói hàm f là hai lần khả vi liên tục trân tập X nếu f là hai lần khả vi tại mọi điểm x ∈ X và 2 ∇ f ( x + ∆x ) − ∇ f ( x ) → 0 khi k∆x k → 0 với ∀ x, x + ∆x ∈ X. Định lý 1.3. [Hàm lồi khả vi][10] a. Một hàm thực một biến ϕ(t) khả vi trong một khoảng mở là lồi khi và chỉ khi đạo hàm của nó ϕ0 (t) là một hàm không giảm. b. Một hàm thực một biến ϕ(t) hai lần khả vi trong một khoảng mở là lồi khi và chỉ khi đạo hàm cấp hai của nó ϕ00 (t) không âm trên toàn bộ khoảng mở này. Định lý 1.4. [10] Cho một tập lồi C ⊂ Rn và một hàm f : Rn → R khả vi trên C. a. Hàm f lồi trên C khi và chỉ khi f (y) ≥ f ( x ) + ∇ f ( x )(y − x ) với ∀ x, y ∈ C. b. Nếu f ( x ) > f ( x ) + ∇ f ( x )(y − x ) với ∀ x, y ∈ C và x 6= y thì f lồi chặt trên C. Chứng minh. Ta lần lượt đi chứng minh từng ý của định lý. a. Giả sử hàm f lồi trên C. Với ∀ x, y ∈ C và với ∀λ ∈ [0, 1], ta có λ f (y) + (1 − λ) f ( x ) ≥ f [λy + (1 − λx )] . 12 Từ đó suy ra f (y) − f ( x ) ≥ f ( x + λ(y − x )) − f ( x ) với ∀λ ∈ [0, 1] . λ Cho qua giới hạn ở vế phải khi λ ↓ 0+ , ta được f (y) − f ( x ) ≥ h∇ f ( x ), y − x i . Ngược lại, giả sử f (y) ≥ f ( x ) + h∇ f ( x ), y − x i với ∀ x, y ∈ C. Với bất kỳ giá trị nào của x, y ∈ C và 0 ≤ λ ≤ 1, đặt z = λx + (1 − λ)y. Do C lồi nên z ∈ C. Với x và z ta có f ( x ) − f (z) ≥ ∇ f (z)( x − z). Với y và z ta có f (y) − f (z) ≥ ∇ f (z)(y − z). Nhân bất đẳng thức đầu với λ, bất đẳng thức sau với 1 − λ và cộng lại ta có λ f ( x ) − λ f (z) + (1 − λ) f (y) − (1 − λ) f (z) ≥ λ∇ f (z)( x − z) + (1 − λ) f (z)(y − z), hay λ f ( x ) + (1 − λ) f (y) ≥ f (z) + ∇ f (z)(λx + (1 − λ)y) − ∇ f (z)z = f (z). Mà z = λx + (1 − λ)y nên bất đẳng thức trở thành λ f ( x ) + (1 − λ) f (y) ≥ f (λx + (1 − λ)y), điều này chứng tỏ hàm f lồi. b. Chứng minh hoàn toàn tương tự như ( a) ở trên. Định nghĩa 1.9. [Ma trận xác định dương][8] Cho ma trận A ∈ Rn×n . Khi đó • A được gọi là nửa xác định dương nếu x T Ax ≥ 0 với mọi vector x ∈ Rn khckhng. • A được gọi là xác định dương nếu x T Ax > 0 với mọi vector x ∈ Rn khckhng. 13 • A được gọi là nửa xác định âm nếu x T Ax ≤ 0 với mọi vector x ∈ Rn khckhng. • A được gọi là xác định âm nếu x T Ax <0 với mọi vector x ∈ Rn .   1  −4 0  Ví dụ 1.3. Kiểm tra tính xác định dương của ma trận sau:  ? 1 0 −4 Ta lấy x = [ x1 , x2 ]t ∈ R2 dùng định nghĩa có   −1 0  −1 2  x= xt  4 ( x1 + x2 2 ) ≤ 0, với ∀ x ∈ Rn .  −1 4 0 4 Như vậy ma trận đã cho nửa xác định âm. Ngoài ra ta còn có tiêu chuẩn Silvestra để kiểm tra tính xác định dương của ma trận như sau: Ma trận A ∈ Rn×n là xác định dương hay xác định âm khi và chỉ khi tất cả các định thức con của ma trận đó tương ứng là dương hay âm. Công thức Taylor. Giả sử X ⊂ Rn mở, f : X → R khả vi cấp p − 1, hơn nữa giả sử f khả vi cấp p tại a ∈ X. Khi đó f ( x ) = f ( a) + f 0 ( a)( x − a) f 00 ( a)( x − a)2 f (n) ( a)( x − a)n + + ... + + R n ( x ). 1! 2! n! Công thức số gia hữu hạn. Giả sử hàm f khả vi liên tục trên một tập mở S và x là một vector nào đó trong S. Khi đó với ∀ vector y thỏa mãn x + y ∈ S luôn tìm được số α ∈ [0, 1] sao cho 0 f ( x + y) − f ( x ) = f ( x + αy)y = Z1 f 0 ( x + ty)ydt. 0 1.3. Tốc độ hội tụ Định nghĩa 1.10. [11] Thuật toán tối ưu có tốc độ hội tụ tuyến tính (linearly convergent) nếu ∃0 ≤ C < ∞, 0 < q < 1, ε(t) ≤ Cqt , 14 (1.1) nghĩa là sai số ε(t) giảm tương đương với một chuỗi cơ số nguyên nào đó và q được gọi là tỉ lệ hội tụ. Từ định nghĩa ta có nhận xét C−1 C−1 thì ε(t) ≤ δ. Tức là sau t = ln δ ln q δ ln q bước lặp ta có sai số ε(t) ≤ δ. Như vậy nếu tốc độ hội tụ là tuyến tính thì số bước Nhận xét 1.1. Nếu Cqt ≤ δ hay t ≥ ln lặp tỉ lệ thuân (tuyến tính) với số bít để mô tả độ chính xác của nghiệm (lưu ý: số 1 bít để mô tả độ chính xác của nghiệm là ln ). δ Nếu không tồn tại q, C như vậy, ta nói thuật toán tối ưu có tốc độ hội tụ chậm hơn tuyến tính . Nhận xét 1.2. Ta có các nhận xét sau • Nói một cách đơn giản thì tốc độ hội tụ chỉ ra một số bước mà thuật toán tối ưu phải thực hiện để giảm được hàm sai số ε(t) về 0. Khi ε(t) → 0 thì các chữ số sau dấu phẩy của ε(t) cũng dẫn chuyển thành 0. • Nếu thuật toán có tốc độ hội tụ tuyến tính thì số bước để chuyển chữ số thứ n + 1 sau dấu phẩy của ε(t) thành 0 bằng số bước để chuyển chữ số thứ n sau dấu phẩy của ε(t) thành 0. • Nếu thuật toán có tốc độ hội tụ nhanh hơn tuyến tính thì số bước để chuyển chữ số thứ n + 1 sau dấu phẩy của ε(t) thành 0 ít hơn số bước chuyển chữ số thứ n của ε(t) thành 0. • Nếu thuật toán có tốc độ hội tụ bậc hai thì số bước để chuyển chữ số thứ n + 1 sau dấu phẩy của ε(t) thành 0 bằng một nửa số bước để chuyển chữ số thứ n sau dấu phẩy của ε(t) thành 0. Ví dụ 1.4. Ta có ví dụ sau: • Nếu ε(t) = e−αt thì tốc độ hội tụ là t tỉ lệ với e−α . 15 C thì tốc độ hội tụ chậm hơn tuyến tính. t ε ( t + 1) < q thì thuật toán có tốc độ hội tụ tuyến tính. Điều kiện đủ 1.1. Nếu lim t→∞ ε (t ) • Nếu ε(t) = ε ( t + 1) < q nên ∃ N sao cho ∀t ≤ N: t→∞ ε (t ) Chứng minh. Do lim ε ( t + 1) < q ⇒ ε (t ) ≥ ε ( N )qt− N . ε(t) Định nghĩa 1.11. [11] Thuật toán tối ưu có tốc độ hội tụ nhanh hơn tuyến tính (super linearly convergent) Nếu ∀0 < q < 1, ∃0 ≥ C ≥ ∞ sao cho ε(t) ≤ Cq T , nghĩa là sai số ε(t) giảm nhanh hơn bất cứ chuỗi CSN nào. 2 Ví dụ 1.5. Nếu ε(t) = eαt thì tốc độ hội tụ nhanh hơn tuyến tính. Điều kiện đủ 1.2. Xét sai số ta nhận thấy: ε ( t + 1) Nếu lim = 0 thì thuật toán tối ưu có tốc độ hội tụ nhanh hơn tuyến t→∞ ε(t) tính. ε ( t + 1) Nếu lim = 0 thì thuật toán tối ưu có tốc độ hội tụ nhanh hơn tuyến t→∞ ε(t) tính. ε ( t + 1) = 0 nên với ∀q > 0 tồn tại N : t→∞ ε(t) Ví dụ 1.6. Do lim ∀t ≤ N: ε ( t + 1) < q. ε(t) Tương tự như trên ta có: ∀q > 0, ∃ N : ε(t) ≥ ε( N ) t q với ∀t > N. qN Định nghĩa 1.12. [11] Thuật toán tối ưu có tốc độ hội tụ bậc p > 1 nên ∃c : ε(t + 1) ≥ cε p (t). t Ví dụ 1.7. Nếu ε(t) = e−αp thì tốc độ hội tụ có bậc p. Định nghĩa 1.13. [11] (Hướng làm giảm hàm mục tiêu). Hướng d là hướng làm giảm hàm mục tiêu f ( x ) tại x nếu: ∃t > 0 sao cho f ( x + td) < f ( x ). 16 (1.2) Để có thể áp dụng dễ dàng về hướng giảm của hàm mục tiêu ta xét định lý sau Định lý 1.5. [11] Nếu d T ∇ f ( x ) < 0 thì d là hướng làm giảm hàm mục tiêu tại x. Chứng minh. Đặt: φ(t) = f ( x + td) ta có: φ 0 (0) = d T ∇ f ( x ) < 0 , φ(t) = φ(0) + tφ0 (0) + o (t2 ),   với t > 0 đủ nhỏ thì: |tφ0 (0)| > o (t2 ) . Vì vậy: φ(t) < φ(0) do tφ0 (0) − o (t2 ) < 0. Tức là: f ( x + td) < f ( x ). Nhận xét 1.3. Mệnh đề ngược lại chưa chắc đã đúng, tức là: Nếu ∃t > 0 để f ( x + td) < f ( x ) thì vẫn có thể có: d T ∇ f ( x ) ≤ 0. Tuy nhiên, nếu f ( x + td) < f ( x ) với ∀t ∈ (0, δ) thì ta có: f ( x + td) − f ( x ) < 0, ∀t ∈ (0, δ), t ⇒ lim t →0+ f ( x + td) − f ( x ) = d T ∇ f ( x ) ≤ 0. t Hệ quả 1.1. Nếu −∇ f ( x ) 6= 0 thì: 1. −∇ f ( x ) là hướng làm giảm hàm mục tiêu tại x. 2. − A∇ f ( x ) là hướng làm giảm hàm mục tiêu tại x với A là ma trận đối xứng xác định dương bất kỳ. Chứng minh. Ta có thể chứng minh rất dễ hai hệ quả này như sau: 1. Rõ ràng rằng: −∇ f ( x ) T ∇ f ( x ) = − k∇ f ( x )k22 < 0 nếu ∇ f ( x ) 6= 0. 2. Rất dễ nhận thấy là: −( A∇ f ( x )) T ∇ f ( x ) = −∇ f ( x ) T A∇ f ( x ) < 0. 17 Chú ý. 1. Các phương pháp tối ưu sử dụng hướng ∇ f ( x ) làm hướng giảm hàm mục tiêu được gọi là phương pháp đối xứng theo hướng đạo hàm (gradient descent) (do hướng −∇ f ( x )) là hướng làm giảm hàm mục tiêu nhanh nhất trong tất cả các hướng (tại x). 2. Để so sánh các hướng làm giảm hàm mục tiêu, người ta thường chuẩn hóa các hướng này sao cho kdk = 1. Định nghĩa 1.14. Tập ứng cử viên[10] Nếu trong các bước lặp của thuật toán tối ưu luôn duy trì một tập Xt sao cho: Xt T X ∗ 6= ∅. Nếu X ∗ 6= ∅ thì Xt gọi là tập ứng viên (lozalizes) tại bước t. Nhận xét 1.4. Ta có nhận xét sau: 1. Rõ ràng mục tiêu của các thuật toán tối ưu là sau một số bước lặp, lý tưởng nhất là ta có Xt ∈ X ∗ (lưu ý: theo định nghĩa thì tập ứng viên luôn khác ∅ nếu X ∗ 6= ∅) 2. Nếu không được như vậy thì thuật toán tối ưu phải đảm bảo: d( Xt ) = sup k x − yk → 0. x,y∈ Xt Khi đó d( Xt ) có thể coi là cận trên của ε(t) vì: ε(t) = ∗int ∗ k xt − x ∗ k ≤ k xt − y∗ k ≤ d( Xt ), x ∈X với y∗ ∈ X T X ∗ ∀ x t ∈ Xt . 3. Tốc độ hôi tụ của ε(t) → 0 ít nhất là bằng tốc độ hội tụ d( Xt ) → 0. 18 Ví dụ 1.8. Thuật toán chia đôi (bisection) nổi tiếng dùng để tìm nghiệm f ( x ) = 0 trên [ a, b] mà f ( a) f (b) < 0 (giá trị hàm liên tục trái đều ở hai đầu đoạn thẳng). Bước 0: gồm [ a0 ; b0 ] = [ a; b] . Bước t: • Lập ứng viên [ at ; bt ] với f ( at ) f (bt ) < 0. • Đặt ct = a t + bt . 2 – Nếu f (ct ) = 0 thì ta có nghiệm x = c1 . – Nếu f ( at ) f (ct ) < 0 thì gắn: [ at+1 ; bt+1 ] . Ngược lại ta gắn [ at+1 ; zz+1 ] = [ct ; bt ] → bước t + 1. 1.4. Điều kiện tối ưu Với bài toán quy hoạch phi tuyến không ràng buộc đã được giới thiệu, ta có một số phát biểu về điều kiện tối ưu sau. Định lý 1.6. [12] Vector z ∈ Rn được gọi là một điểm cực tiểu địa phương của một hàm f ( x ) khả vi trên Rn khi đó ∇ f (z) = 0và nếu f ( x ) hai lần khả vi thì ∇2 f (z)  0 (ma trận ∇2 f (z) nửa xác định dương). Ngược lại, nếu z ∈ Rn là một điểm mà tại đó f ( x ) hai lần khả vi và ∇ f (z) = 0, ∇2 f (z)  0 (ma trận ∇2 f (z) xác định dương), thì z là một điểm cực tiểu địa phương chặt của f ( x ) trên Rn , nghĩa là có một số ε > 0 sao cho f (z) < f ( x ) với mọi x ∈ Rn , x 6= z và k x − zk < ε. Chứng minh. Do z là cực tiểu địa phương nên với |t| đủ nhỏ và d ∈ Rn ta có 19