ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - TRẦN VĂN THIỆN HÀM TOÀN PHƯƠNG LỒI SUY RỘNG VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN - TRẦN VĂN THIỆN HÀM TOÀN PHƯƠNG LỒI SUY RỘNG VÀ ỨNG DỤNG Chuyên ngành: TOÁN GIẢI TÍCH Mã số: 60460102 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN NĂNG TÂM Hà Nội – 2015 Mục lục Một số kí hiệu Kiến thức chuẩn bị 1.1 Không gian Ơclit 1.2 Tập lồi 1.3 Hàm lồi 1.4 Hàm tựa lồi 10 1.5 Hàm giả lồi 14 1.6 Mối quan hệ hàm lồi suy rộng 16 Hàm toàn phương lồi suy rộng 18 2.1 Nhắc lại số định nghĩa 18 2.2 Một số tính chất hàm toàn phương lồi suy rộng 19 2.3 Tiêu chuẩn kiểm tra theo giá trị riêng véctơ riêng 23 2.4 Tiêu chuẩn kiểm tra theo ma trận Hessian tăng cường 32 2.5 Tiêu chuẩn kiểm tra theo định thức biên 33 2.6 Tiêu chuẩn xác định cho oc-tan không âm 34 2.7 Tính giả lồi oc - tan nửa dương oc - tan không âm 51 Ứng dụng vào lý thuyết tối ưu 54 3.1 Ứng dụng vào toán tối ưu với ràng buộc hình học 54 3.2 Ứng dụng vào toán tối ưu có ràng buộc bất đẳng thức 57 Tài liệu tham khảo 64 Bảng kí hiệu R đường thẳng thực Rn không gian Euclid n - chiều R = R ∪ {−∞, +∞} tập số thực suy rộng f :X→R ánh xạ từ X vào R int A phần A A bao đóng A dom(f ) miền hữu hiệu f epi(f ) đồ thị f ϕ (x) đạo hàm ϕ x f (x) gradient f x ϕ (x) đạo hàm bậc hai ϕ x ma trận Hessian f x f (x) tích vô hướng Rn , ||.|| chuẩn không gian Rn |x| trị tuyệt đối số x af f (A) bao lồi affine A coA bao lồi A (x, y) = {λx + (1 − λ)y | λ ∈ (0, 1)} đoạn thẳng mở nối x y (x, y] = {λx + (1 − λ)y | λ ∈ (0, 1]} đoạn thẳng mở nối x y [x, y] = {λx + (1 − λ)y | λ ∈ [0, 1]} đoạn thẳng đóng nối x y L(f, α) = {x ∈ X | f (x) tập mức α} Mở đầu Trong quy hoạch phi tuyến kinh tế lượng, tính tựa lồi giả lồi xem mở rộng quan trọng tính lồi Một trở ngại làm việc với khái niệm lồi suy rộng chúng không dễ kiểm tra Vì vậy, người ta mong muốn đưa tiêu chuẩn thực tiễn để kiểm tra tính lồi suy rộng Luận văn trình bày cách có hệ thống nội dung lớp hàm toàn phương lồi suy rộng số ứng dụng vào lý thuyết tối ưu Luận văn trình bày gồm chương Chương 1: Kiến thức Tác giả trình bày kiến thức tập lồi, hàm lồi, hàm tựa lồi, hàm giả lồi mối quan hệ hàm lồi suy rộng Các kiến thức sử dụng để nghiên cứu vấn đề chương Chương 2: Hàm toàn phương tựa lồi hàm toàn phương giả lồi Nội dung chương tập trung trình bày tiêu chuẩn kiểm tra tính lồi suy rộng hàm toàn phương Các tiêu chuẩn nêu chương gồm: tiêu chuẩn kiểm tra theo giá trị riêng véc tơ riêng, tiêu chuẩn kiểm tra theo ma trận Hessian tăng cường, tiêu chuẩn kiểm tra theo định thức biên, tiêu chuẩn kiểm tra cho Oc-tan không âm xét tính giả lồi hàm toàn phương oc-tan nửa dương oc - tan không âm Chương 3: Ứng dụng vào toán tối ưu Luận văn trình bày ứng dụng hàm toàn phương lồi suy rộng vào nghiên cứu toán tối ưu toàn phương với ràng buộc hình học toán tối ưu với ràng buộc bất đẳng thức Nhân dịp này, tác giả luận văn xin bày tỏ lòng kính trọng biết ơn sâu sắc tới PGS.TS Nguyễn Năng Tâm hướng dẫn tận tình tác giả hoàn thành luận văn Tác giả xin bày tỏ lòng biết ơn chân thành đến thầy phản biện dành thời gian đọc đóng góp nhiều ý kiến quý báu cho tác giả Tác giả xin trân trọng cảm ơn ban lãnh đạo khoa Toán – Cơ – Tin học, khoa Sau đại học thầy cô giáo trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội trang bị kiến thức, tạo điều kiện thuận lợi cho tác giả suốt thời gian tác giả học tập trường Cuối cùng, tác giả xin cảm ơn gia đình, bạn bè đồng nghiệp quan tâm, động viên chia sẻ để tác giả hoàn thành luận văn Hà Nội, ngày 02 tháng 10 năm 2015 Tác giả luận văn Trần Văn Thiện Chương Kiến thức chuẩn bị Chương trình bày số nội dung kiến thức tập lồi, hàm lồi, hàm tựa lồi, hàm giả lồi mối quan hệ hàm lồi suy rộng Những nội dung trình bày chương chủ yếu chọn từ tài liệu Mathematics of Optimization: Smooth and Nonsmooth Case G Giorgi, A Guerraggio and J Thierfelder [17] tài liệu trích dẫn 1.1 Không gian Ơclit Tập hợp Rn := {x = (x1 , , xn ) | x1 , , xn ∈ R} với hai phép toán (x1 , , xn ) + (y1 , , yn ) := (x1 + y1 , , xn + yn ) λ(x1 , , xn ) := (λx1 , , λxn ), λ∈R lập thành không gian véc tơ Ơclit n−chiều Nếu x = (x1 , , xn ) ∈ R xi gọi thành phần tọa độ thứ i x Véc tơ không không gian gọi gốc Rn kí hiệu đơn giản 0, = (0, , 0) Trong Rn ta định nghĩa tích vô hướng tắc , sau: với x = (x1 , , xn ), y = (y1 , , yn ) ∈ Rn , n x, y = xi yi i=1 Khi với x = (x1 , , xn ) ∈ Rn ta định nghĩa n x := (xi )2 x, x = i=1 gọi chuẩn Euclid véc tơ x 1.2 Tập lồi Định nghĩa 1.1 Tập C ⊂ Rn gọi lồi, ∀x, y ∈ C, ∀λ ∈ R : ≤ λ ≤ ⇒ λx + (1 − λ) y ∈ C Mệnh đề 1.2 Cho Cα ⊂ Rn (α ∈ I) tập lồi, với I tập số Khi C = Cα lồi α∈I Mệnh đề 1.3 Cho tập Ci ⊂ Rn lồi, λi ∈ R (i = 1, 2, , m) Khi λ1 C1 + + λm Cm tập lồi Mệnh đề 1.4 Cho tập Ci ⊂ Rni lồi, (i = 1, 2, , m) Khi tích Đề C1 × × Cm tập lồi Rn1 × × Rnm Định nghĩa 1.5 Véc tơ x ∈ Rn gọi tổ hợp lồi véctơ m n x1 , , xm thuộc R , ∃λi ≥ (i = 1, 2, , m) , λi = cho i=1 m x= λ i xi i=1 Định lý 1.6 Cho tập C ⊂ Rn lồi; x1 , , xm ∈ C Khi C chứa tất tổ hợp lồi x1 , , xm Định nghĩa 1.7 Cho C ⊂ Rn Giao tất tập lồi chứa C gọi bao lồi tập C, kí hiệu coC Định nghĩa 1.8 Giả sử C ⊂ Rn Giao tất tập lồi đóng chứa C gọi bao lồi đóng tập C kí hiệu coC Mệnh đề 1.9 Cho C ⊂ Rn lồi Khi đó, i) Phần intC bao đóng C C tập lồi; ii) Nếu x1 ∈ intC, x2 ∈ C, {λx1 + (1 − λ)x2 : < λ ≤ 1} ⊂ intC 1.3 Hàm lồi Định nghĩa 1.10 Cho hàm f : C → R, C ⊂ Rn , tập epi(f ) = {(x, α) ∈ C × R | f (x) ≤ α} , gọi đồ thị f Định nghĩa 1.11 Cho C ⊂ Rn tập lồi, f : C → R Hàm f gọi lồi C đồ thị epi(f ) tập lồi Rn × R Hàm f gọi lõm C −f hàm lồi C Ta nhắc lại số đặc trưng tính chất hàm lồi biến khả vi Định lý 1.12 Cho ϕ : (a, b) → R i) Nếu ϕ khả vi (a, b) ϕ lồi (a, b) ϕ không giảm (a, b) ii) Nếu ϕ có đạo hàm bậc hai (a, b) ϕ lồi (a, b) ϕ (t) với t ∈ (a, b) iii) Nếu ϕ lồi [a, b] ϕ liên tục (a, b) Định lý 1.13 Cho C tập lồi không gian Rn f : C → R Khi đó, điều kiện sau tương đương: a) f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) , ∀λ ∈ [0, 1] , ∀x, y ∈ C b) f (λx + (1 − λ) y) λf (x) + (1 − λ) f (y) , ∀λ > 1, ∀x, y ∈ C cho λx + (1 − λ) y ∈ C c) f (λx + (1 − λ) y) λf (x) + (1 − λ) f (y) , ∀λ < 0, ∀x, y ∈ C cho λx + (1 − λ) y ∈ C d)(Bất đẳng thức Jensen) Với x1 , , xm ∈ C, i = 1, , m với m λi ∈ [0, 1], i = 1, , m, λi = bất đẳng thức sau đúng: i=1 f (λ1 x1 + + λm xm ) ≤ λ1 f (x1 ) + + λm f (xm ) e) Với x ∈ C, với y ∈ Rn , hàm ϕx,y (t) = f (x + ty) hàm lồi đoạn Tx,y = {t ∈ R | x + ty ∈ C} f) Với x, y ∈ C, hàm ψx,y (λ) = f (λx + (1 − λ)y) lồi đoạn [0, 1] g) Trên đồ thị f tập lồi Rn+1 Định lý 1.14 Giả sử C ⊂ Rn tập lồi mở, f : C → R Khi đó, f lồi C với x0 ∈ C, tồn x∗ ∈ Rn cho f (x) − f (x0 ) x∗ (x − x0 ), x ∈ C Định lý 1.15 Cho C ⊂ Rn tập lồi f : C → R Khi đó, f lồi C thì, với α ∈ R tập mức f L(f, α) = {x ∈ C | f (x) ≤ α} tập lồi Ví dụ Xét hàm số f : R → R xác định f (x) = x3 Ta có f không lồi R, L(f, α) = {x ∈ R | x3 ≤ α} = {x ∈ R | x ≤ α1/3 } tập lồi với α ∈ R Định lý 1.16 Cho C ⊂ Rn tập mở f : C → R khả vi C Khi khẳng định sau tương đương: a) f lồi C T x Ax + bT x giả lồi Rn Giả sử + n b = Khi Q(x) giả lồi R+ Định lý 2.55 Cho Q(x) = Chứng minh Từ Định lý 2.19, với (2.31), ta thấy Rn + ⊂ C1 n = {x ∈ R | Q(x) ≤ δ, tT x −tT b > }, λ1 t1 ≥ Ta phải tT x −tT b > , λ1 ∀x ≥ Điều tT b < Vì b ≤ t1 ≥ 0, ta có tT b ≤ Tồn bk = Từ nhận xét 2.33, ta thấy ak = 0, ngược lại ta có bk = Theo Bổ đề 2.52, ak = suy t1,k = Vì vậy, tT b ≤ t1,k bk < Cả hai Định lý 2.53 2.55 hữu dụng quy hoạch toàn phương điều kiện đảm bảo tính giả lồi oc - tan không âm (có thể bao gồm giá trị 0) Kết luận Trong chương luận văn trình bày tiêu chuẩn xác định tính lồi suy rộng hàm toàn phương Các tiêu chuẩn nêu là: tiêu chuẩn kiểm tra theo giá trị riêng, véc tơ riêng; tiêu chuẩn kiểm tra theo ma trận Hessian tăng cường; tiêu chuẩn kiểm tra theo định thức biên; tiêu chuẩn xác định cho oc - tan không âm Đồng thời nghiên cứu tính giả lồi hàm toàn phương oc - tan nửa dương oc - tan không âm 53 Chương Ứng dụng vào lý thuyết tối ưu Trong mục trình bày vài ứng dụng hàm toàn phương lồi suy rộng vào toán tối ưu toàn phương Những nội dung mục cải biến từ kết cho hàm lồi suy rộng tài liệu Mathematics of Optimization: Smooth and Nonsmooth Case G Giorgi, A Guerraggio and J Thierfelder [17] Shuzhong Zhang, (1998), On Extensions of the Frank-Wolfe Theorems, Econometric Institute, Erasmus University Rotterdam, The Netherlands [37] 3.1 Ứng dụng vào toán tối ưu với ràng buộc hình học Xét toán tối ưu toàn phương {Q (x) | x ∈ C} , (QP1 ) C ⊂ Rn tập lồi Q : Rn → R hàm toàn phương Định lý 3.1 Giả sử Q tựa lồi chặt C Khi đó, x0 nghiệm cực tiểu địa phương (QP1 ) x0 nghiệm cực tiểu địa phương nghiệm cực tiểu toàn cục toán (QP1 ) Chứng minh 54 Giả sử x0 x1 hai nghiệm cực tiểu địa phương khác (QP1 ) Q(x0 ) ≤ Q(x1 ) Khi đó, Q(x) tựa lồi chặt C nên ta có Q(tx0 + (1 − t)x1 ) < Q(x1 ) với t ∈ (0, 1) x1 nghiệm địa phương Như có nhiều nghiệm cực tiểu địa phương Vì x0 nghiệm địa phương nên tồn ε > cho Q(x0 ) ≤ Q(x) với x ∈ B(x0 , ε), B(x0 , ε) cầu mở tâm x0 , bán kính ε Giả sử tồn x2 ∈ Q, không thuộc B(x0 , ε), cho Q(x2 ) < Q(x0 ) Vì Q tựa lồi chặt, ta có Q(tx2 + (1 − t)x0 ) < Q(x0 ), Nhưng, với λ < δ x2 −x0 ∀t ∈ (0, 1) (3.1) ta có tx2 + (1 − t)x0 ∈ C ∩ B(x0 , ε) Q(x0 ) ≤ Q(λx2 + (1 − t)x0 ) với < t < δ x2 −x0 , mâu thuẫn với (3.1) Vậy x0 nghiệm toàn cục Định lý 3.2 Giả sử Q tựa lồi C Khi đó, x0 nghiệm cực tiểu địa phương chặt (QP1 ) x0 nghiệm cực tiểu toàn cục toán (QP1 ) Chứng minh Giả sử x0 nghiệm cực tiểu địa phương chặt (QP1 ), nghĩa tồn lân cận mở U x0 Rn cho với x ∈ U ∩ C, x = x0 ta có Q(x0 ) < Q(x) Giả sử x0 cực tiểu toàn cục Khi tồn x ∈ C, x = x0 cho Q(x) ≤ Q(x0 ) Vì Q tựa lồi, ta có Q(tx + (1 − t)x0 ) ≤ Q(x0 ), ∀t ∈ [0, 1] Thế nhưng, với t đủ nhỏ ta có tx + (1 − t)x0 ∈ U ∩ C, mâu thuẫn với điều x0 nghiệm địa phương chặt Định lý 3.3 Giả sử Q giả lồi tập mở D C ⊂ D Khi đó,x0 nghiệm cực tiểu địa phương chặt (QP1 ) (x − x0 ), Q(x0 ) 55 0, ∀x ∈ C Chứng minh Nếu x0 nghiệm (QP1 ) hàm ϕ(t) = Q(x0 +λ(x−x0 )) đạt cực tiểu đoạn [0, 1] t = (x − x0 ), Q(x0 ) = ϕ (0) Điều ngược lại suy trực tiếp từ định nghĩa hàm giả lồi Hệ 3.4 Nếu Q hàm giả lồi tập lồi mở C x0 nghiệm (QP1 ) Q(x0 ) = Giả sử rằng, Q khả vi tập mở D chứa C Kí hiệu tập nghiệm (QP1 ) Sol(QP1 ) Định lý 3.5 a) Nếu Q tựa lồi C Sol(QP1 ) tập lồi b) Nếu Q giả lồi chặt tựa lồi chặt C Sol(QP1 ) chứa nhiều phần tử, nghĩa là: x0 ∈ Sol(QP1 ) =⇒ Sol(QP1 ) = {x0 } Nói cách khác, Sol(QP1 ) = ∅ có phần tử Chứng minh a) Với α∗ = min{Q(x) | x ∈ C}, ta có Sol(QP1 ) = L(Q, α∗ ) Vì Q tựa lồi nên L(Q, α∗ ) lồi Sol(QP1 ) lồi b) Với hàm Q giả lồi chặt tựa lồi chặt C kết suy từ định lý 3.1 Hệ 3.6 Nếu Q hàm giả lồi chặt tập lồi mở C ta có: Sol(QP1 ) = {x0 } Q(x0 ) = Định nghĩa 3.7 Cho C ⊂ Rn Ta nói điểm x0 nghiệm cực tiểu toàn cục theo tia toán (QP1 ) với y ∈ Rn t 0, x0 điểm cực tiểu toàn cục (nhỏ nhất) Q tập Q ∩ {x ∈ Rn | x = x0 + ty, t 0} Định nghĩa 3.8 Cho C ⊂ Rn Ta nói điểm x0 nghiệm cực tiểu địa phương theo tia toán (QP1 ) với y ∈ Rn tồn t0 (y) cho Q(x0 ) điểm cực tiểu toàn cục (nhỏ nhất) Q tập C ∩ {x ∈ Rn | x = x0 + ty, t ∈ (0, t0 (y))} Lưu ý rằng, điểm cực tiểu địa phương theo tia không thiết phải điểm cực tiểu địa phương Ví dụ tiếng sau G Peano: Hàm 56 f : R2 → R, f (x, y) = (y − x2 )(y − 2x2 ), có điểm địa phương theo tia x0 − (0, 0), x0 = (0, 0) điểm cực tiểu địa phương Tuy nhiên, ta có Định lý 3.9 Xét toán (QP1 ) Nếu Q hàm tựa lồi C nghiệm cực tiểu địa phương theo tia nghiệm cực tiểu địa phương Chứng minh Xem [36] Định lý 3.10 Xét toán (QP1 ) Nếu Q hàm tựa lồi nửa chặt C x0 nghiệm cực tiểu toàn cục x0 nghiệm cực tiểu địa phương theo tia Chứng minh Xem [36] 3.2 Ứng dụng vào toán tối ưu có ràng buộc bất đẳng thức Bây ta xét toán quy hoạch toàn phương {Q (x) | x ∈ C, Qi (x) + αi 0, i = 1, , m} , (QP2 ) C ⊂ Rn tập lồi Q, Qi : Rn → R, i = 1, , m, hàm toàn phương Kí hiệu x∗ nghiệm (QP2 ), đặt I(x∗ ) = {i | Qi (x∗ ) + αi = 0} gọi tập số ràng buộc hoạt x∗ Định lý 3.11 Giả sử hàm Q (QP2 ) hàm tựa lồi chặt C, với i ∈ I(x∗ ) hàm Qi tựa lồi C Khi / min{Q(x) | x ∈ C, Qi (x) + αi x 0, i ∈ I(x∗ )} = Q(x∗ ) Chứng minh Giả sử phản chứng rằng, tồn x0 ∈ C cho Qi (x0 )+αi ≤ với i ∈ I(x∗ ) Q(x0 ) < Q(x∗ ) Khi đó, với t ∈ (0, 1) ta có 57 xt = tx0 + (1 − t)x∗ ∈ t Q(xt ) < Q(x∗ ), Qi (xt ) + αi ≤ max{Qi (x0 ) + αi , Qi (x∗ ) + αi }, ∀i ∈ I(x∗ ) (3.2) Với i ∈ I(x∗ ), Qi (x∗ ) + αi < và, Qi liên tục x∗ , ta có / Qi (xt ) + αi < với t đủ nhỏ Do đó, xt thỏa mãn điều kiện ràng buộc toán (QP2 ) (3.2) mâu thuẫn với x∗ nghiệm tối ưu Bây ta xét toán sau đây: (QP3 ) : cực tiểu với điều kiện Q0 (x) = xT A0 x + bT x Qi (x) = xT Ai x + bT x + ci i Ax b, 0, i = 1, 2, , l + Q0 (x) hàm toàn phương tựa lồi tập đa diện {x ∈ Rn | Ax b} tất hàm toàn phương ràng buộc Qi (x) lồi (i = 1, 2, , m) Chú ý rằng, toán (QP3 ) có ràng buộc đa diện Ta có kết sau: Định lý 3.12 (Lou-Zhang) Giả sử (QP3 ) có tập chấp nhận khác rỗng hàm mục tiêu bị chặn tập chấp nhận Hơn nữa, giả sử hàm mục tiêu Q0 (x) tựa lồi tập đa diện {x : Ax ≤ b} Khi đó, tập nghiệm tối ưu (QP3 ) khác rỗng Chứng minh Chúng ta sử dụng phép quy nạp theo m (m số ràng buộc dạng toàn phương) Nếu m = định lý Giả sử định lý với m l Hơn nữa, Q0 (x) hàm tựa lồi, không tính tổng quát giả sử rằng: Q0 (x) = −x2 + x2 + + x2 r Ax b ⇒ Q0 (x) 58 0, x1 Bây ta xét trường hợp m = l + Ta xây dựng dãy toán chặt sau: cực tiểu Q0 (x) = xT A0 x + bT x với điều kiện Qi (x) = xT Ai x + bT x + ci i Ax b, (QP3 )k x 0, i = 1, 2, , l + k, k = 1, 2, Với (QP3 )k tồn nghiệm tối ưu tính compact miền chấp nhận Giả sử, kí hiệu xk nghiệm có chuẩn cực tiểu (QP3 )k Chắc chắn, dãy xk : k = 1, 2, bị chặn định lý Không tính tổng quát, ta giả sử xk lim k→∞ xk xk → ∞ = u, với vài u có ||u|| = Từ Q0 (xk ) : k = 1, 2, dãy đơn điệu giảm Qi (x) hàm toàn phương lồi với i = 1, 2, , l + cho ta kết quả: uT A0 u =0 uT Ai u =0, i = 1, 2, , l + bT i Au 0, i = 1, 2, , l + Bây giờ,chúng ta xét riêng hai trường hợp Trường hợp : Tồn j ∈ {1, 2, , l + 1} cho bT u < Không j tính tổng quát, ta giả sử j = l + Trong trường hợp ta xét cực tiểu Q0 (x) = xT A0 x + b0 x với điều kiện: Qi (x) = xT Ai x + bT x + ci i Ax b, (QP3 )k : 0, i = 1, 2, , l + Có hai khả với toán cực tiểu hóa trên: vừa không bị chặn đạt nghiệm cực tiểu giả thiết quy nạp 59 Trong hai tình huống, tính liên tục Q0 (x) tồn nghiệm x cho Q0 (x ) = inf Q0 xk k≥1 Qi (x ) 0, i = 1, 2, , l Ax Nếu Ql+1 (x ) b x nghiệm tối ưu (QP3 ) định lí chứng minh Bây ta xét khả khác, ví dụ Ql+1 (x ) > Nhớ lại Q0 (xk ) → Q0 (x ) Q0 (x) hàm tựa lồi miền Chúng ta đòi hỏi uT Q0 (x ) Để thấy điều ta nhớ lại kết r r x1 (xi ) 2 , xk xk , ∀k i i=2 i=2 Từ định nghĩa Q0 (x) có r T ( Q0 (x )) (x − x ) = − 2x1 xk xi xk − 2Q0 (x ) i +2 i=2 r − 2x1 xk r (xi ) +2 xk i i=2 r −2 (xi ) (xk i=2 (xi )2 i=2 r = xk ) − 2Q0 (x ) i − i=2 r − 2Q0 (x ) i=2 r 2 xk + Q0 (xk ) − 2Q0 (x ) xk i i=2 Chia hai vế cho xk − x cho k → ∞ có T lim sup ( Q0 (x )) k→∞ 60 xk − x xk − x ≤0 l+1 Bây định nghĩa vô hướng dương t∗ := − QQT (x ) u l+1 đặt x (t∗ ) := x + t∗ u Rõ ràng, T Ql+1 (x (t∗ )) =Ql+1 (x ) + t∗ ( Ql+1 (x )) u =Ql+1 (x ) + t∗ bT u l+1 =0, Ở ta sử dụng Al+1 u = định nghĩa t∗ Sử dụng kết ta có: T Qi (x (t∗ )) =Qi (x ) + t∗ ( Qi (x )) u =Qi (x ) + t∗ bT u i Qi (x ) với i = 1, 2, , l Cuối ta có Q0 (x (t∗ )) = Q0 (x ) + t∗ uT Q0 (x ) ≤ Q0 (x ) = inf ((QP3 )) Từ kết luận ta kết luận x (t∗ ) nghiệm tối ưu (QP3 ) Trường hợp : bT u = với i = 1, 2, , l + Trong trường hợp i biết u −u phương chấp nhận cho toán (QP3 ) Với k cố định bất kỳ, từ Q0 (xp ) < Q0 (xk ) với p > k từ tính tựa lồi Q0 (x) suy xp − xk T Q0 xk ≤ 0, ∀p > k Chia hai vế hai vế cho ||xp | | cho p → ∞ ta có: uT Q0 xk ≤ Vì u phương chấp nhận (QP3 ) bị chặn dưới, ta kết luận uT Q0 xk = 0, ∀k = 1, 2, 61 Bây giờ, u = lim k→∞ xk xk , ta suy với k đủ lớn ta có uT xk > 0, ta có kéo theo (Au)i < ⇒ (Axk − b)i < với i Điều có nghĩa là, tồn ε0 > cho với < ε ε0 , xk (ε) := xk − εu nghiệm chấp nhận với (QP3 ) (QP3 )k Do ta có Q0 (xk (ε)) = Q0 (xk ) với < ε ε0 Tuy nhiên, xk (ε) = xk − 2ε uT xk + ε2 ta chọn ε > đủ nhỏ cho: xk (ε) < xk Điều mâu thuẫn với xk nghiệm có chuẩn cực tiểu Do trường hợp hai không xảy Kết luận Trong chương 3, tác giả trình bày ứng dụng hàm toàn phương lồi suy rộng vào nghiên cứu toán tối ưu toàn phương với ràng buộc hình học toán tối ưu với ràng buộc bất đẳng thức 62 Kết luận Luận văn trình bày cách có hệ thống nội dung sau: Một số khái niệm tính chất hàm lồi hàm lồi suy rộng Một số tính chất hàm toàn phương lồi suy rộng, số tiêu chuẩn để kiểm tra tính lồi suy rộng hàm toàn phương Ứng dụng tính lồi suy rộng vào nghiên cứu toán tối ưu toàn phương với ràng buộc hình học ràng buộc bất đẳng thức Vì khả điều kiện có hạn, luận văn chắn tránh thiếu sót Kính mong thầy cô đồng nghiệp góp ý kiến để có điều kiện chỉnh sửa luận văn tốt 63 Tài liệu tham khảo [1] Arrow, K J., and Enthoven, A D.(1961), "Quasiconcave Programming, Econometrica",29, pp 779-800 [2] Avriel, L.(1976), "Nonlinear Programming: Analysis and Methods", Prentice-Hall, Englewood Cliffs, New Jersey [3] Avriel, M., and Schaible, S.(1981), Second-Order Criteria for Pseudoconvex Functions, General Inequalities, Vol 1, pp 231-232, Edited by E F Beckenbach, Birkhauser-Verlag, Basel, Switzerland [4] Avriel, M., and Schaible, S.(1978), "Second-Order Characterizations of Pseudoconvex Functions", Mathematical Programming, Vol 14, pp 170-185 [5] Cottle, R W.(1967), "On the Convexity of Quadratic Forms over Convex Sets", Operations Research, Vol 15, pp 170-172 [6] Cottle, R W., and Ferland, J A.(1971), "On Pseudoconvex Functions of Non-negative Variables", Mathematical Programming, Vol 1, pp 95-101 [7] Cottle, R W., and Ferland, J A.(1972), "Matrix-Theoretic Criteria for the Quasiconvexity and Pseudoconvexity of Quadratic Functions",Linear Algebra and Its Applications, Vol 5, pp 123-136 [8] Cottle, R W.(1974), "Manifestations of the Schur Complement", Linear Algebra and Its Applications, Vol 8, pp 189-211 64 [9] Crouzeix, J P.(1980), "Conditions for Convexity of Quasiconvex Functions",Mathe-matics of Operations Research, Vol pp 120-125 [10] J P Crouzeix and J A Ferland (1982), "Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons", Math Programming, 23, 193-201 [11] W E Diewert, M Avriel and I Zang (1981), Nine kinds of quasi concave and concave, J Econ.Theory 25, 397-420 [12] Ferland, J A.(1971), "Quasi-Convex and Pseudo-Convex Functions on Solid Convex Sets",Stanford University, Operations Research House, Technical Report No 71-4 [13] Ferland, J A.(1972), "Maximal Domains of Quasi-Convexity and Pseudo-Convexity for Quadratic Functions",Mathematical Programming, Vol 3, pp 178-192 [14] Gantmacher, F R.(1959), The Theory of Matrices, Vol 1, Chelsea Publishing Company, New York [15] Gantmacher, F R.(1959), The Theory of Matrices, Vol 2, Chelsea Publishing Company, New York [16] Greenberg, H J., and Pierskalla, W P.(1971), "A Review of Quasiconvex Functions",Operations Research, Vol 19, pp 1553 – 1570 [17] G Giorgi, A Guerraggio and J Thierfelder (2004), Mathematics of Optimization: Smooth and Nonsmooth Case ,Elsevier B.V Amsterdam The Netherlands [18] Jacobson, D H.(1976), "A Generalization of Finslers Theorem for Quadratic Inequalities and Equalities", Quaestiones Mathematicae, Vol 1, pp 19-28 [19] S Karamadian (1967),Strictly quasi convex (concave) functions and duality in mathematical programming, J Math Anal Appl., 20, 344358 65 [20] D G Luenberger (1968), Quasiconvex programming, SIAM J Appl Math., 16, 1090-1095 [21] Mangasarian, O L.(1965), "Pseudo-Convex Functions", SIAM Journal on Control, Vol 3, pp 281-290 [22] Mangasarian, O L.(1969), Nonlinear Programming, McGraw-Hill Book Company, New York, New York [23] Martos, B.(1969), Subdefinite Matrices and Quadratic Forms, SIAM Journal on Applied Mathematics, Vol 17, pp 1215-1223 [24] Martos, B.(1971), Quadratic Programming with a Quasiconvex Objective Function, Operations Research, Vol 19, pp 82-97 [25] Martos, B., Nonlinear Programming: Theory and Methods, NorthHolland Publishing Company, Amsterdam, Holland, 1975 [26] K Otani (1983), A characterization of quasi convex functions, J Eco Theory 31, 194-196 [27] Ponstein, J.(1967), Seven Kinds of Convexity, SIMA Review, Vol 9, pp 115-119 [28] Schaible, S., J A Ferland (1971), Private Communication [29] Schaible, S.(1971), Beitrage zur Quasikonvexen Programmierung, Universitat Koln, Doctoral Dissertation [30] Schaible, S.(1972), Quasiconvex Optimization in Real Linear Space, Zeitschrift fur Operations Research, Vol 16, pp 205-213 [31] Schaible, S.(1973), Quasi-Concave, Strictly Quasi-Concave, and Pseudo-Concave Functions, Methods of Operation Research, Vol 17, pp 308-316 [32] Schaible, S.(1973), "Quasiconvexity and Pseudoconvexity of Cubic Functions", Mathematical Programming, Vol 5, pp 243-247 66 [33] Schaible, S.(1977), "Second-Order Characterizations of Pseudoconvex Quadratic Functions", Jounal of Optimization Theory and Applications, Vol 21, pp 15-26 [34] Schaible, S.(1977), "Generalized Convexity of Quadratic Functions",Generalized Concavity in Optimization and Economics ions, Vol 21, pp 15-26 [35] Schaible, S., and Cottle, R W.(1980), On Pseudoconvex Quadratic Forms, General Inequalities, Vol 2, pp 81-88, Edited by E F Beckenbach, Birk-hauser-Veriag, Basel, Switzerland [36] Schaible, S.(1981), Quasiconvex, Pseudoconvex and Strictly Pseudoconvex Quadratic Functions Vol 35 [37] Shuzhong Zhang, (1998), On Extensions of the Frank-Wolfe Theorems, Econometric Institute, Erasmus University Rotterdam, The Netherlands [38] W A Thompson and D W Parke (1973), Some properties of generalized concave functions, Operation Research, 21, 305-313 67