Dowód

Weźmy punkty x0 i x jak w założeniach lematu. Z otwartości intW wynika, że istnieje kula B⁢x0,ε⊂intW. Połączmy punkty tej kuli z punktem x. Dostaniemy ,,stożek” o wierzchołku x i podstawie B⁢x0,ε (patrz rys. 3.1). Stożek ten leży w całości w W. Jego wnętrze zawiera odcinek od x0 do x bez końca x. Kończy to zatem dowód (I). Dowód (II) wynika natychmiast z (I).

Rys. 3.1. Stożek o wierzchołku x i podstawie B⁢x¯,ε.

Dowód twierdzenia 3.2

Określmy funkcję d:U×V→R wzorem d⁢x,y=x-y. Z ograniczoności zbioru U wynika, że d jest funkcją koercywną; zbieżność do nieskończoności może się tylko odbywać po argumencie ze zbioru V. Na mocy tw. 1.2 funkcja d jako ciągła i koercywna określona na zbiorze domkniętym U×V osiąga swoje minimum w pewnym punkcie x0,y0∈U×V. Z faktu, że U∩V=∅ wynika, że x0≠y0. Połóżmy a=y0-x0. Pokażemy, że jest to szukany wektor z tezy twierdzenia.

Udowodnimy, że aT⁢y≥aT⁢y0. Niech y∈V, y≠y0. Zdefiniujmy funkcję

Rozwijając dostajemy

Funkcja ta jest różniczkowalna dla t∈R i g⁢0≤g⁢t dla t∈0,1 (na mocy wypukłości V i definicji y0). Zatem g′⁢0≥0, czyli

Nierówność ta jest równoważna aT⁢y≥aT⁢y0.

Podobnie pokazujemy, że aT⁢x≤aT⁢x0 dla x∈U. Do zakończenia dowodu wystarczy sprawdzić, że aT⁢y0>aT⁢x0. Ta nierówność jest równoważna a2>0, co zachodzi, gdyż x0≠y0.

Dowód twierdzenia 3.1

Rozważmy zbiór C=V-U=y-x:⁢x∈U,⁢y∈V. Zbiór ten jest wypukły i 0∉C. Równoważne tezie twierdzenia jest znalezienie wektora niezerowego a∈Rn oddzielającego C od 0, tzn. takiego że aT⁢x≥0 dla x∈C.

Zdefiniujmy zbiory

Wystarczy pokazać, że ⋂x∈CAx≠∅. Będziemy rozumować przez sprzeczność. Załóżmy więc, że ⋂x∈CAx=∅. Niech Bx=S∖Ax, gdzie S jest sferą jednostkową S=a∈Rn:⁢a=1. Zbiory Bx, x∈C, są otwartymi podzbiorami zbioru zwartego S. Z założenia, że przecięcie ich dopełnień w S jest puste, wynika, że rodzina Bxx∈C jest pokryciem otwartym S. Na mocy zwartości S istnieje podpokrycie skończone Bx1,…,Bxk, czyli

Połóżmy

Zbiór C⌃ jest wypukły i domknięty oraz C⌃⊂C. Stąd 0∉C⌃ i na mocy mocnego twierdzenia o oddzielaniu zastosowanego do C⌃ i 0 istnieje wektor a∈Rn∖0, taki że

W szczególności, aT⁢x1>0,…,aT⁢xk>0, czyli aa∈Axi, i=1,…,k, co przeczy założeniu, że przecięcie ⋂i=1kAxi=∅.

Dowód

Patrz dowód tw. Sierpińskiego w [7, str. 12].

Dowód

Pokażemy najpierw, przez indukcję po k, że nierówność wypukłości zachodzi dla λ postaci p/2k, p=0,1,…,2k. Własność ta jest spełniona dla k=1 z założenia twierdzenia. Przeprowadźmy teraz krok indukcyjny. Załóżmy, że nierówność jest prawdziwa dla k. Weźmy p,q>0 całkowite, o sumie p+q=2k+1. Załóżmy p≤q. Wówczas p≤2k≤q i możemy napisać:

Mamy zatem

Pierwsza nierówność wynika z założenia twierdzenia, zaś druga – z założenia indukcyjnego. Dowód w przypadku p≥q jest symetryczny, ze zmienioną rolą x i y.

Zbiór punktów postaci p/2k, k=1,2,…, jest gęsty w odcinku 0,1. Z ciągłości funkcji f otrzymujemy nierówność wypukłości dla dowolnego λ∈0,1.

Dowód tw. 3.8

Na mocy twierdzenia 3.5, epigraf epif jest zbiorem wypukłym. Zastosujemy słabe twierdzenie o oddzielaniu do zbiorów U=epif i V=x¯,f⁢x¯. Istnieje niezerowy wektor a=ξ,α∈Rn×R, takie że

