Mogliśmy już zaobserwować na kilku przykładach, że wypukłość znacznie ułatwia rozwiązywanie problemów optymalizacyjnych. W rozdziale 3 zauważyliśmy, że warunkiem koniecznym i dostatecznym minimum funkcji wypukłej jest zerowanie się pochodnej. Później wykazaliśmy, że identyczny warunek zachodzi dla większej rodziny funkcji: funkcji pseudowypukłych. W rozdziale 4 zajmowaliśmy się maksymalizacją funkcji wypukłej na zbiorze wypukłym i zwartym. Udowodniliśmy, że maksimum jest przyjmowane w jednym z punktów ekstremalnych tego zbioru. W tym rozdziale rozszerzymy rodzinę funkcji, dla których jest to prawdą; wprowadzimy własność quasi-wypukłości.
Patrząc na powyższą listę można się domyślać, że wypukłość może również pomagać przy rozwiązywaniu zadań z ograniczeniami nierównościowymi. Jeśli założymy, że funkcje , opisujące ograniczenia nierównościowe, są wypukłe lub, ogólniej, quasi-wypukłe oraz funkcja
jest pseudowypukła, to spełnienie warunku pierwszego rzędu w pewnym punkcie
jest wystarczające, by stwierdzić jego optymalność. Dowód powyższego faktu przytoczymy pod koniec tego rozdziału.
W tym podrozdziale rozszerzymy rodzinę funkcji, dla których maksimum znajduje się w punktach ekstremalnych dziedziny.
Niech będzie zbiorem wypukłym, zaś
.
Funkcję nazywamy quasi-wypukłą, jeśli dla dowolnych
i
mamy
![]() |
Funkcję nazywamy quasi-wklęsłą, jeśli funkcja
jest quasi-wypukła, tzn. dla dowolnych
i
zachodzi
![]() |
Funkcję nazywamy quasi-liniową, jeśli jest ona jednocześnie quasi-wypukła i quasi-wklęsła.
Na rys. 7.1 pokazane są przykłady jednowymiarowych funkcji quasi-wypukłych i quasi-wklęsłych. Zwróćmy uwagę na to, że funkcje takie nie muszą być ciągłe, nie mówiąc już o różniczkowalności. Ciekawym jest również uogólnienie rodziny funkcji afinicznych do funkcji quasi-liniowych, patrz rys. 7.2.
Funkcja afiniczna jest quasi-liniowa. Rzeczywiście, niech dla
i
. Wówczas dla dowolnych
i
mamy
![]() |
Prawa strona jest oczywiście nie mniejsza od minimum z i
i nie większa od maksimum tych liczb, czyli
jest zarówno quasi-wypukła jak i quasi-wklęsła.
Przypomnijmy, że zbiorem poziomicowym funkcji nazywamy zbiór
![]() |
Niech , gdzie
wypukły. Wówczas funkcja
jest quasi-wypukła wtw, gdy zbiór poziomicowy
jest wypukły dla każdego
.
Załóżmy, że funkcja jest quasi-wypukła i ustalmy
. Niech
. Wówczas
i
. Dla dowolnego
dostajemy
![]() |
Wnioskujemy stąd, że , czyli
jest zbiorem wypukłym.
Załóżmy teraz, że jest wypukły dla każdego
. Ustalmy
oraz
. Na mocy założenia zbiór
jest wypukły dla
Wynika stąd, że
, czyli
![]() |
Analogiczne twierdzenie dla funkcji wypukłej, tw. 3.5, brzmiało: funkcja jest wypukła wtw, gdy jej epigraf jest zbiorem wypukłym.
Funkcja wypukła jest quasi-wypukła.
Twierdzenie przeciwne nie jest prawdziwe. Poniżej podajemy przykład funkcji quasi-wypukłej, która nie jest wypukła.
Funkcja , dla
, jest quasi-wypukła choć jest ściśle wklęsła. Dla
zbiór
, zaś dla
mamy
. Wszystkie te zbiory są wypukłe, więc na mocy twierdzenia 7.1 funkcja
jest quasi-wypukła. W podobny sposób możemy także pokazać, że funkcja
jest quasi-wklęsła, a zatem quasi-liniowa.
Funkcja ,
, jest ściśle wklęsła a zarazem quasi-liniowa (czyli, między innymi, quasi-wypukła).
Funkcja jest quasi-wypukła, lecz nie jest quasi-wklęsła. Quasi-wypukłość wynika z wypukłości
. Quasi-wklęsłość badamy rozpatrując zbiory poziomicowe funkcji
. Dla
mamy
. Nie jest to zbiór wypukły, czyli funkcja
nie jest quasi-wypukła.
Dowód poniższego lematu pozostawiamy jako zadanie.
Funkcja ,
wypukły, jest quasi-liniowa wtw, gdy jej obcięcie do dowolnego odcinka jest funkcją monotoniczną.
Na mocy tego lematu możemy od razu zauważyć, że funkcja z przykładu 7.2 jest quasi-liniowa.
Okazuje się, że istnieją funkcje quasi-wypukłe jednej zmiennej, które nie są ani wypukłe ani monotoniczne.
Funkcja jest quasi-wypukła. Mamy następujące zbiory poziomicowe w zależności od
:
![]() |
|||
![]() |
|||
![]() |
Wszystkie te zbiory są wypukłe, czyli na mocy tw. 7.1 funkcja jest quasi-wypukła.
Na koniec podamy przykład funkcji quasi-wypukłej wielu zmiennych, która nie jest wypukła.
Funkcja zadana wzorem
jest quasi-wypukła. Jej zbiory poziomicowe dla
są trywialne:
, zaś dla
mają formę przedstawioną na rysunku 7.3. Funkcja
nie jest ani wypukła ani wklęsła, gdyż jej hesjan ma wartości własne
i
Niech i
. Połóżmy
Wówczas funkcja wymierna
![]() |
jest quasi-liniowa. Dowód pozostawiamy jako ćwiczenie.
Zbadamy teraz własności różniczkowalnych funkcji quasi-wypukłych.
Niech dla wypukłego zbioru
.
I) Jeśli funkcja jest quasi-wypukła i różniczkowalna w
, to
![]() |
II) Załóżmy, że funkcja jest różniczkowalna w każdym punkcie
. Wówczas
jest quasi-wypukła wtw, gdy zachodzi następujący warunek:
![]() |
Implikacja ma równoważną postać:
![]() |
Jeśli funkcja jest quasi-liniowa i
, to
.
(I): Ustalmy , dla których zachodzi warunek
. Dla każdego
mamy
![]() |
Wynika stąd, że
![]() |
Z definicji pochodnej kierunkowej dostajemy
![]() |
Dowód (II) pozostawiamy jako niełatwe ćwiczenie.
∎Wiemy już, że funkcja wypukła jest quasi-wypukła. Okazuje się, że również funkcja pseudowypukła jest quasi-wypukła.
Jeśli określona na zbiorze wypukłym
jest pseudowypukła, to
jest quasi-wypukła.
Zakładając, że funkcja nie jest quasi-wypukła doprowadzimy do sprzeczności z pseudowypukłością. Weźmy więc punkty
oraz
spełniające
![]() |
Oznaczmy . Na mocy pseudowypukłości (wykorzystujemy tu warunek pseudowypukłości zapisany w uwadze 4.3) dostajemy:
![]() |
|||
![]() |
Wektory i
mają ten sam kierunek lecz przeciwne zwroty. Pochodna
w punkcie
nie może być ujemna w obu kierunkach. Sprzeczność.
Twierdzenie odwrotne nie jest prawdziwe. Możemy jednak podać warunek dostateczny, przy którym funkcja quasi-wypukła jest pseudowypukła.
Niech określona na zbiorze wypukłym otwartym
będzie quasi-wypukła i ciągła. Jeśli
jest różniczkowalna w
oraz
, to
jest pseudowypukła w
.
Musimy pokazać, że dla każdego warunek
pociąga
. Oznaczmy przez
przestrzeń afiniczną prostopadłą do
i przechodzącą przez
:
![]() |
Z warunku, że wynika, że przestrzeń
ma wymiar
, czyli jest właściwą hiperpłaszczyzną w
.
Zauważmy najpierw, że jeśli i
, to pochodna kierunkowa jest ściśle dodatnia:
. Na mocy uwagi 7.2 wnioskujemy, że
, czyli to, co mieliśmy wykazać. Ustalmy teraz punkt
. Z otwartości
i z tego, że
jest hiperpłaszczyzną wynika, że istnieje ciąg punktów
zmierzający do
i taki że
. Zatem
. Korzystając z ciągłości funkcji
dostajemy
.
Jak zostało zasygnalizowane wcześniej, funkcja quasi-wypukła zachowuje się podobnie jak funkcja wypukła przy maksymalizacji na zbiorze wypukłym zwartym. Dla pełności przytoczymy dowód, który jest prawie identyczny jak dowód twierdzenia 4.5.
Niech quasi-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 quasi-wypukłości
dostajemy
![]() |
Ponieważ w punkcie jest maksimum
na zbiorze
, to dla któregoś z punktów
zachodzi równość
Zajmiemy się problemem optymalizacyjnym, w którym występują zarówno ograniczenia nierównościowe jak i równościowe:
![]() |
(7.1) |
gdzie jest zbiorem otwartym i
. A zatem zbiór punktów dopuszczalnych zadany jest następująco:
![]() |
(7.2) |
Funkcje nazywane są ograniczeniami nierównościowymi, funkcje
są ograniczeniami równościowymi, zaś cały problem (7.1) nazywa się zadaniem optymalizacyjnym z ograniczeniami mieszanymi.
Podamy teraz warunki dostateczne, by punkt spełniający warunki pierwszego rzędu był rozwiązaniem globalnym.
Rozważmy problem optymalizacyjny w kanonicznej formie (7.1) i punkt . Załóżmy, że
funkcje ,
są ciągłe w
, funkcje
,
są różniczkowalne w
i quasi-wypukłe,
funkcje ,
są quasi-liniowe i różniczkowalne w
,
funkcja jest pseudowypukła w
.
Jeśli istnieją stałe oraz
spełniające warunek pierwszego rzędu:
![]() |
(7.3) |
to punkt jest rozwiązaniem globalnym.
Ustalmy dowolny punkt dopuszczalny i pomnóżmy obie strony pierwszego równania w warunku (7.3) przez
:
![]() |
Na mocy tw. 7.2 mamy dla każdego
, bo
. To samo twierdzenie implikuje, że
dla
, ponieważ
. Korzystając z tych obserwacji wnioskujemy z powyższego równania, że
![]() |
Z definicji funkcji pseudowypukłej, . Punkt
wybraliśmy dowolnie spośród punktów dopuszczalnych, a zatem
jest rozwiązaniem globalnym.
Jeśli założenia twierdzenia 7.6 są spełnione lokalnie, na pewnym otoczeniu , to
jest rozwiązaniem lokalnym.
Na mocy twierdzenia 7.4 zamiast zakładać pseudowypukłość funkcji w punkcie
możemy założyć jej ciągłość na
, quasi-wypukłość oraz warunek
. Jest to jedna z form warunku koniecznego zaprezentowana w pracy Arrowa i Enthovena z 1961 roku [1].
Kenneth Joseph Arrow jest amerykańskim ekonomistą. Wspólnie z John'em Hicks'em otrzymał nagrodę Nobla z ekonomii w 1972 roku.
Udowodnij, że funkcja jest quasi-liniowa wtw, gdy jest monotoniczna.
Niech ,
wypukły. Udowodnij następujący fakt: funkcja
jest quasi-liniowa wtw, gdy jej obcięcie do każdego odcinka zawartego w
jest funkcją monotoniczną.
Wykaż, że jeśli funkcja ,
wypukły, jest quasi-wypukła oraz
jest niemalejąca, to funkcja
jest quasi-wypukła. Jeśli natomiast funkcja
jest nierosnąca, to
jest quasi-wklęsła.
Niech będzie funkcją jednej zmiennej. Wykaż, że
jest quasi-wypukła wtw, gdy zachodzi jeden z warunków:
jest monotoniczna,
istnieje taki że
jest nierosnąca dla
oraz niemalejąca dla
.
Dla jakich wartości parametrów funkcja
jest quasi-wypukła?
Sprawdź, że funkcja zadana wzorem
jest quasi-wklęsła.
Znajdź przykład pokazujący, że suma funkcji quasi-wypukłych nie musi być quasi-wypukła.
Niech i
. Wykaż, że funkcja wymierna
![]() |
jest quasi-liniowa na swojej dziedzinie
Niech będzie funkcją liniową i
Wykaż, że jeśli
jest wypukła, to funkcja
dla
jest quasi-wypukła.
Udowodnij, że jeśli jest rodziną funkcji quasi-wypukłych,
jest funkcją nieujemną, to
jest quasi-wypukła, o ile jest skończona dla każdego
.
Niech ,
będą zbiorami wypukłymi, zaś
będzie quasi-wypukła. Wykaż, że
jest quasi-wypukła.
Niech zbiór wypukły,
. Udowodnij, że jeśli
quasi-liniowa, to zbiór
jest wypukły dla dowolnego
.
Niech , ciągła. Udowodnij następującą równoważność:
jest quasi-liniowa wtw, gdy
dla funkcji monotonicznej, ciągłej
oraz wektora
.
Wykaż, że powyższa równoważność nie musi być prawdziwa, gdy funkcję rozważamy na wypukłym podzbiorze właściwym
.
Przeprowadź dowód punktu (II) twierdzenia 7.2.
Dla dowolnych punktów uporządkowanych tak, że
rozważ funkcję
![]() |
oraz zbiór
![]() |
Pokaż, że jeśli zbiór ten jest niepusty, to prowadzi to do sprzeczności z ciągłością funkcji . Oznacz przez
spójną składową
, tzn. przedział.
Udowodnij, że .
Wykaż, że ma niepuste wnętrze.
Wykaż, że funkcja jest stała na
oraz ściśle większa od
.
Wykaż, że istnieje przedział otwarty taki że
.
Zauważ sprzeczność z ciągłością funkcji , bo
.
Wykaż, że funkcja quasi-wypukła (niekoniecznie ciągła) określona na zbiorze wielościennym zwartym przyjmuje swoje maksimum globalne w jednym z punktów ekstremalnych.
Rozważmy problem optymalizacyjny (7.1). Niech będzie punktem dopuszczalnym, w którym spełnione są warunki pierwszego rzędu z mnożnikami Lagrange'a
i
.
Załóżmy, że jest pseudowypukła w
, zaś funkcja
![]() |
jest quasi-wypukła w . Udowodnij, że
jest rozwiązaniem globalnym.
Przypomnijmy, że jest funkcją Lagrange'a. Udowodnij, że jeśli
jest pseudowypukła w
, to
jest rozwiązaniem globalnym.
Wykaż, że warunki zawarte w powyższych punktach nie są równoważne. Znajdź zależności pomiędzy nimi a założeniami twierdzenia 7.6.
Niech będzie rozwiązaniem globalnym problemu optymalizacyjnego (7.1). Załóżmy, że
dla pewnego
. Wykaż, że jeśli ograniczenie
zostanie usunięte, to
może nie być nawet lokalnym rozwiązaniem otrzymanego problemu. Udowodnij natomiast, że jeśli funkcja
jest ciągła w
, to po usunięciu tego ograniczenia
pozostaje rozwiązaniem lokalnym.
Dla jakich wartości parametru problem
![]() |
ma rozwiązanie? Jak zależy ono od wartości ?
Rozwiąż zadanie optymalizacyjne:
![]() |
gdzie , zaś
i
.
Niech będzie funkcją quasi-wklęsłą o pochodnej
dla każdego
. Ustalmy liczbę
i wektor
. Rozważmy problem optymalizacyjny
![]() |
Wektor pełni rolę cen produktów,
ich ilości,
jest wielkością budżetu, zaś funkcja
ocenia satysfakcję z decyzji zakupowej
.
Zapisz warunki Kuhn'a-Tucker'a dla powyższego problemu.
Załóżmy, że jest rozwiązaniem. Czy będzie wówczas istniał wektor mnożników Lagrange'a, dla którego warunki Kuhn'a-Tucker'a są spełnione w
?
Załóżmy, że warunki Kuhn'a-Tucker'a są spełnione w . Czy
jest rozwiązaniem problemu optymalizacyjnego?
Niech będzie rozwiązaniem. Co możesz powiedzieć o związku pomiędzy
a
, gdy
i
?
i
?
i
?
Rozwiąż problem optymalizacyjny
![]() |
gdzie są parametrami.
Niech będzie macierzą symetryczną
dodatnio określoną, zaś
. Rozwiąż problem optymalizacyjny:
![]() |
w zbiorze macierzy symetrycznych i dodatnio określonych.
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.