1.Pojęcie zbioru wypukłego, otoczki wypukłej zbioru. Działania na zbiorach wypukłych (przecięcie dowolnej rodziny zbiorów wypukłych jest zbiorem wypukłym).

Definicja:

X rzeczywista przestrzeń liniowa. Mówimy, że zbiór C
X jest zbiorem wypukłym

x,y
C odcinek [x,y]
C

[x,y] odcinek domknięty o końcach x i y

[x,y] : = {z
X ׀ z =
_x + (1-
y) }

0

<1

Zbiór pusty z definicji jest zbiorem wypukłym.

Stwierdzenie:

(At) _t€T dowolna indeksowana rodzina zbiorów wypukłych przestrzeni X,Ť dowolny zbiór skończony lub nieskończony
A_t wypukły podzbiór X

wtedy
A_t jest wypukłym zbiorem w X

x€A_t

ω (X)rodzina wszystkich wypukłych podzbiorów przestrzeni X

C
X, coC lub conrC czytamy: otoczka wypukła zbioru C.

coC:=
A A€ ω (X)

coC- otoczka wypukła zbioru C jest to przecięcie (część wspólna, iloczyn) wszystkich zbiorów wypukłych zawierających zbiór C. Jest to najmniejszy zbiór wypukły zawierający zbiór C.

PRZYKŁAD:

X=
coC = [x,y]

C={x=(
,
), y=(
,
)}

x
y

2.Pojęcie funkcji wypukłej, efektywny zbiór funcji f (domf), epifgrat f (epif), nierówność Jensena, (działania na funkcjach wypukłych).

X - rzeczywista przestrzeń liniowa

f: X →¯R= R
{
,
}

z funkcją f są związane dwa zbiory:

dom f - efektywny zbiór funkcji f

dom f:= {x € X | f(x) <
}

epi f - epigraf funkcji f (nadwykres funkcji f)

epi f:= {(x,
) € X
R|

Niech f: X → ¯R

Mówimy, że funkcja f jest funkcją wypukłą, jeżeli epif jest zbiorem wypukłym

Mówimy, że funkcja f: X → ¯R jest funkcją właściwą, jeżeli Vx € X f(x)>-∞ oraz domf ≠Ø (to oznacza że f
+∞ (nie jest tożsamościowo równa +∞)

TWIERDZENIE:

Niech f: X → ¯R właściwa funkcja, gdzie X rzeczywista przestrzeń liniowa wtedy są równoważne następujące warunki:

1)
n € N

,
…
€ domf

,
,……

zachodzi nierówność Jensena

f (
)≤
f(x_i)

2)

,
€ domf

zachodzi nierówność Jensena

f(
)≤
-warunek 2 geometrycznie oznacza że wykres funkcji y = f(x) leżące pomiędzy prostymi pionowymi o równaniach x =
i x =
leży poniżej odcinka łączącego punkty (
,f(
) i (
,f(
)

3) epif jest zbiorem wypukłym

STWIERDZENIE

a) (f _t ) _t€T dowolna indeksowana rodzina właściwych funkcji wypukłych określonych na przestrzeni liniowej X o wartościach w ¯R, T - dowolny zbiór skończony lub nieskończony wtedy funkcja f =
jest funkcją wypukłą

f =
(x) jest funkcją wypukłą (f =
(x)
x€X)

b)
,..,
wypukłe właściwe funkcje określone na X o wartościach w ¯R wtedy funkcja
jest właściwą funkcją wypukłą tzn. suma skończonej liczby funkcji wypukłych jest funkcją wypukłą.

: X → ¯R wypukłe właściwe funkcji

f = max{
}

x € X f(x) = max {
(x),
(x)} wtedy f jest właściwą wypukłą funkcją

epif = epi
∩ epi

epif = ∩ epif_t

WYKRES

3. Pojęcie subróżniczki funkcji wypukłej , twierdzenie Rockafellara - Moreau, twierdzenie Dubowickiego - Miliutina , uogólnione twierdzenie Fermata?

Subróżniczka różniczkowalnej funkcji wypukłej pokrywa się z jej pochodną. Dla funkcji jednej zmiennej subróżniczka
jest zbiorem współczynników kierunkowych, a dla których proste y = ax + b przechodzące przez punkt
leżą poniżej wykresu funkcji y=f(x).

Przykład: f: R → R,
x € R ,

