Zagadnienia

7.1 Quasi-wypukłość
7.2 Maksymalizacja funkcji quasi-wypukłej
7.3 Warunki dostateczne
7.4 Zadania

7. Funkcje quasi-wypukłe i warunki dostateczne

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 gi, opisujące ograniczenia nierównościowe, są wypukłe lub, ogólniej, quasi-wypukłe oraz funkcja f jest pseudowypukła, to spełnienie warunku pierwszego rzędu w pewnym punkcie x¯ jest wystarczające, by stwierdzić jego optymalność. Dowód powyższego faktu przytoczymy pod koniec tego rozdziału.

7.1. Quasi-wypukłość

W tym podrozdziale rozszerzymy rodzinę funkcji, dla których maksimum znajduje się w punktach ekstremalnych dziedziny.

Definicja 7.1

Niech W⊂Rn będzie zbiorem wypukłym, zaś f:W→R.

Funkcję f nazywamy quasi-wypukłą, jeśli dla dowolnych x,y∈W i λ∈0,1 mamy

f⁢λ⁢x+1-λ⁢y≤max⁡f⁢x,f⁢y.

Funkcję f nazywamy quasi-wklęsłą, jeśli funkcja -f jest quasi-wypukła, tzn. dla dowolnych x,y∈W i λ∈0,1 zachodzi

f⁢λ⁢x+1-λ⁢y≥min⁡f⁢x,f⁢y.

Funkcję f nazywamy quasi-liniową, jeśli jest ona jednocześnie quasi-wypukła i quasi-wklęsła.

Rys. 7.1. Przykłady funkcji quasi-wypukłych i quasi-wklęsłych.

Rys. 7.2. Przykłady funkcji quasi-liniowych.

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.

Przykład 7.1

Funkcja afiniczna jest quasi-liniowa. Rzeczywiście, niech f⁢x=aT⁢x+b dla a∈Rn i b∈R. Wówczas dla dowolnych x,y∈W i λ∈0,1 mamy

f⁢λ⁢x+1-λ⁢y=λ⁢f⁢x+1-λ⁢f⁢y.

Prawa strona jest oczywiście nie mniejsza od minimum z f⁢x i f⁢y i nie większa od maksimum tych liczb, czyli f jest zarówno quasi-wypukła jak i quasi-wklęsła.

Przypomnijmy, że zbiorem poziomicowym funkcji f:W→R nazywamy zbiór

Wα⁢f=x∈W:f⁢x≤α,⁢α∈R.

Twierdzenie 7.1

Niech f:W→R, gdzie W⊂Rn wypukły. Wówczas funkcja f jest quasi-wypukła wtw, gdy zbiór poziomicowy Wα⁢f jest wypukły dla każdego α∈R.

Dowód

Załóżmy, że funkcja f jest quasi-wypukła i ustalmy α∈R. Niech x,y∈Wα⁢f. Wówczas f⁢x≤α i f⁢y≤α. Dla dowolnego λ∈0,1 dostajemy

f⁢λ⁢x+1-λ⁢y≤max⁡f⁢x,f⁢y≤α.

Wnioskujemy stąd, że λ⁢x+1-λ⁢y∈Wα⁢f, czyli Wα⁢f jest zbiorem wypukłym.

Załóżmy teraz, że Wα⁢f jest wypukły dla każdego α∈R. Ustalmy x,y∈W oraz λ∈0,1. Na mocy założenia zbiór Wα⁢f jest wypukły dla α=max⁡f⁢x,f⁢y. Wynika stąd, że λ⁢x+1-λ⁢y∈Wα⁢f, czyli

f⁢λ⁢x+1-λ⁢y≤α=max⁡f⁢x,f⁢y.

∎

Uwaga 7.1

Analogiczne twierdzenie dla funkcji wypukłej, tw. 3.5, brzmiało: funkcja f jest wypukła wtw, gdy jej epigraf jest zbiorem wypukłym.

Wniosek 7.1

Funkcja wypukła jest quasi-wypukła.

Dowód

Wynika to wprost z twierdzeń 3.6 i 7.1.

∎

Twierdzenie przeciwne nie jest prawdziwe. Poniżej podajemy przykład funkcji quasi-wypukłej, która nie jest wypukła.

