Bài tập lý thuyết tối ưu phi tuyến năm 2024
- Các khái niệm về tập lồi, hàm lồi, tính liên tục của hàm lồi, định lý Hahn-Banach, tách tập lồi. Show - Lý thuyết tồn tại cực trị. - Nón pháp tuyến, nón tiếp xúc, định lý Lusternik . - Đạo hàm, dưới vi phân của hàm phi tuyến. - Điều kiện tối ưu: cần, đủ - Lý thuyết đối ngẫu, điểm yên ngựa. 3. Tóm tắt nội dung học phần Tiếng Việt: Khóa học cung cấp cho sinh viên các kiến thức về: - Các khái niệm về tập lồi, hàm lồi, tính liên tục của hàm lồi, định lý Hahn-Banach, tách tập lồi. - Lý thuyết tồn tại cực trị. - Nón tiếp xúc, nón pháp tuyến, định lý Lusternik - Đạo hàm, dưới vi phân của hàm phi tuyến. - Điều kiện tối ưu: cần, đủ - Lý thuyết đối ngẫu, điểm yên ngựa Tiếng Anh: This course provides: - Convex analysis, convex sets, affine sets, Caratheodory’s Theorem - Convex functions, quasiconvex functions, lower and upper semicontinuity, continuity, Lipschitz continuity, Karamardian’s Theorem, local minima - Weak and star-weak topologies, general topology, topological vector spaces, locally convex spaces - The Hahn-Banach Theorem, extension version, separation versions, Minkowski functional, Mazur’s Theorem, strict separation - Existence theorems for minima - Tangent cones, the Lusternik Theorem - Generalized derivatives, subdifferentials, quasidifferentials, Clarke derivative - Optimality conditions, necessary conditions, sufficient conditions - Duality theorems, saddle points 4. Nội dung chi tiết học phần Chương 1. Giải tích lồi 1.1 Tập lồi trong không gian tuyến tính 1.2 Hàm lồi trong không gian tuyến tính 1.3 Tính liên tục của hàm lồi trong không gian định chuẩn 1.4 Nửa liên tục trong không gian định chuẩn 1.5 Hàm tựa lồi trong không gian định chuẩn 1.6 Tôpô yếu và tôpô yếu * 1.7 Định lí Hahn-Banach Chương 2 Các định lí tồn tại 2.1 Các định lí tồn tại 2.2 Tập các điểm cực tiểu 2.3 Các áp dụng Chương 3. Nón pháp tuyến 3.1 Các định nghĩa và tính chất 3.2 Điều kiện tối ưu tổng quát 3.3 Định lí Lusternik Chương 4. Đạo hàm suy rộng 4.1 Đạo hàm theo phương, đạo hàm Gateaux và Fréchet 4.2 Dưới vi phân 4.3 Tựa khả vi 4.4 Đạo hàm Clarke Chương 5. Qui tắc nhân tử Lagrange 5.1 Tối ưu có ràng buộc 5.2 Điều kiện cần tối ưu 5.3 Điều kiện đủ tối ưu 5.4 Các áp dụng Chương 6. Đối ngẫu 6.1 Định lí đối ngẫu dạng đối ngẫu Lagrange 6.2 Đối ngẫu Wolfe 6.3 Điểm yên ngựa 5. Phương pháp dạy và học Phương pháp truyền thống: giáo viên truyền đạt kiến thức cho sinh viên, cung trao đổi về các nội dung bài học. Kết hợp phương pháp điện tử: giáo án bằng slide, các bài tập qua email… 6. Phương pháp, hình thức kiểm tra, đánh giá kết quả học tập Giữa kỳ: 30% Cuối kỳ: 70% [1] J.F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
100% found this document useful (1 vote) 512 views 168 pages Copyright© © All Rights Reserved Available FormatsPDF, TXT or read online from Scribd Share this documentDid you find this document useful?100% found this document useful (1 vote) 512 views168 pages Tối ưu phi tuyến - phần 2Jump to Page You are on page 1of 168 Chương 7 PHƯƠNG PHÁP GRADIENT 7.1ẵPHƯƠNG PHÁP HƯỚNG Dốc NHÂT 7.1.1ệ Nội dung phưưng phápXét bài toán tối ưu không ràng buộc min (f(x): X £ K"|. Ta sẽ xây dựng một dãy điểm x°, X1, X2, ... sao cho f(xk+l) < f(xk) với mọi k = 0, 1,2,..., dãy (xkỊ hội tụ tới X* khi k -> 00 và Vf(x*) = 0. Giả sử ta có điểm xk thuộc lân cận của X*, khi đó để giảm hàm mục tiêu ta sẽ dịch chuyển từ xk theo hướng dk tạo với véctơ gradient Vf(xk) một góc tù, tức là xác địnhxk+l = xk + akdk trong đó ak \> 0, a2 f(x) = f(xk) + a ....... mf. v>f(j) . ỠX| ỡx2 ỡxn ƠXịỡXjcấp nxn và xk = xk + 0(x - xk) với 0 e [0,1]. Nếu độ dài bước ak khác nhau sẽ cho ta các phương pháp gradient khác nhau. Nếu chọn dk — - Vf(xk) với mọi k thì phương pháp gradient như thế gọi là phương 183 pháp luỉớng dốc nhất (Steepest Descent Method). Đây là 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ất rộng. Phương pháp này xây dựng dãy lặp:xk+' \= xk - otkVf(xk), ctk \> 0, k \= 0, 1,... (7.1)Ì3. Thuật toán xác định ak tại mỗi bước lặp {Qui tắc Armijo):
a \= 1) và xác định điểm X \= xk- ccVf(xk).
0 < £ < 1là một hằng số được chọn tùy ý, như nhau với mọi k \= 0,1, ...
a. Nếu (7.2) không thỏa mãn thì ta giảm a (bằng cách nhân a với một số Ấ 6 (0, 1), chẳng hạn Ằ = Vì) cho đến khi bất đẳng thức (7.2) được thỏa mãn.7.1.2. Sự hội tụ của phương pháp gradient Ta nói dãy (xk) hội tụ tới điểm X* với tôỆc độ liội tụ tuyến lính hay tốc độ hội tụ cấp số nhân (công bội q) nếu bắt đầu từ một chi số k nào đó ta có bất đảng thức llxk+l - x*ll < q llxk - x*ll, 0 < q < 1. Cơ sở của việc lựa chọn a như trên và sự hội tụ của phương pháp gradient cho trong định lý sau.Định lý 7.1ẻ Giả sử hàm f(x) bị chặn dưới, gradient Vf(x) thỏa mãn điều kiện Lipschitz :IIVf(x) - Vf(y)ll < Lllx - yll, Vx, yel”và ak được chọn theo thuật toán nêu trên. Khi đó, với bát kỳ’ điềm ban đầu x°, quá trình lặp (7.1) có tính chất: IIVf(xk)ll -> 0 khi k -►X. 184 Chứng minh. Theo định lý giá trị trung bình: f(x) - f(xk) = trong đó xk = xk + 0(x - xk) với 0 e [0, 1], Do X- xk \= - aVf(xk) nên ta có f(x) - f(xk) = < - a < - allVf(xk)ll2 + cxLllx - xkII.IIVf(xk)ll \= allVf(xk)ll2(- 1+ aL). Từ đánh giá đó suy ra rằng, nếu chọn a sao cho- 1+ aL < - £ hay a < (1 - e)/ Lthì bất đẳng thức (7.2) sẽ được thỏa mãn. Vậy việc chọn a theo thuật toán trên là có thể thực hiện được. Khi đã chọn aknhư trên ta có f(xk+l) - f(xk) < - sakIIVf(xk)ll2, (7.3) tức là với bất kỳ k thì f(xk+l) - f(xk) < 0 (với điểu kiện Vf(xk) * 0). Vì hàm f(x) bị chạn dưới, nên bất đẳng thức nhận được cho thấyf(xk+l) - f(xk) —» 0 khi k -» co. (7.4)Từ (7.3) suy ra: IIVf(xk)ll2 < [f(xk) - f(xk+1)]/(scxk). (7.5)Chú ý là thuật toán chọn akđảm bảo cho với bất kỳ k sẽ có ock \> ã \> 0, trong đó ã có thể chọn là hằng sô' tùy ý không vượt quá (1 - £)/ L (vì bất đảng thức (7.2) hay (7.3) được thỏa mãn với a \= (1 - e)/L). Từ (7.4), (7.5) và chú ý này suy ra IIVf(xk)ll -» 0 khi k -> 00 . Định lý được chứng minh. Định lý 7.1 bảo đàm giá trị hàm mục tiêu hội tụ hoặc đến cận iưới inf f(x), hoặc tới giá trị của hàm tại điểm dừng nào đó (có thể à điểm cực tiểu địa phương hay điểm yên ngựa). Với những giả 185 Reward Your CuriosityEverything you want to read. Anytime. Anywhere. Any device. No Commitment. Cancel anytime. |