Luận văn Thạc sĩ Toán học: Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu

Chia sẻ: Tri Lễ | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

33
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày các điều kiện Karush - Kuhn - Tucker cần và đủ và các định lý đối ngẫu cho bài toán quy hoạch thương có ràng buộc bất đẳng thức với các hàm lồi suy rộng Lipschitz địa phương của H. Kuk, G. M. Lee, T. Tanino đăng trong tạp chí J. Math. Anal. Appl. 262 (16, 2001), 365 - 375, và các điều kiện tối ưu cho bài toán quy hoạch thương đối với các hàm liên tục của N. Gadhi đăng trong tạp chí Optimization 57 (8, 2008), 527 - 537.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VŨ THỊ THUẦN ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VŨ THỊ THUẦN ĐIỀU KIỆN TỐI ƯU VÀ ĐỐI NGẪU CHO BÀI TOÁN QUY HOẠCH THƯƠNG ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số : 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Đỗ Văn Lưu THÁI NGUYÊN - 2017
i Mục lục Mở đầu 1 Chương 1 Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương không trơn với các hàm lồi suy rộng 4 1.1. Các khái niệm và định nghĩa . . . . . . . . . . . . . . . . . . 4 1.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3. Đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chương 2 Điều kiện tối ưu cho bài toán quy hoạch thương đa mục tiêu qua dưới vi phân suy rộng 19 2.1. Phát biểu bài toán và các kết quả bổ trợ . . . . . . . . . . . . . 19 2.2. Điều kiện cần tối ưu . . . . . . . . . . . . . . . . . . . . . . 29 2.3. Điều kiện đủ tối ưu . . . . . . . . . . . . . . . . . . . . . . . 32 Kết luận 37 Tài liệu tham khảo 38
1 Mở đầu 1. Lí do chọn đề tài Các bài toán quy hoạch thương đa mục tiêu đóng một vai trò quan trọng trong tối ưu, mô hình phân tích gói dữ liệu Charnes–Cooper– Rhodes là một ví dụ cho bài toán quy hoạch thương trong kinh tế. Các điều kiện tối ưu và đối ngẫu cho các bài toán quy hoạch thương đa mục tiêu đã và đang được nhiều tác giả quan tâm nghiên cứu. H. Kuk, G. M. Lee và T. Tanino ([16], 2001) đã thiết lập các điều kiện Karush - Kuhn - Tucker và các định lí đối ngẫu cho bài toán quy hoạch thương đa mục tiêu Lipschitz địa phương có ràng buộc bất đẳng thức với các hàm lồi suy rộng Lipschitz địa phương. N. Gadhi ([8], 2008) đã dẫn các điều kiện tối ưu cho nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu có ràng buộc bất đẳng thức với các hàm liên tục, không nhất thiết Lipschitz địa phương. Đây là đề tài được nhiều tác giả quan tâm nghiên cứu. Chính vì vậy tôi chọn đề tài: "Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương đa mục tiêu". 2. Mục đích của đề tài luận văn Luận văn trình bày các điều kiện Karush - Kuhn - Tucker cần và đủ và các định lý đối ngẫu cho bài toán quy hoạch thương có ràng buộc bất đẳng thức với
2 các hàm lồi suy rộng Lipschitz địa phương của H. Kuk, G. M. Lee, T. Tanino đăng trong tạp chí J. Math. Anal. Appl. 262 ([16], 2001), 365 - 375, và các điều kiện tối ưu cho bài toán quy hoạch thương đối với các hàm liên tục của N. Gadhi đăng trong tạp chí Optimization 57 ([8], 2008), 527 - 537. 3. Nội dung của đề tài luận văn, những vấn đề cần giải quyết Chương 1. Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương không trơn với các hàm lồi suy rộng Trình bày các kết quả về điều kiện Karush - Kuhn - Tucker cho nghiệm hữu hiệu của bài toán quy hoạch thương đa mục tiêu không trơn với các hàm Lipschitz địa phương, có ràng buộc bất đẳng thức, dưới ngôn ngữ dưới vi phân Clarke, và các định lý đối ngẫu yếu, mạnh, ngược chặt với các giả thiết về tính lồi suy rộng. Các kết quả trình bày trong chương này là của Kuk - Lee - Tanino ([16], 2001). Chương 2. Điều kiện tối ưu cho bài toán quy hoạch thương đa mục tiêu qua dưới vi phân suy rộng Trình bày các kết quả về điều kiện cần cho nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu với các hàm không nhất thiết Lipschitz địa phương, có ràng buộc bất đẳng thức dưới ngôn ngữ dưới vi phân suy rộng. Các điều kiện đủ cho nghiệm hữu hiệu được trình bày với các giả thiết về tính lồi suy rộng. Các kết quả trình bày trong chương này là của Gadhi ([8], 2008). Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của PGS.TS. Đỗ Văn Lưu. Tác giả
3 xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn tận tình và đầy trách nhiệm để tác giả hoàn thành luận văn này. Tác giả đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Nhân dịp này tác giả xin gửi lời cảm ơn sâu sắc tới các Thầy giáo, Cô giáo đã tham gia giảng dạy lớp Cao học Toán K9Y; Nhà trường và các phòng chức năng của Trường; Khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin cảm ơn gia đình, bạn bè và đồng nghiệp đã động viên, ủng hộ và tạo mọi điều kiện cho tác giả trong suốt thời gian nghiên cứu và học tập. Thái Nguyên, ngày 10 tháng 11 năm 2017 Tác giả luận văn Vũ Thị Thuần
4 Chương 1 Điều kiện tối ưu và đối ngẫu cho bài toán quy hoạch thương không trơn với các hàm lồi suy rộng Chương 1 trình bày các kết quả của Kuk - Lee - Tanino [16] về điều kiện Karush - Kuhn - Tucker cho nghiệm hữu hiệu của bài toán quy hoạch thương đa mục tiêu không trơn có ràng buộc bất đẳng thức, với các hàm Lipschitz địa phương, dưới ngôn ngữ dưới vi phân Clarke, và các định lý đối ngẫu yếu, mạnh, ngược chặt với các giả thiết về tính lồi suy rộng. 1.1. Các khái niệm và định nghĩa Cho Rn là không gian Euclide n chiều. Trong suốt chương này, ta sử dụng mối quan hệ so sánh giữa các vectơ trong Rn như sau: x > y ⇔ xi > yi , với mọi i = 1, ..., n, x ≥ y ⇔ xi ≥ yi , với mọi i = 1, ..., n. Hàm giá trị thực f : Rn → R được gọi là Lipschitz địa phương nếu với bất kì z ∈ Rn , tồn tại một hằng số dương K và một lân cận N của z sao cho, với
5 mỗi x, y ∈ N , | f (x) − f (y) |≤ K k x − y k, trong đó, k . k là kí hiệu chuẩn trong Rn . Trong chương này, ta xét bài toán quy hoạch thương đa mục tiêu sau:  min f1 (x) , ..., fp (x) ,  g1 (x) gp (x) (F P ) : x ∈ X = {x ∈ Rn | hj (x) ≤ 0, j = 1, ..., m },  trong đó fi : Rn → R, gi : Rn → R, i = 1, ..., p và hj : Rn → R, j = 1, ..., m là các hàm Lipschitz địa phương. Giả sử rằng fi (x) ≥ 0; gi (x) > 0 trong Rn với i = 1, ..., p. Giả thiết gi (x) > 0 là để hàm mục tiêu được xác định. Giả thiết fi (x) ≥ 0 (i = 1, . . . , p) cần để chứng minh các kết quả trong luận văn. Định nghĩa 1.1. Đạo hàm theo phương suy rộng Clarke [6] của hàm Lipschitz địa phương f tại x theo phương d được kí hiệu bởi f ◦ (x; d) được định nghĩa như sau: f ◦ (x; d) = lim sup t−1 (f (y + td) − f (y) ). y−→x;t↓0 Gradient suy rộng Clarke [6] của f tại x được định nghĩa bởi ∂f (x) = ξ | f ◦ (x; d) ≥ ξ T d, ∀d ∈ Rn }. Mệnh đề 1.1. [1] Giả sử f Lipschitz địa phương với hằng số Lipschitz K tại x. Khi đó, (i) Hàm v 7−→ f ◦ (x; v) hữu hạn, thuần nhất dương, dưới cộng tính trên Rn , và | f ◦ (x; v) |≤ K k v k;
6 (ii) f ◦ (x; v) nửa liên tục trên theo (x, v); f ◦ (x, ·) Lipschitz với hằng số K trên Rn ; (iii) f ◦ (x; −v) = (−f )◦ (x; v). Mệnh đề 1.2. [1] Giả sử f là hàm Lipschitz địa phương tại x với hằng số Lipschitz K. Khi đó, a) ∂f (x) 6= ∅, lồi, compắc và kξk ≤ K (∀ξ ∈ ∂f (x)); b) Với mọi v ∈ Rn , ta có f ◦ (x; v) = max {hξ, v i: ξ ∈ ∂f (x) }. Ví dụ 1.1. Cho hàm affine trên Rn : f (x) = hx∗ , x i+α (x∗ ∈ Rn , α ∈ R). Ta có ∂f (x) = {x∗ } (∀x ∈ Rn ). Ví dụ 1.2. Cho hàm f (x) =| x | (x ∈ R) Ta có   1 , nếu x > 0,  ∂f (x) =  −1 , nếu x < 0.  Với x = 0, ta có f ◦ (0; v) =| v | (với mọi v ∈ R), ∂f (0) = [−1, 1].
7 Ví dụ 1.3. Cho hàm f : R −→ R được xác định bởi f (x) = max xi (x = (x1 , ..., xn ) ∈ Rn ) 1≤i≤n Đặt I(x) = {i : x1 = max1≤j≤n xj }. Ta có (xem [1]):    X  ∂f (x) = (ζ1 , ..., ζn ) : ζi ≥ 0, ζi = 1, ζj = 0, j ∈ / I(x)   i∈I(x) f ◦ (x; v) = max vi (v = (v1 , ..., vn ) ∈ Rn ) . i∈I(x) Egudo và Hanson [7] đã định nghĩa tính lồi bất biến của hàm Lipschitz địa phương như sau Định nghĩa 1.2. Một hàm Lipschitz địa phương f được gọi là lồi bất biến trên X0 ⊂ Rn nếu với mỗi x, u ∈ X0 tồn tại một hàm η (x, u ): X0 × X0 → Rn thỏa mãn f (x) − f (u) ≥ ξ T η(x, u), với mọi ξ ∈ ∂f (u). Egudo và Hanson [6] đã tổng quát tính V - lồi bất biến của Jeyakumar và Mond [10] cho các trường hợp không trơn như sau Định nghĩa 1.3. Một hàm vectơ f : X0 → Rn được gọi là V - lồi bất biến nếu tồn tại các hàm η : X0 × X0 → Rn và αi : X0 × X0 → R+ \ {0 } thỏa mãn fi (x) − fi (u) − αi (x, u)ξiT η(x, u) ≥ 0, với mỗi ξi ∈ ∂fi (u). Kuk, Lee và Kim [15] định nghĩa V - ρ - lồi bất biến cho các trường hợp không trơn như sau :
8 Định nghĩa 1.4. Cho fi : Rn → R, gi : Rn → R, i = 1, ..., p, và hj : Rn → R, j = 1, ..., m là các hàm Lipschitz địa phương, cho υ ∈ Rp và đặt e = (1, ..., 1) ∈ Rp . (a)f − υge := (f1 − υ1 g1 , ..., fp − υp gp ) được gọi là V - ρ - lồi bất biến theo các hàm η và θ : Rn × Rn → Rn nếu tồn tại αi : Rn × Rn → R+ \ {0 } và ρi ∈ R, i = 1, ..., p sao cho với bất kì x, u ∈ Rn và bất kì ξi ∈ ∂fi (u) và ζi ∈ ∂gi (u), αi (x, u) {fi (x) − υi gi (x) − fi (u) + υi gi (u) } (1.1) 2 ≥ (ξi − υi ζi )η(x, u) + ρi k θ(x, u) k . Nếu ta có bất đẳng thức chặt trong (1.1) với mọi x, u ∈ Rn , với x 6= u thì f −υge được gọi là V - ρ - lồi bất biến chặt theo các hàm η và θ : Rn × Rn → Rn . (b) h được gọi là V - σ - lồi bất biến theo các hàm η và θ : Rn × Rn → Rn nếu tồn tại βj : Rn × Rn → R+ \ {0 } và σj ∈ R, j = 1, ..., m, sao cho với bất kì x, u ∈ Rn và bất kì µj ∈ ∂hj (u), βj (x, u) hj (x) − hj (u) ≥ µj η(x, u) + σj k θ(x, u) k2 . Nhận xét 1.1. Nếu trong định nghĩa trên ρi = 0 với mọi i, thì hàm đã cho là V - lồi bất biến. Để chỉ ra sự tồn tại của các hàm V - ρ - lồi bất biến, ta xét ví dụ sau: Ví dụ 1.4. Xem xét hàm số fi : X0 = [−1; 1] → R, i = 1, 2, xác định bởi  2x2 , −1 ≤ x ≤ 0,  f1 (x) = x, 0 ≤ x ≤ 1, 
9  5x4 , −1 ≤ x ≤ 0,  f2 (x) = 2x, 0 ≤ x ≤ 1.  Với  2x2 , −1 ≤ x ≤ 0,  f1 (x) = x, 0 ≤ x ≤ 1,  ta có  d ≥ 0, d,  f1 (y + td) − f1 (y) f1◦ (0; d) = lim sup = y−→0;t↓0 t 0, d < 0.   d ≥ ξd, d ≥ 0,  ◦ f1 (0; d) ≥ ξd ⇔ ⇔ 0 ≤ ξ ≤ 1. 0 ≥ ξd, d < 0,  Với  5x4 , −1 ≤ x ≤ 0,  f2 (x) = 2x, 0 ≤ x ≤ 1,  ta có  2d, d ≥ 0,  f2 (y + td) − f2 (y) f2◦ (0; d) = lim sup = y−→0;t↓0 t 0, d < 0.   2d ≥ ξd,  d ≥ 0, f2◦ (0; d) ≥ ξd ⇔ ⇔ 0 ≤ ξ ≤ 2. 0 ≥ ξd,  d < 0, Do đó ∂f1 (0) = {ξ | 0 ≤ ξ ≤ 1 } và ∂f2 (0) = {ξ | 0 ≤ ξ ≤ 2 } . Xác định η : X0 × X0 → R , η(x, u) = 2x2 − 1 − u, p θ : X0 × X0 → R , θ(x, u) = 2x2 − 1 + u2 ,
10 α1 : X0 × X0 → R+ \ 0 , α1 (x, u) = 2x2 + 1, và α2 : X0 × X0 → R+ \ 0 , α2 (x, u) = u2 + 3. Với ρ1 = 1 và ρ2 = 2, hàm vectơ f (x) = (f1 (x), f2 (x)) là V - ρ - lồi bất biến tại u = 0. Trong ví dụ này, chú ý rằng khi phát biểu kết quả thì đã cố định η, θ, α và ρ rồi. Định nghĩa 1.5. Một điểm u ∈ X được gọi là một nghiệm hữu hiệu của (F P ) nếu không tồn tại x ∈ X thỏa mãn fi (x) fi (u) ≤ , với mọi i = 1, ..., p, gi (x) gi (u) và fk (x) fk (u) < , với k nào đó. gk (x) gk (u) 1.2. Điều kiện tối ưu Phần này trình bày các điều kiện cần Karush - Kuhn - Tucker và các điều kiện đủ cho nghiệm hữu hiệu của bài toán (F P ). Xét bài toán cực tiểu vô hướng sau:  min l(x)  (P ) : hj (x) ≤ 0, j = 1, ..., m,  trong đó l, hj : Rn → R, j = 1, ..., m là các hàm Lipschitz địa phương. Tại một điểm u ∈ Rn , ta định nghĩa I ∗ = {j ∈ I | hj (u) = 0 }, với I = {1, ..., m },
11   d ∈ Rn | h◦ (u; d) ≤ 0, j ∈ I ∗ }, nếu I ∗ 6= ∅,  j Ω= Rn , nếu I ∗ = ∅,    d ∈ Rn | h◦ (u; d) < 0, j ∈ I ∗ }, nếu I ∗ 6= ∅,  j Ω◦− = Rn , nếu I ∗ = ∅.  Với bài toán (P ), ta xét điều kiện chính quy sau: Điều kiện chính quy 1.1. Tại điểm u, Ω◦− 6= ∅. Bổ đề 1.1. [18 ] Nếu u là cực tiểu địa phương của (P ) và Điều kiện chính quy 1.1 thỏa mãn thì tồn tại λ1 , ..., λm sao cho m X 0 ∈ ∂l(u) + λj ∂hj (u), j=0 λj hj (u) = 0, j = 1, ..., m, λj ≥ 0, j = 1, ..., m. Bổ đề 1.2. [16 ] u là một nghiệm hữu hiệu của (F P ) nếu và chỉ nếu u là nghiệm của (F Pk ), k = 1, ..., p, với (F Pk ) là bài toán dưới đây :   fk (x)   min ,    g k (x) fi (x) fi (u)  (F Pk ) ≤ với mọi i 6= k,    g i (x) g i (u)   hj (x) ≤ 0, j = 1, ..., m.  Ta phát biểu điều kiện cần Karush - Kuhn - Tucker suy rộng cho (F P ) mà chứng minh của nó bằng một phương pháp tương tự như chứng minh trong [17, định lý 3.2.9].
12 Định lý 1.1. (Điều kiện cần tối ưu) Nếu u là một nghiệm hữu hiệu của (F P ) và thỏa mãn Điều kiện chính quy 1.1 cho (F Pk ), k = 1, ..., p thì tồn tại τ ∈ Rp và λ ∈ Rm sao cho p X m X 0∈ τi {∂fi (u) − yi ∂gi (u)} + λj ∂hj (u), (1.2) i=1 j=1 λj hj (u) = 0, j = 1, ..., m, (1.3) τ > 0, λ ≥ 0, (1.4) fi (u) trong đó yi = , i = 1, ..., p. gi (u) Định lý 1.2. (Điều kiện đủ tối ưu) Cho (u, τ, λ) ∈ Rn × Rp × Rm thỏa mãn điều kiện (1.2) - (1.4), Giả sử rằng f − yge := (f1 − y1 g1 , ..., fp − yp gp ) là V - ρ- lồi bất biến và h là V - σ- lồi bất biến theo cùng η và θ và p X m X τ i ρi + λj σj ≥ 0, (1.5) i=1 j=1 fi (u) trong đó yi = , i = 1, ..., p. Khi đó, u là một nghiệm hữu hiệu của (F P ). gi (u) Chứng minh. Giả sử rằng u không là một nghiệm hữu hiệu của (F P ). Khi đó, tồn tại x ∈ X thỏa mãn fi (x) fi (u) ≤ , i = 1, ..., p, gi (x) gi (u) và fk (x) fk (u) < , với k nào đó. gk (x) gk (u) Do gi (x) > 0 với mọi i = 1, ..., p, ta có fi (x) − yi gi (x) ≤ fi (u) − yi gi (u), với mọi i = 1, ..., p,
13 và fk (x) − yk gk (x) < fk (u) − yk gk (u), với k nào đó. Do τ > 0 và αi (x, u) > 0 với mọi i = 1, ..., p, ta có p X p X τi αi (x, u) {fi (x) − fi (u)} < τi αi (x, u) {yi gi (x) − yi gi (u)} . i=1 i=1 Do tính V -ρ - lồi bất biến của f − yge, ta có p X p X τi (ξi − yi ζi )η(x, u) + τi ρi k θ(x, u) k2 < 0, (1.6) i=1 i=1 với mỗi ξi ∈ ∂fi (u) và ζi ∈ ∂gi (u). Từ (1.2) và (1.5), (1.6) ta suy ra m X m X λj µj η(x, u) + λj σj k θ(x, u) k2 > 0, j=1 j=1 với µj nào đó thuộc ∂hj (u). Do tính V - σ - lồi bất biến của h, ta nhận được m X λj βj (x, u) {hj (x) − hj (u) }> 0. j=1 Bởi vì λj hj (u) = 0 với mọi j = 1, ..., m, ta có m X λj βj (x, u)hj (x) > 0. j=1 Điều này mâu thuẫn với các điều kiện βj (x, u) > 0, λj ≥ 0, hj (x) ≤ 0 với mọi j = 1, ..., m. Vì vậy u là một nghiệm hữu hiệu của (F P ).
14 1.3. Đối ngẫu Theo cách tiếp cận của Bector, Chandra và Husain [4 ] ta xây dựng bài toán đối ngẫu cho (F P ). (FD): max (υ1 , ..., υp ) , p X m X 0∈ τi {∂fi (u) − υi ∂gi (u)} + λj ∂hj (u), (1.7) i=1 j=1 fi (u) − υi gi (u) ≥ 0, i = 1, ..., p, (1.8) λj hj (u) ≥ 0, j = 1, ..., m, (1.9) τ ∈ Rp , λ ∈ Rm , υ ∈ Rp , τ > 0, λ ≥ 0, υ ≥ 0. (1.10) Ta thiết lập định lý đối ngẫu yếu, mạnh và ngược chặt giữa (F P ) và (F D). Định lý 1.3. (Đối ngẫu yếu) Cho x là một điểm chấp nhận được của (F P ) và cho (u, τ, λ, υ) là một điểm chấp nhận được của (FD). Giả sử rằng f − υge := (f1 − υ1 g1 , ..., fp − υp gp ) là V - ρ - lồi bất biến và h là V - σ - lồi bất biến theo cùng η và θ và p X m X τ i ρi + λj σj ≥ 0 (1.11) i=1 j=1 Khi đó, fi (x) ≤ υi , với mọi i = 1, ..., p, (1.12) gi (x) và fk (x) < υk , với k nào đó, (1.13) gk (x) không thể xảy ra.
15 Chứng minh. Giả sử ngược lại kết luận của định lý không xảy ra, tức là với điểm x chấp nhận được nào đó của (FP) và (u, τ, λ, υ) của (FD). fi (x) ≤ υi , với mọi i = 1, ..., p, gi (x) và fk (x) < υk , với k nào đó. gk (x) Khi đó, ta có fi (x) − υi gi (x) ≤ 0, với mọi i = 1, ..., p, và fk (x) − υk gk (x) < 0, với k nào đó. Vì vậy, từ (1.8) và (1.10), ta nhận được p X p X τi {fi (x) − υi gi (x)} < τi {fi (u) − υi gi (u)} . i=1 i=1 Do tính V - ρ - lồi bất biến của f − υge, ta có p X p X τi (ξi − υi ζi )η(x, u) + τi ρi k θ(x, u) k2 < 0, (1.14) i=1 i=1 với mọi ξi ∈ ∂fi (u) và mọi ζi ∈ ∂gi (u). Từ (1.7) và giả thiết p X m X τi ρi + λj σj ≥ 0, i=1 j=1 ta suy ra tồn tại µj ∈ ∂hj (u) sao cho m X p X λj µj η(x, u) + λi σi k θ(x, u) k2 > 0. (1.15) j=1 i=1
16 Từ (1.9), (1.10) và βj (x, u) > 0 với mọi j = 1, ..., m, ta có βj (x, u)λj hj (x) ≤ βj (x, u)λj hj (u), với mọi j = 1, ..., m. Do tính V - ρ - lồi bất biến của h ta có m X m X λj µj η(x, u) + λj σj k θ(x, u) k2 ≤ 0, j=1 j=1 với mọi µj ∈ ∂hj (u). Điều này mâu thuẫn với bất đẳng thức (1.15). Hệ quả 1.1. Giả sử rằng các điều kiện của định lý đối ngẫu yếu (Định lý 1.3) thỏa mãn. Nếu x là điểm chấp nhận được của bài toán (F P ) và (u, τ , λ, υ) là fi (x) điểm chấp nhận được của bài toán (F D) với υi = , i = 1, ..., p thì x và gi (x) (u, τ , λ, υ) tương ứng là các nghiệm hữu hiệu của bài toán (F P ) và bài toán (F D). Định lý 1.4. (Đối ngẫu mạnh) Cho x là một nghiệm hữu hiệu của (FP) và giả sử rằng x thỏa mãn Điều kiện chính quy 1.1 cho (F Pk ), k = 1, ..., p. Khi đó, tồn tại τ ∈ Rp , λ ∈ Rm , và υ ∈ Rp sao cho (x, τ , λ, υ) là điểm chấp nhận được của (F D). Nếu các điều kiện của định lý đối ngẫu yếu (Định lý 1.3) cũng đúng thì (x, τ , λ, υ) là một nghiệm hữu hiệu của (F D). Chứng minh. Bởi vì x là một nghiệm hữu hiệu của (F P ), từ Bổ đề 1.2, x giải được (F Pk ) với mỗi k = 1, ..., p. Từ Định lý 1.1, tồn tại τ ∈ Rp , λ ∈ Rm , và υ ∈ Rp sao cho (x, τ , λ, υ) là một điểm chấp nhận được của (F D) và υ i = fi (x) , i = 1, ..., p. Do định lý đối ngẫu yếu giữa (F P ) và (F D), tính hữu hiệu gi (x) của (x, τ , λ, υ) của (F D) được suy ra từ Hệ quả 1.1.
17 Định lý 1.5. (Đối ngẫu ngược chặt) Giả sử x là một điểm chấp nhận được của (F P ) và cho (u, τ , λ, υ) là một điểm chấp nhận được của (F D), với υ i = fi (x) , i = 1, ..., p. Giả sử rằng f − υge là V - ρ - lồi bất biến chặt và h là V - gi (x) σ - lồi bất biến theo cùng η và θ và p X m X τ i ρi + λj σj ≥ 0. (1.16) i=1 j=1 Khi đó x = u, hay u là một nghiệm hữu hiệu của (F P ). Chứng minh. Ta giả sử rằng x 6= u. Bởi vì (u, τ , λ, υ) là một điểm chấp nhận được của (F D), tồn tại ξi ∈ ∂fi (u) và ζi ∈ ∂gi (u), i = 1, ..., p và µj ∈ ∂hj (u), j = 1, ..., m sao cho p X m X τ i (ξi − υ i ζi ) + λj µj = 0, (1.17) i=1 j=1 p X m X τ i αi (x, u) {fi (u) − υ i gi (u)} + λj βj (x, u)hj (u) ≥ 0 (1.18) i=1 j=1 Từ (1.17), ta thu được p X m X τ i (ξi − υ i ζi ) η (x, u) + λj µj η (x, u) = 0. i=1 j=1 Do đó, từ (1.16) và các định nghĩa của tính V - ρ - lồi bất biến chặt và V - σ - lồi bất biến của f − υge và h, ta nhận được p X m X τ i αi (x, u) {fi (x) − υ i gi (x)} + λj βj (x, u)hj (x) i=1 j=1 p X m X > τ i αi (x, u) {fi (u) − υ i gi (u)} + λj βj (x, u)hj (u). (1.19) i=1 j=1