Przykład 7.2

Funkcja f⁢x=-ex2, dla x≥0, jest quasi-wypukła choć jest ściśle wklęsła. Dla α≥-1 zbiór Wα⁢f=0,∞, zaś dla α<-1 mamy Wα⁢f=log⁡-α,∞. Wszystkie te zbiory są wypukłe, więc na mocy twierdzenia 7.1 funkcja f jest quasi-wypukła. W podobny sposób możemy także pokazać, że funkcja f jest quasi-wklęsła, a zatem quasi-liniowa.

Przykład 7.3

Funkcja f⁢x=-ex, x∈R, jest ściśle wklęsła a zarazem quasi-liniowa (czyli, między innymi, quasi-wypukła).

Przykład 7.4

Funkcja f⁢x=x2 jest quasi-wypukła, lecz nie jest quasi-wklęsła. Quasi-wypukłość wynika z wypukłości f. Quasi-wklęsłość badamy rozpatrując zbiory poziomicowe funkcji -f. Dla α<0 mamy Wα⁢-f=-∞,--α∪-α,∞. Nie jest to zbiór wypukły, czyli funkcja -f nie jest quasi-wypukła.

Dowód poniższego lematu pozostawiamy jako zadanie.

Lemat 7.1

Funkcja f:W→R, W⊂Rn 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.

Przykład 7.5

Funkcja f⁢x=e-x2 jest quasi-wypukła. Mamy następujące zbiory poziomicowe w zależności od α:

		Wα⁢f=∅,⁢α≤0,
		Wα⁢f=--log⁡-α,-log⁡-α,⁢α∈0,1,
		Wα⁢f=R,⁢α>1.

Wszystkie te zbiory są wypukłe, czyli na mocy tw. 7.1 funkcja f jest quasi-wypukła.

Na koniec podamy przykład funkcji quasi-wypukłej wielu zmiennych, która nie jest wypukła.

Przykład 7.6

Funkcja f:0,∞2→R zadana wzorem f⁢x1,x2=-x1⁢x2 jest quasi-wypukła. Jej zbiory poziomicowe dla α≥0 są trywialne: Wα⁢f=0,∞2, zaś dla α<0 mają formę przedstawioną na rysunku 7.3. Funkcja f nie jest ani wypukła ani wklęsła, gdyż jej hesjan ma wartości własne -1 i 1.

Rys. 7.3. Zbiór poziomicowy dla funkcji z przykładu 7.6.

Przykład 7.7

Niech a,c∈Rn i b,d∈R. Połóżmy D=x∈Rn:cT⁢x+d>0. Wówczas funkcja wymierna f:D→R

f⁢x=aT⁢x+bcT⁢x+d

jest quasi-liniowa. Dowód pozostawiamy jako ćwiczenie.

Zbadamy teraz własności różniczkowalnych funkcji quasi-wypukłych.

Twierdzenie 7.2

Niech f:W→R dla wypukłego zbioru W⊂Rn.

I) Jeśli funkcja f jest quasi-wypukła i różniczkowalna w y∈W, to

∀⁢x∈W⁢⁢f⁢x≤f⁢y⟹D⁢f⁢y⁢x-y≤0.
II) Załóżmy, że funkcja f jest różniczkowalna w każdym punkcie W. Wówczas f jest quasi-wypukła wtw, gdy zachodzi następujący warunek:

∀⁢x,y∈W⁢⁢f⁢x≤f⁢y⟹D⁢f⁢y⁢x-y≤0.

Uwaga 7.2

Implikacja f⁢x≤f⁢y⟹D⁢f⁢x⁢x-y≤0 ma równoważną postać:

D⁢f⁢y⁢x-y>0⟹f⁢x>f⁢y.
Jeśli funkcja f jest quasi-liniowa i f⁢x=f⁢y, to D⁢f⁢y⁢x-y=0.

Dowód tw. 7.2

(I): Ustalmy x,y∈W, dla których zachodzi warunek f⁢x≤f⁢y. Dla każdego λ∈0,1 mamy

f⁢y+λ⁢x-y=f⁢λ⁢x+1-λ⁢y≤max⁡f⁢x,f⁢y=f⁢y.

Wynika stąd, że

