Chương 1 Một số kiến thức chuẩn bị Trong chương này chúng tôi trình bày một số kiến thức chuẩn bị về tập lồi, hàm lồi, bài toán tối ưu lồi và bài toán đối ngẫu cũng như các điều kiện tối ưu được dùng trong toàn bộ luận văn. Các kết quả trong chương này được tham khảo chủ yếu từ các tài liệu [1, 4, 8, 13].1 Khái niệm về tập lồi và hàm lồi trong IR" 1.1 Tập lồi Định nghĩa 1. Đoạn thẳng nối hai điểm # và y trong R” 1A tap hợp các véctơ z có dạng {z € R'|lz = Àz + (1— À),À e [0, 1]}. Một tập Œ C ]R” được gọi là một tập lồi nêu C chứa mọi đoạn thẳng nối hai điểm bất kỳ của nó.
Tức là, Œ là tập lồi nếu Vz, € Œ,A € [0,1] = Àz + (1— À)w € Œ.,n} la tap loi. (b) Tap C = [—2;3) la tap loi trong R. (c) 7@p Œ = (—2;0)UJ(0;3) không là tập loi trong R.2 Hàm lồi Định nghĩa 1. Với một hàm ƒ:R" — R|J{+co}, miền hữu hiệu domƒ, đồ thị Grƒ và trên đồ thị eplƒ của nó được định nghĩa là các tập hợp domf := {x € R"|f(x) < +oo}, Grf := {(2, f(x)) € R" x R|x € domf}, epif := {(x,t) € R" x R| f(x) < t}.
Khi domƒ zZ Ú, ta nói ƒ là hàm chánh thường. Cho hàm (chính thường) ƒ: R“ — RU{+co}. Lr Hàm ƒ được gọi là nửa lién tuc dudi trén R” néu no nita lién tuc dudi tại mọi điểm trong R”. (ii) Ham f được gọi là hàm nửa liên tục trên nêu — ƒ là hàm nửa liên tục dưới.
Cho hàm (chính thường) ƒ : IRh — RJ{+o©}. Khi đó các phát biểu sau đây là tương đương: (i) ƒ là nửa liên tục dưới. (it) epif la tap đóng trong IR" x R. (iu) Với mỗi t € R tập múc dưới [ƒ < †] là đóng trong R”.
() (fj)jey là họ các hàm núa liên tục dưới thà hàm ƒ := sup ƒ; nhận jes duoc bing cach lay supremum theo titng diém f(x) := sup f;(x) cũng jes là ntta lién tuc dudi. (ii) Nếu ƒ uà g đều là nửa liên tục dưới thà hàm tổng ƒ + g cũng là nửa liên tục dưới. Một hàm ƒ : R" —> RỤJ{+ee} là lôi nếu domƒ là một tập lồi và Vz,+ € domƒ, 0 < À < 1, ta có Z@# + (1= Ajg) < Àƒ(z) + (1— À)Z0): e Hàm ƒ gọi là lồi chặt nếu: Vz, € domƒ, z #,0<À< 1 #(@#z + (1= À)g) < Àƒ(z) +(1—= À)ƒ0): e Hàm ƒ gọi là iốm nêu —ƒ lồi. Cho hèm (chính thường) ƒ : R" > RU{+00}.
Khi do f la loi néu va chi néu epif la mot tap loi trong Re, Trước khi đi đến các kết quả tổng quát hơn, chúng ta xem xét về tính chất khả vi cũng như tiêu chuẩn đạo hàm đặc trưng tính lồi. Cho ƒ là hàm số khả ti trên một tập lồi mỏ CCTR". Khi đó các phát biểu sau là tương đương: (i) f la ham loi trén C. Cho f la kha vi liên tục cấp hai trong một tập lồi mé CCR”.
Khi đó ƒ là lồi khá uà chỉ khi Vˆ?ƒ(%) > 0 uới z € Ở bất hà., ƒ„ là các bầm lỗi chính thường tồ Àt,., À„ là các tham số đương. Khi đó, nếu (\g_\ domjf, # 0 thi f := `Akfi cũng là k=1 hàm lồi chính thường. () Nếu (ƒ;)¡cr là một họ các hàm lỗi. Khi đó ƒ : z => sup ƒ¡(œ) cũng là iel một hàm lồi.
(iit) Néu f :R" > RU{+o0} la ham lỗi uà ó : R” — IR" là ánh xạ affine sao cho domf Nd(R™) 4 O thi hop thành ƒ o Ò cũng là một hàm lồi. Cho hàm lồi (chính thường) ƒ : R" > RU{+oo}. Ta ndi 2* € R” 1a dudi dao ham (hay subgradient) cia ƒ tại z nêu (a*,z—a) + f(x) < ƒ(),Vz € R". Kí hiệu tập hợp tất cả các dưới đạo hàm của ƒ tại z là ؃(+).
Vậy Of (2) là một tập (có thể bằng Í) trong R". Khi ؃(z) # Ú, thì ta nói hàm ƒ khả dưới vi phân tai zx. Néu ƒ khả vi tai x thi Of (x) chỉ gồm duy nhất mot diém va Of (x)= {Vf (x)}. Cho hàm (chính thuong) f : R? + RU {+00}.1) xeER” được gọi là hàm liên hợp của ƒ.
W3 ƒ* là supremum theo từng điểm của một họ các hầm a[line nên nó là lôi. Giá sử f : R° 4 RU{+oo} là hàm lồi chính thường nủa liên tục dưới. Khi đó hàm liên hợp f* cũng là hàm lồi chính thường 0à nửa liên tục đưới. Nếu ƒ : R" — R(J{+ee} là hàm lồi chính thường nửa liên tục dưới thà ta có Ƒ** = ƒ.
Cho trude ham lồi chính thường nữa liên tục dưới ƒ : R" — R|(J{+co}. Khi đó các phát biểu sau đâu là tương đương: (i) Vecto p la một subgradient của ƒ tại œ. (iti) Vecto x la mét subgradient ctia f* tai diém p. Cho f : R” > RU {+00} la mot ham lồi chính thường.
Khi đó, một điểm x* € R” la cực tiểu toàn cục của ƒ nếu uà chỉ nếu nó thỏa mãn bao hàm thức sau đâu 0€ Of(a*). Cho f : R” ~ RU {+00} 1A ham 16i ntta lién tục dưới. Toán tử proximity của hàm ƒ, kí hiệu prox;, được xác định bởi prox, : R" > R" y+ 2" = prox;(y) = argmin (f(x) + Ely — 21?) trong đó ||.|| là chuẩn Euclide thong thường. Hàm cực tiểu bên phải là lồi mạnh, vì vậy nó có duy nhất một cực tiểu cho mỗi ¿ € IR*" (ngay cả khi domf ¢ R").
Nói cách khác, prox/(w) = (9ƒ + 1) `(0). Để tiện sử dụng về sau, chúng tôi dùng kí hiệu F(X) để chỉ tập các hàm lồi, nửa liên tục dưới trên X.2 Bài toán tối ưu lồi Cho # Œ C R" và ƒ : Œ — R. Xét bài toán min f(x).2) LEC Bài toán này được hiểu là tìm một điểm #* sao cho ƒ(#*) < ƒ(+) với mọi LEC. e Mỗi điểm z* € Œ được gọi là một phương án chấp nhận được của bai toán (1.
Tập Œ được gọi là miễn (tập) chấp nhận duoc (tap rang buộc). e Ham ƒ được gọi là hàm mục tiêu của bài toán (1.2) là bà¿ toán tối ưu lồi nêu Ở là tập lồi đóng và hàm mục tiêu ƒ là lồi. Cho Ở C ïR" và ƒ : Ở — R. z* € Ở được gọi là điểm cực tiểu toàn cục của f trén C néu f(x) > f(2*) với z € Ở bất ki.+* € Ở được gọi là điểm cực tiểu toàn cục ngặt của ƒ trên Ở nếu f(x) > f(a*) với z* # z € Ở bất kì.
z* € Ở được gọi là điểm cực tiểu địa phương của ƒ trên Ở nếu tồn tại r >0 mà ƒ(#) > ƒ(œ*) với z € CN B(a*,r) bat ki. +” € Œ được gọi là điểm cực tiểu địa phương ngặt của ƒ trên Ở nêu tồn tại r > 0 mà ƒ(#) > ƒ(4°) với z* # + € CñnB(+*,r) bất kì. Cho f : C > R la ham loi duoc rac dinh trén tap loi Œ. Nếu z* € Œ là cực tiểu địa phương của ƒ trên C thi x* cting la cuc 2 ` ? “A tiểu toàn cục của f trên Œ.
Cho f : C > R là hàm lôi ngặt được sác định trên tap loi C. Néu x* € C la cuc tiéu dia phuong cia f trén C thi x* cing la cực tiểu toàn cục ngặt của f trén C.1 Tồn tại nghiệm và điều kiện tối ưu Mệnh đề 1. Giả sử ƒ là nửa liên tục dưới, tà ƒ thôa mãn điều kiện búc trên tập đóng Ở, tức là củ" ƒ(z) — +œ. Khi đó, bài toán (1.9) có ít nhất một nghiệm.
Nó có một nghiệm duy nhất nếu hàm f la hàm lồi chặt trên tập lồi đóng Œ. Giả sử ƒ là hàm lồi chính thường nửa liên tục dưới, va kha vi Gateaur vdi dao ham lién tuc V f(x). Khi dé néu x* € C, thi ba diéu kién sau day la tuong duong voi nhau: (i) «* là nghiệm của (1. Cho ƒ là hàm khả vi liên tục trên tập lồi đóng Œ.
Khi đó zø* € Œ được gọi là điểm đừng nếu Vƒ(œ*)(œ—z*) > 0 với z € Œ bất kì. Néu C = JR", khi đó điểm dừng của (1.2) là điểm x* théa man Vf (2*)"(@— a") > 0, (1.3), ta thu duoe — ||V f(a*)||? > 0, nghia la V/@*) =0. Do đó, khái niệm điểm dừng của một hàm số tà điểm đừng của một bài toán cực tiểu trùng nhau khả bài toán không bị ràng buộc.2 Đối ngẫu Lagrange Bằng cách thêm giá trị {+co} nếu cần thiết, bài toán tối ưu lồi (1.2) luôn được viết lại dưới dạng min f(x), (P) xeER" véi f : R" — RU {+00}. Trong mục này, chúng tôi xem xét bài toán đối ngẫu của bài toán tối ưu lồi cũng như điều kiện tối ưu dựa trên đối ngẫu.
Chúng tôi trình bày hai cách dẫn ra bài toán đối ngẫu, đó là phương pháp nhiễu và hàm Lagrange. Tài liệu tham khảo chính trong mục này là [8], ở đó các tác giả nghiên cứu trong các không gian tôpô Hausdoff. Ỏ đây để đơn giản chúng tôi sẽ trình bày lại trong không gian hữu hạn chiều. 11 Phương pháp nhiễu Định nghĩa 1.
Giả sử ta có một họ các bài toán nhiễu của (P), được cho như sau. Ta xét ham ¢: X x Y + RU{+co}, sao cho o(x,0) = f(z).4) Với mỗi y € Y, xét bài toán tối thiểu inf. Cho bài toán (P) và bài toán nhiễu (Py), ta có thể xác định một bài toán đối ngẫu như sau. Cho gt Ee T(X* x Y*), gi: X*xY* > R| {+o} (1.5) là hàm liên hợp của ó.
Bài toán sup {—9"(0, ") } (P*) y*eY* được gọi là bài toán đối ngẫu của (P) tương ứng với hàm nhiễu ¿ đã cho. Mối quan hệ đầu tiên giữa bài toán (P) và (P*) được cho trong mệnh đề sau.6) 12 Trong các phần sau, chúng tôi giả sử chung rằng @¿€T(X x Y), tức là ¿ là hàm lồi nửa liên tục dưới.7) Với € Y, xét hàm h : Y — R(J{+ce} được cho bởi h(y) = inf(Py) = inf o(a,y). Dudi gid thiét (1.7), ham h: Y + RU {+00} la loi. Bài toán (P) được gọi là tiêu chuẩn (normal) nếu (0) là hữu hạn và h là nửa liên tục dưới tại 0.
Dưới giả thiết (1.7), ba điều kiện sau là tương đương uới nhau: (¡) (P) là tiêu chuẩn (normal). (iit) sup(P*) = inf(P) va con 86 nàu là hữu hạn. Bài toán (P) được gọi là ổn định (stable) néu h(0) là hữu hạn và ở là khả dưới vi phân (subdifferentiable) tại 0. Hai điều kiện sau là tương đương uới nhau: (i) (P) la 6n dinh (stable).