f (x) = ׀x׀ = {

Twierdzenie Rockafellara - Moreau

Niech f₁, f₂:X→¯R wypukłe właściwe funkcje, gdzie X=Rⁿ wtedy

1.∂(f₁+f₂) (x) > ∂f₁(x) + ∂f₂ (x)

2.jeśli istnieje punkt x₀ taki, że x₀ € domf₁ tzn.│ f₁ (x₀)<∞, a funkcja f₂ jest ciągła w punkcie x₀, to ∂(f₁+f₂) (x) > ∂f₁(x) + ∂f₂ (x)
x € X

Twierdzenie Rockafellara - Moreau jest naturalnym uogólnieniem twierdzenia z klasycznej analizy o pochodnej sumy funkcji: pochodna sumy funkcji jest równa sumie pochodnych.

Twierdzenie Dubowickiego Miliutina

Niech f₁, f₂:X→¯R wypukłe właściwe funkcje

x₀ € domf₁∩ domf₂

f₁, f₂ ciągłe w punkcie x₀ i f₁(x₀) = f₂(x₀), wtedy ∂ max { f₁, f₂ }(x₀) = conv( ∂ f₁(x₀) u ∂ f₂(x₀))

Uogólnione Twierdzenie Fermata

f:X→¯R wypukłe właściwe funkcje, X=Rⁿ

€ absminf
0 € ∂ f (
)

€ absminf

x € X f(x)≥ f (
)

x € X f(x)- f (
) ≥ 0
0 € ∂ f (
)

Uogólnione Twierdzenie Fermata sformułowane powyżej jest warunkiem koniecznym i dostatecznym, aby punkt x ( z daszkiem) był absolutnym minimum wypukłej właściwej funkcji. Tw. Fermata w klasycznej analizie jest tylko warunkiem koniecznym lokalnego ekstremum gładkiej funkcji (różniczkowalnej).

4.Zadanie programowania wypukłego i sformułuj twierdzenie KUNATUCKERA.

Zadanie programowania wypukłego

X- rzeczywista przestrzeń liniowa

A- nie pusty zbiór wypukły w X

fi: X → ¯R i = 0,1,…..m

Zadaniem programowania wypukłego nazywamy następujące ekstremalne zadania:

(P) f_o (x)
min,

f_i (x)
0, i=1,2,…,m x
A

Dp - zbiór elementów dopuszczalnych z zadania P

Dp: {x
X │f_i (x)
0, i=1,2,…,m }

x
А}

Punkt
- punkt
jest absolutnym minimum z zadania P

α
gdzie

R ^m+1

Funkcja α (x,
) nazywamy funkcją Lagrange^'a zadania (P).

Liczby
i = 0,1,…,m nazywamy mnożnikami Lagrange^'a.

Wektor
= (
o,
1,….,
m) nazywamy wektorem mnożników Lagrange^'a.

Uwaga - ograniczenie x
А nie wchodzi do funkcji Lagrange^'a.

Twierdzenie KUHNA-TUCKERA

1.Niech
będzie absolutnym minimum w zadaniu (P), gdzie P to zadanie programowania wypukłego wtedy istnieje
^m+1

taki, że dla funkcji Lagrange^'а zadania (P) zachodzą następujące warunki:

а) min α(x,
) = α
x
А

Zasada minimum funkcji Lagrange^'а

b) warunki komplementarności

c) warunki nieujemności

2. Jeżeli
(jest elementem dopuszczalnym zadania(P))i są spełnione warunki а) - c) z

3. Jeżeli
i są spełnione warunki а) - c) oraz zachodzi warunek SLATERA

to

Uwaga. Dla zadania wypukłego programowania idea Lagrange^'а uzyskała najbardziej doskonałą postać. Punkt
będący rozwiązaniem wypukłego zadania jest punktem minimum funkcji Lagrange^'а (dotyczy warunku а)). Warunki b) i c) są charakterystyczne dla zadań z ograniczeniami nierównościowymi. Warunek konieczny na absolutne minimum w zadaniu programowania wypukłego jest bliski warunkowi dostatecznemu. Warunek konieczny pokrywa się z warunkiem dostatecznym, jeśli
jest różna od 0(
).

5. Pojęcie miary ryzyka, pojęcie wypukłej miary ryzyka i pojęcie koherentnej miary ryzyka.

Definicja.

Odwzorowanie ℓ :

R nazywamy miarą ryzyka jeżeli są spełnione następujące warunki:

1.
X, Y

, X
Y
ℓ (X)
ℓ(Y) monotoniczność+

2.
X


m
R
ℓ (X+m) = ℓ(X) - m niezmienność względem przesunięcia z której wynika, że ℓ( X+ ℓ (X)) = 0 i ℓ(m) = ℓ (0) - m
m
R.

W większości przypadków zakłada się, że miara ryzyka spełnia warunek unormowania czyli

ℓ (0) = 0

Definicja

Mówimy, że miara ryzyka ℓ :

R jest wypukła jeżeli dla

X, Y


0


1

zachodzi nierówność

ℓ (
X + (1-
)Y)

ℓ(X) + (1-
) ℓ (Y)

Definicja

Wypukłą miarą ryzyka ℓ nazywamy koherentną miarą ryzyka jeżeli spełnia ona następujący warunek

0 ℓ (
X) =
ℓ(X) to się nazywa dodatnia jednorodność.

Z dodatniej jednorodności miary wynika, że spełnia ona warunek unormowania tzn., że

ℓ(0) = 0.

Jeżeli spełniony jest warunek dodatniej jednorodności to wypukłość miary ryzyka jest równoważna jej subaddytywności ℓ (X+Y)
ℓ(X) + ℓ (Y)
X,Y

6. Sformułuj skończenie wymiarowe gładkie zadanie z ograniczeniami równościowymi oraz zasadę Lagrang'ea dla tego zadania?