f⁢y+λ⁢x-y-f⁢yλ≤0.

Z definicji pochodnej kierunkowej dostajemy

D⁢f⁢y⁢x-y=limλ↓0⁡f⁢y+λ⁢x-y-f⁢yλ≤0.

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.

Twierdzenie 7.3

Jeśli f:W→R określona na zbiorze wypukłym W⊂Rn jest pseudowypukła, to f jest quasi-wypukła.

Dowód

Zakładając, że funkcja f nie jest quasi-wypukła doprowadzimy do sprzeczności z pseudowypukłością. Weźmy więc punkty x,y∈W oraz λ∈0,1 spełniające

f⁢λ⁢x+1-λ⁢y>max⁡f⁢x,f⁢y.

Oznaczmy z=λ⁢x+1-λ⁢y. Na mocy pseudowypukłości (wykorzystujemy tu warunek pseudowypukłości zapisany w uwadze 4.3) dostajemy:

		f⁢x<f⁢z⟹D⁢f⁢z⁢x-z<0,
		f⁢y<f⁢z⟹D⁢f⁢z⁢y-z<0.

Wektory x-z i y-z mają ten sam kierunek lecz przeciwne zwroty. Pochodna f w punkcie z 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.

Twierdzenie 7.4

Niech f:W→R określona na zbiorze wypukłym otwartym W⊂Rn będzie quasi-wypukła i ciągła. Jeśli f jest różniczkowalna w x¯∈W oraz D⁢f⁢x¯≠0T, to f jest pseudowypukła w x¯.

Dowód

Musimy pokazać, że dla każdego y∈W warunek D⁢f⁢x¯⁢y-x¯≥0 pociąga f⁢y≥f⁢x¯. Oznaczmy przez A przestrzeń afiniczną prostopadłą do D⁢f⁢x¯ i przechodzącą przez x¯:

A=x∈Rn:⁢D⁢f⁢x¯⁢⁢x-x¯=0.

Z warunku, że D⁢f⁢x¯≠0T wynika, że przestrzeń A ma wymiar n-1, czyli jest właściwą hiperpłaszczyzną w Rn.

Zauważmy najpierw, że jeśli y∈W∖A i D⁢f⁢x¯⁢y-x¯≥0, to pochodna kierunkowa jest ściśle dodatnia: D⁢f⁢x¯⁢y-x¯>0. Na mocy uwagi 7.2 wnioskujemy, że f⁢y>f⁢x¯, czyli to, co mieliśmy wykazać. Ustalmy teraz punkt y∈W∩A. Z otwartości W i z tego, że A jest hiperpłaszczyzną wynika, że istnieje ciąg punktów yn⊂W∖A zmierzający do y i taki że D⁢f⁢x¯⁢yn>0. Zatem f⁢yn>f⁢x¯. Korzystając z ciągłości funkcji f dostajemy f⁢y≥f⁢x¯.

∎

7.2. Maksymalizacja funkcji quasi-wypukłej

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.

Twierdzenie 7.5

Niech f:W→R quasi-wypukła, ciągła, określona na wypukłym i zwartym zbiorze W⊂Rn. Wówczas punkt ekstremalny zbioru W jest jednym z rozwiązań globalnych problemu

f⁢x→max,x∈W.

Dowód

Funkcja ciągła osiąga swoje kresy na zbiorze zwartym. Powyższy problem maksymalizacyjny ma zatem rozwiązanie x¯∈W. Na mocy tw. 4.4 punkt x¯ jest kombinacją wypukłą skończonej liczby punktów ekstremalnych, x1,…,xm, zbioru W, tzn.

x¯=a1⁢x1+a2⁢x2+…+am⁢xm

dla liczb a1,…,am>0 takich że a1+…+am=1. Z quasi-wypukłości f dostajemy

f⁢x¯≤max⁡f⁢x1,…,f⁢xm.

Ponieważ w punkcie x¯ jest maksimum f na zbiorze W, to dla któregoś z punktów xi zachodzi równość f⁢xi=f⁢x¯.

∎

7.3. Warunki dostateczne

Zajmiemy się problemem optymalizacyjnym, w którym występują zarówno ograniczenia nierównościowe jak i równościowe:

