BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI ====== BÙI ANH ĐỨC VỀ ĐIỀU KIỆN TỐI ƯU BẬC HAI CỔ ĐIỂN CỦA CÁC BÀI TOÁN TỐI ƯU PHI TUYẾN LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI ====== BÙI ANH ĐỨC VỀ ĐIỀU KIỆN TỐI ƯU BẬC HAI CỔ ĐIỂN CỦA CÁC BÀI TOÁN TỐI ƯU PHI TUYẾN Chun ngành: Tốn Giải tích Mã số: 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS NGUYỄN VĂN TUYÊN HÀ NỘI - 2018 Lời cảm ơn Luận văn “Về điều kiện tối ưu bậc hai cổ điển toán tối ưu phi tuyến” kết trình cố gắng không ngừng thân tác giả giúp đỡ, động viên khích lệ thầy cơ, bạn bè đồng nghiệp người thân Tác giả xin bày tỏ lòng biết ơn sâu sắc T.S Nguyễn Văn Tuyên trực tiếp tận tình hướng dẫn, cung cấp tài liệu thông tin khoa học cần thiết cho luận văn Tác giả xin chân thành cảm ơn tồn thể thầy giáo giảng viên Khoa Tốn, thầy phòng Sau Đại học thầy cô Trường Đại Học Sư Phạm Hà Nội giảng dạy tạo điều kiện tác giả hồn thành tốt cơng việc nghiên cứu khoa học Cuối tác giả xin chân thành cảm ơn đồng nghiệp, đơn vị cơng tác, gia đình bạn bè động viên, tạo điều kiện giúp đỡ tơi q trình học tập thực luận văn Lời cam đoan Tôi xin cam đoan số liệu kết nghiên cứu luận văn trung thực không trùng lặp với đề tài khác Tôi xin cam đoan giúp đỡ cho việc thực luận văn cảm ơn thơng tin trích dẫn luận văn rõ nguồn gốc Tác giả luận văn Bùi Anh Đức Mục lục Một số kiến thức chuẩn bị 1.1 Tập lồi hàm lồi 1.1.1 Các khái niệm 1.1.2 Hàm lồi trơn 11 1.2 Nón tiếp tuyến 11 1.2.1 Định nghĩa 11 1.2.2 Ràng buộc trơn tính quy metric 13 1.3 Điều kiện tối ưu bậc 20 1.3.1 Bài tốn trơn khơng có ràng buộc 20 1.3.2 Bài tốn trơn có ràng buộc 22 Điều kiện tối ưu bậc hai cổ điển 2.1 Điều kiện MFCQ điều kiện tối ưu bậc hai cổ điển 28 28 2.2 Điều kiện MFCQ cải biên điều kiện tối ưu bậc hai cổ điển 36 2.2.1 Mở rộng bổ đề Hestenes 38 2.2.2 Mở rộng bổ đề Yuan 42 2.2.3 Kết tổng quát 43 2.2.4 Kết 44 2.2.5 Một điều kiện quy 50 Mở đầu Lý chọn đề tài Trong luận văn này, tập trung nghiên cứu điều kiện cần tối ưu bậc hai cho tốn tối ưu phi tuyến có dạng sau f (x) (P) n x ∈ X := {x ∈ R : gi (x) 0, i ∈ I, hj (x) = 0, j ∈ J}, I = {1, , p}, J = {1, , q}, hàm f : Rn → R, gi : Rn → R, hj : Rn → R hàm số thực khả vi liên tục đến cấp hai Rn Hàm Lagrange suy rộng toán (P) định nghĩa p q L(x, λ0 , λ, µ) = λ0 f (x) + λi gi (x) + i=1 µj hj (x) j=1 Hàm L(x, λ, µ) := L(x, 1, λ, µ) gọi hàm Lagrange Bài toán (P) Với x ∈ X, tập số hoạt I(x), nón hướng tới hạn C(x), tập nhân tử Lagrange suy rộng Λ0 (x), tập nhân tử Lagrange Λ(x) định nghĩa bởi: I(x) = {i ∈ I | gi (x) = 0}, C(x) = {d | ∇f (x)t d 0, ∇gi (x)t d 0, i ∈ I(x), ∇hj (x)t d = 0, j ∈ J}, Λ0 (x) = {(λ0 , λ, µ) = | ∇x L(x, λ0 , λ, µ) = 0, (λ0 , λ) ∈ Rp+1 + , λi gi (x) = 0, i ∈ I}, Λ(x) = {(λ, µ) | (1, λ, µ) ∈ Λ0 (x)} Như biết nghiệm tối ưu địa phương x∗ toán (P) thỏa mãn điều kiện cần bậc bậc hai kiểu Fritz-John sau: (1) Λ0 (x∗ ) = ∅; (2) với phương d ∈ C(x∗ ), tồn nhân tử Lagrange suy rộng (λ0 , λ, µ) cho dt ∇2xx L(x∗ , λ0 , λ, µ)d 0; (0.1) xem [4] Điều kiện cần tối ưu bậc hai (0.1) viết lại tương đương sau: sup (λ0 ,λ,µ)∈Λ0 (x∗ ) dt ∇2xx L(x∗ , λ0 , λ, µ)d ∀d ∈ C(x∗ ) (0.2) Điều kiện có hai hạn chế Hạn chế thứ nhân tử Lagrange λ0 hàm mục tiêu khơng; tức hàm mục tiêu khơng đóng vai trò điều kiện tối ưu Hạn chế thứ hai nhân tử (λ0 , λ, µ) khơng thiết giống cho tất hướng tới hạn Muốn kiểm tra điều kiện (0.2) ta phải kiểm tra tính nửa xác định dương cận trên tập tất nhân tử Lagrange dạng toàn phương Tuy nhiên, việc tính tốn tập tất nhân tử Lagrange (P) tốn khó Quan trọng thuật tốn đảm bảo tính xấp xỉ nghiệm cho cặp nhân tử Lagrange Khi nhân tử Lagrange λ0 hàm mục tiêu khác khơng, ta nói x∗ thỏa mãn điều kiện tối ưu kiểu Karush–Kuhn–Tucker (KKT) Để đạt điều x∗ phải thỏa mãn điều kiện quy Như biết, x∗ thỏa mãn điều kiện chuẩn hóa ràng buộc độc lập tuyến tính (LICQ); tức véctơ ∇gi (x∗ ), i ∈ I(x∗ ), ∇hj (x∗ ), j ∈ J, độc lập tuyến tính, Λ(x∗ ) = {(λ, µ)} tập điểm ta có dt ∇2xx L(x∗ , λ, µ)d ∀d ∈ C(x∗ ) (0.3) Điều kiện (0.3) gọi điều kiện cần tối ưu bậc hai cổ điển cho Bài toán (P) Như phân tích trên, điều kiện tối ưu kiểu đóng vai trò quan trọng phương diện lý thuyết ứng dụng lý thuyết tối ưu Điều kiện (LICQ) điều kiện đủ để đảm bảo điều kiện cần tối ưu bậc hai cổ điển Tuy nhiên, nhiều trường hợp, điều kiện (LICQ) chặt Nếu điều kiện (LICQ) khơng thỏa mãn, tập nhân tử (KKT) khơng tập điểm điều kiện (0.3) khơng thỏa mãn Điều kiện tối ưu (0.3) số trường hợp đặc biệt sau (xem [3]): (i) tất hàm gi hj affine; (ii) hàm f gi lồi, hàm hj affine x∗ thỏa mãn điều kiện Slater; (iii) tồn ti (, à) Rp+ ì Rq cho (x , λ, µ) điểm yên ngựa hàm Lagrange Bài toán (P) λ0 = Gần đây, Baccari [1] điều kiện chuẩn hóa ràng buộc Mangasarian–Fromovitz (MFCQ) thỏa mãn x∗ điều kiện (0.3) số trường hợp sau: (C1) n (C2) px∗ 2, 2, px∗ số ràng buộc hoạt bất đẳng thức x∗ Sau đó, Baccari Trad [2] đề xuất số điều kiện gọi điều kiện chuẩn hóa ràng buộc Mangasarian-Fromovitz cải biên (MMF) điều kiện bù chặt (GSCS) Các tác giả điều kiện (MMF) (GSCS) đủ để đảm bảo cho tính đắn điều kiện tối ưu bậc hai cổ điển Trên sở tài liệu tham khảo trích dẫn trên, luận văn khảo sát điều kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến với liệu trơn C Mục đích nghiên cứu Nghiên cứu điều kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến Nhiệm vụ nghiên cứu Nghiên cứu điều kiện quy điều kiện cần tối ưu bậc hai cho toán tối ưu phi tuyến với liệu trơn C tn1 Pn (d) + tn2 Qn (d) = tn1 P (d) + tn2 Q (d) + (1/n ) d > 0, ∀d ∈ K, d = Dãy (tn1 , tn2 )n chứa dãy (tn1 k , tn2 k )k hội tụ tới (t1 , t2 ) , t1 ≥ 0, t2 ≥ : t1 + t2 = với d ∈ K, d = cố định, tn1 P (d) + tn2 Q (d) + (1/n ) d > ⇒ t1 P (d) + t2 Q (d) ≥ Hệ chứng minh 2.2.3 Kết tổng quát Định lí 2.4 hệ dùng để chứng minh kết tổng quát sau Định lý 2.5 Cho x∗ nghiệm tối ưu địa phương (P) Λ (x∗ ) đoạn thẳng bị chặn Khi đó, với nón bậc K chứa nón tới hạn C (x∗ ) , tồn λK , µK ∈ Λ (x∗ ) cho: (d)t ∇2xx L x∗ , λK , µK d ≥ 0, ∀d ∈ K (2.16) Hơn nữa, x∗ thỏa mãn điều kiện đủ SC2, chọn λK , µK cho (d)t ∇2xx L x∗ , λK , µK d > 0, ∀d ∈ K, d = (2.17) Chứng minh Chứng minh (2.16): x∗ nghiệm tối ưu địa phương (P) thỏa mãn MFCQ, GN2 Nếu Λ (x∗ ) tập phần tử, GN2 kéo theo (2.16) Giả sử đoạn thẳng đóng bị chặn Λ (x∗ ) khơng phải tập phần tử, Λ (x∗ ) chứa hai điểm cực biên λ1 , µ1 , λ2 , µ2 ∈ Λ (x∗ ) Đặt P (d) = (d)t ∇2xx L x∗ , λ1 , µ1 d; Q (d) = (d)t ∇2xx L x∗ , λ2 , µ2 d 43 Ta thấy (d)t ∇2 L (x∗ , λ, µ) d tuyến tính theo (λ, µ) “max” GN2 đạt điểm cực biên Vì vậy, ta có 0≤ max (λ,µ)∈Λ(x∗ ) (d)t ∇2xx L (x∗ , λ, µ) d = max (P (d) , Q (d)) , ∀d ∈ K, (2.12) thỏa mãn Từ Hệ 2.1, ta suy (2.12) kéo theo (2.13), nghĩa là, tồn t1 ≥ 0, t2 ≥ cho t1 + t2 = 1, t1 P (d) + t2 Q (d) ≥ 0, ∀d ∈ K, λK , µK = t1 λ1 , µ1 + t2 λ2 , µ2 ∈ Λ (x∗ ) , t1 P (d) + t2 Q (d) = (d)t ∇2xx L x∗ , λK , µK d ≥ 0, ∀d ∈ K Để chứng minh (2.17) ta sử dụng Định lý 2.4 chứng minh tương tự 2.2.4 Kết Các điều kiện cần tối ưu cấp hai cổ điển CN2 khơng dễ đạt khơng có điều kiện LICQ, giả thiết tính lồi hay điều kiện SCS Trước hết ta xét toán tối ưu mà nón tới hạn nón bậc tập nhân tử Lagrange đoạn thẳng bị chặn Kết tiểu mục sau Định lý 2.6 Cho x∗ nghiệm tối ưu địa phương (P) cho điều kiện sau thỏa mãn: (i) tập nhân tử Lagrange Λ(x∗ ) đoạn thẳng bị chặn; (ii) tồn nhiều số i0 ∈ I (x∗ ) cho (λ, µ) ∈ Λ (x∗ ) ⇒ λi0 = 0; 44 (2.18) tồn nhân tử Lagrange (λ∗ , µ∗ ) ∈ Λ (x∗ ) cho (d)t ∇2xx L (x∗ , λ∗ , µ∗ ) d ≥ 0, ∀d ∈ C (x∗ ) Hơn nữa, x∗ thỏa mãn điều kiện đủ tối ưu cấp hai SC2, chọn (λ∗ , µ∗ ) cho: (d)t ∇2xx L (x∗ , λ∗ , µ∗ ) d > 0, ∀d ∈ C (x∗ ) , d = Chứng minh Đầu tiên ta chứng minh C (x∗ ) nón bậc Ta xét hai trường hợp sau: (1) Không tồn i0 ∈ I (x∗ ) cho (2.18) thỏa mãn Điều có nghĩa x∗ thỏa mãn điều kiện SCS C (x∗ ) không gian véctơ con; xem Nhận xét 2.3 (2) Tồn số i0 ∈ I (x∗ ) cho (2.18) thỏa mãn Điều dẫn đến d ∈ C (x∗ ) ∇gi (x∗ )t d = 0, ∀i ∈ I (x∗ ) − {i0 } , ∇gi0 (x∗ )t d ≤ 0, ∇hj (d)t d = 0, j = 1, 2, , q Nếu C (x∗ ) khơng gian tồn d0 ∈ C (x∗ ) cho ∇gi0 (x∗ )t d0 < với d ∈ C (x∗ ) khác,tồn r ≥ cho: ∇gi0 (x∗ )t d = r∇gi0 (x∗ )t d0 , ∇gi0 (x∗ )t d − rd0 = 0, ∇gi (x∗ )t d − rd0 = 0, ∀i ∈ I (x∗ ) − {i0 } ; ∇hj (x∗ )t d − rd0 = 0, j = 1, 2, , q, w = d − rd0 thuộc không gian véctơ E = w | ∇gi (x∗ )t w = 0, ∀i ∈ I (x∗ ) ; ∇hj (x∗ )t w = 0,j = 1, 2, , q ⊂ C (x∗ ) 45 Do đó, C (x∗ ) = E + R+ d0 Do đó, (ii) suy C(x∗ ) nón bậc từ Định lý 2.5 ta thu điều cần chứng minh Nhận xét 2.4 (i) Ta đưa mơt chứng minh trực tiếp cho Định lý 2.6 cách sử dụng bổ đề Hestenes, việc sử dụng bổ đề Yuan mở rộng (Định lý 2.4) kết tổng quát (Định lý 2.5) làm cho việc chứng trở nên rõ ràng (ii) Nếu (2.18) thỏa mãn với nhiều số i ∈ I (x∗ ), nón tới hạn C (x∗ ) khơng phải nón bậc sử dụng Định lý 2.5 để chứng minh Định lý 2.6 Để thấy điều này, chẳng hạn, giả sử ∈ I (x∗ ) ∈ I (x∗ ) số hoạt thỏa mãn (2.18), giả sử tồn d1 ∈ C(x∗ ) d2 ∈ C(x∗ ) cho ∇g1 (x∗ )t d1 < 0, ∇g2 (x∗ )t d1 = 0, ∇g2 (x∗ )t d2 < 0, ∇g1 (x∗ )t d2 = Với d ∈ C(x∗ ), ta tìm r1 ≥ r2 ≥ cho ∇g1 (x∗ )t d − r1 d1 − r2 d2 = ∇g1 (x∗ )t d − r1 d1 = ∇g1 (x∗ )t (d) − r1 ∇g1 (x∗ )t d1 = 0, ∇g2 (x∗ )t d − r1 d1 − r2 d2 = ∇g2 (x∗ )t d − r2 d2 = ∇g2 (x∗ )t (d) − r2 ∇g2 (x∗ )t d2 = Điều có nghĩa w = d − r1 d1 − r2 d2 thuộc không gian véctơ E = w | ∇gi (x∗ )t w = 0, ∀i ∈ I (x∗ ) ; ∇hj (x∗ )t w = 0, j ∈ J, ⊂ C (x∗ ) , C (x∗ ) = E + R+ d1 + R+ d2 , C (x∗ ) nón bậc 46 Ví dụ 2.2 Xét tốn tối ưu không lồi R4 sau {−x1 | gi (x) , i = 1, 2, 3} , g1 (x) = 2x21 − x22 + 2x23 + x1 ; g2 (x) = −x22 + x1 − 2x4 ; g3 (x) = −x21 + x22 − x23 + x1 + x4 Với điểm chấp nhận x, g1 (x) + g2 (x) + 2g3 (x) = 4x1 ≤ Dễ thấy x∗ = (0, 0, 0, 0) nghiệm tối ưu toàn cục, Λ (x∗ ) = {(λ1 , λ2 , λ3 ) ≥ | λ1 + λ2 + λ3 = 1; 2λ2 = λ3 } đoạn thẳng bị chặn, x∗ thỏa mãn điều kiện SCS, C (x∗ ) = d = (d1 , d2 , d3 , d4 )t |d1 = d4 = Ta thấy λ = (1/4, 1/4, 1/2 ) nhân tử thỏa mãn điều kiện CN2 Một tiêu chuẩn đơn giản cho Λ (x∗ ) trở thành đoạn thẳng bị chặn trình bày bổ đề Bổ đề 2.3 Giả sử x∗ nghiệm tối ưu địa phương (P) thỏa mãn MFCQ số ràng buộc bất đẳng thức hoạt nhiều Khi đó, Λ(x∗ ) đoạn thẳng bị chặn Chứng minh Giả sử px∗ số ràng buộc bất đẳng thức hoạt Nếu px∗ ≤ x∗ thỏa mãn điều kiện LICQ Λ (x∗ ) tập có phần tử Xét px∗ = Khơng tính tổng qt giả sử I (x∗ ) = {1, 2} Giả sử điều kiện sau đúng: 47 (i) tồn λ0 , µ0 ∈ Λ (x∗ ) : λ01 = = λ02 (ii) tất (λ, µ) ∈ Λ (x∗ ) thỏa mãn λi > 0, i = 1, (iii) tất (λ, µ) ∈ Λ (x∗ ) thỏa mãn λ1 = (iv) tất (λ, µ) ∈ Λ (x∗ ) thỏa mãn λ2 = Ta cần chứng minh Λ (x∗ ) tập phần tử Giả sử (i) đúng, đó: q ∗ µ0j ∇hj (x∗ ) = ∇f (x ) + j=1 với (λ, µ) ∈ Λ (x∗ ) ta có q ∗ ∗ ∗ µj ∇hj (x∗ ) = ∇f (x ) + λ1 ∇g1 (x ) + λ2 ∇g2 (x ) + j=1 Trừ theo vế hai phương trình từ Bổ đề 2.1, ta được: λ1 = = λ2 , µ = µ0 Với trường hợp lại ta dùng lập luận tương tự trường hợp (i) Vậy, Λ (x∗ ) khơng phải tập phần tử tồn λ1 , µ1 , λ2 , µ2 ∈ Λ (x∗ ) cho λ11 > 0, λ12 = 0, λ21 = 0, λ22 > 0, (a) ∇f (x∗ ) + λ11 ∇g1 (x∗ ) + (b) ∇f (x∗ ) + λ22 ∇g1 (x∗ ) + q j=1 q µ1j ∇hj (x∗ ) = 0, µ2j ∇hj (x∗ ) = j=1 ∗ Ta có x thỏa mãn điều kiện MFCQ véctơ {∇g1 (x∗ ) , ∇hj (x∗ ) , j = 1, 2, q} độc lập tuyến tính λ1 , µ1 Tương tự, λ2 , µ2 Lấy (λ, µ) ∈ Λ (x∗ ) Khi đó: (c) ∇f (x∗ ) + λ1 ∇g1 (x∗ ) + λ2 ∇g2 (x∗ ) + q j=1 48 µj ∇hj (x∗ ) = Nếu λ1 = λ2 = (λ, µ) = λ1 , µ1 (λ, µ) = λ2 , µ2 Giả sử λ1 > λ2 > Với t = λ1 /λ11 , (c) − t (a), ta có: (d) (1 − t) ∇f (x∗ ) + λ2 ∇g2 (x∗ ) + q µj − tµ1j ∇hj (x∗ ) = j=1 Nếu t = 1, thì: q ∗ µj − µ1j ∇hj (x∗ ) = 0, λ2 ∇g2 (x ) + j=1 λ2 = 0, điều khơng thể Nếu t > 1, ta viết (d) dạng: (e) ∇f (x∗ ) + (λ2 /(1 − t) ) ∇g2 (x∗ ) + q µj − tµ1j /(1 − t) ∇hj (x∗ ) = j=1 λ22 = λ2 /(1 − t) < 0, điều xảy Do đó, < t < 1, λ22 = λ2 /(1 − t), µ2j = µj − tµ1j /(1 − t), λ2 , µ2 = (λ, µ) − t λ1 , µ1 /(1 − t) , (λ, µ) = t λ1 , µ1 + (1 − t) λ2 , µ2 Điều có nghĩa cặp (λ, µ) ∈ Λ (x∗ ) tổ hợp lồi điểm λ1 , µ1 λ2 , µ2 Λ (x∗ ) đoạn thẳng bị chặn Nhận xét 2.5 Ta liệt kê số trường hợp Định lý 2.6 mà không cần giả thiết (ii): (i) Không gian xét R R2 ; xem [1] (ii) Số ràng buộc bất đẳng thức hoạt tối đa 2; xem [1] (iii) Nón tới hạn nằm khơng gian véctơ chiều (sử dụng điều kiện GN2) Nhận xét 2.6 Định lý 2.6 không Λ(x∗ ) không đoạn thẳng bị chặn Thật vậy, xét toán (P) Ví dụ 2.1 Khi 49 đó, x∗ = (0, 0, 0) nghiệm tối ưu toàn cục thỏa mãn điều kiện MFCQ Ta thấy tập nhân tử Lagrange Λ (x∗ ) = λ ∈ R3 |λi ≥ 0, i = 1, 2, 3; λ1 + λ2 + λ3 = không đoạn thẳng Nón tới hạn C (x∗ ) = d = (d1 , d2 , d3 )t |d3 = không gian véctơ Với véctơ tới hạn d1 = (1, 0, 0)t d2 = (0, 1, 0)t , không tồn λ ∈ Λ (x∗ ) cho t d1 ∇2xx L (x∗ , λ) d1 ≥ 2.2.5 t d2 ∇2xx L (x∗ , λ) d2 ≥ Một điều kiện quy Cho x∗ điểm chấp nhận Khơng tính tổng quát, giả sử tồn số nguyên p∗ ≤ p cho gi (x∗ ) = 0, i = 1, 2, , p∗ gi (x∗ ) < 0, i = p∗ + 1, , p Định nghĩa 2.6 Ta nói điểm chấp nhận x∗ thỏa mãn điều kiện hạng (RC) véctơ {∇gi (x∗ ) , i = 1, 2, , p∗ ; ∇hj (x∗ ) , j = 1, 2, , q} có p∗ + q − véctơ độc lập tuyến tính Bổ đề 2.4 Cho x∗ điểm chấp nhận cho (i) Λ (x∗ ) tập khác rỗng, (ii) x∗ thỏa mãn RC Khi đó, Λ (x∗ ) đoạn thẳng đóng 50 Chứng minh Ta cần chứng minh bổ đề trường hợp Λ (x∗ ) tập phần tử p∗ = p Lấy (λ∗ , µ∗ ) ∈ Λ (x∗ ) Khi p ∗ q λ∗i ∇gi (x∗ ) ∇f (x ) + µ∗j ∇hj (x∗ ) = + i=1 j=1 Với (λ, µ) ∈ Λ (x∗ ) khác, ta có: p ∇f (x∗ ) + q λi ∇gi (x∗ ) + i=1 µj ∇hj (x∗ ) = 0; j=1 p q (λi − λ∗i ) ∇gi (x) µj − µ∗j ∇hj (x) = + i=1 (2.19) j=1 Từ (2.19) suy ma trận Jacobian, Dc(x∗ ), ràng buộc hoạt c = (g1 , g2 , , gp , h1 , h2 , , hq ) thỏa mãn Dc(x∗ )t ((λ, µ) − (λ∗ , µ∗ )) = 0; (λ, µ) − (λ∗ , µ∗ ) ∈ Ker Dc(x∗ )t , Dc(x∗ )t ma trận chuyển vị ma trận Dc (x∗ ) Ta có KerDc(x∗ )t = (R (Dc (x∗ )))⊥ , (R (Dc (x∗ )))⊥ không gian trực giao với Dc (x∗ ) Do số chiều R (Dc (x∗ )) p∗ + p − 1, nên (R (Dc (x∗ )))⊥ không gian chiều tồn z ∈ Rp+q , z = cho Ker Dc(x∗ )t = (R (Dc (x∗ )))⊥ = Rz (λ, µ) ∈ Λ (x∗ ) thỏa mãn (λ, µ) − (λ∗ , µ∗ ) ∈ Rz, nên Λ (x∗ ) ⊂ (λ∗ , µ∗ ) + Rz Lấy J = {α ∈ R| (λ∗ , µ∗ ) + αz ∈ Λ (x∗ )} Λ (x∗ ) J tập lồi đóng, nên Λ (x∗ ) = (λ∗ , µ∗ ) + Jz đoạn thẳng đóng 51 Bổ đề 2.5 Cho x∗ điểm chấp nhận toán (P) thỏa mãn: (i) Λ (x∗ ) tập khác rỗng bị chặn , (ii) x∗ thỏa mãn RC; Khi đó, tồn b ≥ 0, z ∈ Rp+q , điểm cực biên (λ∗ , µ∗ ) ∈ Λ (x∗ ) cho Λ (x∗ ) = (λ∗ , µ∗ ) + [0, b] z Chứng minh Λ (x∗ ) tập lồi compact có điểm cực trị (λ∗ , µ∗ ) Từ Bổ đề 2.4 Nhận xét 2.2, ta có: Λ (x∗ ) = (λ∗ , µ∗ ) + [a, b] z với véctơ z ∈ Rp+q với số thực a ≤ b Giả sử a < b, ta cần chứng minh ∈ / ]a, b[ Giả sử phản chứng, với ε ∈ ]0, b[ , ε < −a, ta có: λ1 , µ1 = (λ∗ , µ∗ ) + εz ∈ Λ (x∗ ) ; λ2 , µ2 = (λ∗ , µ∗ ) − εz ∈ Λ (x∗ ) , λ1 , µ1 + λ2 , µ2 (λ , µ ) = , mâu thuẫn với giả thiết (λ∗ , µ∗ ) điểm cực biên Λ (x∗ ) Suy ∗ ∗ 0∈ / ]a, b[ (λ∗ , µ∗ ) ∈ Λ (x∗ ) a = b = Thay z −z, cần thiết, ta giả sử a = Định nghĩa 2.7 Ta nói điểm chấp nhận x∗ thỏa mãn điều kiện bù chặt suy rộng (GSCS) tồn tối đa số i0 ∈ I (x∗ ) cho (λ, µ) ∈ Λ (x∗ ) ⇒ λi0 = Định nghĩa 2.8 Ta nói điểm chấp nhận x∗ thỏa mãn điều kiện MFCQ cải biên (MMF) x∗ thỏa mãn điều kiện RC MFCQ 52 Bây giờ, ta trình bày số tiêu chuẩn để mô tả điều kiện MMF Cho x∗ ∈ X {i1 , i2 } ⊂ I (x∗ ) Khi x∗ điểm chấp nhận toán tối ưu sau: {f (x) |gi (x) ≤ 0, i = i1 , i2 , gi (x) = 0, i ∈ I (x) , i = i1 , i2 , h (x) = 0} (P2) Trong toán (P2), tất bất đẳng thức hoạt (P) trừ i1 i2 , chuyển thành đẳng thức Bổ đề x∗ thỏa mãn điều kiện MMF tồn {i1 , i2 } ⊂ I (x∗ ) cho x∗ thỏa mãn MFCQ cho toán (P2 ) Bổ đề 2.6 Với điểm chấp nhận x∗ có nhiều ràng buộc bất đẳng thức hoạt, điều kiện tương đương: (i) x∗ thỏa mãn điều kiện MMF (ii) Tồn {i1 , i2 } ⊂ I (x∗ ) cho khơng tồn (λ, µ) = thỏa mãn λi1 ≥ 0, λi2 ≥ 0, (2.20) q ∗ µj ∇hj (x∗ ) = λi ∇gi (x ) + i∈I(x∗ ) j=1 (iii) Tồn {i1 , i2 } ⊂ I (x∗ ) cho véctơ ∇gi (x∗ ) , i ∈ I (x∗ ) − {i1 , i2 } , ∇hj (x∗ ) , ∀j, độc lập tuyến tính tồn véctơ d∗ cho ∇gi1 (x∗ )t d∗ < 0, ∇gi2 (x∗ )t d∗ < 0, 53 (2.21) ∇gi1 (x∗ )t d∗ = 0, i ∈ I (x∗ ) − {i1 , i2 } , ∇hj (x∗ )t d∗ = 0, ∀j Chứng minh Trước tiên ta chứng minh (i) kéo theo (ii): Nếu véctơ C = {∇gi (x∗ ) , i ∈ I (x∗ ) , ∇hj (x∗ ) , j = 1, 2, , q} độc lập tuyến tính i1 , i2 ∈ I (x∗ ) thỏa mãn (ii) Giả sử véctơ C khơng độc lập tuyến tính Khi tồn i1 ∈ I (x∗ ) cho q λ∗i ∇gi (x∗ ) + ∇gi1 (x∗ ) = i∈I(x∗ )−{i1 } µ∗j ∇hj (x∗ ) j=1 Nếu với i ∈ I (x∗ ) − i1 thỏa mãn λi ≤ 0, q λ∗i ∇gi (x∗ ) + ∇gi1 (x∗ ) − i∈I(x∗ )−{i1 } µ∗j ∇hj (x∗ ) = j=1 Từ điều kiện MFCQ Bổ đề 2.1, ta có: λ∗i = 0, ∀i ∈ I (x∗ ) ; µ∗j = 0, j = 1, 2, , q, mâu thuẫn với λ∗i1 = Vậy tồn i2 ∈ I (x∗ ) − {i1 }sao cho λ∗i2 > Từ điều kiện RC, ta có véctơ B = {∇gi (x∗ ) , i ∈ I (x∗ ) − {i1 } , ∇hj (x∗ ) , j = 1, 2, , q} độc lập tuyến tính thành phần (λ∗ , µ∗ ) ∇gi1 (x∗ ) tương ứng với B Giả sử (λ, µ) thỏa mãn (2.20) (2.21) Nếu λi1 > 0, −λi2 /λi1 ≤ λ∗i2 > 0; điều không thể, nên λi1 = thành phần khác (λ, µ) triệt tiêu Chứng minh (ii) kéo theo (iii): Theo Bổ đề 2.1,(ii) có nghĩa với toán (P2 ) , x∗ thỏa mãn điều kiện MFCQ, mệnh đề (iii) 54 Bởi vậy, (ii) (iii) tương đương với Để chứng minh (ii) kéo theo (i), ta để ý theo Bổ đề 2.1, với toán (P2 ) , x∗ thỏa mãn điều kiện MFCQ Từ (2.21), véctơ B = {∇gi (x∗ ) , i ∈ I (x∗ ) − {i1 } , ∇hj (x∗ ) , j = 1, 2, , q} độc lập tuyến tính điều kiện RC Sử dụng Định lý 2.6 điều kiện MMF GSCS, ta thu kết mục sau Định lý 2.7 Cho x∗ nghiệm tối ưu địa phương (P) cho điều kiện sau nghiệm (i) x∗ thỏa mãn điều kiện MMF, (ii) x∗ thỏa mãn điều kiện GSCS Khi đó, tồn (λ∗ , µ∗ ) ∈ Λ (x∗ ) cho (d)t ∇2xx L (x∗ , λ∗ , µ∗ ) d ≥ 0, ∀d ∈ C (x∗ ) Hơn nữa, x∗ thỏa mãn điều kiện đủ tối ưu bậc hai SC2, chọn (λ∗ , µ∗ ) cho: dt ∇2xx L(x∗ , λ∗ , µ∗ )d > 0, ∀d ∈ C(x∗ ), d = 55 Kết luận Trong luận văn trình bày cách hệ thống điều kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến với liệu trơn C Chương trình bày số kiến thức chuẩn bị Nội dung chương trình bày số kiến thức giải tích biến phân toán tối ưu phi tuyến Chương trình bày điều kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến với liệu trơn C điều kiện chuẩn hóa ràng buộc Mangasarian-Fromovitz số cải biên 56 Tài liệu tham khảo [1] A Baccari (2004), “On the classical necessary second-order optimality conditions”, J Optim Theory Appl., 123, 213–221 [2] A Baccari, A Trad (2004), “On the classical necessary second-order optimality conditions in the presence of equality and inequality constraints”, SIAM J Optim., 15, 394–408 [3] M S Bazaraa, H D Sherali, C M Shetty (1993), “Nonlinear Programming: Theory and Algorithms”, John Wiley and Sons, New York [4] J F Bonnas, A Shapiro (2000), “Perturbation Analysis of Optimization Problems”, Springer, New York [5] M R Hestenes (1975), “Optimization Theory: The Finite Dimensional Case”, Robert E Krieger Publishing Company, Huntington, New York [6] A Ruszczy´ nski (2006), “Nonlinear Optimization”, Princeton University Press [7] Y Yuan (1990), “On a subproblem of trust-region algorithms for constrained optimization”, Math Program., 47, 53-63 ... 1.3.2 Bài tốn trơn có ràng buộc 22 Điều kiện tối ưu bậc hai cổ điển 2.1 Điều kiện MFCQ điều kiện tối ưu bậc hai cổ điển 28 28 2.2 Điều kiện MFCQ cải biên điều kiện tối ưu bậc hai cổ. .. kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến với liệu trơn C Mục đích nghiên cứu Nghiên cứu điều kiện tối ưu bậc hai cổ điển cho toán tối ưu phi tuyến Nhiệm vụ nghiên cứu Nghiên cứu điều. .. BÙI ANH ĐỨC VỀ ĐIỀU KIỆN TỐI ƯU BẬC HAI CỔ ĐIỂN CỦA CÁC BÀI TỐN TỐI ƯU PHI TUYẾN Chun ngành: Tốn Giải tích Mã số: 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS NGUYỄN VĂN TUYÊN