ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM KHOA TOÁN ——— * ——— DƯƠNG XUÂN HIỆP GIẢI THUẬT GRADIENT CHO BÀI TỐN TỐI ƯU KHƠNG ĐIỀU KIỆN RÀNG BUỘC CHUYÊN NGÀNH: SƯ PHẠM TOÁN HỌC LUẬN VĂN TỐT NGHIỆP Giảng viên hướng dẫn: T.S Phạm Quý Mười Đà Nẵng, Tháng năm 2016 MỤC LỤC LỜI NÓI ĐẦU KIẾN THỨC CƠ SỞ 1.1 Ma trận 1.2 Không gian Euclid Rn 1.3 Giá trị riêng dạng toàn phương 1.3.1 Giá trị riêng 1.3.2 Dạng toàn phương 1.4 Các khái niệm Tôpô 1.5 Hàm số liên tục Rn 1.6 Định lý Taylor định lí giá trị trung gian 1.7 Các khái niệm tập lồi hàm lồi 1.7.1 Tập lồi 1.7.2 Hàm lồi 1.8 Các định lý tách, siêu phẳng siêu phẳng tựa 1.9 Cực điểm CỞ SỞ TÍNH CHẤT NGHIỆM VÀ GIẢI THUẬT CỦA TỐI ƯU 2.1 Điều kiện cần thứ 2.1.1 Ràng buộc có hướng 2.1.2 Điều kiện cần thứ 2.2 Điều kiện cần thứ hai 2.3 Điều kiện đủ 2.4 Cực tiểu cực đại hàm lồi 2.5 Sự hội tụ toàn cục giải thuật giảm 2.5.1 Giải thuật 2.5.2 Hàm giảm 2.5.3 Ánh xạ đóng 2.5.4 Định lý hội tụ toàn cục 2.5.5 Tốc độ hội tụ 5 9 11 12 14 16 16 16 18 21 24 BÀI TOÁN 25 25 26 27 30 32 33 34 35 36 36 37 38 GIẢI THUẬT GRADIENT CHO BÀI TOÁN TỐI ƯU KHÔNG RÀNG BUỘC 3.1 Giải thuật lặp cho Bài tốn tối ưu khơng điều kiện ràng buộc 3.2 Đường tìm kiếm khơng xác 3.2.1 Quy tắc Armijo 3.2.2 Quy tắc Goldstein 3.3 Phương pháp giảm bước nhanh 3.3.1 Hướng giảm nhanh 3.3.2 Kích thước bước 3.3.3 Quy tắc Goldstein giải thuật giảm bước nhanh 3.3.4 Hướng giảm cực tiểu 3.3.5 Tốc độ hội tụ 3.3.6 Bài toán tối ưu bậc hai 3.3.7 Chương trình Matlab cho giải thuật 40 40 41 41 42 43 43 44 45 47 50 54 61 KẾT LUẬN 74 TÀI LIỆU THAM KHẢO 74 LỜI NÓI ĐẦU Lý thuyết tối ưu lĩnh vực đóng vai trị quan trọng việc nghiên cứu vấn đề cực trị có nhiều ứng dụng đời sống thực tế ngành khoa học Tuy nhiên phải đến năm 30, 40 kỉ XX, Toán tối ưu hình thành với tư cách lý thuyết độc lập với nhiều hướng nghiên cứu khác ngày ứng dụng nhiều sống nhờ phát triển công nghệ thông tin, đặc biệt máy tính Luận văn nghiên cứu sở lý thuyết cho toán tối ưu trơn phương pháp gradient Cụ thể, luận văn trình bày số kết điều kiện cần đủ cho nghiệm Bài toán tối ưu Giải thuật gradient cho Bài tốn tối ưu khơng có điều kiện ràng buộc Luận văn gồm ba chương khái quát vấn đề chung tiếp cận với lý thuyết giải thuật cho Bài tốn tìm cực tiểu Chương 1: Kiến thức sở Chương trình bày khái niệm kí hiệu sử dụng luận văn gồm: số khái niệm giá trị riêng, tập lồi, hàm lồi, hàm số liên tục Rn định lý Taylor, định lý giá trị trung gian định lý tách, tạo sở, tiền đề cho việc tiếp cận kiến thức chương sau Chương 2: Cơ sở tính chất nghiệm giải thuật tốn tối ưu Chương trình bày số kết khái niệm mở đầu toán tối ưu tổng quát, điều kiện nghiệm cần đủ tốn tối ưu, tính chất quan trọng cực trị hàm lồi hội tụ giải thuật giảm - sở việc hình thành giải thuật sau Chương 3: Giải thuật Gradient cho tốn tối ưu khơng ràng buộc Chương trình bày kết việc hình thành giải thuật giảm Bài tốn tối ưu khơng điều kiện ràng buộc, phương pháp tìm gần cực tiểu hàm biến, hội tụ, tốc độ phương pháp giảm nhanh trường hợp riêng toán tối ưu bậc hai Sau thời gian tích cực học tập nghiên cứu, bảo tận tình thầy giáo hướng dẫn, thân em tích lũy cho nhiều kiến thức kinh nghiệm niềm đam mê lý thuyết Toán học thân đến luận văn em hoàn thành Em xin gửi lời cảm ơn chân thành tới nhà trường, ban chủ nhiệm khoa Toán-trường ĐHSP Đà Nẵng tạo hội cho em làm Luận văn tốt nghiệp Em xin bày tỏ lòng biết ơn tới thầy giáo T.S Phạm Quý Mười, thầy tận tình hướng dẫn em suốt thời gian làm luận văn Em xin bày tỏ lòng biết ơn chân thành đến thầy giáo tận tình giảng dạy chúng em suốt bốn năm học vừa qua Cuối em xin chân thành cảm ơn gia đình, bạn bè giúp đỡ, động viên, tạo điều kiện cho em hoàn thành luận văn Đà Nẵng, tháng năm 2016 Sinh viên thực Dương Xuân Hiệp CHƯƠNG KIẾN THỨC CƠ SỞ Phần trình bày số khái niệm ma trận, không gian Rn , giá trị riêng dạng toàn phương, khái niệm Tôpô, hàm số liên tục, định giá trị trung gian, tập lồi, hàm lồi, định lý tách, cực điểm công cụ để tiếp cận kiến thức chương sau luận văn 1.1 Ma trận Định nghĩa 1.1 Một ma trận cỡ m × n bảng số hình chữ nhật gồm m hàng n cột gọi ma trận m × n, kí hiệu Am×n , có dạng:   a11 a12 a1n  a21 a22 a2n    Am×n =     am1 am2 amn Ma trận cỡ m × n gọi m × n-ma trận Nếu m n rõ ma trận Am×n kí hiệu gọn A (aij )m×n Định nghĩa 1.2 (i) Một m × n-ma trận gọi ma trận khơng, kí hiệu 0, aij = ∀i ∈ {1, 2, , m}, j ∈ {1, 2, , n} (ii) Một ma trận vng cấp n (n × n-ma trận) mà phần tử aij = với i = j aii = 1, ∀i ∈ {1, 2, , n} gọi ma trận đơn vị cấp n, kí hiệu In I Khi đó:   0       In =  0      0 Các phép tốn ma trận thơng thường hiểu thực bình thường Định nghĩa 1.3 (a) Ma trận chuyển vị m × n-ma trận A, kí hiệu AT n × m-ma trận với aTij = aji (b) Ma trận vuông A gọi ma trận đối xứng AT = A (c) Ma trận A gọi không suy biến có ma trận A−1 Khi ma trận A gọi ma trận khả nghịch, thỏa mãn A−1 A = I = AA−1 Các khái niệm định thức ma trận vuông A tính chất khơng trình bày, người đọc tham khảo thêm 1.2 Khơng gian Euclid Rn Trong luận văn này, xét không gian Euclide n-chiều Rn Định nghĩa 1.4 Một điểm x không gian Euclid Rn n số thực xếp theo thứ tự viết dạng n-cột   x1  x2    x =   ,   xn với số xi ∈ R, i ∈ {1, 2, , n} gọi tọa độ thứ i điểm x Đề thuận tiện ta quy ước    x = (x1 , x2 , , xn ) =   T x1 x2      xn Kí hiệu = (0, 0, , 0)T ∈ Rn gốc tọa độ không gian Rn Mỗi điểm x thuộc Rn xác định véctơ Rn với điểm gốc điểm x Véctơ xác định kí hiệu x Định nghĩa 1.5 Hai điểm (véctơ) x y Rn , kí hiệu [x, y], tập hợp điểm (véctơ) có dạng αx + (1 − α) y, ∀ ≤ α ≤ Định nghĩa 1.6 Cho hai véctơ x = (x1 , x2 , , xn )T y = (y1 , y2 , , yn )T Rn Khi đó: (i) Tích vơ hướng hai véctơ, kí hiệu xT y, yT x x, y , xác định n T T x y = y x = x, y = xi yi i=1 (ii) Hai véctơ x y trực giao xT y = yT x = x, y = (iii) Độ dài hay chuẩn véctơ x, kí hiệu x , xác định n T x = x x 1/2 x2i = i=1 Hình 1.1: Đoạn thẳng Nhận xét 1.1 Trong khơng gian véctơ Cn , tích vơ hướng hai véctơ x, y có tính chất sau: (i) Tích vơ hướng hai véctơ, kí hiệu x, y , xác định n x, y = xi y i i=1 (ii) x ≥ x = x = (iii) x, y = y, x (iv) λx, y = λ x, y với λ ∈ C x, λy = λ x, y với λ liên hợp λ Tính chất 1.1 Một số tính chất biết chuẩn véctơ: (a) x ≥ (b) αx =| α | x , với α ∈ R (c) x+y ≤ x x = x = + y , với véctơ x, y Rn (d) Bất đẳng thức Cauchy-Schwarz xT y ≤ x y , với véctơ x, y Rn Định nghĩa 1.7 Các véctơ a1 , a2 , , ak gọi là: (i) Phụ thuộc tuyến tính tồn số thực λ1 , λ2 , , λk không đồng thời cho ki=1 λi = (ii) Độc lập tuyến tính khơng tồn số thực λ1 , λ2 , , λk không đồng thời cho ki=1 λi = Định nghĩa 1.8 (i) Một tổ hợp tuyến tính véctơ a1 , a2 , , ak véctơ có dạng ki=1 λi với λ1 , λ2 , , λk ∈ R Khi tập hợp véctơ dạng gọi tập hợp véctơ sinh a1 , a2 , , ak (ii) Tập hợp véctơ độc lập tuyến tính sinh Rn gọi sở Rn Mỗi sở Rn chứa n véctơ Định nghĩa 1.9 Hạng m × n-ma trận A số cột độc lập tuyến tính lớn ma trận A số hàng độc lập tuyến tính lớn ma trận A Hơn nữa, hạng m × n-ma trận A min{m, n} ma trận A gọi có cấp đầy đủ Định nghĩa 1.10 Một không gian M E n tập đóng phép cộng phép nhân vơ hướng, tức là: λa + µb ∈ M, ∀a, b ∈ M, ∀λ, µ ∈ R Định nghĩa 1.11 Số chiều không gian M số véctơ độc lập tuyến tính lớn M Định nghĩa 1.12 Với M không gian E n , phần bù trực giao M , kí hiệu M ⊥ , tập hợp gồm véctơ trực giao với véctơ thuộc M Dựa vào kết giải tích hàm, ta chứng minh phần bù trực giao M không gian E n , M M ⊥ cảm sinh không gian E n Nói cách khác với véctơ x ∈ E n biểu diễn dạng x = a + b với a ∈ M, b ∈ M ⊥ Lúc đó, a, b gọi hình chiếu trực giao véctơ x lên không gian M M ⊥ Định nghĩa 1.13 Một quan hệ tương ứng A gán điểm không gian X với điểm không gian Y gọi ánh xạ từ X đến Y kí hiệu A:X →Y Ánh xạ A tuyến tính phi tuyến tính Định nghĩa 1.14 Chuẩn ánh xạ tuyến tính A, kí hiệu là: A = max Ax A , đinh nghĩa x ≤1 Tính chất 1.2 Với véctơ x, ta có: Ax ≤ A 1.3 1.3.1 x Giá trị riêng dạng toàn phương Giá trị riêng Định nghĩa 1.15 Cho n × n-ma trận vng A Nếu tồn vô hướng λ ∈ R véctơ x = thỏa mãn Ax = λx λ gọi giá trị riêng ứng với véctơ riêng x A Nhận xét 1.2 Điều kiện cần đủ để λ ∈ R giá trị riêng ma trận A ma trận A − λI suy biến, tức det (A − λI) = hay (λI − A) = Từ nhận xét ta nhận thấy giá trị riêng λ nghiệm đa thức det (λI − A) = λn + an−1 λ + + a1 λ + a0 = Đa thức phương trình gọi đa thức phương trình đặc trưng ma trận vng A Định lý 1.16 Giả sử phương trình đặc trưng det (λx − A) = có n nghiệm thực phân biệt λ1 , λ2 , , λn Khi tồn n véctơ độc lập tuyến tính x1 , x2 , , xn véctơ riêng ma trận A, tức véctơ thỏa mãn: Axi = λxi , ∀i ∈ {1, 2, , n} Chứng minh Ta có: det (λxi − A) = nên tồn véctơ xi = cho Axi = λxi với i ∈ {1, 2, , n} Bây ta chứng minh hệ n véctơ x1 , x2 , , xn độc lập tuyến tính Thật vậy: Gọi c1 , c2 , , cn vô hướng cho ni=1 ci xi = Xét ma trận B = (λ2 I − A)(λ3 I − A) (λn I − A) Khi đó: Bxn = (λ2 I − A)(λ3 I − A) (λn I − A)xn = (λ2 I − A)(λ3 I − A) (λn xn − Axn ) Bxn = λn xn − Axn = Tương tự ta chứng minh được: Chia vế cho f (xk ) − f (x∗ ), ta có f (xk+1 ) − f (x∗ ) (M − m)2 4M m ≤ o( xk − x∗ − ∗ 2 ∗ f (xk ) − f (x ) (M + m) (M + m) f (xk ) − f (x ) ) (3.33) Mặt khác, theo (3.18), ta có M nên xk − x∗ ≥ f (xk ) − f (x∗ ) ≥ f (xk ) − f (x∗ ) M xk − x∗ Kết hợp với (3.33), ta có (M − m)2 f (xk+1 ) − f (x∗ ) 4M m o( xk − x∗ ≤ − f (xk ) − f (x∗ ) (M + m)2 (M + m)2 M xk − x∗ 2 ) Chuyển qua giới hạn ta f (xk+1 ) − f (x∗ ) ≤ lim sup k→∞ f (xk ) − f (x∗ ) M −m M +m Để việc tính tốn nhanh chóng xác, người ta thường sử dụng phần mềm Matlab cơng cụ hữu dụng q trình giải toán tối ưu Sau số chương trình cho giải thuật cho dạng tốn tối ưu nêu 3.3.7 Chương trình Matlab cho giải thuật 3.3.7.1 Bài toán tối ưu bậc Bài tốn tối ưu bậc hai có dạng: minn f (x) = xT Qx − xT b, x∈R với Q n × n-ma trận xác định dương Dãy {xk } xác định bởi: xk+1 = xk − αk ∇f (xk )T , với αk vơ hướng dương gọi kích thước bước Với toán tối ưu bậc hai ta xác định αk = gkT gk gkT Qgk 61 Do đó: xk+1 = xk − gkT gk gkT Qgk gk , với gk = Qxk − b Khi đó, chương trình Matlab cho tốn tối ưu bậc hai với kích thước bước xác : Chương trình Matlab cho tốn tối ưu bậc hai với kích thước bước xác % Định nghĩa hàm mục tiêu, ma trận Q, véctơ b f=@(x) x’*Q*x/2-b’*x; % Chọn giá trị khởi tạo x0 ; % Lưu thông tin dãy xn f (xn ) xn=[]; fn=[]; % Chọn giá trị n cho vòng lặp for i=1:n xn=[xn x0]; tg=(x0-xstar)’*Q*(x0-xstar)/2; Error=[Error tg]; tg=f(x0); fn=[fn tg]; gk=Q*x0-b; ak=gk’*gk/(gk’*Q*gk); x1=x0-ak*gk; x0=x1; end 3.3.7.2 Bài toán tối ưu tổng quát Bài toán tối ưu tổng quát có dạng f (x) x∈Rn Dãy {xk } xác định xk+1 = xk − αk ∇f (xk )T , với kích thước bước αk > giá trị thực dương để hàm số ϕ(αk ) = f (xk − αk ∇f (xk )T ), xấp xỉ giá trị nhỏ Khi ta cần sử dụng đường tìm kiếm khơng xác để tìm giá trị αk xấp xỉ cực tiểu hàm số ϕ Sau chương trình Matlab cho đường tìm kiếm theo quy tắc Armijo 62 tiểu chuẩn Goldstein a) Quy tắc Armijo + α xem không bé theo quy tắc Armijo ϕ(0) + εϕ(0)α với ε cố định < ε < + α xem không nhỏ với giá trị η > chọn trước ta có ϕ(ηα) > ϕ(0) + εϕ (0)ηα Chương trình Matlab cho tốn tối ưu với kích thước bước xác định đường tìm kiếm Armijo % Định nghĩa hàm mục tiêu tính véctơ gradient f=@(x) ; gradf=@(x) ; % Chọn giá trị khởi tạo x0 ; % Lưu thông tin dãy xn f (xn ) x=[x0]; F=[f(x0)]; % Chọn tham số cho quy tắc Armijo eps=1/2; nu=2; % Chọn giá trị n cho vòng lặp % Khởi tạo vòng lặp for i=1:n an=1; tg=gradf(x0); x1=x0-an*tg’; if f(x1)