f⁢x→min,gi⁢x≤0,⁢i=1,…,m,hj⁢x=0,⁢j=1,…,l,x∈X,

(7.1)

gdzie X⊂Rn jest zbiorem otwartym i f,g1,…,gm,h1,…,hl:X→R. A zatem zbiór punktów dopuszczalnych zadany jest następująco:

W=x∈X:g1⁢x≤0,…,gm⁢x≤0,⁢h1⁢x=0,…,hl⁢x=0.

(7.2)

Funkcje gi nazywane są ograniczeniami nierównościowymi, funkcje hj 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.

Twierdzenie 7.6

Rozważmy problem optymalizacyjny w kanonicznej formie (7.1) i punkt x¯∈W. Załóżmy, że

funkcje gi, i∉I⁢x¯ są ciągłe w x¯, funkcje gi, i∈I⁢x¯ są różniczkowalne w x¯ i quasi-wypukłe,
funkcje hj, j=1,…,m, są quasi-liniowe i różniczkowalne w x¯,
funkcja f jest pseudowypukła w x¯.

Jeśli istnieją stałe μ∈0,∞m oraz λ∈Rl spełniające warunek pierwszego rzędu:

D⁢f⁢x¯+∑i∈I⁢x¯μi⁢D⁢gi⁢x¯+∑j=1lλj⁢D⁢hj⁢x¯=0T,μi⁢gi⁢x¯=0,⁢i=1,…,m,

(7.3)

to punkt x¯ jest rozwiązaniem globalnym.

Dowód

Ustalmy dowolny punkt dopuszczalny x∈W i pomnóżmy obie strony pierwszego równania w warunku (7.3) przez x-x¯:

D⁢f⁢x¯⁢x-x¯+∑i∈I⁢x¯μi⁢D⁢gi⁢x¯⁢x-x¯+∑j=1lλj⁢D⁢hj⁢x¯⁢x-x¯=0.

Na mocy tw. 7.2 mamy D⁢hj⁢x¯⁢x-x¯=0 dla każdego j, bo hj⁢x=hj⁢x¯=0. To samo twierdzenie implikuje, że D⁢gi⁢x¯⁢x-x¯≤0 dla i∈I⁢x¯, ponieważ 0=gi⁢x¯≥gi⁢x. Korzystając z tych obserwacji wnioskujemy z powyższego równania, że

D⁢f⁢x¯⁢x-x¯≥0.

Z definicji funkcji pseudowypukłej, f⁢x≥f⁢x¯. Punkt x wybraliśmy dowolnie spośród punktów dopuszczalnych, a zatem x¯ jest rozwiązaniem globalnym.

∎

Uwaga 7.3

Jeśli założenia twierdzenia 7.6 są spełnione lokalnie, na pewnym otoczeniu x¯, to x¯ jest rozwiązaniem lokalnym.

Uwaga 7.4

Na mocy twierdzenia 7.4 zamiast zakładać pseudowypukłość funkcji f w punkcie x¯ możemy założyć jej ciągłość na X, quasi-wypukłość oraz warunek D⁢f⁢x¯≠0T. 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.

7.4. Zadania

Ćwiczenie 7.1

Udowodnij, że funkcja f:a,b→R jest quasi-liniowa wtw, gdy jest monotoniczna.

Ćwiczenie 7.2

Niech f:W→R, W⊂Rn wypukły. Udowodnij następujący fakt: funkcja f jest quasi-liniowa wtw, gdy jej obcięcie do każdego odcinka zawartego w W jest funkcją monotoniczną.

Ćwiczenie 7.3

Wykaż, że jeśli funkcja f:W→R, W⊂Rn wypukły, jest quasi-wypukła oraz g:R→R jest niemalejąca, to funkcja g∘f jest quasi-wypukła. Jeśli natomiast funkcja g jest nierosnąca, to g∘f jest quasi-wklęsła.

Ćwiczenie 7.4

Niech f:a,b→R będzie funkcją jednej zmiennej. Wykaż, że f jest quasi-wypukła wtw, gdy zachodzi jeden z warunków:

f jest monotoniczna,
istnieje x¯∈a,b taki że f jest nierosnąca dla x<x¯ oraz niemalejąca dla x>x¯.

Ćwiczenie 7.5

