Konvex optimalizálás feladatok

Konvex optimalizálás feladatok (1. gyakorlat, 2014. szeptember 16.)

Mutassuk meg, hogy az f : R → R, f (x) := x2 függvény konvex (a másodrend¶ derivált segítségével, illetve deníció szerint is)!

1. Feladat.

2. Feladat.

Mutassuk meg, hogy az f : R → R, f (x) := |x| függvény konvex (deníció szerint)!

3. Feladat.

Legyen c1 , c2 ∈ R és r ∈ R rögzített. Mutassuk meg, hogy a {(x, y) ∈ R2 | (x − c1 )2 + (y − c2 )2 ≤ r2 }

halmaz konvex! Általánosítsuk a problémát, és igazoljuk, hogy ha X normált tér, p ∈ X és r > 0 tetsz®legesek, akkor B(p, r)cl := {x ∈ X | kx − pk ≤ r}

konvex halmaz! 4. Feladat.

Mutassuk meg, hogy a {(x, y) ∈ R2 | x > 0, y > 0, xy ≥ 1}

halmaz konvex! Határozzuk meg a halmaz konvex burkát, kúp burkát, an burkát és lineáris burkát! 5. Feladat.

Igazoljuk, hogy ha H konvex halmaz, akkor cone(H) is konvex!

6. Feladat.

Vizsgáljuk meg a {f ∈ CR ([0, 1]) | f (0) = 0, f (1) = 1, f (1/2) ≤ 1/2}

halmazt konvexitás szempontjából!

Konvex optimalizálás feladatok (2. gyakorlat, 2014. szeptember 23.)

Igazoljuk, hogy (1) az üres halmaz konvex; (2) ha X lineáris tér, és K(X) jelöli az X konvex részhalmazainak összességét, akkor K(X) konvex kúp; (3) ha X és Y lineáris tér és A ⊆ X × Y konvex, akkor π (A) és π (A) is konvex.

1. Feladat.

X

2. Feladat.

Mutassuk meg, hogy ha X lineáris tér, akkor bármely x , . . . , x 0

esetén

n

∈X

elemek esetén

aff{x0 , . . . , xn } = x0 + lin{x1 − x0 , . . . , xn − x0 }

teljesül! 3. Feladat.

Y

Legyen X topologikus vektortér, D ⊆ X zárt, konvex halmaz. Mutassuk meg, hogy bármely x ∈ X !cl Tx (K) :=

[

λ (K − {x})

λ>0

konvex kúp. (Segítség: rajzoljuk le el®tte a halmazt; mi történik, ha x ∈ K ?) 4. Feladat.

Számoljuk ki a

halmaz an burkát!

{f ∈ C([0, 1]) | f (0) = 0, f (1) = 1, f (1/2) ≤ 1/2}

Legyen X lineáris tér, valamint f : X → R adott függvény. Mutassuk meg, hogy (1) ha f konvex, akkor {f ≤ c} konvex halmaz minden c ∈ R számra; (2) f pontosan akkor kvázikonvex, ha {f ≤ c} konvex minden c ∈ R számra!

5. Feladat.

6. Feladat.

Legyen X lineáris tér, D ⊆ X pedig olyan, hogy 0 ∈ D. Mutassuk meg, hogy az f : X → R,

f (x) := inf{λ ∈ R+ | x ∈ λD}

függvény pontosan akkor konvex a D halmazon, ha D konvex! Legyen X lineáris tér, D ⊆ X és D akkor konvex, ha D konvex kúp! 7. Feladat.

∗

. Mutassuk meg, hogy D pontosan

:= {(λx, λ) | λ > 0, x ∈ D}

∗

8. Feladat.

Legyen I ⊆ R valódi intervallum. Igazoljuk, hogy egy f : I → R függvény pontosan akkor konvex, ha epi(f ) := {(x, y) ∈ I × R | f (x) ≤ y}

konvex halmaz. (Az f függvény pontosan akkor alulról félig folytonos, ha epi(f ) zárt halmaz.) 9. Feladat.

Határozzuk meg a {(0, 0), (0, 1), (1, 0)} ⊆ R halmaz konvex burkát! Vizsgáljuk meg a 2

H := {(x, y) ∈ R2 | x, y ≥ 0, x + y ≤ 1} ⊆ R2

halmazt konvexitás szempontjából!

Konvex optimalizálás feladatok (3. gyakorlat, 2014. szeptember 30.)

1. Feladat.

Tekintsük a

H := {(x, y, z) ∈ R3 | |x| + |y| + |z| ≤ 1}

halmazt (poliéder el®állítás). a.) Mutassuk meg, hogy H konvex halmaz! b.) Adjuk meg a H halmaz politóp el®állítását! c.) Adjuk meg a cone(H), aff(H) és lin(H) halmazokat! 2. Feladat.

