Tài liệu Dưới vi phân dưới của hàm toàn phương và ứng dụng

LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Thầy đã hướng dẫn và truyền đạt cho tác giả những kinh nghiệm quý báu trong học tập cũng như trong nghiên cứu khoa học. Thầy luôn động viên, khích lệ tác giả vươn lên trong học tập, tự tin vượt qua khó khăn trong việc nghiên cứu và hoàn thiện luận văn. Tác giả xin bày tỏ lòng biết ơn lớn lao, lòng kính trọng sâu sắc nhất đối với Thầy. Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường và các thầy cô giáo dạy cao học chuyên ngành Toán giải tích đã giúp đỡ, tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập. Tác giả xin chân thành cảm ơn Ban lãnh đạo tỉnh Lào Cai, Sở GD-ĐT tỉnh Lào Cai, Ban giám hiệu, các thầy cô giáo, đồng nghiệp trường Trung học phổ thông số III Bảo Yên cùng gia đình, người thân, bạn bè đã giúp đỡ, động viên và tạo điều kiện thuận lợi để tác giả hoàn thành khóa học Thạc sĩ và hoàn thành luận văn này. Hà Nội, tháng 12 năm 2013 Tác giả Phạm Trọng Dần LỜI CAM ĐOAN Luận văn được hoàn thành tại trường Đại Học Sư phạm Hà Nội 2 dưới sự hướng dẫn của PGS. TS Nguyễn Năng Tâm. Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi. Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 12 năm 2013 Tác giả Phạm Trọng Dần Mục lục Lời cảm ơn i Lời cam đoan ii Bảng ký hiệu v Mở đầu 1 1 KIẾN THỨC CHUẨN BỊ 3 1.1. Không gian Euclid Rn . . . . . . . . . . . . . . . . . . . 3 1.1.1. Tích vô hướng và chuẩn . . . . . . . . . . . . . . 4 1.1.2. Tập đóng và tập mở . . . . . . . . . . . . . . . . 4 1.1.3. Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . 5 1.1.4. Tập bị chặn, tập compact . . . . . . . . . . . . . 5 Tập lồi, hàm lồi, hàm lồi suy rộng . . . . . . . . . . . . 6 1.2.1. Tập lồi - tập affine . . . . . . . . . . . . . . . . . 6 1.2.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3. Hàm lồi suy rộng . . . . . . . . . . . . . . . . . . 7 1.3. Không gian tôpô lồi địa phương . . . . . . . . . . . . . . 9 1.3.1. Không gian tôpô . . . . . . . . . . . . . . . . . . 9 1.2. iii 1.3.2. Không gian tôpô tuyến tính . . . . . . . . . . . . 10 1.3.3. Không gian tôpô lồi địa phương . . . . . . . . . . 11 1.3.4. Nón lồi và nón lùi xa của tập lồi . . . . . . . . . . 12 Hàm Lipschitz . . . . . . . . . . . . . . . . . . . . . . . 13 1.5. Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6. 14 1.4. Hàm toàn phương và bài toán quy hoạch toàn phương . 1.6.1. Hàm toàn phương . . . . . . . . . . . . . . . . . 14 1.6.2. Bài toán quy hoạch toàn phương . . . . . . . . . 16 2 DƯỚI VI PHÂN DƯỚI CỦA HÀM TOÀN PHƯƠNG 18 2.1. Khái niệm dưới vi phân dưới . . . . . . . . . . . . . . . . 18 2.2. Dưới vi phân dưới bị chặn của hàm toàn phương . . . . . 19 2.3. Dưới vi phân dưới của hàm toàn phương . . . . . . . . . 30 3 ỨNG DỤNG CỦA DƯỚI VI PHÂN DƯỚI VÀO BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG 46 3.1. Bài toán tối ưu toàn phương . . . . . . . . . . . . . . . . 46 3.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 47 3.3. Thuật toán tìm nghiệm . . . . . . . . . . . . . . . . . . . 48 Kết luận 51 Tài liệu tham khảo 52 iv BẢNG KÝ HIỆU R Tập số thực R R ∪ (−∞; +∞) Rn Không gian Euclide n - chiều Rs n×n Tập các ma trận thực đối xứng n × n Rm×n Tập các ma trận thực m × n hx; yi Tích vô hướng của x và y kxk Chuẩn của x
B x0 ; ε Hình cầu mở tâm x0 bán kính ε intK Phần trong của tập K K Bao đóng của tập K af f K Bao afine của tập K coK Bao lồi của tập K O+D Nón lùi xa của tập D N Hằng số Lipschitz ΠH Phép chiếu lên siêu phẳng H Q(x) = 12 xT Ax + bT x Hàm toàn phương ∇Q(x0 ) Đạo hàm của Q(x) tại x0 ∂ − f (x) Dưới vi phân dưới của f tại x  Kết thúc chứng minh 1. Lý do chọn đề tài Khái niệm dưới vi phân dưới được giới thiệu bởi Plastria [10] xem như một sự nới lỏng khái niệm dưới vi phân trong giải tích lồi. Động cơ thúc đẩy việc đưa ra khái niệm mới này là thuật toán, từ khi Plastria chứng minh rằng, phương pháp mặt phẳng cắt cổ điển của Kelley cũng dùng được cho bài toán tối ưu lồi, dưới một số giả thiết thích hợp sử dụng dưới gradient dưới để sinh ra những mặt phẳng cắt. Plastria cũng lưu ý rằng, tính dưới khả vi dưới của hàm số suy ra tính tựa lồi. Sau đó mối liên quan giữa khái niệm dưới vi phân dưới với một số khái niệm khác đã được nghiên cứu bởi Greenberg và Pierskalla [4]. Một số kết quả của dưới vi phân dưới của hàm số được định nghĩa trong không gian lồi và được ứng dụng vào các bài toán trong lĩnh vực quy hoạch phân thức. Tính tựa lồi của hàm toàn phương được nghiên cứu bởi một số tác giả [3]. Động cơ thúc đẩy họ là sự tin tưởng khái niệm dưới vi phân dưới là điều kiện chắc chắn thích hợp mà ta đặt cho hàm tựa lồi để tạo nên một lý thuyết, ở một mức độ nào đó, song song với giải tích lồi. Sau khi học được các kiến thức về Toán giải tích, với mong muốn tìm hiểu sâu hơn về các kiến thức đã học, mối quan hệ và ứng dụng của chúng. Tôi đã chọn đề tài nghiên cứu: “ Dưới vi phân dưới của hàm toàn phương và ứng dụng ”. 2. Mục đích nghiên cứu Để hiểu sâu hơn về những kiến thức đã học, mối quan hệ và ứng dụng của chúng. Đồng thời thu nhận được kiến thức về dưới vi phân dưới của hàm toàn phương và ứng dụng. 2 3. Nhiệm vụ nghiên cứu Dưới vi phân dưới của hàm toàn phương và ứng dụng. 4. Đối tượng và phạm vi nghiên cứu Hàm toàn phương, dưới vi phân dưới của hàm toàn phương và bài toán tối ưu với hàm mục tiêu là hàm toàn phương. 5. Phương pháp nghiên cứu Nghiên cứu lý thuyết: Thu thập tài liệu, đọc và phân tích, tổng hợp để được một nghiên cứu tổng quan về dưới vi phân dưới của hàm toàn phương và bài toán tối ưu với hàm mục tiêu là hàm toàn phương. 6. Dự kiến đóng góp mới Một tổng quan về dưới vi phân dưới của hàm toàn phương và ứng dụng. Chương 1 KIẾN THỨC CHUẨN BỊ Chương này trình bày những khái niệm cơ bản dùng trong không gian Euclid Rn và một số kiến thức có liên quan khác, xem như là công cụ sẽ dùng đến trong các chương sau. Những điều không chứng minh sẽ được tìm thấy trong [1] [2]. 1.1. Không gian Euclid Rn Tập hợp n o T R = x = (x1 , x2 , ..., xn ) | x1 , x2 , ..., xn ∈ R n trong đó x = (x1 , x2 , ..., xn )T với hai phép toán (x1 , ..., xn )T + (y1 , ..., yn )T = (x1 + y1 , ..., xn + yn )T λ(x1 , ..., xn )T = (λx1 , ..., λxn )T , λ ∈ R lập thành một không gian véc tơ thực n - chiều. Nếu x = (x1 , ..., xn )T ∈ Rn thì xi gọi là thành phần tọa độ thứ i của x. Véc tơ không của không gian này gọi là gốc của Rn và được kí hiệu là 0, vậy 0 = (0, ..., 0)T . 3 4 Ta gọi hệ e1 = (1, 0, ..., 0)T ; e2 = (0, 1, 0, ..., 0)T ; ...; en = (0, ..., 0, 1)T là cơ sở chính tắc của không gian Rn . 1.1.1. Tích vô hướng và chuẩn Trong không gian Rn ta định nghĩa tích vô hướng chính tắc h., .i như sau: với x = (x1 , ..., xn )T , y = (y1 , ..., yn )T ∈ Rn , hx, yi = n X xi yi i=1 Khi đó với mọi x = x1 , ..., xn )T ∈ Rn ta định nghĩa v u n p uX kxk = hx, xi = t x2i i=1 và gọi là chuẩn Euclid của véc tơ x. 1.1.2. Tập đóng và tập mở Định nghĩa 1.1.1. Cho x0 ∈ Rn ,ε > 0 ,ta gọi tập  B(x0 , ε) = x ∈ Rn | x − x0 < ε là hình cầu mở trong Rn có tâm tại x0 , bán kính ε. Định nghĩa 1.1.2. Tập K ⊂ Rn được gọi là tập mở nếu với mọi x0 ∈ U tồn tại ε > 0 sao cho B(x0 , ε) ⊂ K. Tập L ⊂ Rn gọi là tập đóng nếu tập Rn \L là tập mở. Định nghĩa 1.1.3. Cho K là tập con bất kì trong Rn . Kí hiệu {Ui (K)}i∈I là họ tất cả các tập mở chứa trong K. {Fj (K)}j∈J là họ tất cả các tập đóng chứa trong K. Ta có U = ∪ Ui (K) là tập mở và F = ∩ Fj (K) là i∈I j∈J tập đóng. Tập U gọi là phần trong của K và kí hiệu: intK. Tập F gọi là bao đóng của K và kí hiệu: K 5 Ta có một số kết quả: (i) K là tập mở khi và chỉ khi K = intK. (ii) K là tập đóng khi và chỉ khi K = K. 1.1.3. Sự hội tụ  Định nghĩa 1.1.4. Dãy điểm xk trong Rn gọi là hội tụ đến x0 ∈ Rn khi k → ∞ nếu dãy số xk − x0 hội tụ tới 0 ∈ R khi k → ∞. Khi đó  ta gọi x0 là giới hạn của dãy xk và kí hiệu xk → x0 . Ta nói x ∈ Rn tiến đến x0 ∈ Rn . Kí hiệu x → x0 nếu x − x0 → 0. Dễ dàng chứng minh được tính chất sau: Tập A ⊂ Rn được gọi là  tập đóng khi và chỉ khi với mọi dãy xk ⊂ A mà xk hội tụ đến x0 thì x0 ∈ A. 1.1.4. Tập bị chặn, tập compact Định nghĩa 1.1.5. Tập K trong Rn được gọi là tập bị chặn nếu tồn tại m > 0 sao cho kxk < m với mọi x ∈ K. Định nghĩa 1.1.6. Tập K trong Rn được gọi là tập compact nếu mọi   dãy xk trong K đều có dãy con xkm hội tụ đến một điểm x∗ ∈ K. Định lý 1.1.1. Tập K ⊂ Rn compact khi và chỉ khi K là tập đóng và bị chặn. 6 1.2. Tập lồi, hàm lồi, hàm lồi suy rộng 1.2.1. Tập lồi - tập affine Định nghĩa 1.2.1. Cho X là không gian véc tơ. Tập M ⊂ X được gọi là đa tạp affine (tập affine) nếu với ∀x, y ∈ M , λ ∈ R ta có: λx + (1 − λ) y ∈ M Nếu K ⊂ X bất kì. Ta gọi bao affine của K, kí hiệu: af f K, là giao của tất cả các tập affine chứa K. Định nghĩa 1.2.2. Tập K ⊂ Rn được gọi là lồi nếu λx + (1 − λ) y ∈ K ∀x, y ∈ K, ∀λ ∈ [0; 1] Giả sử X ⊂ Rn . Giao của tất cả các tập lồi trong Rn chứa X được gọi là bao lồi của tập X, kí hiệu là coX. Theo định nghĩa tập rỗng được xem là tập lồi. Ví dụ 1.2.1. Các tam giác và hình tròn trong mặt phẳng là tập lồi. Hình cầu đơn vị trong không gian Rn là tập lồi. 1.2.2. Hàm lồi Định nghĩa 1.2.3. Cho K ⊂ Rn là một tập lồi và f : K → R là một hàm số. Hàm f được gọi là hàm lồi trên K nếu với mọi x, y ∈ K và với mọi t ∈ [0, 1] ta có: f (tx + (1 − t)y ≤ tf (x) + (1 − t)f (y) Hàm f được gọi là hàm lồi chặt trên K nếu với mọi x, y ∈ K và với mọi t ∈ [0, 1] ta có: f (tx + (1 − t)y < tf (x) + (1 − t)f (y) 7 Hàm f được gọi là hàm lõm trên K nếu với mọi x, y ∈ K và với mọi t ∈ [0, 1] ta có: f (tx + (1 − t)y ≥ tf (x) + (1 − t)f (y) Dễ nhận thấy, f là hàm lõm khi và chỉ khi (−f ) là hàm lồi trên K, trong đó (−f ) được xác định bởi (−f )(x) = −f (x) với ∀x ∈ K. Định nghĩa 1.2.4. Nếu f là một hàm lồi trên tập K ⊂ Rn thì tập epi(f ) = {(x; α) ∈ X × R|f (x) ≤ α} gọi là trên đồ thị của hàm f . Ví dụ 1.2.2. Hàm hằng f : X → R; f (x) = a với ∀x ∈ X là một hàm lồi. Ví dụ 1.2.3. Hàm f : R → R; f (x) = x3 không phải là hàm lồi trên R. Thật vậy với x = −1, y = 0, t = 1 2 ta có 1 1 f (tx + (1 − t) y) = − , tf (x) + (1 − t)f (y) = − 8 2 Chứng tỏ f (tx + (1 − t) y) > tf (x) + (1 − t)f (y) Vậy f (x) = x3 không phải là hàm lồi trên R 1.2.3. Hàm lồi suy rộng Định nghĩa 1.2.5. Cho K ⊂ Rn là một tập lồi và f : K → R là một hàm số. Hàm f được gọi là hàm giả lồi trên K nếu với mọi x, y ∈ K sao cho f (x) ≤ f (y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa mãn f (λx + (1 − λ)y) ≤ f (y) − λ(1 − λ)β 8 Hàm f được gọi là hàm giả lồi chặt trên K nếu với mọi x, y ∈ K sao cho f (x) ≤ f (y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa mãn f (λx + (1 − λ)y) < f (y) − λ(1 − λ)β Ta có một số tính chất sau: (i)Hàm lồi là hàm giả lồi, hàm lồi chặt là hàm giả lồi chặt, nhưng hàm giả lồi có thể không lồi. (ii)Hàm lồi chưa chắc đã là hàm giả lồi chặt. (iii)Hàm giả lồi chưa chắc đã là hàm giả lồi chặt. Định nghĩa 1.2.6. Cho K ⊂ Rn là một tập lồi và f : K → R là một hàm số. Hàm f được gọi là hàm tựa lồi trên K nếu với mọi x, y ∈ K và với mọi t ∈ [0, 1], ta có: f (tx + (1 − t)y) ≤ max {f (x), f (y)} Hàm f được gọi là hàm tựa lồi chặt trên K nếu với mọi x, y ∈ K và với mọi t ∈ [0, 1], ta có: f (tx + (1 − t)y) < max {f (x), f (y)} Ta có một số tính chất sau: (i)Hàm tựa lồi chặt là hàm tựa lồi. (ii)Hàm tựa lồi thì chưa chắc tựa lồi chặt. (iii)Nếu hàm f lồi thì nó là hàm tựa lồi. Điều ngược lại không đúng. (iv)Hàm lồi chưa chắc đã là hàm tựa lồi chặt. 9 1.3. Không gian tôpô lồi địa phương 1.3.1. Không gian tôpô Cho X là tập hợp. Kí hiệu P(X) là họ các tập con của X. Họ τ ⊂ P(X) được gọi là một tôpô trên X nếu nó thỏa mãn các tính chất sau: (i) ∅; X ∈ τ . (ii) Giao của một số hữu hạn phần tử thuộc τ thì thuộc τ . (iii) Hợp của một họ tùy ý các phần tử thuộc τ thì thuộc τ . Khi đó X được gọi là không gian tôpô và mỗi phần tử U ∈ τ được gọi là tập mở trong X. Cho A ⊂ X, x0 ∈ X, ta nói x0 là: - Điểm trong của A nếu tồn tại U ∈ τ sao cho x0 ∈ U ⊂ A. - Điểm ngoài của A nếu tồn tại U ∈ τ sao cho x0 ∈ U và U ∩A = ∅. - Điểm biên nếu cả hai mệnh đề trên đều sai. Định nghĩa 1.3.1. Nếu x0 là điểm trong của A thì ta cũng nói A là lân cận của x0 . Cho không gian tôpô (X, τ ). Một họ B ⊂ τ được gọi là một cơ sở lân cận của τ nếu mọi tập U ∈ τ đều được biểu diễn dưới dạng hợp của các tập thuộc B. Một họ V ⊆ τ được gọi là một cơ sở lân cận của x0 ∈ X nếu mọi lân cận U của x0 đều tồn tại V ∈ V sao cho x0 ∈ V ⊆ U . 10 1.3.2. Không gian tôpô tuyến tính Cho không gian véc tơ X. Khi đó một tôpô τ trên X được gọi là tương đương với cấu trúc đại số trên X nếu dưới tôpô này các ánh xạ sau lên tục: +:X ×X →X .:R×X →X Tức là: Với mọi x, y ∈ X và mọi lân cận W của x + y, tồn tại các lân cận U của x, V của y sao cho U + V ⊂ W . Với mọi λ ∈ R, x ∈ X và mọi lân cận W của λx, tồn tại ε > 0 và lân cận V của x sao cho µV ⊂ W với mọi µ ∈ (λ − ε, λ + ε). Khi đó, τ được gọi là tôpô tuyến tính trên X và X được gọi là không gian tôpô tuyến tính. Định nghĩa 1.3.2. Cho A là tập con của không gian véc tơ X trên trường K Tập A được gọi là cân đối nếu với mọi x ∈ A ta có λx ∈ A với mọi |λ| ≤ 1. Tập A được gọi là hấp thụ nếu với mọi x ∈ X đều tồn tại λ > 0 sao cho x ∈ µA với mọi µ thỏa mãn điều kiện |µ| ≥ λ. Định lý 1.3.1. Cho X là một không gian véc tơ (a) Nếu τ là một tôpô tuyến tính, thì tồn tại cơ sở lân cận gốc V ⊂ τ thỏa mãn: (i) V cân đối, hấp thụ với mọi V ∈ V, (ii) αV ⊂ V với mọi α 6= 0 và V ∈ V, (iii) Với mọi V ∈ V tồn tại U ∈ V sao cho U + U ⊂ V, (iv) Với mọi V1 , V2 ∈ V sao cho U ⊂ V1 ∩ V2 . 11 (b) Ngược lại nếu V ⊂ P(X) là họ các tập thỏa mãn các điều kiện (i iv), thì tồn tại tôpô tuyến tính τ trên X nhận V làm cơ sở lân cận gốc. 1.3.3. Không gian tôpô lồi địa phương Từ kết quả trên ta thấy cấu trúc tôpô tuyến tính hoàn toàn được xác định bởi hệ cơ sở lân cận gốc. Nếu tồn tại một hệ cơ sở lân cận gốc gồm toàn các tập lồi thì τ được gọi là tôpô lồi địa phương và X được gọi là không gian tô pô lồi địa phương. Định lý 1.3.2. Cho X là một không gian véc tơ. (i) Nếu τ là một tôpô lồi địa phương trên X, thì tồn tại một cơ sở lân cận gốc gồm các tập lồi, cân đối và hấp thụ. (ii) Ngược lại, nếu V0 là họ gồm các tập lồi, cân đối và hấp thụ thì họ sau o n m V = ε ∩ Vi | ε > 0; m ∈ N; Vi ∈ V0 1 là cơ sở lân cận gốc của một tôpô lồi địa phương nào đó. Hơn nữa, tôpô là Hausdorff khi và chỉ khi ∩ V ∈V0 ,ε>0 εV = {0} Trong phần này ta định nghĩa phần trong tương đối của K (Với K là tập lồi trong X) là phần trong của tập này theo tôpô cảm sinh trong af f (K). Cụ thể: riK = {x ∈ K | ∃V : (x + V ) ∩ aff(K) ⊂ K} (Với V là lân cận gốc) Ví dụ 1.3.1. Không gian định chuẩn là không gian tôpô lồi địa phương sinh bởi họ gồm một tập: V0 = {B(0, 1)}. Khi đó, cơ sở lân cận gốc tương ứng V = {εB(0, 1) | ε > 0} = {B(0, ε)|ε > 0} 12 1.3.4. Nón lồi và nón lùi xa của tập lồi Định nghĩa 1.3.3. Tập K ⊂ Rn được gọi là một nón nếu với mọi x ∈ K, với mọi λ ≥ 0 ta có: tx ∈ K. Định nghĩa 1.3.4. Tập K ⊂ Rn được gọi là một nón lồi nếu K vừa là nón vừa là một tập lồi, tức là: với mọi x, y ∈ K và với mọi λ, µ ≥ 0, ta có λx + µy ∈ K Định lý 1.3.3. Tập K ⊂ Rn được gọi là một nón lồi khi và chỉ khi ∀x; y ∈ K, ∀λ ≥ 0 ⇒ x + y ∈ K; λx ∈ K Chứng minh. ⇒ Giả sử K là hình nón lồi. Khi đó do K là tập lồi, ta có: z = 12 (x + y) ∈ K. Do K là nón nên ta có:x + y = 2z ∈ K. ⇐ Ngược lại, với ∀x; y ∈ K, ∀λ ≥ 0 ta có λx ∈ K , vậy K là hình nón. Với 0 < λ < 1; x, y ∈ K ta có (1 − λ)x ∈ K; λy ∈ K và (1 − λ)x + λy ∈ K Chú ý với λ = 0 ta vẫn có (1 − λ)x + λy ∈ K. Vậy K là tập lồi. Từ đó ta suy ra K là nón lồi. Định nghĩa 1.3.5. Cho D là tập lồi khác rỗng trong Rn . Véc tơ v ∈ Rn khác 0 được gọi là phương lùi xa của D nếu với mọi x ∈ D, với mọi t ≥ 0 ta có x + tv ∈ D. Tập tất cả các phương lùi xa của D cùng véc tơ 0 của Rn lập thành một nón lồi. Ta gọi nón đó là nón lùi xa của D và kí hiệu là 0+ D. 13 1.4. Hàm Lipschitz Định nghĩa 1.4.1. Giả sử X là không gian Banach, f : X → R Hàm f được gọi là Lipschitz địa phương tại x0 ∈ X hay Lipschitz địa phương gần x0 , nếu tồn tại lân cận U của x0 số K > 0 sao cho với mọi x, x0 ∈ X ta có |f (x) − f (x0 )| ≤ K kx − x0 k Hàm f được gọi là Lipschitz địa phương trên tập Y ⊂ X, nếu f là Lipschitz địa phương tại mọi x ∈ Y . Hàm f được gọi là Lipschitz địa phương với hằng số Lipschitz K trên tập Y ⊂ X, nếu biểu thức trên đúng với mọi x, x0 ∈ Y 1.5. Ma trận Định nghĩa 1.5.1. Gọi Rs n×n là tập hợp các ma trận thực đối xứng n × n Giả sử A là ma trận thuộc Rs n×n ta có: (i) A được gọi là nửa xác định dương nếu xT Ax ≥ 0; ∀x ∈ Rn . (ii) A được gọi là xác định dương nếu A là nửa xác định dương trên Rs n×n và xT Ax = 0 ⇔ x = 0. (iii) A được gọi là nửa xác định âm (xác định âm) nếu −A là nửa xác định dương (xác định dương) . Ta kí hiệu:  a1  diag(a1 , ..., an ) =   0    ... 0  an 14 1.6. Hàm toàn phương và bài toán quy hoạch toàn phương 1.6.1. Hàm toàn phương Trong luận văn này ta xét hàm toàn phương Q : Rn → R được cho 1 dưới dạng: Q(x) = xT Ax + bT x , trong đó A là ma trận thực đối xứng 2 n cấp n × n và b ∈ R . Ta có định lý sau: Định lý 1.6.1. Nếu A là ma trận vuông cấp n × n, đối xứng, nửa xác 1 định dương, b ∈ Rn thì hàm toàn phương Q(x) = xT Ax + bT x là một 2 hàm lồi. Chứng minh. Vì A là nửa xác định dương nên với x, y ∈ Rn ta có (x − y)T A(x − y) ≥ 0 suy ra 1 1 T x Ax + y T Ay ≥ xT Ay 2 2 Do đó với mọi x, y ∈ Rn và với mọi t ∈ (0, 1) ta có: t2 T 1 − t2 T x Ax + tbT x + y Ay 2 2 + (1 − t) bT x + t (1 − t) xT Ay Q [tx + (1 − t) y] = t2 T ≤ x Ax + tbT x 2 1 − t2 T + y Ay + (1 − t) bT y 2   1 T 1 T + t (1 − t) x Ax y Ay 2 2 ≤ tQ(x) + (1 − t)Q(y) Vậy Q lồi. 15 Áp dụng. Trường hợp n = 1 ta thấy hàm toàn phương như trên có dạng hàm bậc hai f (x) = ax2 + bx Theo định lý trên ta thấy hàm bậc hai là hàm lồi khi a > 0. Dựa vào các kết quả của S.Schaible [12], các tính chất của hàm toàn phương, tựa lồi, ta có các kết quả sau: 1 Định lý 1.6.2. Cho K ⊂ Rn là thể lồi và Q(x) = xT Ax + bT x. 2 Khi đó Q là tựa lồi, nhưng không lồi trên K khi và chỉ khi rankA = rank(A; b) và tồn tại ma trận không suy biến P sao cho với mọi véc tơ v thỏa mãn Av + b = 0 ta có: (i) Hàm số hợp G(y) = G(P v + b) có thể viết lại là: 1 G(y) = y T Λy + δ 2 trong đó Λ = diag(−1, 1, ..., 1, 0, ..., 0) (ii) Tập hợp D = {y ∈ Rn | x = P y + v ∈ K} thỏa mãn một trong hai điều sau: D ⊂ {y = (y1 , y2 , ..., yn ) ∈ Rn | G(y) ≤ δ, y1 ≥ 0} hoặc D ⊂ {y = (y1 , y2 , ..., yn ) ∈ Rn | G(y) ≤ δ, y1 ≤ 0} 1 trong trường hợp này hàm số h(x) = −(δ − Q(x)) 2 là hàm lồi trên K. Hệ quả 1.6.1. Cho K ⊂ Rn là tập lồi, mở. Khi đó 1 Q(x) = xT Ax + bT x 2 gọi là tựa lồi trên clK khi và chỉ khi nó là hàm giả lồi trên K. Định lý 1.6.3. K ⊂ Rn là tập lồi, mở. Khi đó 1 Q(x) = xT Ax + bT x 2