Luận văn Qui hoạch phi tuyến và ánh xạ đa trị

yên ngựa tương ứng với hàm Lagrange L của. (P). Hơn thế nữa điều kiện này nhận được nếu và chỉ nêu X và thành phẩn λi của ̅ * thỏa Chứng minh : Theo định nghĩa của điểm yên ngựa thì ta có : ( ̅*, ̅ ) là điểm yên ngựa của L nếu và chỉ nếu sup Tuy nhiên từ công thức hàm Lagrange nêu trên ta luôn luôn có (xem ̅*cố định ) và (xem ̅ là cổ định ) Như vậy là điểm yên ngựa nếu và chỉ nếu Không quan tâm đến việc lựa chọn x ta có . Ở dây Co là tập các nghiệm chấp nhận được của (P) . Mặt. khác với bất kì Bài toán qui hoạch lồi | 27 ̅*= (λ1,...,λm ) cho trước ta có Ở dây h = fo+ λ1 f1 + ...+ λmfm . Như vậy( ̅ * , ̅ ) là điểm yên ngựa của L nếu và chỉ nếu Điều kiện (d) đuợc thỏa khi ̅*là vectơ Kuhn Tucker và ̅ là một nghiệm tối ưu , từ đó inf h= α và fo( ̅)= α, α là giá trị tối ưu của (P) và là hữu hạn . Mặt. khác giả sử (d) được thỏa , với x bất. kì thuộc Co ta có : và như vậy h(x) ≤ fo(x) , tức là và kéo theo rằng inf h =α =fo( ̅) Như vậy (d) suy ra rằng ̅*là vectơ Kuhn Tucker và ̅ là nghiệm tối ưu . Dĩ nhiên là từ lập luận vừa cho nêu trên ta có khi ̅* ∈ Er và ̅ ∈ Coở đây bất đẳng thức thứ hai là nghiêm ngặt. trừ các trường hợp λ i fi ( ̅)=0 với i : = 1,..., r Như thế (d) suy ra (a) , (b) và điều kiện (c’):h( ̅) =infh Đảo lại (a), (b) , (c) kéo theo (d) bởi vì h( ̅) =fo( ̅) dựa theo (a) và (b) . Để kết thúc chứng minh ta cần chỉ ra rằng (c) tương đương với (c’) giả sử ̅* ∈ Er. Thật vậy do định nghĩa , h đạt, được infimuin tại ̅ nếu và chỉ nếu 0 là subgradient của h lại ̅, tức là 0∈ δ h( ̅). Từ việc với mỗi X như vậy điều kiện 0 ∈ δ h( ̅) là thương đương với (c) . || Điều kiện (a) (b),(c) đựơc biết như là điều kiện Kuhn Tucker đối với bải toán (P) . Khi các hàm fj khả vi tại ̅, δ fi( ̅). qui về gradient, fi( ̅) của fi tại ̅ và (c) trở thành phương trình gradient : Hệ quả sau đây sẽ cho thấy việc tìm cực tiểu của bài toán quy hoạch với các ràng buộc là tương đương với việc tìm điểm yên ngựa của hàm Lagrange tương ứng với (P) . Bài toán qui hoạch lồi | 28 Hệ quả 1.20.1 Cho (P) là bài toán qui hoạch lồi thỏa các giả thiết của định lý 1.20. Để vectơ ̅ cho trước là nghiệm tối ưu của (P) thì điều kiện cần và đủ là tồn tại vectơ ̅*sao cho ( ̅*, ̅ ) là điểm yên ngựa hàm Lagrange L liên kết với (P) . Một cách tương đương , ̅ là nghiệm tối ưu nếu và chỉ nếu tồn tại các nhân tử Lagrơnge λi mà nó củng với ̅ thoả điều kiện Kuhn Tucker của (P). Định lý 1.20 nêu trên đã chỉ ra làm thế nào mà nghiệm tối ưu và vectơ Kuhn Tucker có thể được dùng để mô tả các điều kiện của hàm Lagrange . Tiếp sau đây sẽ chỉ ra làm thế nào mà giá trị tối ưu trong (P) cũng có thể mô tả các diều kiện của hàm Lagrange L . Định lý 1.21 Cho (P) là bài toán qui hoạch lồi với hàm Lagrange liên kết . Nếu ̅*là vectơ Kuhn Tucker và ̅ là nghiệm tối ưu của (P). Thì giá trị tại điểm yên ngựa L( ̅*, ̅ ) là, giá trị tối ưu của (P) . Tổng quát hơn ̅* là vectơ Kuhn Tacker của (P) nếu và chỉ nếu Trong trường hợp này giá trị cực trị chung của phương trình sau là giá trị tối ưu, của bài toán (P) . Chứng minh : Nếu ̅* =(λ1,, λm) là vectơ Kuhn Tucker và ̅ là một nghiệm tối ưu cua (P) thì ta có do điều kiện Kuhn Tucker của định lý 1.3 và như vậy L( ̅*, ̅ ) là giá trị tối ưu của(P). Trong trường hợp tổng quát như đã chỉ ra trong chứng minh của định lý 1.3 ở đây là hàm mục liêu của (P) . Như vậy là giá trị tối ưu trong bài toán (P)) Với bất kì Tức là Hơn thế nữa theo chứng minh của định lý 1.3 ta có Thế thì ̅* là vectơ Kuhn Tucker nếu và chỉ nếu supremumcủa hàm g = infx L(.,x) trên R m là bằng α > - ∞ và supremum này đạt được tại ̅* Định lý được chứng minh . | Ánh xạ đa trị - Ánh xạ đa diện lồi | 29 PHẦN 2 Ánh xạ đa trị -Ánh xạ đa diện lồi -Ánh xạ đa trị đa diện lồi. Trong phần này dành để trình bày các kiến thức cơ bản của hàm đa trị , hàm số đa diện lồi và đặc biệt chú ý đến hàm đa trị đa diện lồi mà các kết quả của nó sẽ đuợc dùng dể xem xét đến các vấn đề liên quan đến bài toán qui hoạch có tham số trong phần 3 của luận văn . Ánh xạ đa trị - Ánh xạ đa diện lồi | 30 §1. Ánh xạ đa trị : 1.1 Các khái niệm cơ bản : 1.1.1 Hàm tựa của một tập : Cho A N,A ≠ ta nói hàm tựa của A là hàm số thực mở rộng Với trong đó là giá trị của phiếm hàm x* tại x còn N* là không gian đối ngẫu của N . 1.1.2 Định nghĩa ánh xạ đa trị : Cho A,B ≠ ,G AxB Xét phép tương ứng X∈ A với tập con nào đó của B . Kí hiệu Ta nói (A, B , F ) là ánh xạ đa trị . Kí hiệu x → F(x) G gọi là đồ thị của ánh xạ đa trị F kí hiệu GrF F(x) gọi là ảnh của F tại x . Im F = F(A) Ta nói F là ánh xạ da trị có tính chất nếu và chỉ nếu GrF có tính chất Ta nói F là ánh xạ đa trị có giá trị nếu và chỉ nếu F(x) có tính chất với mọi X . Ta nói F là ánh xạ đa trị thuần nhất. dương nếu GrF là nón . 1.1.3 Hàm đặc trưng của ánh xạ đa trị : Định nghĩa : Cho Y là không gian Metric , F là ánh xạ đa trị F : F(x) đóng ∀x∈X .Hàm đặc trưng của F là hàm định bởi Qui ước : d(y, )= ∞ Nhận xét : Mệnh đề : F là Lipshitz địa phương tại xo ↔Tồn tại lân cận U của xo sao cho χ F là Lipshitz trên UxY . Ánh xạ đa trị - Ánh xạ đa diện lồi | 31 Chứng minh: F là Lipshitz địa phương tại xo nên tồn tại U(xo) và α sao cho ∀ x1 , x2 ∈ U ta có : Với mỗi y ∈ Y ta có : Vậy χF là Lipshitz trên U đều theo y . Mặt khác χF(x,y) = d (x,F(x)) là Lipshitz đều theo x với hằng số 1 Nên χF là Lipshitz theo cả hai biến trên UxY. Nếu χF là Lipshitz trên UxY với lân cận U nào đo của Xo , ta sẽ tìm được số dương α sao cho ∀ x1 , x2 ∈ U , ∀ y thoc Y ta có χF(x1,y) – χF(x1,y) ≤ α || x1 - x2 || Với mỗi y ∈ F(x2) ta có χF(x2, y) = 0 do đó χF (x1,y) ≤ α|| x1 - x2 || khi đó d (y, F(x1)≤ α|| x1 - x2 || Suy ra Vậy F Lipshitz trên U. 1.1.4 Hàm tựa của ánh xạ đa trị : Cho Y là không gian định chuẩn F từ X vào Y là ánh xạ đa trị . Hàm tựa của F là hàm số định bởi : Trong đó ζF(x ) (y * ) = sup { < y * ,y > , y ∈ F(x) } 1.1.5 Định lý đồ thị đóng : Cho B1, B2 là hai không gian Banach , ̅ là hình cầu đơn vị đóng F là ánh xạ đa trị từ B1 vào B2 có Dom(F) ≠ F là ánh xạ. đa trị lồi ¹ đóng và Int (ImF) ≠ Với yo ∈ Int (ImF) , xo ∈ F -1 (yo) ta có : Một cách tương đương ta có : ¹ Ánh xạ đa trị lồi nếu F(x) lồi , đóng nếu F(x) đóng Ánh xạ đa trị - Ánh xạ đa diện lồi | 32 Với ta có : sao cho 1.2 Ánh xạ đa trị Lipshitz địa phương. 1.2.1 Định nghĩa : Cho N1 , N2 là các không gian định chuẩn đầy đủ . Ánh xạ đa trị F từ N1 vào N2 là ánh xạ chặt ( Dom F = N1), ̅ là hình cầu đơn vị đóng , Cho Ta nói F là Lipshitz trên A nếu và chỉ nếu Ta nói F là Lipshitz tai xo nếu và chỉ nếu ∃U(xo)sao cho F là Lipshitz trên U(xo). Ta nói F là ánh xạ Lip nếu F Lipshitz trên N1 , hằng số α gọi là hằng số Lipshitz . 1.2.2 Điều kiện đủ của ánh xạ Lipshitz. Định lý 2.1: Nếu F là ánh xạ đa trị lồi đóng và ∃xo ∈Int(DomF) sao cho F(xo) là bị chặn thì F là ánh xạ. Lipshitz địa phương tại xo . Chứng minh : Việc chứng minh định lý này có thể suy ra từ định lý đồ thị đóng như sau : Từ các giả thiết của mệnh đề ta suy ra ∃ >0 sao cho với Do F bị chặn địa phương tại xo nên ∃r>0, ∃M>0 để với yo∈ F(xo)ta có: Chọn δ =Min(r, ),chọn U=U(xo, ) ta sẽ chứng minh rằng tồn tại ∃α sao cho Ánh xạ đa trị - Ánh xạ đa diện lồi | 33 Thật vậy : ,nên với có Mặt khác nên Suy ra để Chọn Suy ra Suy ra Định lý 2.2 : Cho F là quá trình lồi , đóng từ không gian X x Y ( X ,Y là các không gian Banach ) Nếu ImF = Y thì F-1 là Lipshitz . Chứng minh : Ta sẽ chứng minh rằng ∃ sao cho Đặt x0 = x = 0, y0= 0 , từ bất đẳng thức ta đuợc : Vì F -1 là thuần nhất dương nên áp dụng bất đẳng thức này cho ta suy ra Bây giờ xem ∀ ε>0 , chọn sao cho Như vậy Cho ε→0 ta có Hay Ánh xạ đa trị - Ánh xạ đa diện lồi | 34 1.2.3 Tính liên tục của ánh xạ đa trị : Cho F là ánh xạ đa trị từ X vào Y với X,Y - không gian định chuẩn.  F là nưa liên tục trên tại x ∈ X nếu : sao cho ∀x ∈ U→ F(x) ∈V  F là nửa liên tục trên nếu F là nửa liên tục trên tại mọi x ∈ X  F là nửa liên tục dưới tại xo nếu • F là nửa liên tục dưới nếu F là nửa liên tục dưới tại mọi x ∈ X . F liên tục tại Xo nếu F nửa liên tục trên và nửa liên tục dưới tại Xo. F liên tục nếu F nửa liên tục trên và nửa liên tục dưới . Định lý 2.3 : Nếu F là, ánh xạ đa trị chặt (DomF = X) , nửa liên tục trên , có giá trị Compact và X là tập Compact thì F(X) là tập Compact . Chứng minh: Xét phủ mở M của F(X) , ta sẽ chỉ ra có phủ con hữu hạn phủ F(X). Với mỗi x ∈ X, F(x) là tập compact , vì M là phủ mở của F(x) nên có phủ con hữu hạn Mx . Đặt Vx= È {Vi/Vi ∈Mx} là lân cận của F(x) . Do F là nửa liên tục trên nên với X đo ,∃x sao cho F(Ux) Vx Xét.{Ux /x∈X}là phủ mở của X ma X là compact nên có phủ con hữu hạn{Ux1,,Uxn} phủ X . Đặt M* = Mxi , với i := 1,.., n thì M * là phủ con hữu hạn của M ta sẽ chỉ ra nó phủ F(X) bằng cách chứng minhF(X) (V/V∈M*) Lấy x ∈ X →∃Ui : x ∈ Ui Khi đó vậy M* phủ F(X) hay F(X) là tập Compact . Định lý 2.4. Nếu. F là nửa liên tục trên có giá trị đóng thì F đóng . Chứng minh: Ta sẽ chứng minh rằng với dãy bất kì(xn,yn) ∈GrF mà(xn,yn) → (xo, y0) thì (xo, y0) ∈GrF Thật, vậy : do F là nửa liên tục trên tại x nên , Vì xn→xonên ∃no sao cho Vì V bất kì chứa trong F(xo) và ánh xạ y → d (y, F(xo) ) là liên tục nên ta có d(yo,F(x0)) = 0 hay yo∈ F(xo) vì F(xo) đóng . Ánh xạ đa trị - Ánh xạ đa diện lồi | 35 .Ánh xạ đa diện lồi . 2.1 Các khái niệm cơ bản . 2.1.1 Các khái niệm liên quan đến hàm . • Hàm lồi thực sự (proper) : Cho f là hàm số có tập xác định Ta nói f là hàm lồi thực sự nếu Epi f ≠ , f(x) > -∞ với mọi X . Dom f ≠ •Hàm dấu : Hàm dấu ứng với tập c là hàm δc:R n→ ̅ định bởi • Hàm nửa liên tục : Cho f là hàm số thực xác định trên S Rn Ta nói f là nửa liên tục dưđi tại x∈ S nếu Điều này có t h ể được biểu diễn như sau : Ta nói f là nửa liên tục trên nếu (-f) là nửa liên tục dưới . Hàm nửa liên tục trên và nửa liên tục dưới tại x gọi là liên tục tại x 2.1.2. Tập đa diện lồi . • Tập đa diện lồi : Ta gọi tập đa diện lồi là tập lồi có thể biểu diễn dưới dạng giao của một số hữu h ạ n các nửa không gian đóng . Tức là có thể xem nó là tập nghiệm đối với hệ hữu hạn các bất phương trình dạng ≤ βi , i:= 1,...,m. A - đa diện lồi Nhận xét : Tập đa diện lồi là tập đóng . • Cực điểm (Extreme point) : Cho c là tập lồi , điểm x∈C gọi là cực điểm của C nếu x không thể biểu diễn dưới dạng bất kì tổ hợp lồi của hai điểm x1 , x2 nào đó thuộc C thỏa x ≠ x1, x ≠ x2 , x1 ≠ x2 . Nói cách khác : x∈ C, X - cực điểm • Phương cực (Extreme direction ) : Trong trường hợp tập lồi C không bị chặn thì ta xem cực điểm tại vô tận là phương cực điểm . •Mặt của tập lồi : Cho hai l ậ p lồi C , C với C’ C Ánh xạ đa trị - Ánh xạ đa diện lồi | 36 • Mặt của tập lồi : Cho hai tập lồi C , C’ với C’ C Ta nói C là mặt của C nếu C’ có tính chất sau : Mọi đoạn thẳng (đóng) trong C có điểm trong tương đối thuộc C’ thì cả hai điểm đầu và cuối của đoạn thẳng cũng thuộc C’ . Nhận xét: Theo định nghĩa trên thì và cá c cũng là mặt của C. Mặt không chiều của C là cực điểm của C . Trường hợp nón lồi thì chỉ có điểm gốc là cực điểm . • Mặt ngoài của tập lồi (Exposed face ) : Cho h là hàm tuyến tính nào đó trên C , gọi C’ là tập các điểm của C mà trên đó h đạt, maximum α thì C là một mặt của C (C’=C {x/h(x)= α}) Mặt, ngoài của c có dạngC Htrong đó H là siêu phẳng tựa với C . • Tập lồi hữu hạn sinh : Tập lồi hữu hạn sinh là bao lồi của tập hữu hạn các điểm và phương . Như vậy C là tập lồi hữu hạn sinh nếu và chỉ nếu tồn tại các vectơ a1,,an sao cho với số k xác định 0 ≤ k ≤ m , C gồm các vectơ có dạng 2.1.3 Vài kết quả liên quan đến tập của đa diện lồi. Định lý 2.5 : Cho C là tập lồi , cho C’ là mặt của C . Nếu D là tập lồi trong C sao cho Chứng minh : Cho z ∈ riD C , nếu X là điểm bất kì của D khác z thì có điểm y ∈ D sao cho z thuộc phần trong tương đối của đoạn thẳng giữa x và y . Vì C’ là một mặt nên x và y đều phải thuộc C , như vậy D C || . Hệ quả 2.5.1: Nếu C là mặt của. tập lồi C thì C’=C ̅ .C’ đóng nếu C là tập đóng . Chứng minh : Đặt D= C ̅, theo định lý trên thì D C C’ có nghĩa là C ̅ C’ và hiển nhiên C’ là tập con của c nên C’= C ̅ || . Việc chỉ ra C’ đóng nếu C đóng là hiển nhiên . Hệ quả 2.5.2 : Nếu C’ và C" là các mặt của tập lồi C sao cho riC' và riC" có một điểm trong chung thì C' = C". Chứng minh : Vì riC’ riC’’ ≠ nên riC’ C’’ ≠ , suy ra C’ C’’ Tương tự ta cũng có C’’ C’, vậy C’ = C’’ || Định lý 2.6 : Cho C là tập lồi khác rỗng , U là, tập hợp lất cả các phần trong tương đối của các mặt khác. rỗng của C . Khi đó tất cả các tập hợp trong U là rời nhau và hợp của chúng bằng C Mỗi tập con của C lồi, mở tương đối đều chưa trong một tập hợp nào đó trong U và tập U này là tập con lồi , mở tương đối lớn nhất của C. Ánh xạ đa trị - Ánh xạ đa diện lồi | 37 Chứng minh : Do hệ qua 2.5.2 thì các phần trong tương đối của các mặt là rời nhau . Cho D là tập con của C sao cho mở tương đối , lồi , khác rỗng . Cho C là mặt nhỏ nhất của C chứa D ( giao của tất cả các mặt chứa D ) . Nếu D chứa trong biên tương đối của C thì có siêu phẳng H tựa với C chứa D nhưng không hoàn toàn chứa C vì rằng ta biết nếu C là tập lồi và D là tập con nào dó của C thì điều kiện cần và đủ để có siêu phẳng tựa với C chưa D là D riC = .Vậy D phải là chứa trong mặt ngoài của C là C’’=C’ H nó là mặt của C và thực sự nhỏ hơn C’. Như vậy D không thể hoàn toàn chứa trong biên tương đối của C và D phải giao với riC , ta sẽ chứng minh riD riC’ Thật. vậy xét tập ( ̅\riC’ ) là tập đóng chứa riD và ̅ nên ta có từ đó riD riC’. Nhưng riD = D như vậy D phải là một trong những tập hợp nào đó của U.Vì rằng các tập hợp của U là rời nhau nên U là tập con lồi , mở tương đối lớn nhất. của C và hợp các tập hợp đó bằng C ||. Định lý 2.7: Cho C là tập lồi đóng , không chứa đường thẳng , cho S là tập tất cả các cực điểm và phương cực của C thì C = conv S . Chứng minh : Định lý hiển nhiên đúng trong trường hợp dim C ≤ 1 . Bây giờ giả sử định lý đúng với các trường hợp dim C 1 ta sẽ chứng minh định lý đúng với trường hợp dimC = m . Theo định nghĩa ta có convS C Vì C không chứa đường thẳng và chính nó không phải là nửa đường thẳng nên nó là bao lồi của biên tương đối của nó , để chỉ ra C convS ta chỉ cần chỉ ra rằng mỗi điểm biên tương đối của C là thuộc convS. Do định lý 2.6 , với X là điểm biên tương đối của C thì X chứa Trong phần trong tương đối nào đó của mặt C do hệ quả 2.5.1 thì C đóng và có số chiều nhỏ hơn C (*) . Áp dụng giả thiết của chứng minh với C thì x ∈ convS' với S' là tập các cực điểm và phương cực của C Vì S’ S nên ta có x ∈ S Tóm lại C = convS || . Định lý 2.8 : Các tính chất. sau đây là tương đương a) C là một đa diện ( Polỵheral) b) C đóng và chỉ có hữu hạn mặt . c) C là hữu hạn sinh . Chứng minh : (*) Xem đlý 11-6 trang 100 Convex Analysis - Rockaffellar (*)Xem hệ qua 18.1.3 trang 164 Analysis - Rockkaffellar Ánh xạ đa trị - Ánh xạ đa diện lồi | 38 : Xem C là giao của hữu hạn các nửa không gian.Ta có C= Hi i:=1,.., m . Gọi C’ ≠ là một mặt của C . Với mỗi i ta có riC’ Int(Hi) hay riC’ Mi với Mi là siêu phẳng bị chặn của Hi . Đặt D là giao của hữu hạn các tập mở lồi tương đối Int(Hi) , D= Int(Hi) với i:=l ... m hay là giao của các Mi , ta có D là tập con lồi của C và nó cũng là tập mở tương đối của C . Vì rằng riC' là tập con lồi, mở tương đối lớn nhất của C nên ta phải có riC' = D . Do chỉ có hữu hạn các tập hợp dạng D như trên và các mặt khác của C có phần trong tương đối rời nhau ( do hệ quả 2.5.2 nếu có điểm trong chung thì các mặt ấy trùng nhau ) nên kéo theo rằng C chỉ có hữu hạn mặt . Trước hết xét trường hợp C không chứa đường thẳng , theo định lý 2.7 thì C là bao lồi của các điểm cực trị và phương cực trị . Vì C chỉ có hữu hạn mặt nên C chỉ có nhiều lắm là hữu hạn điểm cực trị và phương cực trị . Vậy C là hữu hạn sinh . Trường hợp C chứa đường thẳng thì C = Co + L , ở đây L là không gian tuyến tính của C và Co là tập lồi đóng không chưa đường thẳng , còn Co= C L Mặt của Co là có dạng C’o= C’ L với C' là mặt của C thì Co chỉ có hữu hạn mặt . Như vậy Co là hữu hạn sinh . Cho b1,..., bm là cơ sở của L thì mọi x ∈ C đều có thể biểu diễn dưới dạng : . với xo ∈ Co còn các μi và μ'i không âm , i:=l ,,m . Vậy C là hữu hạn sinh . Giả sử C = convS , S là tập hữu hạn các điểm và phương , ta biểu diễn C như là hợp của hữu hạn các đơn hình sinh bởi định lý Caratheodory. Mỗi đơn hình sinh này là một tập đóng vì vậy C cũng là tập đóng . Có một sự tương ứng 1-1 giữa các mặt của C và tập con nào đó của s vì vậy C chỉ có thể có hữu hạn mặt . Ta sử dụng kết quả sau : " Một tập lồi đóng n-chiều trong Rn là giao của các nửa không gian đóng tiếp xúc với nó " (*) . Xét trường hợp C là n chiếu trong Rn thì ta có C là giao của các nửa không gian tiếp xúc với C . Nếu H là siêu phẳng biên của nửa không gian tiếp xúc thì theo định nghĩa sẽ tồn tại X nào đó thuộc C sao cho H là siêu phẳng tựa duy nhất của c đi qua X . Như vậy H là siêu phẳng tựa duy nhất của C đi qua mặt ngoài C H . Vì C chỉ có hữu hạn mặt nên nó chỉ có hữu hạn các nửa không gian đóng tiếp xúc như vậy C là đa diện lồi . Hệ quả 2.8.1: Tập đa diện lồi có nhiều nhất là một số hữu hạn cực điểm và phương cực điểm. Chứng minh : (*)Xem định lý 18.8 trang 169 Analysis của Rockaffellar Ánh xạ đa trị - Ánh xạ đa diện lồi | 39 Do có sự tương ứng giữa các cực điểm và phương cực với mặt của tập đa diện lồi nên ta suy ra được kết quả . 2.1.4 Hàm số đa diện lồi ( Polyhedral Convex function ) .  Hàm số đa diện lồi : Cho C là tập lồi Rn, f là hàm lồi trên C . Ta nói f là hàm đa diện lồi nếu Epi f là một đa diện lồi Nếu Epi f chỉ là đa diện ta nói f là hàm đa diện . Nhận xét : f là hàm đa diện lồi trên Rn thì Epi f là giao của hữu hạn các nửa không gian trong R n+1 • f là hàm đa diện lồi nếu và chỉ nếu f(x) = h(x) + δc(x) ở đây và • Một hàm lồi đuợc gọi là hàm lồi hữu hạn sinh nếu tồn tại các vectơ a1,,ak,ak+1,,amvà các vô hướng αi tương ứng sao cho : ở đây infimum lấy trên các hệ số λi sao cho : Chú ý : Hàm lồi là hàm đa diện lồi nếu nó là hữu hạn sinh. 2.1.5 Các định lý liên quan đến hàm đa diện: Hàm liên hợp của hàm lồi : Cho f là hàm lồi đóng trên X , ta định nghĩa hàm liên hợp f* của f như sau: Hàm tựa của tập lồi : Cho C là tập lồi , hàm tựa của tập lồi C đuợc định nghĩa như sau : Định lý 2.9 : Hàm liên hợp của hàm đa diện lồi cũng là hàm đa diện lồi. Chứng minh : Nếu F là hàm đa diện lồi thì nó là hữu hạn sinh và có thể biểu diễn như trên với các véctơ a1,,ak,ak+1,,am nào đó tương ứng với các vô hướng αi Thay thế công thức của f vào hàm liên hợp f* ta nhận được ở đây supremum lấy trên các λi ≥0 , i:=1,,m và λ1+.λk=1 Nhận thấy rằng khi < αi, x * > - αi ≤ 0 , với i = k +1,...,m thì có : Mặt, khác f*(x*) = + ∞ như vậy f *là hàm đa diện . || Ánh xạ đa trị - Ánh xạ đa diện lồi | 40 Hệ quả 2.9.1. ( Đặc trưng của tập đa diện ) . Tập lồi c đóng là đa diện nếu và chỉ nếu hàm tựa δ*c (.) là hàm đa diện . Chứng minh: Hàm tựa và hàm dấu của c là liên hợp nhau , như vậy theo định lý trên hàm này là hàm đa diện nếu và chỉ nếu hàm kia là đa diện . Ngoài ra giữa hàm dấu xác định trên tập lồi c và bản thân tập lồi c lại có quan hệ sau : c là tập lồi nếu và chỉ nếu hàm dấu δ (. / C) là hàm lồi . Ở đây hàm dấu xác định như sau : 2.1.6 Các phép toán tập các hàm đa diện lồi. Định lý 2.10: Nếu. f1 , f2 là các hàm đa diện lồi thực sự thì f1+f2 là hàm da diện . Chứng minh: Ta có fi (x) = hi (x) + δci (x) với C1, C2là các tập da diện lồi . Đặt C = C1 C2 , dij = ai + bj và thì C là tập đa diện lồi và ta có (f1 + f2 ) (x) = h(x) + δc (x) . Ở đây Như vậy f1 + f2 là hàm đa diện . Định lý 2.11: Nếu f là hàm đa diện thì λ f cũng là hàm đa diện với λ ≥0 2.1.6 Điều kiện để một tập là tập đa diện lồi. Định lý 2.12 : Cho A là phép biến đổi tuyến tính từ Rn→ Rm Với mỗi đa diện lồi C trong Rn thì AC là tập đa diện lồi trong Rm Với mỗi. đa diện lồi D trong Rm thì A-1D là tập đa diện lồi trong Rn Chứng minh : Cho C là tập đa diện lồi trong Rn , do định lý 2.8 thì C là hữu hạn sinh,như vậy tồn tại các vectơ a1 , ... ak , ak+1 , ... ar sao cho Cho bi là ảnh cua ai dưới phép biến dổi thì Vậy AC là hữu hạn sinh và theo định lý 2.8 thì nó cũng là đa diện lồi . Bây giờ cho D là tập đa diện lồi trong Rn . xem D như là tập các nghiệm y với hệ xác định < y, ai * > ≤ αi , i = 1 ,,S thì A -1 D là tập nghiệm x ứng với hệ <Ax, ai * > < αi , i = 1, ... , S Đây là hệ hữu hạn các bất phương trình tuyến tính nên A-1D là đa diện . Ánh xạ đa trị - Ánh xạ đa diện lồi | 41 Hệ quả 2.12.1 : Cho A là phép biến đổi tuyến tính từ Rn vào Rm , với mỗi hàm đa diện lồi f trên Rn, hàm lồi Af là hàm đa diện trên Rm và infimum trong đinh nghĩa đạt được nếu tồn tại . Với mỗi hàm đa diện lồi g trên Rm thì gA là hàm đa diện . Chứng minh: Xét epigraph của f , ảnh của epi f dưới phép biến đổi tuyến tính A từ Rn → Rm : (x, μ ) → (Ax , μ ) là tập đa diện lồi và bằng epi Af vậy Af là hàm đa diện . Ảnh ngược của epi g dưới phép biến đổi tuyến tính này cũng là một đa diện lồi và bằng epi gA . Vậy gA là hàm đa diện . Hệ quả 2.12.2 : Nếu c1, và c2 là các tập đa diện lồi trong R n thì c1 + C2 cũng là, đa diện . Chứng minh : Cho , rõ ràng rằng C có thể biểu diễn như là giao của hữu hạn các nửa không gian trong R2n . Như vậy c là đa diện lồi . Ảnh của c qua phép biến đổi tuyến tính A: (x1, x2 ) → x1 +x2 cũng là đa diện lồi và ảnh này là C1 + C2 . || Định lý 2.13:Nếu c là tập đa diện lồi thì -C , λC cũng là tập đa diện lồi Chứng minh : Xem C là tập tất cả các nghiệm của hệ bất phương trình ≤ βi , i= 1, ... , m Thì λC với λ, > 0 là tập nghiệm của hệ bất phương trình ≤ λβ , i= 1, ... , m . Ngoài ra -C là Ảnh tuyến tính của C bởi phép biến đổi x → - x Từ đó kéo theo λC lả đa diện lồi với λ < 0 . Hơn nữa khi λ =0 thì 0C={0) cũng là đa diện lồi . Định lý 2.14: Nếu A1 , A2 là các đa diện lồi và A1 A2 là tập lồi Thì A1 A2 là tập đa diện lồi . Chứng minh : A1 là tập lồi hữu hạn sinh , A2 cũng là tập lồi hữu hạn sinh nên A1 A2 là hữu hạn sinh . Do A1 A2 là tập lồi nên là đa diện lồi . Ánh xạ đa trị - Ánh xạ đa diện lồi | 42 . Ánh xạ đa trị đa diện (lồi). Trong phần này ta sẽ nghiên cứu chi tiết hơn về lớp các xạ đa trị là ánh xạ đa trị đa diện , đồng thời tìm hiểu các ứng dụng của nó vào bài toán qui hoạch có tham số . 3.1 Định nghĩa : Cho hàm đa trị F : Grf= Γ F = , gọi là đồ thị của hàm đa trị F Xét các phép chiếu tự nhiên π1, π2 từ R n x R m vào R n và vào R m ta có Dom F= π1 (Γ F), Im F= π2(Γ F), Nếu GrF là tập da diện lồi thì ta nói F là ánh xạ đa trị đa diện lồi . Nếu GrF ( không cần lồi ) là hợp của hữu hạn các tập đa diện lồi thì ta gọi F là ánh xạ đa trị đa diện . Nhận xét 1: Nếu F là ánh xạ đa trị đa diện lồi thì F là ánh xạ đóng . Do đó F là ánh xạ đa trị có giá trị đóng . Nhận xét 2: Do có thể đặc trưng tập đa diện lồi bởi hàm tựa của nó nên ta có thể đặc trưng hàm đa trị đa diện lồi bằng hàm tựa của tập GrF. Thật vậy F là ánh xạ đa trị đa diện lồi GrF là đa diện lồi Hàm dấu trên GrF là hàm đa diện lồi Hàm tựa trên GrF là hàm đa diện lồi (Vì hàm tựa và hàm dấu là liên hợp nhau ) Mệnh đề l : Cho F là hàm đa trị có đồ thị là GrF , F là hàm đa trị đa diện lồi khi và chỉ khi hàm tựatrên tập GrF là hàm đa diện lồi . 3.2. Các phép toán . 3.2.1 Định nghĩa các phép toán trên tập các hàm đa diện (lồi): Cho F,G là hai hàm đa trị đa diện lồi từ Rn vào Rm Ta định nghĩa F G là hàm định bởi (F G)(x)=F(x) G(x) F Glà hàm định bởi (F G)(x)= F(x) G(x) F+Glà hàm định bởi(F+G)(x)=F(x)+G(x) F-G là hàm định bởi (F-G)(x)=F(x)-G(x) λ F là hàm định bởi (λF)(x)= (λF)(x) 3.2.2 Các tính chất : Định lý 2.15 : Nếu F,G là các hàm đa trị đa diện thì các hàm đa trị xây dựng nêu trên đều là hàm đa, trị đa diện . Chứng minh: Ánh xạ đa trị - Ánh xạ đa diện lồi | 43 Xem H=F G , ta có GrH là đa diện nên hàm F G là hàm đa diện Hàm F G được chứng minh lương tự . Xem H=F+G , ta có Vì rằng tổng của hai đa diện lồi là đa diện nên GrH là đa diện , có nghĩa F+G là hàm đa diện . Các phần còn lại đều có thể chứng minh tương tự . 3.3 Đặc trưng ánh xạ đa trị đa diện ( lồi ). Vấn đề đặt ra ở đây là có thể đặc trưng ánh xạ đa trị đa diện bởi một hàm đa diện lồi nào đó hay không . Trước hết ta hãy thử khảo sát vân đề này trên R Xét ánh xạ đa trị đa diện lồi F: Hàm đặc trưng Để xem xét hàm này có thể là hàm đa diện lồi hay không ta xét Epi của nó là Nếu giới hạn hàm đặc trưng xác định trên GrF thì rõ ràng Epi χF là đa diện lồi Bây giờ sẽ mở rộng việc chứng minh cho hàm đặc trưng tổng quát Đặt S= GrF , do S là tập da diện lồi nên là hữu hạn sinh tức là : Trong đó là các cực điểm và là các phương cực . Các hệ số λi là không âm và λ1++ λk=1 Bây giờ mỗi điểm thuộc Epi χF đều có dạng ( , μ ) Ánh xạ đa trị - Ánh xạ đa diện lồi | 44 Tức là Epi χ F cũng hữu hạn sinh , vậy Epi χ F là đa diện . Mệnh đề 2: Hàm đa trị F : là đa trị đa diện khi và chỉ khi hàm đặc trưng của nó trên GrF là hàm đa diện lồi. 3.4. Tính Lipshitz : Cho hàm đa trị F : Ta nói F là hàm đa trị Lipshitz địa phương trên tại điểm xo với modul (λ) ( Kí hiệu UL (λ)) nếu với lân cận nào đó của xo và với mọi x∈N ta có F(x) F(xo) + λ ||X - Xo || B ( B là hình cầu đơn vị mở ) . Ta nhắc lại rằng đồ thị của hàm đa trị đa diện là hợp hữu hạn các đa diện lồi, các đa diện lồi này gọi là các thành phần của đồ thị . Bổ đề: Cho p là hàm đa trị. đa diện lồi có đồ thị khác rỗng . Gọi Gi với i:= 1 , ... , k là các. thành phần của nó , cho xo ∈ Dom P. Xác định I={i/xo∈ π1(Gi)} ở đây π1 phép chiếu chính tắc từR n xR m→ Rn Khi đó tồn tại lân cận U(xn) sao cho Chứng minh : Với mỗi i , cả {xo }xR m và Gi đều là các tập đa diện lồi khác rỗng trong R n+m . Nếu i I thì xo π1 (Gi) và như vậy {xo} x R m và Gi là rời nhau và có thể tách nghiêm ngặt . Trong trường hợp đặc biệt có lân cận Ui (x0) sao cho(Ui x R m ) Gi ≠ Đặt. thì U là lân cận của xo vì số thành phần của đồ thị là hữu hạn .Rõ ràng rằng || Nhận xét : Bổ đề này nói lên rằng nếu x ∈ U và y ∈ P(x) thì (x,y) phải thuộc về thành phẩn thứ i là Gi nào dó . Có nghĩa là với xo và y ∈ P(x) thì có Gi chưa ( xo , yo) . Sự kiện này cùng với các kết quả về tập đa diện lồi là cơ sở cho ta nghiên cứu hiếp các tính chất về sự liên tục sau đây. Định lý 2.16: Nếu F là ánh xạ. đa trị đa diện lồi từ thì tồn tại hằng số X sao cho F là Lipshitz địa phương trên với modul λ tại mỗi điểm xo ∈ R n Chứng minh : Nếu GrF= thì không có gì để chứng minh . Ánh xạ đa trị - Ánh xạ đa diện lồi | 45 Xét GrF= với Gi là các thành phần của nó , i := 1 ... k . Với mỗi i đặt hàm da trị Fi như sau : do định lý của Walkup và Wets 11 thì ánh xạ giao Gi π -1 (. ) là Lipshitz trên không gian metric Hausdorff khi nó ≠ . Như vậy có λ i nào đó sao cho nếu Fi (W1 ) ≠ ≠ Fi(Wo) thì Đặt λ = Max λ i với i:= 1, ... , k , chọn X o R n Nếu X o Dom F thì có lân cận nào đó của X o là không với DomF vì DomF là hợp của hữu hạn các tập đa điện lồi . Như vậy F là UL( λ ) tại x 0 tương ứng với lân cận đó . Nếu x 0∈ Dom F , xác định I = ( i / (Gi ) , do bổ đề nêu trên sẽ tồn tại lân cận U(x0) saocho (U X R m ) Gr F Bây giờ chọn X∈ U bất kì , nếu X Dom F thì F(x)= và bao hàm thức được suy ra dễ dàng . Nếu X∈ Dom F thì với y là điểm bất, kì thuộc F(x) ta có (x,y) ∈ , nên với i ∈ I nào đó , (x, y) ∈ Gi và ta biết rằng Fi (x) , Fi (xo) là≠ như vậy Mặt, khác y là tuy ý trong F(x) vì vậy Tiếp sau đây ta sẽ nghiên cứu các kết quả dựa trên định lý này. Có thể bắt dầu với sự nhắc lại khái niệm khoảng cách giữa điểm và tập hợp. Ta có d (x, A ) = Inf {||X - a || a ∈ A } Qui ước nếu Hệ quả 2.16.1. Cho F là hàm đa trị đa diện lồi từ , cho là μ modul kết hợp bởi F-1 trong định lý 2.16 . Khi đó với mỗi y∈R'm tồn tại ε > 0 sao cho nếu X∈R" với d[y , F( x ) ] < ε thì d[ x, F-1 ( y ) ] ≤ μ d (y, F(x)). Chứng minh : Theo định lý 2.16 , tồn tại lân cận của y sao cho trong lân cận đó p' là Lipshitz trên tại y với modul μ . Chọn ε sao cho quả cầu tâm y bán kính ε chứa trong lân cận nêu trên . Nếu X∈Rn với (Uy, F(x) ] < ε thì vì F(x) đóng nên có y ∈F(x) vái d[y F(x)] = || y - y 1 || < ε . Như thế thì Fm (y1 ) F -1 (y) + μ | |y - y 1 || B Nhưng vì X∈F -1 (y1 ) nên ta có 1 A Lipshiteian characterization of convex polyhedra DW Walkup and RJB Wets Proceeding of the American Mathematiccal Society 20 (1969 ) 167-173 Ánh xạ đa trị - Ánh xạ đa diện lồi | 46 Vế phải là nên ta có Suy ra đó là điều cần chứng minh. Nhận xét : Qua định lý này ta thấy nếu F là ánh xạ đa trị đa diện lồi từ thì nó có tính Lipshitz địa phương tại mọi Xo . Điều này không phải lúc nào cũng có đối với hàm đa trị khác. Định lý 2.17 Cho F là hàm đa trị đa diện lồi từ Nếu K là tập con bị chặn nào đó của ImF Thì có tập bị chặn sao cho Chứng minh: Ảnh của F là hợp hữu hạn nhiều tập có dạng với Gi là thành phần thứ i của đồ thị . Vì ảnh tuyến tính của một tập đa diện lồi là đóng nên ImF đóng . Như vậy K cũng là tập con bị chặn của ImF . Không mất tính tổng quát ta giả sử rằng K là Compact , chọn điểm yo ∈ Kbất kì và áp dụng bổ đề cho F -1 để xây dựng một lân cận V cuả y0 sao cho Đặt w lả lân cận đa diện lồi bị chặn chứa trong V và xác định , i = 1,.... , k . Các tập Hi là các tập đa diện lồi Compact như vậy mỗi Hi là bao lồi của những điểm cực trị của nó .Vì vậy với mỗi i , hàm lồi đạt tới cực đại trên Hi ( tại điểm cực trị ) gọi là μi .Đặt μ = Max μi , i=l,...., k . Nếu y ∈ W ImF với i nào đó , ta có. y ∈ Hi Như vậy tồn tại X với (x,y) ∈ Gi (tức là y ∈ F(x)) và Như vậy Bây giờ , với mỗi điểm của K , một lân cận tương đối có dạng W ImF có thể đuợc xây dựng và do tính Compact , một số hữu hạn của các lân cận loại này sẽ phủ K . Mỗi lân cận như thế chưa trong ảnh của quả cầu dưới tác động của F và ta có kết quả cần chứng minh. Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 47 PHẦN 3 Vài ứng dụng của ánh xạ đa trị & Ánh xạ đa trị đa diện lồi vào bài toán qui hoạch có tham số. Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 48 I. Áp dụng các kết quả của ánh xạ đa trị đa diện lồi vào bài toán qui hoạch có tham số. Cho f:R n Rm →R A : hàm đa trị đa diện từ Rn vào Rm h : R m→ [-∞,+∞] định bởi h(z)= Inf {f(x,z)/x ∈ A-1 (z)} biểu diễn giá trị tối ưu là hàm theo tham số z . Xác định Dom h={z / h(z)< +∞} Ta sẽ chứng minh hai kết quả tổng quát về sự liên tục cho hàm h . Định lý 3.1. Cho f: R n Rm → R , A là hàm đa trị đa diện từ Giả sử rằng f là Lipshitz trên tập mỗi tập con bị chặn củaRnxRm Nếu z0 là một điểm của. Dom h sao cho A -1 (z0) bị chặn thì với mọi z gần z0 ta có :h(z0)-h(z) ≤ L || z-z0|| với L nào đó chỉ phụ thuộc vào || z0 || và tập bị chặn A -1 (z0) Chứng minh : Cho hai số xác định α và β, f là Lipshitz với Modul λ trên tập . Với A-1 là hàm đa trị , cho μ >0 là hằng số Lipshitz điạ phương đôi với hàm đa trị A-1, xác định L= λ (1+ μ)Chọn bất kì z0 ∈ α β với A -1 (z0) βB. Cho N là lân cận của Z0 sao cho N z0 +μ -1 Bvà với mỗi z ∈ N Chọn z ∈ N , nếu z Dom h thì bất đẳng thức cần chứng minh được thoả . Nếu z ∈ Dom h thì z ∈ DomA-1.Chọn ε >0 và tìm x (z) ∈ A-1 với |f(x,z)-h(z)| ≤ ε Nhận thấy rằng từ ta có và (ii) với Xo nào đó Thì Cho ε →0ta nhận đuợc kết quả cần chứng minh . Trong kết quả này ta đã giả sử với một điều kiện mạnh hơn đó là tập chấp nhận đuợc A -1 (zo)là bị chặn . Có thể bỏ bớt giả thiết này nếu tập nghiệm tối ưu của bài toán cực tiểu là đa diện lồi . Định lý 3.2 . Cho f : R n X R m→ R và A là hàm đa trị từ Rn vào Rm ,Giả sử rằng f là Lipshitz trên mỗi tập con bị chặn của, Rn X Rmvờ, hàm đa. trị P: định bởi P(z) = { x ∈ (z) | f(x,z) = h(z)} là hàm đa diện Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 49 Thế thì với mỗi tập bị chặn Q Rm, có một hằng số L sao cho nếu zo∈Q Dom P thì với mỗi z ∈ Dom p gần với zo ta có ||h(z)- h(zo) || ≤ L|| z-zo || Hơn nữa h là Lipshitz trên mỗi tập con lồi , bị chặn của DomP . Chứng minh : Cho là hằng số Lipshitz trên ddiạ phương đối với P (định lý 2.16 phần 2 ). Chọn tập bị chặn Q Rm nào đó , cho Q αB và cho β đủ lớn sao cho P -1 (βB) [(α+l)B] DomP (định lý 2.17 phần 2 ) . Cho f là Lipshitz trên tập { (x, z) / || X || < p + y , || z || ≤ α +1 } với modul λ , xác định L = λ (y +1) . Bây giờ chọn zo Q Dom P , cho N là lần cận của zo chưa trong zo +B sao cho nêu z ∈ N thì P(z) P(z0) +Y || z - zo || B . Chọn bất kì z ∈ N DomP thì vì z ∈ (α+1 )B DomP có X nào đó∈ P(z) với || X 1||≤ β . Thế thì có xo∈ P(zo ) với ||x - xo || ≤ y || z - zo ||≤ y (tức là ||xo || ≤ β + y) và ta có Theo chứng minh trên rõ ràng rằng trên mỗi tập con lồi, bị chặn của Dom p thì h là Lipshitz . Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 50 II. ứng dụng ánh xạ đa trị dể nghiên cứu về hàm tập nghiệm tối ưu trong bài toán qui hoạch có tham số. Cho R n và R m là các không gian vectơ hữu hạn chiều có trang bị chuẩn Euclide || . || và tích vô hướng . Cho f : R m x R n → R là hàm số thực . n : Rm → Rn là hàm đa trị . Xét bài toán qui hoạch phụ thuộc tham số X ( tham số nhiễu ) sau: Với mỗi xét bài toán : (Làm cực tiểu f(x,y) theo y∈ Ω (x)) Gọi M(x) là tập tất cả các nghiệm của nghĩa là Như vậy ta có thể định nghĩa ánh xạ đa trị sau : Gọi hàm là hàm giá trị tối ưu . Qui ước Trong trường hợp này ta giả sử hàm đa trị Ω (x)có dạng I, J là các tập chỉ số hữu hạn Sau đây ta sẽ nghiên cứu về tính liên tục và Lipshitz của hàm đa trị M(x) tập các nghiệm tối ưu . Giả sử rằng miền chấp nhận được Ω (xo)ứng với xo là khác rỗng. Kí hiệu là khoảng cách từ điểm y đến tập S . Kí hiệu V = P(y, S) là điểm thuộc tập S gần với y nhất , tức là ||y - V || = dist (y, S ) . Với L là không gian con tuyến tính trong Rn , kí hiệu không gian con trực giao của L là L , ở đây 2.1. Các kết quả về liên tục : Lấyxo ∈ R n , giả sử M(xo) ≠ , giả sử r và gi với i ∈ I J là các hàm C' trên R m x R n . Với điểm (x,y) , đặt Với x=xo đặt Jo(y) = J(xo , y) . Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 51 Ta nói rằng điều kiện Mangasarian Promovit.z (MF) nhận được tại điểm ̅ ∈ Mo nếu : 1.Vectơ Gradient là độc lập tuyến tính . 2.Tồn tại vectơ V sao cho : Xét hàm Lagrange liên kết với bài toán qui hoạch PX : Dựa theo điều kiện (MF) nêu trên , điều kiện cần cấp 1 Kuhn Tucker nhận đựơc tại ̅. Điều này có nghía là tồn tại vectơ ̅ = ̅ ( ̅) của nhân tử Lagrange sao cho ̅ ≥0với i ∈ Jo ( ̅) và ̅ =0 với I ∈ J\Jo( ̅) Tập các nhân tử Lagrange thỏa điều kiện cần cấp 1 tại (xo, ̅) được kí hiệu là Ao ̅. Ta biết rằng tập Ao ̅ bị chặn nếu và chỉ nếu điều kiện MF nhận được tại ̅. Trong trường hợp này Ao ̅) là khác rỗng, compact, đa diện lồi và như vậy nó là bao lồi của tập hữu hạn Eo ̅các điểm cực trị . Giả thiết 1: Điều kiện inf -Compact . Tồn. tại số α và tập compact S R sao cho φ (xo)< α và với mọi x thuộc lân cận của xo Từ giả thiết trên có thể suy ra rằng với mọi x thuộc lân cận của xo thì lập nghiệm tối ưu M(x) là khác rỗng và M(x) là compact khi mà tập chấp nhận đuợc Ω(x) là khác rỗng 1 Nếu điều kiện inf - Compact được thoả và điều kiện (MF) nhận đuợc tại yo ∈Mo nào đó thì hàm M(x ) là đóng tại x0. Điều này có nghĩa là tập các điểm tụ của M(x) là chứa trong Mo ,M’ Mo Chúng ta sẽ giới hạn chính xác hơn về tập các điểm tụ của tập nghiệm tối ưu . Xét đường cong tiếp xúc với vectơ h. Kí hiệu y ∈ Mo r ∈ o(y) 1 Xem Fiacco AV 1983 Introduction to Sensivity and stability Analysis in Nonlinear Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 52 Mệnh đề sau đây liên quan đến các kết. quả của Gauvin và Dubeau về đạo hàm cấp 1 theo hướng của hàm giá trị tối ưu Mệnh dề 1: Nếu điều kiện (MF) và điều kiện, Inf -Compact được thỏa tại mỗi điểm ,y ∈Mo thì Chứng minh : Xét điểm ̅ ∈ lim sup M(x(t)), theo định nghĩa của lim sup , tồn tại dãy {tn →0 +}và yn→ ̅ sao cho yn ∈M(xn) với xn=x(tn).Ta có ̅ ∈ Movà như vậy điều kiện MF thoả tại (xo, ̅), kéo theo hàm đa trị Ω là giả Lipshitz tại (xo, ̅). Điều này suy ra rằng sẽ tồn tại vn ∈ Ω (xo) sao cho ||yn-vn|| ≤ K||xn-xo||, ∀n và k > 0 nào đó . Hơn nữa vn có thể chọn sao cho với λo∈ Eo( ̅) nào đó , ở đây Vì rằng tập Eo( ̅) là hữu hạn , ta có thể giả sử rằng thế thì ta có Tương lự ta cũng có Như vậy ta có : Áp dụng định lý về giá trị chính cho vế phải ta có : ở đây (x*n, y * n) là điểm thuộc khoảng giữa (xn , yn ) và ( xo , vn ). Ta có do điều kiện cần cấp 1 Từ ||yn - vn || ≤ K|| xn - xo || và (*) kéo theo rằng : Như vậy : Mặt khác lim sup ở vế trái ≤ δ (h) và như vậy : Và như vậy có ̅ ∈ M1 *(h) và suy ra điều phải chứng minh . Bây giờ xét trường hợp x=xo tương ứng với bài toán qui hoạch lồi Po Tức là f(xo, .) và gi (xo, . ) , i ∈ J được giả sử lồi và gi (xo, .) với i∈I là hàm affin thì tập Ao(y) Ao của nhân tử Lagrange là như nhau với mọi Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 53 y∈ Mo và nếu điều kiện MF thoả mãn tại y ∈ Mo nào đó thì nó thoả tại mọi y ∈ Mo . Trong trường hợp hàm lồi , đạo hàm theo hướng của hàm giá trị tối ưu được cho bởi δ(h) và kết. quả của mệnh đề này được làm tốt hơn bằng mệnh đề sau : Mệnh đề 2 : Giả sử rằng bài toán qui hoạch ,Po là lồi , các điều kiện Inf -Compact , điều kiện (MF) được thỏa thì Chứng minh : Xét điểm là các dãy tương ứng sao cho yn∈ M(xn) , xn = x(tn ) . Xét, điểm ̅ ∈ Ao và cho λn là vectơ của nhân tử Lagrange tương ứng với điểm (xn , yn) thì và do giả thiết lồi nên Như vậy φ(xn) - φ(xo) = L (xn , yn, λn ) - L(xo , ̅, ̅) ≥ L (xn , yn ̅) - L(xn , yn, ̅) và như vậy do định lý giá trị chính Vì ̅ là điểm tùy ý của Ao ta nhận được Mặt khác Lim sup ở vế trái ≤ δ (h) suy ra ̅ ∈ M1(h) nên suy ra đpcm. Giả thiết 2: ( Điều kiện độc lập tuyến tính ) Với mỗi ̅ ∈ Mo, vectơ gradient ygi(xo, ̅) là độc lập tuyến tính Từ giả thiết trên kéo theo rằng với mọi y ∈ Mo , tập Aoy của các nhân tử Lagrange là đơn trị , Aoy={ ̅(y)}.Cũng theo giả thiết 1 và 2 thì là đạo hàm theo hướng φ (Xo , h ) của hàm giá trị tối ưu và M1 * (h)=M1(h) với mọi h . 2.2 Tính liên tục Lipshitz trên của hàm đa trị tối ưu . Bây giờ ta sẽ nghiên cứu dáng điệu Lipshitz của hàm đa trị M(x) . Trước hết ta nhắc lại định nghĩa về Lipshitz theo từng điểm Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 54 Định nghĩa 2.1: Hàm đa trị gọi là Lipshitz trên theo từng điểm tại x0 với modul μ nếu ϕ(x) ϕ(x0)+ μ ||x-x0||B∀x ∈ lân cận của x0 Hàm đa trị ϕ gọi là Lipshitz tại xo theo hướng h nếu tổn tại một số dương μ sao cho với mọi đường cong dạng x(t)=x0+th+o(t), có ε > 0 sao cho ϕ(x) ϕ(x0)+ μtB với mọi t ∈ [0, ε) Hiển nhiên rằng nếu ϕ là Lipshitz trên theo từng điểm tại x0 thì ϕ là Lipshitz trên tại x0 theo mọi hướng h , ngược lại cũng vậy . Bây giờ giả sử rằng các hàm f và gi , i ∈ I J là C 2 trên R m X R n và có điều kiện độc lập tuyến tính trong giả thiết. 2. Với điểm y ∈ Mo và ̅= ̅(y) , xét nón đa diện lồi ở đây Nón C(y) đuợc gọi là tới hạn và xuất hiện mối liên quan với điều kiện tối ưu cấp hai . Nếu y’∈ Mo thì Ma trận Hessian là xác định không âm trên C(y*) tức là Điều kiện đủ cấp hai tương ứng của nghiệm chấp nhận được ̅ thỏa điều kiện cần cấp một để làm cực tiểu địa phuơng là xác định dương trên C( ̅) Xét. tập của dạng toàn phuơng tương ứng với ma trận trên nón C(y). Giả thiết 3: Với mọi y ∈ M1(h) hai điều kiện sau là nhận đuợc : (i) Tồn tại lân cận Ny của y sao cho Tức là tập chỉ số Jo(v) là hằng số ∀v ∈ Mo trong lân cận của y . (ii) Tập nghiệm tối ưu Mo là đa tạp trơn trong một lân cận của y và NS(y) T(y,Mo). ở đây T(y, Mo) là không gian tuyến tính tiếp xúc với Mo tại y . Chú ý rằng điều kiện (i) của giả thiết 3 nêu trên là nhận được một cách tự nhiên nếu tất cả các nhân tử Lagrange ̅ ,i ∈ Jo(y) là dương .Trong trường hợp này nón C(y) trở thành một không gian tuyến tính .Do điều kiện tối ưu bậc hai , không gian tiếp xúc T(y, Mo) nếu tồn tại được chứa trong tập NS(y) và như vậy từ (ii) trên ta có NS(y) = T(y, Mo). Hơn thế nữa điều kiện trong (i) kéo theo rằng T(y, Mo) và NS(y) đuợc chứa trong không gian tuyến tính {v:<v, y gi(xo,y)>=0, i ∈ I Jo(y)} của nón C(y) . Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 55 Định lý 3.3 Giả sử rằng các giả thiết, 1, 2, 3 được thỏa thì tập nghiệm tối ưu của hàm đa trị M là Lipshitz trên tại xo theo hướng h . Chứng minh: Giả sử rằng sự khẳng định trong định lý trên là sai như thế tồn tại dãy {tn}→ 0 + và yn ∈ M(xn),xn=x(tn) sao cho Ở đây dn = dist (yn, Mo) . Giả thiết. 1 và 2 kéo theo rằng dn → 0 . Cũng như vậy , tập Mo là đóng và như thế tồn tại điểm y*n = P(yn, Mo) gần với yn Xét Vn =yn - y * n , Do lập luận của tính compact , ta có thể giả sử rằng {yn} hôi tụ về điểm ̅ ∈ Movà dn -1 vn dần về vectơ V . Dĩ nhiên ||v||= 1 và như vậy V ≠ 0 . Do mệnh đề 1 ta có ̅ ∈ M1(h). Do đó từ giả thiết 3 (ii) ta nhận được Mo là đa tạp trơn gần y và dẳng thức NS(y)= T(y, Mo) là nhận được . Bởi vì yn * là gần với điểm yn của Mo nó kéo theo rằng với n đủ lớn Vn là trực giao với Mo tại y*n và như vậy V là trực giao với Mo tại ̅. Cùng với việc NS(y) = T(y, Mo) điều này kéo theo rằng V là trực giao với không gian vectơ NS( ̅) Xét một hàm ràng buộc g , do định lý giá trị chính ta có ở đây ( ̅n, ̅n) →(x0, ̅ )> Do giả thiết 3(i) với n đủ lớn ta có : Nếu λn cũng là vectơ của nhân tử Lagrange liên kết với điểm (xn, yn) thì do lập luận của tính liên tục , với n đủ lớn , nhân tử Lagrange λn,i tương ứng là dương với mọi i∈ J+ ( ̅, ̅), ̅ = ̅( ̅) nó kéo theo rằng gi(x0,y * n)= 0,i ∈ I J( ̅) Ta nhận được vế trái của (**) bằng 0 khi i ∈ I J+ ( ̅, ̅) và bé hơn hoặc bằng 0 khi i∈ Jo( ̅) /J+ ( ̅, ̅), Điều này cùng với (*) và (**) kéo theo rằng: Tức là v ∈ C( ̅). Hơn thế nữa V là trực giao với NS( ̅) và như vậy V không thuộc về NS( ̅) Thế thì từ điều kiện cần cấp hai nó kéo theo rằng : Bây giờ với Thế thì Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 56 với. Chú ý rằng do điều kiện cần cấp một, áp dụng vào điểm(xo,yn * , n * ), hạng tử trong khai triển Taylor nêu trên biến mất . Từ việc lim t-1ndn=∞khi n→ ∞ và khai triển Taylor nêu trên kéo theo rằng ở đây ε là số dương xác định nêu trên . Mặt khác do giả thiết 2 về sự độc lập tuyến tính tồn tại dãy { wn} và hằng số dương K sao cho gi(xn.wn)=0, I ∈ I Jo ( ̅) và Thế thì với n đủ lớn , Kết. quả là .Áp dụng công thức Taylor nêu trên cho vế phải của bất đẳng thức này và với ta nhận được với c là hằng số dương c nào đó , cùng với lim t-1ndn=∞, điều này kéo theo rằng Điều này mâu thuẫn với Hệ quả : Giả sử rằng các giả. thiết 1 và 2 là nhận được và. điều kiện (i) và (ii) trong giả thiết 3 là thoả. mãn với mọi y ∈ Mo. Thế thì hàm đa trị M(x) là Lipshitz trên theo từng điểm lại xo . Chứng minh : Giả sử rằng khẳng định trên là sai , thế thì tồn tại dãy {xn}→xo và yn ∈ M(xn)sao cho lim t -1 ndn=∞ là nhận đuợc với với tn=||xn-xo||.Do lập luận của tính compact ta có thể giả sử rằng dãy {t-1n(xn-xo)} hội tụ về vectơ h . Thế thì M không phải là Lipshitz trên theo hướng h , điều này trái với kết. luận của định lý 3.3 nêu trên . Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 57 LỜI KẾT Vừa rồi chúng ta đã điểm qua một vài kết quả của bài toán qui hoạch phi tuyến trong đó tính lồi đóng vai trò quan trọng trong các kết quả được tìm ra . Đối với bài toán qui hoạch đơn trị , dựa vào tính lồi , các dấu hiệu về nghiệm của bài toán cực tiểu được thiết lập, đồng thời cũng thiết lập đựơc mối quan hệ giữa các bài toán điểm yên ngựa Kuhn Tucker và Fritz John với bài toán cực tiểu và cực tiểu địa phương . Tiếp tục tìm hiểu về bài toán qui hoạch là phần tìm hiểu về bài toán qui hoạch lồi và qui hoạch có tham số . Ở trong phần tìm hiểu về qui hoạch lồi ta đã chỉ ra được bằng cách nào mà có thể đặc trưng được nghiệm tối ưu của bài toán qui hoạch thông qua điểm yên ngựa của hàm nhân tử Lagrange . Cuối cùng dựa vào các kết quả của hàm đa trị , đặc biệt là đa trị đa diện lồi đã cho ta đã có thể tìm hiểu về sự liên tục , sự Lipshitz của hàm tập nghiệm tối ưu trong bài toán qui hoạch có tham số . Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 58 Tài liệu tham khảo [1] Rockaffelar. Convex Ananlysis Princeton University Press 1970 [2] Jean-Pièrre Aubin & Hélènne Frankowska Set-Valued Ananlysis Birkhauser Boston 1990 [3] Mangasarian Nonlinear Programming Mac Graw – Hill Book Company 1982 [4] Trịnh Công Diệu Bài giảng về ánh xạ đa trị ĐHSP Tp HCM 1994 [5] Alexander Shapiro Applied Mathematics and Springer – Verlag Optimization Newyork 1988 [6] Stephen Robinson Some continuity property North Holland Of Poloyhedrad multifunction Punlishing Company 1979 [7] Stephen Robinson Extract from Mathematical Methods of Nonlinear Optimization 1992 Ứng dụng ánh xạ đa trị vào bài toán qui hoạch bài toán qui hoạch có tham số | 59 MỤC LỤC Một số khái niệm ban đầu . ............................................................................................ 4 PHẦN 1 Bài toán qui hoạch phi tuyến đơn trị . ................................................................ 5 Hàm lồi và hàm lõm . ............................................................................................ 6 .Bài toán qui hoạch phi tuyến đơn trị ..................................................................... 10 2.1 . Bài toán cực tiểu và điểm yên ngựa . .................................................................. 10 2.2. Vài kết quả vê bài toán cực tiểu và cực tiểu địa phương . ...................................... 11 2.3 Điều kiện đủ của tiêu chuẩn tối ưu ....................................................................... 12 2.4 Bài toán cực tiểu mở rộng. .................................................................................. 13 2.5 Điều kiện cần của tiêu chuẩn tối ưu. ..................................................................... 14 2.6 Định lý Kuhn Tucker.......................................................................................... 17 Bài toán qui hoạch lồi. ......................................................................................... 22 PHẦN 2 Ánh xạ đ a trị -Ánh xạ đ a d i ệ n lồi - Ánh xạ đ a trị đ a d i ệ n l ồ i . ............. 29 §1. Ánh xạ đa trị :.................................................................................................... 30 1.1 Các khái niệm cơ bản : ....................................................................................... 30 1.2 Ánh xạ đa trị Lipshitz địa phương. ....................................................................... 32 .Ánh xạ đa diện lồi . ............................................................................................. 35 2.1 Các khái niệm cơ bản . ....................................................................................... 35 2.1.2. Tập đa diện lồi . ............................................................................................. 35 2.1.3 Vài kết quả liên quan đến tập của đa diện lồi. ..................................................... 36 2.1.4 Hàm số đa diện lồi ( Polyhedral Convex function ) . ........................................... 39 2.1.5 Các định lý liên quan đến hàm đa diện: .............................................................. 39 2.1.6 Các phép toán tập các hàm đa diện lồi. .............................................................. 40 2.1.6 Điều kiện để một tập là tập đa diện lồi. .............................................................. 40 . Ánh xạ đa trị đa diện (lồi). .................................................................................. 42 3.2. Các phép toán . ................................................................................................. 42 3.3 Đặc trưng ánh xạ đa trị đa diện ( lồi ). .................................................................. 43 3.4. Tính Lipshitz : .................................................................................................. 44 PHẦN 3 Vài ứng dụng của ánh xạ đa trị & Ánh xạ đa trị đa diện lồi vào bài toán qui hoạch có tham số. ..................................................................................................................... 47 I. Áp dụng các kết quả của ánh xạ đa trị đa diện lồi vào bài toán qui hoạch có tham số. .. 48 II. ứng dụng ánh xạ đa trị dể nghiên cứu về hàm tập nghiệm tối ưu trong bài toán qui hoạch có tham số. ............................................................................................................. 50 LỜI KẾT ................................................................................................................... 57 Tài liệu tham khảo ...................................................................................................... 58 MỤC LỤC ................................................................................................................. 59