Przypomnijmy, za def. 2.2, definicję zbioru wypukłego: zbiór jest wypukły, jeśli
![]() |
dla każdych i każdego
. Równoważnie można wypukłość zdefiniować za pomocą
-tek punktów:
Zbiór jest wypukły wtw, gdy dla dowolnego
, punktów
oraz liczb
, takich że
mamy
![]() |
Dowód tego lematu pozostawiamy jako ćwiczenie (patrz ćw. 3.3). Udowodnimy natomiast geometryczną własność zbiorów wypukłych, która przyda nam się wielokrotnie.
Niech będzie zbiorem wypukłym o niepustym wnętrzu. Wówczas:
I) Dla dowolnego oraz
odcinek łączący
z
, z pominięciem punktu
, należy do wnętrza
:
![]() |
II) .
Weźmy punkty i
jak w założeniach lematu. Z otwartości
wynika, że istnieje kula
. Połączmy punkty tej kuli z punktem
. Dostaniemy ,,stożek” o wierzchołku
i podstawie
(patrz rys. 3.1). Stożek ten leży w całości w
. Jego wnętrze zawiera odcinek od
do
bez końca
. Kończy to zatem dowód (I). Dowód (II) wynika natychmiast z (I).
Przypomnijmy bez dowodu twierdzenia o oddzielaniu zbiorów wypukłych w przestrzeniach (dowody tych twierdzeń można znaleźć np. w rozdziale 2.4 monografii Bazaraa, Sherali, Shetty [3] lub w rozdziale 11 monografii Rockafellar'a [11]).
Niech będą niespustymi zbiorami wypukłymi, takimi że
. Wówczas istnieje hiperpłaszczyzna rozdzielająca
od
, tzn. istnieje niezerowy wektor
spełniający
![]() |
Korzystając z ciągłości odwzorowania liniowego dostajemy bardzo przydatny wniosek, który również będziemy nazywać słabym twierdzeniem o oddzielaniu.
Niech będą niepustymi zbiorami wypukłymi, takimi że
i
. Wówczas istnieje hiperpłaszczyzna rozdzielająca
od
, tzn. istnieje niezerowy wektor
spełniający
![]() |
Niech będą niepustymi zbiorami wypukłymi domkniętymi,
zwarty i
. Wówczas istnieje hiperpłaszczyzna ściśle rozdzielająca
od
, tzn. istnieje niezerowy wektor
spełniający
![]() |
Powyższe twierdzenia mają intuicyjną geometryczną interpretację. Dwa rozłączne zbiory wypukłe mogą być rozdzielone hiperpłaszczyzną w ten sposób, iż jeden z nich leży w domkniętej półprzestrzeni po jednej stronie hiperpłaszczyzny, podczas gdy drugi leży po przeciwnej stronie tejże hiperpłaszczyzny. W słabym twierdzeniu nie możemy zagwarantować, iż któryś ze zbiorów leży we wnętrzu półprzestrzeni, tzn. ma puste przecięcie z hiperpłaszczyzną. Silna wersja właśnie to gwarantuje.
Hiperpłaszczyzna, o której mowa w twierdzeniach zadana jest wzorem:
![]() |
gdzie . Nie musi to być jedyna hiperpłaszczyzna spełniająca warunki słabego/mocnego rozdzielania.
Twierdzenia o oddzielaniu będziemy dowodzić w przeciwnej kolejności niż są podane. Okazuje się bowiem, że łatwiej udowodnić twierdzenie mocne. Później w dowodzie twierdzenia słabego skorzystamy z mocnego oddzielania zbiorów wypukłych.
Określmy funkcję wzorem
. Z ograniczoności zbioru
wynika, że
jest funkcją koercywną; zbieżność do nieskończoności może się tylko odbywać po argumencie ze zbioru
. Na mocy tw. 1.2 funkcja
jako ciągła i koercywna określona na zbiorze domkniętym
osiąga swoje minimum w pewnym punkcie
. Z faktu, że
wynika, że
. Połóżmy
. Pokażemy, że jest to szukany wektor z tezy twierdzenia.
Udowodnimy, że . Niech
,
. Zdefiniujmy funkcję
![]() |
Rozwijając dostajemy
![]() |
Funkcja ta jest różniczkowalna dla i
dla
(na mocy wypukłości
i definicji
). Zatem
, czyli
![]() |
Nierówność ta jest równoważna .
Podobnie pokazujemy, że dla
. Do zakończenia dowodu wystarczy sprawdzić, że
. Ta nierówność jest równoważna
, co zachodzi, gdyż
.
Rozważmy zbiór . Zbiór ten jest wypukły i
. Równoważne tezie twierdzenia jest znalezienie wektora niezerowego
oddzielającego
od
, tzn. takiego że
dla
.
Zdefiniujmy zbiory
![]() |
Wystarczy pokazać, że . Będziemy rozumować przez sprzeczność. Załóżmy więc, że
. Niech
, gdzie
jest sferą jednostkową
. Zbiory
,
, są otwartymi podzbiorami zbioru zwartego
. Z założenia, że przecięcie ich dopełnień w
jest puste, wynika, że rodzina
jest pokryciem otwartym
. Na mocy zwartości
istnieje podpokrycie skończone
, czyli
![]() |
Połóżmy
![]() |
Zbiór jest wypukły i domknięty oraz
. Stąd
i na mocy mocnego twierdzenia o oddzielaniu zastosowanego do
i
istnieje wektor
, taki że
![]() |
W szczególności, , czyli
,
, co przeczy założeniu, że przecięcie
.
Funkcję , gdzie
wypukły, nazwiemy:
wypukłą, jeśli dla każdego i
zachodzi
![]() |
ściśle wypukłą, jeśli dla każdego ,
i
zachodzi
![]() |
Funkcja jest (ściśle) wklęsła, jeśli
jest (ściśle) wypukła.
Okazuje się, że wystarczy rozważać w definicji wypukłości. Zacytujemy najpierw silny wynik noszący nazwisko Sierpińskiego, a później łatwiejszy, który dowiedziemy:
Jeśli funkcja , gdzie
wypukły, jest mierzalna w sensie Lebesgue'a oraz spełnia
![]() |
to jest wypukła.
Patrz dowód tw. Sierpińskiego w [7, str. 12].
∎My udowodnimy słabszy wynik; założymy mianowicie ciągłość .
Jeśli funkcja , gdzie
wypukły, jest ciągła oraz spełnia
![]() |
to jest wypukła.
Pokażemy najpierw, przez indukcję po , że nierówność wypukłości zachodzi dla
postaci
,
. Własność ta jest spełniona dla
z założenia twierdzenia. Przeprowadźmy teraz krok indukcyjny. Załóżmy, że nierówność jest prawdziwa dla
. Weźmy
całkowite, o sumie
. Załóżmy
. Wówczas
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 jest symetryczny, ze zmienioną rolą
i
.
Zbiór punktów postaci ,
, jest gęsty w odcinku
. Z ciągłości funkcji
otrzymujemy nierówność wypukłości dla dowolnego
.
Funkcja afiniczna jest wypukła i wklęsła.
Norma w jest funkcją wypukłą. Wystarczy skorzystać z nierówności trójkąta.
Odległość punktu od zbioru definiujmy następująco . Odległość punktu od zbioru wypukłego jest funkcją wypukłą:
dla pewnego zbioru wypukłego
.
W tym rozdziale zakładamy, iż funkcja jest określona na niepustym wypukłym podzbiorze
.
Epigrafem funkcji nazywamy zbiór
![]() |
Zbiorem poziomicowym funkcji nazywamy
![]() |
Funkcja jest wypukła wtedy i tylko wtedy, gdy jej epigraf
jest wypukłym podzbiorem
.
Jeśli funkcja jest wypukła, to zbiór poziomicowy
jest wypukły dla dowolnego
.
Dowód powyższych twierdzeń pozostawiamy czytelnikowi.
Twierdzenie odwrotne do tw. 3.6 nie jest prawdziwe. Połóżmy i weźmy dowolny niepusty wypukły zbiór
. Rozważmy funkcję
![]() |
Każdy zbiór poziomicowy tej funkcji jest wypukły, zaś funkcja nie jest wypukła.
Okazuje się, że wypukłość gwarantuje ciągłość we wnętrzu . Rezultat ten nie może być rozszerzony na brzeg
.
Jeśli funkcja jest wypukła, to jest również ciągła na
.
Dowód powyższego twierdzenia wykracza poza ramy tego wykładu. Zainteresowany czytelnik może go znaleźć w monografii [10] w rozdziale IV.41.
Jeśli jest wypukła, to w każdym punkcie
istnieje hiperpłaszczyzna podpierająca, tzn. istnieje
takie że
![]() |
Jeśli jest ściśle wypukła, to
![]() |
Jeśli jest różniczkowalna w
, to w obu powyższych nierównościach możemy przyjąć
.
Na mocy twierdzenia 3.5, epigraf jest zbiorem wypukłym. Zastosujemy słabe twierdzenie o oddzielaniu do zbiorów
i
. Istnieje niezerowy wektor
, takie że
![]() |
(3.1) |
dla . Nierówność ta musi być prawdziwa dla wszystkich
. Zatem
. Okazuje się, że
. Dowiedziemy tego przez sprzeczność: załóżmy
. Wówczas dla dowolnego
mamy
. Korzystając z tego, że
jest we wnętrzu
, wiemy, że
dla dostatecznie małego
. Połóżmy
. Wtedy
, a zatem
. Przeczy to niezerowości wektora
. Wnioskujemy więc, że
.
Możemy założyć, że w nierówności (3.1) (wystarczy podzielić obie strony przez
). Dla dowolnego
dostajemy zatem
![]() |
co przepisujemy następująco
![]() |
Kończy to dowód pierwszej części twierdzenia.
Załóżmy teraz, że jest różniczkowalna w
. Dla dowolnego
,
i
, z wypukłości mamy
![]() |
![]() |
|||
![]() |
(3.2) | |||
![]() |
Policzmy granicę, gdy dąży do zera:
![]() |
gdzie istnieje granicy i ostatnia równość wynika z różniczkowalności w punkcie
.
Przypuśćmy, że jest ściśle wypukła. Ustalmy
. Na mocy pierwszej części twierdzenia
dla dowolnego
. Przypuśćmy, że dla pewnego
,
, ta nierówność nie jest ścisła, tj.
.
Ze ścisłej wypukłości dostajemy
![]() |
(3.3) |
Z drugiej strony, z istnienia płaszczyzny podpierającej w mamy
![]() |
Dostajemy sprzeczność z nierównością (3.3). Pokazuje to, że dla funkcji ściśle wypukłej musi być spełniona ścisła nierówność
jeśli tylko
.
Jeśli wypukła i różniczkowalna w
, to w
jest minimum globalne wtw, gdy
.
Implikacja w prawą stronę wynika z tw. 1.4. Aby dowieść implikacji przeciwnej, załóżmy dla pewnego
. Na mocy tw. 3.8 dla dowolnego
mamy
![]() |
co dowodzi, że w punkcie jest minimum globalne.
Poniżej wymieniamy pozostałe własności funkcji wypukłych. Ich dowody pozostawione są jako ćwiczenia.
Niech , wypukły, zaś
dowolny zbiór. Jeśli funkcje
,
, są wypukłe, to
jest wypukła ze zbiorem wartości
.
Niech , wypukły. Jeśli funkcje
,
, są wypukłe i
dla
, to
funkcja
jest wypukła. Jeśli jedna z funkcji
jest ściśle wypukła, to
jest również ściśle wypukła.
Niech ,
wypukłe zbiory. Jeśli funkcja
jest wypukła i ograniczona z dołu, to
![]() |
jest wypukła.
Niech wypukła. Jeśli
afiniczna, to złożenie
jest funkcją wypukłą.
Niech wypukły. Jeśli
jest funkcją wypukłą i
jest wypukła i niemalejąca, to
jest funkcją wypukłą. Jeśli dodatkowo
jest rosnąca, zaś
ściśle wypukła, to
jest ściśle wypukła.
Niech wypukły. Jeśli
jest funkcją (ściśle) wklęsłą i
, to funkcja
jest (ściśle) wypukła.
Niech wypukły o niepustym wnętrzu. Jeśli w każdym punkcie
istnieje wektor
, taki że
![]() |
to funkcja jest wypukła. Jeśli nierówność jest ostra dla
, to
jest ściśle wypukła.
Weźmy ,
i
. Oznaczmy
. Chcemy wykazać, że
. Na mocy Lematu 3.2 punkt
należy do wnętrza
. Stosując założenie do tego punktu dostajemy
, takie że
![]() |
(3.4) |
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 , to nierówności (3.4) są ostre i dostajemy warunek ścisłej wypukłości.
Niech niepusty, otwarty i wypukły, zaś
dwukrotnie różniczkowalna. Wówczas:
I) jest wypukła wtw, gdy hesjan
jest nieujemnie określony dla każdego
.
II) Jeśli hesjan jest dodatnio określony dla każdego
, to
jest ściśle wypukła.
Analogiczna teza zachodzi w przypadku wklęsłości.
Załóżmy najpierw, że hesjan jest nieujemnie określony dla każdego . Wówczas, na mocy wniosku 2.1, dla dowolnych
mamy
![]() |
gdzie jest punktem leżącym na odcinku łączącym
z
. Założenie o nieujemnej określoności hesjanu pociąga nieujemność ostatniego składnika powyższej sumy. Stąd
![]() |
(3.5) |
Ponieważ powyższa nierówność zachodzi dla dowolnych , to
jest wypukła na mocy twierdzenia 3.9.
Jeśli założymy, że hesjan jest dodatnio określony dla każdego punktu , to nierówność (3.5) jest ostra i twierdzenie 3.9 implikuje ścisłą wypukłość
.
Przejdźmy teraz do dowodu implikacji przeciwnej. Załóżmy, że funkcja jest wypukła. Ustalmy
i
,
. Z otwartości
wynika, że istnieje
, dla której
,
. Zdefiniujmy funkcję
,
. 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 :
![]() |
W granicy przy dążącym do zera, drugi składnik zanika i pozostaje
. Co ta nierówność znaczy w terminach funkcji
? Liczymy:
![]() |
Stąd .
Powyższe rozumowanie możemy przeprowadzić dla dowolnego . Wykazaliśmy więc nieujemną określoność
.
Zajmiemy się teraz uogólnieniem pojęcia pochodnej na nieróżniczkowalne funkcje wypukłe. Niech będzie zbiorem wypukłym, zaś
funkcją wypukłą.
Wektor nazywamy subgradientem funkcji
w punkcie
, jeśli
![]() |
Zbiór wszystkich subgradientów w punkcie
nazywamy subróżniczką i oznaczamy
.
Jeśli jest zbiorem wypukłym o niepustym wnętrzu, to
jest wypukła wtw, gdy w każdym punkcie zbioru
istnieje subgradient:
![]() |
Niech będzie zbiorem wypukłym, zaś
funkcją wypukłą. Wówczas subróżniczka
jest zbiorem wypukłym i domkniętym. Jeśli
jest wewnętrzym punktem
,
, to zbiór
jest ograniczony.
Dowód wypukłości i domkniętości pozostawiamy jako ćwiczenie (patrz ćw. 3.24). Ustalmy . Wówczas istnieje
, taki że kula domknięta
jest zawarta w
. Dla dowolnego
![]() |
A zatem
![]() |
Lewa strona jest niezależna od oraz, z ciągłości
na
, skończona. Supremum po prawej stronie jest przyjmowane dla
i wynosi
. Dostajemy zatem
![]() |
co dowodzi ograniczoności zbioru .
Pokażemy teraz związek subróżniczki z pochodnymi kierunkowymi funkcji. Związek ten przyda nam się w dalszych dowodach.
Pochodną kierunkową funkcji w punkcie
w kierunku
nazywamy granicę
![]() |
Z własności pochodnych jednostronnych dla skalarnych funkcji wypukłych wynikają następujące własności pochodnych kierunkowych:
Niech będzie zbiorem wypukłym otwartym, zaś
funkcją wypukłą. Wówczas dla każdego
i
I) istnieje pochodna kierunkowa .
II) .
III) .
Zdefiniujmy funkcję skalarną dla
, takich że
. Z otwartości
wynika, że
jest określona na pewnym otoczeniu zera
. Jest ona także wypukła. Wówczas iloraz różnicowy jest monotoniczny, tzn. dla
mamy
![]() |
(3.6) |
Z monotoniczności ilorazu różnicowego wynika, że istnieją pochodne lewostronna i prawostronna
,
oraz
![]() |
Wystarczy teraz zauważyć, że , zaś
.
Pozostał nam jeszcze dowód monotoniczności ilorazu różnicowego. Weźmy najpierw i zauważmy, że nierówność (3.6) jest równoważna
![]() |
gdzie oraz
. Prawdziwość ostatniej nierówności wynika z wypukłości funkcji
. Przypadek
dowodzimy analogicznie. Dla
nierówność (3.6) jest równoważna
![]() |
która wynika z wypukłości , gdyż
oraz
![]() |
Pochodne kierunkowe pozwalają na nową charakteryzację subróżniczki.
Niech będzie zbiorem wypukłym otwartym, zaś
funkcją wypukłą. Prawdziwa jest następująca równoważność:
wtw, gdy
![]() |
Ustalmy i
. Wówczas dla
i
(oczywiście takich, że
) mamy
![]() |
Zatem
![]() |
co implikuje .
Weźmy teraz wektor spełniający warunek
dla każdego
. Na mocy lematu 3.4(II) dla
mamy
![]() |
A zatem
![]() |
Z dowolności i
wynika, iż
jest subgradientem.
Poniższe twierdzenie precyzuje związek pomiędzy subróżniczką i pochodną kierunkową funkcji. Zwróć uwagę na wykorzystanie twierdzenia o oddzielaniu w dowodzie. Metoda polegająca na sprytnym dobraniu rozłącznych zbiorów wypukłych, które można rozdzielić hiperpowierzchnią, będzie wielokrotnie wykorzystywana w dowodzeniu twierdzeń dotyczących funkcji wypukłych.
Niech będzie funkcją wypukłą zadaną na wypukłym otwartym zbiorze
. Dla dowolnego
i
zachodzi
![]() |
Ponadto, funkcja jest różniczkowalna w
wtw, gdy subróżniczka
składa się z jednego subgradientu. Tym subgradientem jest wówczas
.
Z lematu 3.5 wynika, że dla
. Stąd
![]() |
Udowodnienie przeciwnej nierówności wymaga skorzystania z twierdzenia o oddzielaniu. Zdefiniujmy dwa zbiory:
![]() |
![]() |
||
![]() |
![]() |
Zauważmy, że różni się od epigrafu
tylko brzegiem
. Możemy zatem zastosować podobne rozumowanie jak w dowodzie tw. 3.5, aby wykazać, że
jest zbiorem wypukłym. Zbiór
jest odcinkiem o początku w punkcie
i o kierunku
, więc jest wypukły. Można zauważyć, że jest on wykresem liniowego przybliżenia funkcji
wokół punktu
wzdłuż odcinka
.
Na mocy lematu 3.4(II) mamy , czyli
![]() |
Wniskujemy stąd, że zbiory i
są rozłączne. Stosujemy słabe twierdzenie o oddzialniu, tw. 3.1: istnieje niezerowy wektor
, taki że
![]() |
(3.7) |
gdzie . Zauważmy, że
nie może być ujemna, gdyż wtedy lewa strona mogłaby być dowolnie mała (
może być dowolnie duże). Nie może także być
, gdyż wówczas dla każdego
musiałoby zachodzić
. Jest to możliwe tylko, gdy
(korzystamy tutaj z faktu, że
jest otwarty). A to przeczy niezerowości wektora
. Dowiedliśmy zatem, że
. Dzieląc obie strony nierówności (3.7) przez
możemy założyć, że
, czyli
![]() |
Zbiegając z do
otrzymujemy
![]() |
(3.8) |
Kładąc dostajemy
![]() |
co po przekształeceniu daje
![]() |
A zatem . Biorąc w nierówności (3.8)
i
dostajemy
![]() |
czyli
![]() |
To kończy dowód pierwszej części twierdzenia.
Dowód drugiej części twierdzenia opiera się na dwóch prostych równoważnościach:
Funkcja jest różniczkowalna w punkcie
wtw, gdy istnieje wektor
, taki że
dla każdego
.
Odwzorowanie jest liniowe wtw, gdy subróżniczka
jest jednoelementowa.
Równoważność pierwsza wynika wprost z definicji pochodnej (patrz roz. 2). Jeśli jest różniczowalna w
, jedynym wektorem spełniającym
jest
.
Przypuśćmy więc, że funkcja jest różniczkowalna w
. Wówczas
, czyli pochodna kierunkowa jest funkcją liniową
. Na mocy drugiej równoważności subróżniczka jest jednoelementowa. Łatwo już zauważyć, że
. Do dowodu w przeciwną stronę załóżmy, że subróżniczka
składa się z jednego wektora
. Wówczas
. Na mocy pierwszej równoważności funkcja
jest różniczkowalna w
.
Twierdzenie 3.11 wykorzystamy kilkukrotnie w dowodzie poniższego twierdzenia, które będzie użyteczne w znajdowaniu subróżniczek.
Niech będzie zbiorem wypukłym otwartym, zaś
funkcjami wypukłymi.
I) Niech . Wówczas
, gdzie
![]() |
II) Niech . Wówczas
![]() |
gdzie jest zbiorem kombinacji wypukłych elementów zbiorów
i
.
Zaczniemy od dowodu (I). Ustalmy . Niech
i
. Wówczas dla
zachodzi
![]() |
![]() |
||
![]() |
![]() |
Dodając te nierówności stronami otrzymujemy
![]() |
czyli . Dowiedliśmy zawierania
. Przypuśćmy, że inkluzja ta jest ostra, tzn. istnieje
, taki że
. Na mocy lematu 3.3 subróżniczki
i
są zwartymi zbiorami wypukłymi. A zatem ich suma algebraiczna jest również zbiorem zwartym i wypukłym (patrz ćw. 3.25). Stosujemy silne twierdzenie o oddzielaniu do zbiorów
oraz
. Dostajemy
i stałą
, takie że
![]() |
Bierzemy maksimum po po lewej stronie i stosujemy twierdzenie 3.11:
![]() |
Z drugiej strony, z własności pochodnych kierunkowych mamy
![]() |
Doprowadziliśmy do sprzeczności: o żądanych własnościach nie może istnieć. Kończy to dowód (I).
Dowód (II). Postać subróżniczki na zbiorach
i
jest oczywista. Jedynie przypadek
wymaga dokładnego dowodu. Ustalmy
, dla którego
. Oznaczmy
. Dla
oraz
mamy
![]() |
Stąd dostajemy . Z wypukłości subróżniczki (patrz lemat 3.3) wynika, że
. Załóżmy teraz, że istnieje
. Zbiór
jest wypukły i zwarty. Stosujemy silne twierdzenie o oddzielaniu do zbiorów
i
. Dostajemy
i stałą
, takie że
![]() |
W szczególności dla
,
, czyli, na mocy tw. 3.11,
![]() |
Podobnie, . Podsumowując:
![]() |
(3.9) |
Z drugiej strony, definicja pochodnej kierunkowej daje nam następującą równość (przypomnijmy, że ):
![]() |
Przechodząc z do zera dostajemy
![]() |
Biorąc dostajemy sprzeczność z (3.9), a więc nie może istnieć
.
Niech będzie zbiorem wypukłym otwartym,
funkcją wypukłą, zaś
będzie macierzą
. Zdefiniujmy
. Wówczas
jest zbiorem wypukłym otwartym oraz funkcja
zadana wzorem
ma w punkcie
subróżniczkę zadaną wzorem
![]() |
Dowód będzie przebiegał podobnie jak dowód poprzedniego twierdzenia. Ustalmy . Weźmy
. Wówczas
![]() |
czyli . Stąd mamy zawieranie
. Równości tych dwóch zbiorów dowiedziemy przez sprzeczność. Załóżmy, że istnieje
. Zbiór
jest wypukły i domknięty, jako liniowy obraz zbioru wypukłego i domkniętego. Zastosujemy silne twierdzenie o oddzielaniu, aby oddzielić go od zbioru jednoelementowego
. Dostajemy
oraz
, takie że
![]() |
Biorąc supremum po po lewej stronie i stosując tw. 3.11 otrzymujemy
. Prawą stronę możemy również oszacować przez pochodną kierunkową:
. Podsumowując:
![]() |
Jednak z własności pochodnych kierunkowych natychmiast wnioskujemy, że dla dowolnego
. Mamy zatem sprzeczność. Dowodzi to, iż zbiór
jest pusty.
Niech będą zbiorami wypukłymi. Wykaż, że
jest zbiorem wypukłym.
może nie być zbiorem wypukłym.
Czy zbiór jest zbiorem wypukłym?
Udowodnij lemat 3.1.
Niech
![]() |
Wykaż, że zbiory są wypukłe i rozłączne. Znajdź prostą (hiperpłaszczyznę) je dzielącą. Czy istnieje hiperpłaszczyzna dzieląca ściśle te zbiory (w sensie mocnego twierdzenia o oddzielaniu)?
Niech będą zbiorami wypukłymi. Udowodnij, że
wtw, gdy istnieje hiperpłaszczyzna ściśle (w sensie mocnego tw. o oddzielaniu) oddzielająca te zbiory.
Niech będzie dowolnym zbiorem. Zdefiniujmy zbiór
jako zbiór takich punktów
, dla których istnieje
liczba naturalna
, zależna od punktu, wektor
o tej własności, że
, oraz
i
![]() |
Udowodnij, że
jest zbiorem wypukłym.
jest najmniejszym zbiorem wypukłym zawierającym
.
W definicji zbioru można założyć, że
, gdzie
jest wymiarem przestrzeni (Tw. Caratheodory'ego).
Zbiór nazywa się otoczką wypukłą zbioru
i oznaczane jest
.
Udowodnij twierdzenie 3.5.
Udowodnij twierdzenie 3.6.
Znajdź przykład zbioru i funkcji wypukłej
, która nie jest ciągła na całym zbiorze
.
Twierdzenie 3.7 pomoże w wyborze zbioru .
Niech będzie zbiorem wypukłym i otwartym, zaś
funkcją różniczkowalną. Udowodnij następującą równoważność:
jest wypukła wtw, gdy
![]() |
Udowodnij: Niech , wypukły, zaś
dowolny zbiór. Jeśli funkcje
,
, są wypukłe, to
jest wypukła ze zbiorem wartości
.
Udowodnij: Niech , wypukły. Jeśli funkcje
,
, są wypukłe i
dla
, to
funkcja
jest wypukła. Jeśli jedna z funkcji
jest ściśle wypukła, to
jest również ściśle wypukła.
Udowodnij: Niech , wypukły, zaś
wypukły, zwarty. Jeśli funkcja
jest wypukła i ciągła, to
![]() |
jest wypukła.
Korzystając ze zwartości i ciągłości
, dla każdego
istnieje
realizujący infimum. Dowodzimy teraz z definicji funkcji wypukłej.
Udowodnij uogólnienie twierdzenia z ćwiczenia 3.13: opuścimy zwartość i ciągłość
. Niech
,
wypukłe zbiory. Jeśli funkcja
jest wypukła i ograniczona z dołu, to
![]() |
jest wypukła.
Skonstruuj przykład, który pokaże, że założenie o ograniczoności z dołu nie może być pominięte w twierdzeniu z ćw. 3.14.
Udowodnij, że funkcja odległości od zbioru wypukłego jest funkcją wypukłą. Podaj przykład wskazujący na konieczność wypukłości zbioru.
Udowodnij: Niech wypukła. Jeśli
afiniczna, to złożenie
jest funkcją wypukłą.
Udowodnij: Niech , wypukły. Jeśli
jest funkcją wypukłą i
jest wypukła i niemalejąca, to
jest funkcją wypukłą. Kiedy
jest ściśle wypukła?
Stwórz analog powyższego twierdzenia dla funkcji wklęsłych.
Udowodnij: Niech wypukły. Jeśli
jest funkcją (ściśle) wklęsłą i
, to funkcja
jest (ściśle) wypukła.
Czy jeśli i
wypukłe, to
jest wypukła?
Udowodnij, że funkcja jest wypukła.
Niech i funkcja
klasy
. Załóżmy ponadto, że
dla każdego
(tzn. Hesjan jest nieujemnie określony). Rozstrzygnij, który z następujących warunków jest wystarczający, by zdanie
![]() |
było prawdziwe:
,
jest wypukły i otwarty,
jest wypukły,
jest otwarty.
Znajdź przykład zbioru oraz funkcji
klasy
, takiej że
(tzn. hesjan jest nieujemnie określony) dla każdego
,
istnieje punkt , w którym jest minimum lokalne funkcji
, ale nie jest ono globalne.
Niech będzie zbiorem wypukłym, zaś
funkcją wypukłą. Udowodnij, że
jest zbiorem wypukłym i domkniętym.
Niech będą zbiorami wypukłymi zwartymi. Udowodnij, że suma algebraiczna tych zbiorów
![]() |
jest zbiorem zwartym i wypukłym.
Niech wypukły otwarty i
wypukła. Wykaż, że
jest subgradientem
w
wtw, gdy odwzorowanie
osiąga swoje maksimum w
.
Znajdź subróżniczkę funkcji .
Niech będzie macierzą
symetryczną i nieujemnie określoną. Udowodnij, że
,
, jest funkcją wypukłą i znajdź jej subróżniczkę.
Wykaż, że dla skalarnej funkcji wypukłej mamy
![]() |
gdzie oznaczają prawo- i lewo-stronne pochodne w punkcie
.
Niech wypukła,
ustalone wektory. Zdefiniujmy
,
. Wykaż, że
jest wypukła oraz
![]() |
Wykaż, że funkcja jest wypukła na
i znajdź jej subróżniczkę.
Niech ,
, gdzie
jest zbiorem wypukłym. Znajdź subróżniczkę w następujących przypadkach:
dla pewnego
,
, tzn.
jest odcinkiem,
, tzn.
jest kwadratem.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.