Dla jakich wartości parametrów a,b,c,d∈R funkcja f⁢x=a⁢x3+b⁢x2+c⁢x+d jest quasi-wypukła?

Ćwiczenie 7.6

Sprawdź, że funkcja f:0,∞2→R zadana wzorem f⁢x1,x2=e-x1⁢x2 jest quasi-wklęsła.

Ćwiczenie 7.7

Znajdź przykład pokazujący, że suma funkcji quasi-wypukłych nie musi być quasi-wypukła.

Ćwiczenie 7.8

Niech a,c∈Rn i b,d∈R. Wykaż, że funkcja wymierna

f⁢x=aT⁢x+bcT⁢x+d

jest quasi-liniowa na swojej dziedzinie D=x∈Rn:cT⁢x+d>0.

Ćwiczenie 7.9

Niech h:Rn→R będzie funkcją liniową i W=x∈Rn:⁢h⁢x>0. Wykaż, że jeśli f:W→R jest wypukła, to funkcja g⁢x=f⁢x/h⁢x dla x∈W jest quasi-wypukła.

Ćwiczenie 7.10

Udowodnij, że jeśli gαα∈I jest rodziną funkcji quasi-wypukłych, w:I→R jest funkcją nieujemną, to h⁢x=supα∈I⁡w⁢α⁢gα⁢x jest quasi-wypukła, o ile jest skończona dla każdego x.

Ćwiczenie 7.11

Niech A⊂Rn, C⊂Rm będą zbiorami wypukłymi, zaś f:A×C→R będzie quasi-wypukła. Wykaż, że h⁢x=infc∈C⁡f⁢x,c jest quasi-wypukła.

Ćwiczenie 7.12

Niech W⊂Rn zbiór wypukły, f:W→R. Udowodnij, że jeśli f quasi-liniowa, to zbiór x∈W:f⁢x=α jest wypukły dla dowolnego α∈R.

Ćwiczenie 7.13

Niech f:Rn→R, ciągła. Udowodnij następującą równoważność: f jest quasi-liniowa wtw, gdy f⁢x=g⁢aT⁢x dla funkcji monotonicznej, ciągłej g:R→R oraz wektora a∈Rn.

Wykaż, że powyższa równoważność nie musi być prawdziwa, gdy funkcję f rozważamy na wypukłym podzbiorze właściwym Rn.

Ćwiczenie 7.14

Przeprowadź dowód punktu (II) twierdzenia 7.2.

Wskazówka:

Dla dowolnych punktów x,y∈W uporządkowanych tak, że f⁢x≤f⁢y rozważ funkcję

g⁢λ=f⁢λ⁢x+1-λ⁢y,⁢λ∈0,1

oraz zbiór

A=λ∈0,1:⁢g⁢λ>g⁢0.

Pokaż, że jeśli zbiór ten jest niepusty, to prowadzi to do sprzeczności z ciągłością funkcji f. Oznacz przez A⌃ spójną składową A, tzn. przedział.

Udowodnij, że ∀⁢λ∈A⁢⁢g′⁢λ=0.
Wykaż, że A⌃ ma niepuste wnętrze.
Wykaż, że funkcja f jest stała na A⌃ oraz ściśle większa od g⁢0.
Wykaż, że istnieje przedział otwarty I⊂0,1 taki że I∩A=A⌃.
Zauważ sprzeczność z ciągłością funkcji f, bo fA⌃>fI∖A⌃.

Ćwiczenie 7.15

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.

Ćwiczenie 7.16

Rozważmy problem optymalizacyjny (7.1). Niech x¯ będzie punktem dopuszczalnym, w którym spełnione są warunki pierwszego rzędu z mnożnikami Lagrange'a μ i λ.

Załóżmy, że f jest pseudowypukła w x¯, zaś funkcja

ϕ⁢x=∑i=1mμi⁢gi⁢x+∑j=1lλj⁢hj⁢x

jest quasi-wypukła w x¯. Udowodnij, że x¯ jest rozwiązaniem globalnym.
Przypomnijmy, że L⁢x,μ,λ jest funkcją Lagrange'a. Udowodnij, że jeśli x↦L⁢x,μ,λ jest pseudowypukła w x¯, to x¯ 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.

Ćwiczenie 7.17

