Chương 1 Kiến thức chuẩn bị Chương này trình bày các khái niệm, các tính chất cơ bản nhất của giải tích lồi và các bổ đề hỗ trợ sẽ được dùng trong Chương 2. Các kiến thức ở chương này được tổng hợp từ tài liệu tham khảo [1], [3]. Tập lôi và hàm lồi trong không gian Euclid hữu hạn chiều Định nghĩa 1.1 Một tập Œ C RR*“ được gọi là một tép loi, nếu Œ chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là Ở lồi khi và chỉ khi Vz, € Œ, VÀ € [0,1] > Àz + (1— À)w € C.
Ta nói ø là to hop Idi cia các điểm (vectơ) z!,.,ø! nếu k k + =À }Àjr?,Àj>0 V7 =1, `Àj =1, j=l j=l Tương tự, z là fổ hợp aphzn của các điểm (vectơ) #!,.,ø! nếu 1 Tap hợp của các tổ hợp aphin của z!,.,z# thường được gọi là bao aphin ° ⁄ 2 ` của các điểm này.1 Tập hợp Ở là lồi khi uà chỉ khi nó chúa mọi tổ hợp lồi của các điểm của nó. Tức là tập Ở lồi khi va chỉ khi k k Vk ENV, Ae > 0: SOA; = 1, Ve, ch CCS SO Ajay € C. Diều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp theo số điểm.
Với k = 2, điều cần chứng minh suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với k — 1 điểm. Ta cần chứng minh với & điểm. Giả sử z là tổ hợp lồi của k điểm zl,.
Tức là k k + =À }Àjz?,Àj>0 V7 =1, `Àj =1, j=l j=l Dat k-1 €= Aj. j=l Khi đó 0< £< 1 và k—1 k—1 r= À;#! + Apa” =€ ol + dpa j=l j=l do el À/ =1, ja § yt Aa ec j=l Ta có x = byt Age. E+ \= SoA =1, 5 nên z là một tổ hợp lồi của hai điểm y va x" đều thuộc C.2 Một tập Œ được gọi là tập aph¿n nêu nó chứa đường thẳng đi qua hai điểm bất kỳ của nó, tức là Vz, € Œ, VÀ € ]R= Àz + (1— À) € Œ. Vậy tập aphin là một trường hợp riêng của tập lồi.
Ví dụ điển hình của tập aphin là các không gian con, siêu phẳng được định nghĩa dưới đây.3 Siêu phẳng trong không gian R” 1A mot tap hợp các điểm có đạng {rz € R"a’x = a}, trong dé a € R” la mét vectơ khác 0 và œ € R. Vectơ a thường được gọi là vectơ pháp tuyến của siêu phẳng. Một siêu phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được định nghĩa như sau: Định nghĩa 1.4 Nửa không gian là một tập hợp có dạng {z|afz+ > a}, trong đó a # 0 và œ € IR.
Dây là nửa không gian đóng. Tập {z| afz > a} là nửa không gian mở.+* trong IR" được gọi là độc lập aphin, néu bao aphin của chúng có thứ nguyên là É.6 Một tập hợp được gọi là tập lồi đa điện, nêu nó là giao của một số hữu hạn các nửa không gian đóng. Theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa diện được cho như sau: D:={+c€TR"|(a!,x) < bị, j = 1,.
6 Hoặc nếu ta ký hiệu 4 là ma trận có m hang IA cac vectd a/(j = 1,.,m) và vectơ bŸ = (b\,., b„), thì hệ trên viết được là D={zcR'|Az < b}. Chú ý rằng do một phương trình (a,x = b) có thể viết một cách tương đương dưới dạng hai bất phương trình (a,x) <b, (—a,x) <b, nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương trình cũng là một tập lồi đa diện. Một số các tính chất của tập lồi đa diện sẽ được trình bày trong các phần tiếp theo. Ta nói đc() là khoảng cách từ đến Œ.
Nếu tồn tai t € C sao cho dec(w) := ||m — 9||, thì ta nói z là hành chiếu (vuông góc) của trên C. Theo định nghĩa, ta có hình chiếu poc(0) của trên Œ sẽ là nghiệm của bài toán tối ưu. min{5 Jr ~ yl? le € C} Vậy việc tìm hình chiếu của ¿ trên C c6 thé đưa về việc tìm cực tiểu của hàm toàn phương || — g||Ÿ trên Œ. Ta sẽ ký hiệu = c(ø), hoặc đơn giản hon 1a p(y) néu không cần nhấn mạnh đến tập chiếu Œ.
Chú ý rằng, nếu Œ # @, thì đc(g) hữu hạn, vì 0 < đe(0) < |Ìụ — z|| với mọi z € Œ. Nhớ lại là nón pháp tuyến (ngoài) của tập Œ tại +” là tập hợp Ne(2°) := {wlw" (a — 2°) < 0 Va € Ch.2 Cho Ở là một tập lồi đóng khác rỗng. (ii) Với mọi ụ € ]R", hình chiếu Pc(u) của ụ trên Ở luôn tồn tại uà duy nhất. Do z,7 € Ở và Œ lồi, nên zA € Œ.
Hơn nữa do z là hình chiếu của , nên llm — ll < [ly — al]. Hay Iz = ylP < ||A@ = aI] +(e — y)IP. Khai triển về phải, ước lược và chia hai vế cho À > 0, ta có Ala — |? +2(a —7,7-y) > 0. Điều này đúng với mọi ø € Œ và À € (0,1).
Do đó khi cho À tiến đến 0, ta được —,z—7m) >0 Weed. 8 Bây giờ giả sử có b). Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có: lu — x|lÍ < (w = z)“(w = #) < |l = z||ll(w ~ z)|l- Suy ra || — )|| < |lu — z|| Yz € Œ, và do đó m = p(y). (ii) Do de(y) = inf;ecl||z — 9||, nên theo định nghĩa của cận dưới đúng (infimum), tén tai mot day x2* € C sao cho lim eÊ — g||= đe(y) < +00 Vậy dãy {z"} bị chặn, do đó nó có một dãy con {z"?} hội tụ đến một điểm z nào đó.
Do Ở đóng, nên z € C. Vậy llr = || = lim |lz# — g|| = im |lz” — yl| = do(y), Chứng tỏ z là hình chiếu của trên C. Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm 7 va z! đều là hình chiếu của g trên Œ, thì ụ—m€ Nc(m),u— ' € Ne(®)).
Tức là (1 —y,7! — 7) = 0 va Œ' —1,— `} = 0. Cộng hai bất đẳng thức này ta suy ra ||x — z!|| < 0, và do đó z = zÌ. 9 Vậy {x — ,}) = (m — ,7) là một siêu phẳng tựa của Ở tai z. Siêu phẳng này tách ¿ khỏi C vi y 4 7, nén (—,— ) = ~||r ~ w|Ễ < 0.
Cộng hai bất đẳng thức lại sẽ được (p(y) — p(z). Từ đây và theo bất đẳng thức Cauchy-Schwarz, suy ra |Ip(z) = p)l| < |lz = 9l: Để chứng mnh tính đồng bức, áp dụng tính chất b của (¡), lần lượt với p(x) va p(y), ta cd (p(x) — x, p(x) — p(w)) < 0. Cộng hai bất đẳng thức ta được (p(x) — ply) +y — #, p(x) — p(y)) <0 = (p(x) — p(), — #) + ||p() — p(w)||Ÿ < 0. Chuyển về ta có (p(x) — p(y), 2 — y) > ||p(z) = p()|Ủ: Day chính là tính đồng bức cần được chứng minh.8 Một ánh xạ ?': Œ —> lR" được gọi là đơn điệu trên C, nếu Ánh xạ F' được gọi là đơn điệu mạnh trên Œ với hệ sô 8 > 0, nếu (F(x) — F(y),« —y) = Ø||z — w| Yz.
Ơ Cho C CR" la tap loi va f : CO R. Ta sé ky hicu domf := {x € C| f(x) < +00} Tập domƒ được gọi là miền hữu dụng của f. Tap epiƒ := {(,w) € Œ x R|ƒ(z) < wh được gọi là trên đồ th¿ của hàm ƒ. Bang cach cho f(x) = +œ nếu z £ Œ, ta có thể coi ƒ được xác định trên toàn không gian và hiển nhiên là domf = {x € R”| f(x) < +oo} epif = {(x,) € R"| x Ri f(x) < py} Do sẽ làm việc với hàm số nhận cả giá trị —oo và +œo, ta có quy ước sau: Nếu À = 0,thì Àƒ(z) = 0 với mọi x.9 Cho @ 4 C C R" loi va f : C > R.
Ta nói ƒ là ham lồi trên Œ, nếu epiƒ là một tập lồi trong R“*†, Ta sẽ chủ yếu làm việc với hàm ƒ : R” — RU {+oc}. Trong trường hợp này, dễ thấy rằng định nghĩa trên tương đương với Ham f :R" + RU {+00} được gọi là lôi chặt trên Œ nếu ƒ(z + (1— À)g) < Àƒ(z) +(1— À)ƒ() Vz, € Œ,V À € (0,1). được gọi là lỗi mạnh trên Ở với hệ số + > 0, néu Vz,y € Œ,VÀ € (0, 1) có: fe + (= A)y) SAF (0) + (L—A)/f(y) = 5A. = )lle = v|: Kiểm tra được rằng, ƒ lồi mạnh trên C véi hé s6 7 > 0 khi và chỉ khi hàm h() := ƒ() — AAP ():=Z0 = gILl lồi trên Œ.
Bằng quy nạp, dễ dàng chứng minh được rằng, nếu ƒ nhận giá trị hữu hạn trên tập lồi Ở, thì với mọi số tự nhiên m và moi z!,. j=1 j=l Hàm ƒ được gọi là một ham lém trén C, néu —f 1di trén C. Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp.3 Một hàm ƒ : Ơ -y R là lỗi trên Ở khá uà chỉ khi Vz,u € Œ,Va > ƒ(z),YØ > ƒ(w),VA € |0. Chứng minh Chứng minh điều kiện cần.
Giả sử ƒ lồi. Chon 2, y, a, 8 như đã nêu trong mệnh dé. Vậy (z,a') và (w, Ø') thuộc epiƒ. Do epiƒ lồi, nên; ((1— A)z + Ay), (1 — A)a’ + AB’) € epif.
AB’ < (1— ANA + AP. 12 Chứng minh điều kiện đủ. Thế thi vdi moi ¢ > 0, ta cd f(a) < ute, fly) <<v+te. Điều này đúng với mọi e > 0, nên cho e —> 0, ta được fi — Aja’ +AB‘] < (1 = A) + Av.
O Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh dựa vào khái niệm hệ số lồi, Định nghĩa 1.10 Cho ƒ : R” — RU {+oo} (không nhất thiết lồi), Œ CR' là một tập lồi khác rỗng và ? là một số thực. Ta nói ? là hệ số lồi của ƒ trên Œ, nếu với mọi À € (0,1), mọi #, + thuộc C, ta có f[—AJ# + Ay] <(1— AJƒ0) +Af() — 5A. A) =o? Hiển nhiên nếu „ = 0 thì ƒ lồi trên Œ. Nếu ƒ có hệ số lồi trên Œ là „>0, thì ƒ lồi mạnh trên Ở với hệ số 7.
Một hàm ƒ được gọi là chính thường nêu domƒ # @ và ƒ(#) > —œ với mọi x.