Niech będzie niepustym wypukłym podzbiorem
, zaś
będzie funkcją wypukłą. Rozważmy problem minimalizacji funkcji
na zbiorze
:
![]() |
(4.1) |
Przypomnijmy, że punktami dopuszczalnymi nazywamy elementy zbioru . Rozwiązaniem globalnym nazywamy taki punkt
, że
dla każdego
. Rozwiązaniem lokalnym jest taki punkt
, że istnieje
, dla którego
, jeśli
. Rozwiązanie jest ścisłe, jeśli
dla
i
. Innymi słowy,
jest rozwiązaniem lokalnym, jeśli
jest minimum funkcji
na pewnym otoczeniu
.
Niech wypukły,
wypukła. Jeśli
będzie rozwiązaniem lokalnym (4.1), to:
I) jest rozwiązaniem globalnym,
II) Zbiór rozwiązań globalnych jest wypukły.
III) Jeśli jest ściśle wypukła, to
jest ścisłym rozwiązaniem lokalnym.
IV) Jeśli jest ścisłym rozwiązaniem lokalnym, to
jest jedynym rozwiązaniem globalnym.
Zauważmy, że w powyższym twierdzeniu nie zakładamy różniczkowalności funkcji .
(I): Dowód przez sprzeczność. Przypuśćmy, że istnieje takie że
. Ponieważ
jest rozwiązaniem lokalnym, to
dla
i
. Z wypukłości zbioru
wynika, iż odcinek łączący
i
znajduje się w zbiorze
. Ma on więc niepuste przecięcie z kulą
: dla pewnego
mamy
. Z wypukłości
dostajemy
![]() |
co przeczy lokalnej optymalności .
(II) Pozostawione jako ćwiczenie.
(III) Wynika wprost z definicji ścisłej wypukłości.
(IV) Pozostawione jako ćwiczenie.
∎Dotychczas pokazaliśmy, że warunkiem koniecznym i dostatecznym minimum funkcji wypukłej na zbiorze wypukłym i otwartym jest zerowanie się pochodnej/gradientu. Uogólnimy teraz te wyniki na przypadek dowolnych zbiorów wypukłych.
Niech wypukły,
wypukła. Jeśli
jest różniczkowalna w punkcie
, to mamy następującą równoważność:
jest rozwiązaniem (4.1) wtw, gdy
dla każdego
.
W sformułowaniu powyższego twierdzenia, jak i w wielu miejscach w dalszej części tych notatek, zastosowany jest następujący skrót myślowy. Aby mówić o różniczkowalności funkcji w punkcie
, musi być ona określona w pewnym otoczeniu
, czyli w kuli
dla pewnego
. Jeśli
jest na brzegu
, to zakładać będziemy, że
jest określona na
mimo, że jest to pominięte, dla prostoty notacji, w założeniach twierdzenia.
Jeśli , to warunek powyższy sprowadza się do warunku zerowania się pochodnej
.
Załóżmy, że dla każdego
. Ustalmy
. Na mocy twierdzenia 3.8
![]() |
Z założenia, drugi składnik jest nieujemny, co pociąga . Z dowolności
dostajemy tezę.
Załóżmy teraz, że jest rozwiązaniem (4.1). Ustalmy
. Zauważmy, że wypukłość
implikuje
dla
. Z definicji pochodnej mamy
![]() |
Ponieważ w punkcie jest minimum, to
. Stąd
.
Z dowodu powyższego twierdzenia dostajemy użyteczny wniosek.
Jeśli , gdzie
jest wypukły, jest rozwiązaniem lokalnym (4.1) dla funkcji
(niekoniecznie wypukłej) różniczkowalnej w
, to
dla każdego
.
Rozważmy problem minimalizacyjny:
![]() |
Zbiór zadany jest przez ograniczenia liniowe (patrz rysunek 4.1):
![]() |
Łatwo sprawdzić, że jest on wypukły. Funkcja jest ściśle wypukła: jej hesjan wynosi
![]() |
Na mocy tw. 4.1 minimum jest jednoznaczne. Policzmy gradient :
![]() |
Gradient zeruje się w punkcie , który jest poza zbiorem
. Minimum należy zatem szukać na brzegu
. Nie mamy jeszcze narzędzi ułatwiających znalezienie tego punktu. Zgadujemy… Sprawdźmy wierzchołek
. Gradient w tym punkcie wynosi
. Zauważmy, że wektory
są kombinacjami liniowymi dodatnimi wektorów
i
, tzn.
dla pewnych
. Wystarczy zatem sprawdzić, że
i
:
![]() |
|||
![]() |
Na mocy tw. 4.2 minimum jest rzeczywiście w punkcie .
Rozszerzymy teraz twierdzenie 4.2 na klasę funkcji wypukłych nieróżniczkowalnych – skorzystamy z wprowadzonego w poprzednim rozdziale pojęcia subróżniczki.
Niech wypukły otwarty,
wypukła. Załóżmy, że zbiór punktów dopuszczalnych
jest wypukłym podzbiorem
. Mamy następującą równoważność:
jest rozwiązaniem (4.1) wtw, gdy istnieje
, takie że
dla każdego
.
Niech wypukły otwarty,
wypukła. Wówczas
ma w
minimum globalne wtw, gdy
.
Zacznijmy od łatwiejszej implikacji. Załóżmy, że istnieje , takie że
dla każdego
. Z faktu, że
jest subgradientem wynika, że
![]() |
Wystarczy teraz skorzystać z założenia, żeby zauważyć, że dla
, czyli
jest rozwiązaniem (4.1).
Załóżmy teraz, że jest rozwiązaniem (4.1). Zdefiniujmy dwa zbiory
![]() |
![]() |
||
![]() |
![]() |
Oba zbiory są wypukłe, ma niepuste wnętrze (zbiór
ma puste wnętrze, jeśli
ma puste wnętrze). Z faktu, że punkt
jest rozwiązaniem (4.1) wynika, że
. Stosujemy słabe twierdzenie o oddzielaniu: istnieje niezerowy wektor
i stała
, takie że
![]() |
(4.2) |
Zanim przejdziemy do analitycznych rozważań popatrzmy na geometryczny obraz. Zauważmy, że zbiory i
,,stykają” się w punkcie
. Hiperpłaszczyzna oddzielająca te zbiory musi zatem przechodzić przez ten punkt. Jest ona styczna do wykresu funkcji
– pierwsza grupa współrzędnych
wektora
do niej normalnego, z dokładnością do długości i zwrotu, wyznacza subgradient tego odwzorowania w punkcie
(a zatem także subgradient
). Z faktu, że ta hiperpłaszczyzna jest również styczna do
dostajemy
.
Udowodnijmy to teraz analitycznie. Odejmijmy od obu stron nierówności (4.2) :
![]() |
(4.3) | |||
![]() |
(4.4) |
gdzie . Zauważmy najpierw, że
nie może być większa od zera. Wówczas, wykorzystując dowolność
, dostajemy sprzeczność z (4.4). Kładąc w (4.4)
i
, otrzymujemy
. Wnioskujemy stąd, że niedopuszczalne jest
: z nierówności (4.3) (pamiętając o otwartości
) dostalibyśmy bowiem
, co przeczyłoby niezerowości wektora
. Wykazaliśmy więc, że
![]() |
Biorąc , nierówność (4.3) upraszcza się do
dla
. Stąd
. Łącząc to z poprzednio otrzymaną nierównością
dostajemy
![]() |
Przechodząc w (4.3) z do
mamy
![]() |
Dzieląc obie strony przez i pamiętając, że
dostajemy
![]() |
co dowodzi, że . Kładąc
w (4.4) otrzymujemy
. Dzielimy obie strony przez
:
![]() |
co kończy dowód.
∎W tym podrozdziale wprowadzimy rodzinę funkcji, dla której spełniony jest warunek:
![]() |
Okazuje się, że rodzina ta obejmuje nie tylko funkcje wypukłe.
Niech będzie otwarty i niepusty, zaś
– różniczkowalna w
. Funkcja
jest pseudowypukła w
, jeśli
![]() |
Funkcja jest ściśle pseudowypukła w
, jeśli
![]() |
Funkcja jest (ściśle) pseudowypukła, jeśli jest ona (ściśle) pseudowypukła w każdym punkcie
.
Funkcja jest (ściśle) pseudowklęsła, jeśli
jest (ściśle) pseudowypukła.
Implikacja w definicji pseudowypukłości ma równoważną postać:
![]() |
Na rysunku 4.2 znajdują się przykłady jednowymiarowych funkcji pseudowypukłych i pseudowklęsłych.
Niech , gdzie
wypukły, otwarty i niepusty. Jeśli
jest (ściśle) wypukła i różniczkowalna na
, to
jest (ściśle) pseudowypukła.
Załóżmy, że wypukła. Na mocy tw. 3.8 dla dowolnych
mamy
![]() |
Jeśli zatem , to
i
jest pseudowypukła. W analogiczny sposób dowodzimy, że ścisła wypukłość pociąga ścisłą pseudowypukłość.
Niech , gdzie
, otwarty, niepusty, będzie funkcją pseudowypukłą w
. Wówczas
jest minimum globalnym wtw, gdy
.
Identyczny jak dowód wniosku 3.2.
∎Dowód poniższego lematu jest identyczny jak dowód twierdzenia 4.2.
Niech wypukły,
pseudowypukła. Mamy następującą równoważność:
jest rozwiązaniem (4.1) wtw, gdy
dla każdego
.
Punktem ekstremalnym zbioru wypukłego nazwiemy taki punkt
, który nie jest punktem wewnętrznym żadnego odcinka zawartego w
, tj. jeśli
dla pewnych
i
, to
.
Otoczką wypukłą punktów nazywamy zbiór punktów będących kombinacją wypukłą skończonej liczby spośród punktów
.
Otoczkę wypukłą można równoważnie definiować jako najmniejszy zbiór wypukły zawierający punkty .
Przedstawimy teraz prostą wersję twierdzenia Kreina-Milmana.
Niech będzie zbiorem wypukłym i zwartym. Jest on wówczas otoczką wypukłą swoich punktów ekstremalnych.
Przed przejściem do dowodu powyższego twierdzenia wprowadzimy niezbędne pojęcia. Przypomnijmy, że przestrzenią afiniczną nazywamy zbiór , taki że
dla dowolnych
i
takich że
. Każda podprzestrzeń afiniczna
może zostać przesunięta tak, aby zawierała
. Staje się ona wówczas podprzestrzenią liniową. Wymiarem podprzestrzeni afinicznej nazywamy wymiar związanej z nią podprzestrzeni liniowej.
Wymiarem zbioru wypukłego nazywamy wymiar otoczki afinicznej
, tzn. podprzestrzeni afinicznej generowanej przez U:
![]() |
Zapiszmy łatwe wnioski z powyższej definicji i rozważań ją poprzedzających:
Zbiór wypukły o wymiarze możemy traktować jako podzbiór przestrzeni
.
Zbiór wypukły w przestrzeni ma niepuste wnętrze wtw, gdy jego wymiar wynosi
.
Dotychczas rozważaliśmy hiperpłaszczyzny podpierające epigraf funkcji wypukłej. Teraz uogólnimy to pojęcie na dowolny zbiór wypukły.
Niech będzie zbiorem wypukłym o niepustym wnętrzu. Przez punkt brzegowy
przechodzi wówczas hiperpłaszczyzna, taka że zbiór
leży w jednej z wyznaczonych przez nią półprzestrzeni. Hiperpłaszczyznę tą nazywamy hiperpłaszczyzną podpierającą zbiór
w punkcie
.
Na mocy słabego twierdzenia o oddzielaniu zastosowanego do i
(zauważmy, że
) istnieje
, takie że
dla każdego
. Szukaną hiperpłaszczyzną jest
![]() |
Zbiór zawarty jest w półprzestrzeni
.
Przeprowadzimy indukcję po wymiarze zbioru zwartego i wypukłego
. Przypadki
(
jest punktem) i
(
jest odcinkiem) są trywialne. Czas na krok indukcyjny. Załóżmy, że każdy zbiór wypukły i zwarty o wymiarze nie większym od
jest otoczką wypukłą swoich punktów ekstremalnych. Weźmy zbiór wypukły i zwarty
o wymiarze
. Zbiór ten traktujemy jako podzbiór
. Ma on wówczas niepuste wnętrze. Niech
.
Przypadek (I): leży na brzegu
. Na mocy lematu 4.4 istnieje hiperpłaszczyzna podpierająca
przechodząca przez
. Zbiór
jest wypukły, zwarty i o wymiarze co najwyżej
. Na mocy założenia indukcyjnego punkt
jest kombinacją wypukłą punktów ekstremalnych
. Pozostaje już tylko wykazać, że punkty ekstremalne
są punktami ekstremalnymi
. Wynika to stąd, że żaden punkt
nie może być przedstawiony jako kombinacja wypukła punktów, z których jeden lub oba nie należą do
.
Przypadek (II): leży we wnętrzu
. Przeprowadźmy przez
dowolną prostą. Przecina ona brzeg
w dwóch punktach
. Z przypadku (I) wiemy, że każdy z punktów
może zostać przedstawiony jako kombinacja wypukła skończonej liczby punktów ekstremalnych
. Punkt
może być zapisany jako kombinacja wypukła
, a więc należy do otoczki wypukłej punktów ekstremalnych
.
Poniżej prezentujemy inny dowód twierdzenia 4.4 bazujący częściowo na pomysłach wykorzystywanych w dowodzie ogólnej wersji twierdzenia Kreina-Milmana. W przeciwieństwie do powyższego rozumowania, dowód ten nie jest konstruktywny.
Jeśli zbiór zawarty jest w
, to teza twierdzenia jest trywialna. Załóżmy więc, że każdy wypukły zwarty podzbiór
jest otoczką wypukłą swoich punktów ekstremalnych. Udowodnimy prawdziwość tego stwierdzenia dla
. Niech
będzie otoczką wypukłą punktów ekstremalnych
. Oczywiście
. Przypuśćmy, że istnieje
. Wówczas możemy znaleźć kulę o środku w
i dostatecznie małym promieniu, która nie przecina
. Na mocy mocnego twierdzenia o oddzielaniu, tw. 3.2, istnieje wektor
, taki że
dla
i
. Niech
. Supremum to jest po całym zbiorze
i jest skończone ze zwartości
. Hiperpłaszczyzna
nie przecina
(bo
), ale ma punkt wspólny z
. Rzeczywiście,
jest niepusty, gdyż ze zwartości
wynika, że supremum definiujące
jest osiągane, czyli istnieje
, dla którego
. Pokażemy, że
zawiera punkt ekstremalny
, co będzie sprzeczne z definicją zbioru
. Zbiór
jest niepustym, zwartym zbiorem wypukłym w przestrzeni afinicznej o wymiarze
. Zbiór
możemy traktować jako podzbiór
, czyli na mocy założenia indukcyjnego jest on otoczką wypukłą swoich punktów ekstremalnych. Niech
będzie jednym z punktów ekstremalnych
i załóżmy, że jest on kombinacją wypukłą
,
dla
. Wówczas
. Z konstrukcji
wynika, że zarówno
jak i
muszą być równe
, czyli
. Z faktu, że
jest punktem ekstremalnym
wnioskujemy, że
, czyli
jest punktem ekstremalnym
.
Niech wypukła, ciągła, określona na wypukłym i zwartym zbiorze
. Wówczas punkt ekstremalny zbioru
jest jednym z rozwiązań globalnych problemu
![]() |
Funkcja ciągła osiąga swoje kresy na zbiorze zwartym. Powyższy problem maksymalizacyjny ma zatem rozwiązanie . Na mocy tw. 4.4 punkt
jest kombinacją wypukłą skończonej liczby punktów ekstremalnych,
, zbioru
, tzn.
![]() |
dla liczb takich że
. Z wypukłości
dostajemy
![]() |
Z faktu, że jest maksimum
na zbiorze
wynika, że
.
Rozważmy następujące zadanie optymalizacyjne:
![]() |
Funkcja celu jest wypukła, więc na mocy twierdzenia 4.5 punkt ekstremalny jest rozwiązaniem. Zbiór punktów dopuszczalnych jest kołem przeciętym z półprzestrzenią, czyli zbiorem wypukłym. Zbiór punktów ekstremalnych zaznaczony jest pogrubioną linią na rysunku 4.3. Jest to fragment okręgu. Zmaksymalizujmy więc funkcję celu na całym okręgu i zobaczmy, czy rozwiązanie należy do tego fragmentu okręgu. Podstawiając do funkcji celu dostajemy
![]() |
Rozwiązaniem tego problemu jest Stąd
Para
należy do półokręgu punktów ekstremalnych, więc jest rozwiązaniem, lecz niekoniecznie jedynym. Para
nie należy do zbioru punktów dopuszczalnych.
Twierdzenie 4.5 jest szczególnie użyteczne przy maksymalizacji funkcji wypukłej na zbiorach wielościennych:
Zbiór nazwiemy zbiorem wielościennym, jeśli jest przecięciem skończonej rodziny półprzestrzeni, tzn.
![]() |
gdzie ,
i
.
Łatwo można zauważyć, że punktami ekstremalnymi ograniczonych zbiorów wielościennych są ,,wierzchołki” (patrz rys. 4.4).
Zbiór wielościenny jest domknięty i wypukły.
Zbiór wielościenny jest domknięty i wypukły jako przecięcie rodziny zbiorów domkniętych i wypukłych.
∎Rozważmy problem optymalizacyjny
![]() |
Funkcja celu jest wypukła, zaś zbiór punktów dopuszczalnych jest wielościenny. Jego punkty ekstremalne to ,
i
, patrz rysunek 4.5. Wartość funkcji celu w tych punktach wynosi odpowiednio:
,
i
. Rozwiązaniem jest zatem punkt
. Można łatwo dowieść, że jest to jedyne rozwiązanie tego problemu.
Udowodnij, że zbiór rozwiązań globalnych zagadnienia (4.1) jest wypukły dla wypukłego zbioru i wypukłej funkcji
.
Rozważmy zagadnienie (4.1) dla wypukłego zbioru i wypukłej funkcji
. Wykaż, że ścisłe rozwiązanie lokalne jest jedynym rozwiązaniem globalnym.
Udowodnij: Niech wypukły oraz
różniczkowalne. Jeśli zachodzi jeden z poniższych warunków:
jest wypukła,
, oraz
jest wklęsła,
,
jest wypukła,
, oraz
jest wypukła,
,
to jest pseudowypukła. Podaj przykład, że
nie jest wypukła.
Udowodnij: Niech wypukły oraz
różniczkowalne. Jeśli
jest wypukła i
oraz
jest wklęsła,
, to
jest pseudowypukła.
Udowodnij, że zbiór minimów funkcji pseudowypukłej , gdzie
wypukły, jest zbiorem wypukłym.
Odpowiedz na następujące pytania:
Czy suma funkcji pseudowypukłych jest pseudowypukła?
Czy jeśli funkcje są pseudowypukłe w punkcie
oraz
, to funkcja
jest pseudowypukła w
?
Czy suma funkcji pseudowypukłej i wypukłej jest pseudowypukła?
Odpowiedzi uzasadnij kontrprzykładami lub dowodami.
Znaleźć rozwiązania zadania
![]() |
Skorzystaj z tw. 4.2.
Rozwiąż zadanie
![]() |
Udowodnij, że jest punktem ekstremalnym zbioru wypukłego
wtw, gdy
jest zbiorem wypukłym.
Wykaż, że jeśli w punkcie brzegowym zbioru wypukłego
istnieje hiperpłaszczyzna podpierająca
, taka że
, to punkt
jest punktem ekstremalnym
.
Zbadaj związek pomiędzy subróżniczką funkcji wypukłej w punkcie a hiperpłaszczyznami podpierającymi epigraf tej funkcji w tym punkcie.
Znaleźć rozwiązanie zadania
![]() |
Rozwiąż problem programowania nieliniowego z ograniczeniami:
![]() |
([3, Zadania 3.28, 3.29])
Zdefiniujmy najstępująco:
![]() |
gdzie jest zbiorem wielościennym,
,
.
Wykaż, że jest wklęsła.
Scharakteryzuj subróżniczkę .
Znajdź subróżniczkę w punktach dla
![]() |
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.