Niech f_i:Rⁿ→R, i=0,1,2…m Funkcja n zmiennych rzeczywistych o wartościach rzeczywistych. Zakładam, że funkcja f_i; i=0,1,2…n₁ spełnia pewien warunek gładkości tzn. są różniczkowane w określonym sensie. Gładkie skończenie wymiarowe zadanie ekstremalne z ograniczeniami równościowymi nazywamy następujące zadanie(P):

f₀(x)→extr f_i(x)=0 , i=1,2…m
Przez rozwiązanie pełne zadania P nazywamy: znalezienie lokalnych ekstremum zadania tj. lokalnych minimów i lokalnych maksimów, znalezienie absolutnego min. i maks., oraz określenie wartości minimalnej i maksymalnej zadania. Dp- zbiór elementów dopuszczalnych zadania P
Dp=
ⁿ
f_i(x)=
i=1,2…m
x=(x₁,x₂...x₃)
Rⁿ
||x||- norma wektora X
||x||= ∑ⁿ_i=1 x_i²
Norma określa odległość (metryka)
x=(x₁,x₂…x_n)
y=(y₁,y₂…y_n)
d(x,y)=||x-y||= ∑ⁿ_i=1(x₁-y₁)²

є locmin(P) - punkt
jest lokalnym minimum w zadaniu (P)

єDp


f₀(x)
₀(
)
K(
,
- kula otwarta o środku
i promieniu

K(
,
ⁿI||x-
||

locmax (P)


_^
f₀(x)
f₀ (
)
Lokalne minima i lokalne maksima z zadnia (P) nazywamy lokalnymi ekstremalnymi zadaniami (P)


absmin (P)
f₀(0)
f₀(
)


absmax(P)


f₀(x)
f₀(
)

Funkcja Lagrang'ea z zadania (P)
Funkcja
₀,λ_1,…λ_m)
<sup>m+1

n</sup>_i=oλ_if_i(x)
Funkcje
(x,λ) określoną powyżej nazywamy funkcją Lagrang'ea zadania (P)
wektor λ=(λ₀,λ₁…λ_m)
^m+1nazywamy wektorem wskaźników Lagrang'ea liczbę λ_i, i=0,1…m nazywamy mnożnikami Lagrang'ea.
Warunek konieczny pierwszego rzędu na lokalne ekstremum dla gładkiego zadania z ograniczeniami równościowymi - zasada Lagrang'ea.
Niech

locextr(P) a funkcje f_i, i=0,1…m są ciągle różniczkowane w pewnym otwartym otoczeniu punktu
(warunek gładkości) wtedy istnieje niezerowy wektor nośników Lagrang'ea. Λ=(λ_0,λ₁…λ_n)
R^m+1 , λ
0 taki że dla funkcji Lagrang'ea z zadania (P)
(x,λ) = ∑^m_i=0 λ_if_i(x) zachodzi warunek stacjonarności tzn.
1≤ j ≤ n
x_j(
,λ)=0

x_j (
,λ)- pochodna cząstkowa funkcji Lagrang'ea po x_j w punkcie (
,λ)

7. Sformułuj gładkie, skończenie wymiarowe zadanie ekstremalne z ograniczeniami równościowymi i nierównościowymi oraz zasadę Lagrangea dla tego zadania.

Niech f₁:Rⁿ→R , i=0,1,2....m funkcji n zmienny rzeczywistych o wartościach rzeczywistych. Założenie że funkcje f_i, i=0,1,2…n spełniają pewien warunek gładkości tzn. są różniczkowalne w określonym sensie. Gładkim skończenie wymiarowym zadaniem ekstremalnym z ograniczeniami równościowymi i nierównościowymi nazywamy następujące zadanie (P): f₀(x)→min
f_i(x)≤0 , i =1,2…m'
f_i(x)=0 , i = m'+1,…m

Warunek konieczny I rzędu na lokalne ekstremum w gładkim skończenie wymiarowym zadaniu ekstremalnym z ograniczeniami równościowymi i nierównościowymi - zasada Lagrangea.

Niech

loc min (P) - punkt lokalnego minimum w zadaniu (P), a funkcje f_i, i= 0,1,...,m są ciągle różniczkowalne w pewnym otoczeniu punktu
(warunek gładkości).Wtedy istnieje niezerowy wektor mnożników Lagrangea

λ= λ₀, λ₁, ...,λ_m
R ^m+1 λ ≠ 0 taki, że dla funkcji lagrangea zad. (P)

λ= λ₀, λ₁, ...,λ_m
R ^m+1 λ ≠ 0 taki, że dla funkcji lagrangea zad. (P)

(x, λ) = ^ (x₁,...,x_n), (λ₀,...,λ_n) = ∑^m_i=0 λ_i f_i (x) = ∑^m_i=0 λ_i f_i (x₁, x₂,...,x_m)

zachodzą następujące warunki

a)warunki stacjonarności

_xj (
, λ) = 0
1≤ j ≤ n

b)warunki komplementarności

λ_i f_i (
)= 0 i= 1,2...,m'

c) warunki nieujemności

λ_i ≥ 0 i= 0,1,...,m'

---