Niech x¯ będzie rozwiązaniem globalnym problemu optymalizacyjnego (7.1). Załóżmy, że gk⁢x¯<0 dla pewnego k∈1,…,m. Wykaż, że jeśli ograniczenie gk⁢x≤0 zostanie usunięte, to x¯ może nie być nawet lokalnym rozwiązaniem otrzymanego problemu. Udowodnij natomiast, że jeśli funkcja gk jest ciągła w x¯, to po usunięciu tego ograniczenia x¯ pozostaje rozwiązaniem lokalnym.

Ćwiczenie 7.18

Dla jakich wartości parametru α∈R problem

x1+x2+α⁢x1-12→min,x1-x2≤0,x1≥0

ma rozwiązanie? Jak zależy ono od wartości α?

Ćwiczenie 7.19

Rozwiąż zadanie optymalizacyjne:

bT⁢x→min,xp≤1,

gdzie b∈Rn, zaś xp=∑i=1nxip1/p i p>1.

Ćwiczenie 7.20

Niech u:0,∞n→R będzie funkcją quasi-wklęsłą o pochodnej D⁢u⁢x>0 dla każdego x. Ustalmy liczbę w>0 i wektor p∈0,∞n. Rozważmy problem optymalizacyjny

u⁢x→max,∑i=1npi⁢xi≤w,x≥0.

Wektor p pełni rolę cen produktów, x ich ilości, w jest wielkością budżetu, zaś funkcja u ocenia satysfakcję z decyzji zakupowej x.

Zapisz warunki Kuhn'a-Tucker'a dla powyższego problemu.

Załóżmy, że x¯ 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 x¯?
Załóżmy, że warunki Kuhn'a-Tucker'a są spełnione w x¯. Czy x¯ jest rozwiązaniem problemu optymalizacyjnego?
Niech x¯ będzie rozwiązaniem. Co możesz powiedzieć o związku pomiędzy pi/pj a ui′⁢x¯/uj′⁢x¯, gdy
- x¯i>0 i x¯j>0?
- x¯i=0 i x¯j>0?
- x¯i=0 i x¯j=0?

Ćwiczenie 7.21

Rozwiąż problem optymalizacyjny

x+y→max,p⁢x+y≤I,x,y≥0,

gdzie p,I>0 są parametrami.

Ćwiczenie 7.22

Niech A będzie macierzą symetryczną n×n dodatnio określoną, zaś b∈0,∞. Rozwiąż problem optymalizacyjny:

-log⁢det⁡X→min,t⁢r⁢A⁢X≤b,

w zbiorze macierzy X∈Rn×n symetrycznych i dodatnio określonych.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Optymalizacja II

Zagadnienia

7. Funkcje quasi-wypukłe i warunki dostateczne

7.1. Quasi-wypukłość

Definicja 7.1

Przykład 7.1

Twierdzenie 7.1

Dowód

Uwaga 7.1

Wniosek 7.1

Dowód

Przykład 7.2

Przykład 7.3

Przykład 7.4

Lemat 7.1

Przykład 7.5

Przykład 7.6

Przykład 7.7

Twierdzenie 7.2

Uwaga 7.2

Dowód tw. 7.2

Twierdzenie 7.3

Dowód

Twierdzenie 7.4

Dowód

7.2. Maksymalizacja funkcji quasi-wypukłej

Twierdzenie 7.5

Dowód

7.3. Warunki dostateczne

Twierdzenie 7.6

Dowód

Uwaga 7.3

Uwaga 7.4

7.4. Zadania

Ćwiczenie 7.1

Ćwiczenie 7.2

Ćwiczenie 7.3

Ćwiczenie 7.4

Ćwiczenie 7.5

Ćwiczenie 7.6

Ćwiczenie 7.7

Ćwiczenie 7.8

Ćwiczenie 7.9

Ćwiczenie 7.10

Ćwiczenie 7.11

Ćwiczenie 7.12

Ćwiczenie 7.13

Ćwiczenie 7.14

Ćwiczenie 7.15

Ćwiczenie 7.16

Ćwiczenie 7.17

Ćwiczenie 7.18

Ćwiczenie 7.19

Ćwiczenie 7.20

Ćwiczenie 7.21

Ćwiczenie 7.22