Mutassuk meg, hogy H := {f ∈ CR ([0, 1]) | f (0) + f (1) = 0, |f (1/2)| ≤ 1}

konvex halmaz, és adjuk meg cone(H) és lin(H) halmazokat! 3. Feladat.

Mutassuk meg, hogy az f : X → R függvény pontosan akkor an, ha f − f (0) lineáris (X lineáris

4. Feladat.

Legyen X metrikus tér a d metrikával, H ⊆ X és deniáljuk az fH függvényt a következ® módon:

tér)!

fH : X → [0, +∞[ ,

fH (x) := inf d(x, y). y∈H

Mutassuk meg, hogy ha H konvex halmaz, akkor fH konvex függvény 5. Feladat. Legyen X normált tér, ezen kívül tartsuk meg a 4. Feladat összes jelölését! Mutassuk meg, hogy fH Lipschitz-tulajdonságot teljesít, következésképpen folytonos függvény!

Igazoljuk, hogy egy {x1 , . . . , xk } ⊆ Rn vektorrendszer pontosan akkor an függ®, ha az {x1 − xk , . . . , xk−1 − xk } rendszer lineárisan függ®!

6. Feladat.

Legyen X lineáris tér és p : X → [0, +∞[ tetsz®leges norma X -en. Mutassuk meg, hogy az {(x, r) ∈ X × [0, +∞[ | p(x) ≤ r} halmaz konvex! (Gyengíthet®k-e a p függvényre tett feltételek úgy, hogy ez az állítás érvényben maradjon?) Ha r > 0 rögzített, akkor mit lehet mondani az

7. Feladat.

{(x, a) ∈ X × R | p(x) ≤ r, a ∈ R}

halmaz konvexitásáról? Mutassuk meg, hogy ha X lineáris tér és f : X → R lineáris függvény, akkor az {(x, f (x)) | x ∈ X} halmaz an!

8. Feladat.

9. Feladat.

Legyen X lineáris tér és D ⊆ X konvex halmaz! Mutassuk meg, hogy AD := {x ∈ X | létezik λ ∈ [0, 1] : λx ∈ D}

konvex halmaz!

Konvex optimalizálás feladatok (4. gyakorlat, 2014. október 07.)

Tétel. (Konvex halmazok szeparálása lineáris függvénnyel.) konvex halmazok, és tegyük fel, hogy

int(A) 6= ∅, B 6= ∅

és

A ∩ B = ∅.

Legyen

X

topologikus vektortér,

Ekkor létezik

ϕ:X→R

A, B ⊆ X

folytonos lineáris

függvény, hogy

sup ϕ(p) ≤ inf ϕ(p). p∈A

1.

Feladat.

Legyen

meg az összes olyan

p∈B

A := {(x, y) ∈ R2 | y ≤ 0}, valamint B := {(x, y) ∈ R2 | x, y > 0, xy ≥ 1}. ϕ : R2 → R (folytonos) lineáris függvényt, amely szeparálja a megadott halmazokat

Adjuk a fenti

értelemben!

 1 1 1
o A := (conv{(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)}) , valamint B := . Adjuk meg az 3, 3, 3 3 összes olyan ϕ : R → R (folytonos) lineáris függvényt, amely szeparálja a megadott halmazokat a fenti értelemben! 2.

Feladat.

Legyen

3.

Feladat.

Legyen

olyan

ϕ : R3 → R

A := conv{(1, 1, 1), (1, 2, 3), (2, 3, 1), (3, 1, 2)},

valamint

B := {(2, 2, 2)}.

Adjuk meg az összes

(folytonos) lineáris függvényt, amely szeparálja a megadott halmazokat a fenti értelemben!

Konvex optimalizálás feladatok (6. gyakorlat, 2014. november 04.)

1. Feladat. Legyen X lineáris tér, valamint A, B ⊆ X nemüres halmazok. Igazoljuk, hogy ekkor

(1) cor(A) ∪ cor(B) ⊆ cor(A ∪ B), (2) cor(A) ∩ cor(B) = cor(A ∩ B), (3) ha A ⊆ B , akkor cor(A) ⊆ cor(B).

Deníció. Legyen

X lineáris tér, valamint D ⊆ X konvex halmaz. Egy f : D → R konvex függvény p ∈ D pontbeli szubgradiensén a ∂f (p) := {ϕ : X → R | ϕ lineáris és ϕ(h) ≤ f 0 (p, h) minden h ∈ X esetén}. halmazt értjük, ahol 1 (f (p + th) − f (p)) . t Azt mondjuk, hogy az f a p pontban szubdierenciálható, hogy ∂f (p) nem az üres halmaz. f 0 (p, h) := lim

t→0+

Szubdierenciálási szabályok: (1) minden p ∈ D esetén ∂(f + g)(p) = ∂f (p) + ∂g(p),

(2) minden p ∈ D és λ > 0 esetén ∂(λ · f )(p) = λ · ∂f (p), (3) ha g := max{f1 , . . . , fn }, ahol fj : D → R konvex függvény minden j -re, akkor ∂g(p) = conv

[ fj (p)=g(p)

 ∂fj (p) .

2. Feladat. (Házi feladat) Igazoljuk, hogy a szubgradiens mindig konvex halmaz! 3. Feladat. Mutassuk meg, hogy az alábbi függvények konvexek, de nem szubdierenciálhatók az x0 = 0 pontban:

(1) legyen f (0) := 1, és f (x) := 0, ha x > 0; √ (2) legyen f (x) := − x, ha x ≥ 0.

4. Feladat. Adjuk meg az f : R → R, f (x) := |x| függvény szubgradiensét minden p ∈ R pontban! Ábrázoljuk a szubgradiens elemeinek meredekségét a p pont függvényében! Igaz-e, hogy a dierenciálható függvények osztálya zárt a maximumképzésre nézve? 5. Feladat. Adjuk meg az f : R → R, f (x) := −x · χ{y≤0} (x) + x2 · χ{y>0} (x) függvény szubgradiensét minden p∈R

pontban! Ábrázoljuk a p 7−→ ∂f (p) halmazérték¶ leképezés értékkészletét!

Konvex optimalizálás feladatok (7. gyakorlat, 2014. november 11.)

Ha

g : R → R, g(x) := max{f1 (x), . . . , fn (x)} (n ≥ 2), 0

g (p, h) =

∂g(p) = conv minden

p ∈ Dg

és

h ∈ R \ {0}

[

| fj (p) = g(p)},  ∂fj (p) .

fj (p)=g(p)

esetén.

f : R → R, f (x) := max{0, x2 − 1} p 7−→ ∂f (p) leképezés értékkészletét.

1. Feladat. Írjuk fel az

majd ábrázoljuk a

akkor

max{fj0 (p, h)

függvény szubgradiensét tetsz®leges

f : R → R, f (x) := max{2x + 1, 3 − 4x} függvény p 7−→ ∂f (p) halmazérték¶ leképezés értékkészletét.

2. Feladat. Adjuk meg az

pontban. Ábrázoljuk a

3. Feladat. Legyen

x0 ∈ R

és

0
rögzített. Határozzuk meg az

pontban.

4. Feladat. Határozzuk meg az

f : R3 → R, f (x, y, z) := max{0, x + y + z}, g : R2 → R, g(x, y) := max{k(x, y)k2 , x + 3y} függvények szubgradiensét minden értelmezési tartománybeli pontban.

pontban,

szubgradiensét tetsz®leges

f : R → R, f (x) := t(x0 − x)+ + (1 − t)(x0 − x)− függvény szubgradiensét minden

p∈R

p∈R

Konvex optimalizálás feladatok (9. gyakorlat, 2014. november 25.)

1.

Tétel. (KarushKuhnTucker) Legyen X

lineáris tér,

D ⊆ X konvex halmaz, továbbá f0 , f1 , . . . , fn : D →

R konvex függvények és H := {x ∈ D | f1 (x) ≤ 0, . . . , fn (x) ≤ 0}. f0 (p) ≤ f0 (x), ha x ∈ H . Ekkor léteznek

Tegyük fel, hogy f0 -nak a p ∈ cor(D) pontban minimumhelye van, azaz olyan λ0 , λ1 , . . . , λn ≥ 0 valós számok, hogy (1)

λ0 + · · · + λn = 1, (2) 0 ∈ λ0 ∂f0 (p) + · · · + λn ∂fn (p), és (3) λj fj (p) = 0, ha j = 1, . . . , n. Másfel®l, ha (1) és (2) teljesül egy olyan λ0 , λ1 , . . . , λn ≥ 0, λ0 + · · · + λn = 1 konvex kombinációs rendszerrel, ahol λ0 > 0, akkor f0 -nak minimumhelye van a p pontban a fenti H halmazon.

Feladat.

Keressük meg az feltételek mellett, tehát ha 1.

f : R2 → R, f (x, y) := −x függvény minimumhelyeit az x − y ≥ 1 és x2 + y 2 ≤ 1

H = {(x, y) ∈ R2 | f1 (x, y) := x − y − 1 ≤ 0, f2 (x, y) := x2 + y 2 − 1 ≤ 0}.

Feladat.

Legyen párokat, amelyre

2.

A := {(x, y) ∈ R2 | x < 1} és B := {(x, y) ∈ R2 | y 2 + 1 ≤ x}. Adjuk meg azon (a, b) ∈ R2 sup (ax + by) ≤ (x,y)∈A

3.

Feladat.

mellett.

Minimalizáljuk az

inf (ax + by). (x,y)∈B

f : R2 → R, f (x, y) := x + 3y függvényt az x + 2 ≥ y és x2 ≤ 2 − y 2 feltételek

1. zárthelyi dolgozat Konvex optimalizálás, 2014. október 28.

Összesen 25 pont szerezhet®. Az értékelés független a feladatok megoldásának sorrendjét®l.

Legyenek n, m ∈ N tetsz®legesen rögzített természetes számok, H × D ⊆ Rn × Rm konvex, nemüres halmaz, továbbá f : H × D → R konvex, alulról korlátos függvény. Mutassa meg, hogy a 1. Feladat.

g : H → R,

g(x) := inf{f (x, y) | y ∈ D}.

függvény konvex! (A függvény alulról való korlátossága azért kell, hogy g deníciója értelmes legyen!) (5 pont)

2. Feladat.

Igazolja, hogy a H := {f ∈ CR ([0, 1]) | 3f (1) + f (0) = 0, |f (1/3)| ≤ 2}

halmaz konvex! Határozza meg a cone(H) és lin(H) burkokat! (5 pont)

Tekintsük az A := conv{(0, 0, 0), (1, 2, 0), (0, 1, 2), (2, 0, 1)} és B := {(1, 1, 1)} halmazokat R3 -ban. a.) Határozza meg az A halmaz poliéder el®állítását!

3. Feladat.

b.) Adja meg az összes olyan ϕ : R3 → R folytonos lineáris függvényt, melyekre sup (x,y,z)∈A

ϕ(x, y, z) ≤

inf

ϕ(x, y, z)

(x,y,z)∈B

teljesül! (5+5 pont)

4. Feladat.

Legyen X lineáris tér és D ⊆ X konvex halmaz! Mutassa meg, hogy ekkor az AD := {x ∈ X | létezik λ ∈ ]0, 1] : λx ∈ D}

halmaz is konvex! (5 pont)

1

2. zárthelyi dolgozat

Konvex optimalizálás, 2014. december 16.

Összesen 25 pont szerezhet®. Az értékelés független a feladatok megoldásának sorrendjét®l.

1. Feladat.

mellett!

Optimalizálja az f : R2 → R, f (x, y) := 3x + 2y függvényt az y2 ≤ 3 − (x − 1)2 és y ≤ 1 − x feltételek (10 pont)

Számolja ki deníció alapján a g : R → R, g(x) := −2x·χR− (x)+x3 ·χR+ ∪{0} (x) függvény iránymenti deriváltját és szubgradiensét minden értelmezési tartománybeli pontban!

2. Feladat.

(5 pont)

Határozza meg a ||.||2 : R2 → R+ ∪ {0}, ||(x, y)||2 := szubgradiensét minden (p, q) ∈ R2 pontban! 3. Feladat.

p x2 + y 2

függvény iránymenti deriváltját és (5 pont)

√

Igazolja, hogy a k : [−1, +∞[ → R, k(x) := − x + 1 függvény konvex! Szubdierenciálható-e k a p0 = −1, illetve q0 = 2 pontokban? (A függvény konvexitásának igazolásához bármilyen, arra alkalmas módszer felhasználható!) 4. Feladat.

(5 pont)

Szorgalmi feladatok Legyen X lineáris tér, A ⊆ X nemüres konvex halmaz. Mutassa meg, hogy bármely x0 ∈ core(A), és 0 < λ ≤ 1 esetén λx0 + (1 − λ)y ∈ core(A).

1. Feladat.

y∈A

(1 pont)

2. Feladat.

Legyen X lineáris tér. Mutassa meg, hogy ha A ⊆ X nemüres konvex halmaz, akkor core(A)

= core(core(A))

Mely irányú tartalmazás marad érvényben, ha az A halmazról nem tesszük fel, hogy konvex? (1 pont)

Ábrázolja a második feladatban szerepl® g függvény esetén a p 7−→ ∂g(p) halmazérték¶ leképezés értékkészletét! (1 pont) 3. Feladat.

(1 pont) 1Jelölések: R := {u ∈ R | u < 0}, R := {u ∈ R | u > 0}, illetve ha A ⊆ R, akkor χ (x) = 1, ha x ∈ A és χ (x) = 0, ha − + A A

x ∈ R \ A. (Azaz χA jelöli az A halmaz karakterisztikus függvényét.)