dla x,y∈epif. Nierówność ta musi być prawdziwa dla wszystkich y≥f⁢x. Zatem α≤0. Okazuje się, że α≠0. Dowiedziemy tego przez sprzeczność: załóżmy α=0. Wówczas dla dowolnego x∈W mamy ξT⁢x-x¯≤0. Korzystając z tego, że x¯ jest we wnętrzu W, wiemy, że x¯+ε⁢ξ∈W dla dostatecznie małego ε>0. Połóżmy x=x¯+ε⁢ξ. Wtedy 0≥ξT⁢x-x¯=ε⁢ξT⁢ξ=ε⁢ξ2, a zatem ξ=0. Przeczy to niezerowości wektora ξ,α. Wnioskujemy więc, że α<0.

Możemy założyć, że α=-1 w nierówności (3.1) (wystarczy podzielić obie strony przez α). Dla dowolnego x∈W dostajemy zatem

co przepisujemy następująco

Kończy to dowód pierwszej części twierdzenia.

Załóżmy teraz, że f jest różniczkowalna w x¯. Dla dowolnego x∈W, x≠x¯ i λ∈0,1, z wypukłości mamy

Policzmy granicę, gdy λ dąży do zera:

gdzie istnieje granicy i ostatnia równość wynika z różniczkowalności f w punkcie x¯.

Przypuśćmy, że f jest ściśle wypukła. Ustalmy x¯∈intW. Na mocy pierwszej części twierdzenia f⁢x≥f⁢x¯+ξT⁢x-x¯ dla dowolnego x∈W. Przypuśćmy, że dla pewnego x∈W, x≠x¯, ta nierówność nie jest ścisła, tj. f⁢x=f⁢x¯+ξT⁢x-x¯. Ze ścisłej wypukłości dostajemy

Z drugiej strony, z istnienia płaszczyzny podpierającej w x¯ mamy

Dostajemy sprzeczność z nierównością (3.3). Pokazuje to, że dla funkcji ściśle wypukłej f musi być spełniona ścisła nierówność f⁢x<f⁢x¯+ξT⁢x-x¯ jeśli tylko x≠x¯.

Dowód

Implikacja w prawą stronę wynika z tw. 1.4. Aby dowieść implikacji przeciwnej, załóżmy D⁢f⁢x¯=0 dla pewnego x¯=0. Na mocy tw. 3.8 dla dowolnego x∈W mamy

co dowodzi, że w punkcie x¯ jest minimum globalne.

Dowód

Weźmy x∈intW, y∈W i λ∈0,1. Oznaczmy xλ=λ⁢x+1-λ⁢y. Chcemy wykazać, że f⁢xλ≤λ⁢f⁢x+1-λ⁢f⁢y. Na mocy Lematu 3.2 punkt xλ należy do wnętrza W. Stosując założenie do tego punktu dostajemy ξ∈Rn, takie że

Stąd

gdyż wielkości w nawiasie kwadratowym zerują się. Kończy to dowód twierdzenia. Jeśli nierówność w założeniu jest ostra i x≠y, to nierówności (3.4) są ostre i dostajemy warunek ścisłej wypukłości.

Dowód

Załóżmy najpierw, że hesjan jest nieujemnie określony dla każdego x∈W. Wówczas, na mocy wniosku 2.1, dla dowolnych x¯,x∈W mamy

gdzie x~ jest punktem leżącym na odcinku łączącym x¯ z x. Założenie o nieujemnej określoności hesjanu pociąga nieujemność ostatniego składnika powyższej sumy. Stąd

Ponieważ powyższa nierówność zachodzi dla dowolnych x¯,x∈W, to f jest wypukła na mocy twierdzenia 3.9.

Jeśli założymy, że hesjan jest dodatnio określony dla każdego punktu W, to nierówność (3.5) jest ostra i twierdzenie 3.9 implikuje ścisłą wypukłość f.

Przejdźmy teraz do dowodu implikacji przeciwnej. Załóżmy, że funkcja f jest wypukła. Ustalmy x¯∈W i h∈Rn, h≠0. Z otwartości W wynika, że istnieje δ>0, dla której x¯+t⁢h∈W, t∈-δ,δ. Zdefiniujmy funkcję g⁢t=f⁢x¯+t⁢h, t∈-δ,δ. Jest to funkcja jednej zmiennej, dwukrotnie różniczkowalna oraz wypukła. Stosując twierdzenie 3.8 dostajemy

Na mocy twierdzenie Taylora z resztą w postaci Peano, tw. 1.9, mamy

Powyższa nierówność i wzór Taylora dają następujące oszacowanie na drugą pochodną

Dzielimy obie strony przez t2:

W granicy przy t dążącym do zera, drugi składnik zanika i pozostaje g′′⁢0≥0. Co ta nierówność znaczy w terminach funkcji f? Liczymy:

Stąd g′′⁢0=hT⁢D2⁢f⁢x¯⁢h.

Powyższe rozumowanie możemy przeprowadzić dla dowolnego h∈Rn. Wykazaliśmy więc nieujemną określoność D2⁢f⁢x¯.

Dowód

Implikacja w prawą stronę wynika z twierdzenia 3.8, zaś implikacja w stronę lewą – z tw. 3.9.

Dowód

Dowód wypukłości i domkniętości pozostawiamy jako ćwiczenie (patrz ćw. 3.24). Ustalmy x¯∈intW. Wówczas istnieje ε>0, taki że kula domknięta B⁢x¯,ε jest zawarta w intW. Dla dowolnego ξ∈∂⁡f⁢x¯

A zatem

Lewa strona jest niezależna od ξ oraz, z ciągłości f na intW, skończona. Supremum po prawej stronie jest przyjmowane dla x=x¯+ε⁢ξ/ξ i wynosi ε⁢ξ. Dostajemy zatem

co dowodzi ograniczoności zbioru ∂⁡f⁢x¯.

Dowód

Zdefiniujmy funkcję skalarną g⁢t=f⁢x+t⁢d dla t, takich że x+t⁢d∈W. Z otwartości W wynika, że g jest określona na pewnym otoczeniu zera -δ,δ. Jest ona także wypukła. Wówczas iloraz różnicowy jest monotoniczny, tzn. dla -δ<t1<t2<δ mamy

Z monotoniczności ilorazu różnicowego wynika, że istnieją pochodne lewostronna g′⁢0- i prawostronna g′⁢0+, g′⁢0-≤g′⁢0+ oraz

Wystarczy teraz zauważyć, że f′⁢x;d=g′⁢0+, zaś f′⁢x;-d=-g′⁢0-.

Pozostał nam jeszcze dowód monotoniczności ilorazu różnicowego. Weźmy najpierw 0<t1<t2<δ i zauważmy, że nierówność (3.6) jest równoważna

gdzie λ=t1/t2∈0,1 oraz λ⁢t2+1-λ⁢0=t1. Prawdziwość ostatniej nierówności wynika z wypukłości funkcji g. Przypadek -δ<t1<t2<0 dowodzimy analogicznie. Dla -δ<t1<0<t2<δ nierówność (3.6) jest równoważna

która wynika z wypukłości g, gdyż 1/1+λ∈0,1 oraz

Dowód

Ustalmy x¯∈W i ξ∈∂⁡f⁢x¯. Wówczas dla λ>0 i d∈Rn (oczywiście takich, że x¯+λ⁢d∈W) mamy

Zatem

co implikuje f′⁢x¯;d≥ξT⁢d.

Weźmy teraz wektor ξ∈Rn spełniający warunek f′⁢x¯;d≥ξT⁢d dla każdego d∈Rn. Na mocy lematu 3.4(II) dla λ>0 mamy

A zatem

Z dowolności λ i d wynika, iż ξ jest subgradientem.

Dowód

Z lematu 3.5 wynika, że f′⁢x¯;d≥ξT⁢d dla ξ∈∂⁡f⁢x¯. Stąd

Udowodnienie przeciwnej nierówności wymaga skorzystania z twierdzenia o oddzielaniu. Zdefiniujmy dwa zbiory:

Zauważmy, że C1 różni się od epigrafu f tylko brzegiem x,z∈W×R:⁢z=f⁢x. Możemy zatem zastosować podobne rozumowanie jak w dowodzie tw. 3.5, aby wykazać, że C1 jest zbiorem wypukłym. Zbiór C2 jest odcinkiem o początku w punkcie x¯,f⁢x¯ i o kierunku d,f′⁢x¯;d, więc jest wypukły. Można zauważyć, że jest on wykresem liniowego przybliżenia funkcji f wokół punktu x¯ wzdłuż odcinka x¯+λ⁢d:λ≥0∩W.

Na mocy lematu 3.4(II) mamy f′⁢x;d≤f⁢x¯+λ⁢d-f⁢x¯λ, czyli

Wniskujemy stąd, że zbiory C1 i C2 są rozłączne. Stosujemy słabe twierdzenie o oddzialniu, tw. 3.1: istnieje niezerowy wektor μ,γ∈Rn×R, taki że

gdzie L=sup⁡λ≥0:⁢x¯+λ⁢d∈W. Zauważmy, że γ nie może być ujemna, gdyż wtedy lewa strona mogłaby być dowolnie mała (z może być dowolnie duże). Nie może także być γ=0, gdyż wówczas dla każdego x∈W musiałoby zachodzić μT⁢x-x¯≥λ⁢μT⁢d. Jest to możliwe tylko, gdy μ=0 (korzystamy tutaj z faktu, że W jest otwarty). A to przeczy niezerowości wektora μ,γ. Dowiedliśmy zatem, że γ>0. Dzieląc obie strony nierówności (3.7) przez γ możemy założyć, że γ=1, czyli

Zbiegając z z do f⁢x otrzymujemy

Kładąc λ=0 dostajemy

co po przekształeceniu daje

A zatem -μ∈∂⁡f⁢x¯. Biorąc w nierówności (3.8) λ>0 i x=x¯ dostajemy

czyli