To Seminar 2 Convexitate [PDF]

Zitiervorschau

Tehnici de optimizare Seminar 2 Multimi si functii convexe

1

1

Multimi convexe

Definitie 1. O multime S se numeste convexa, daca pentru oricare doua puncte x1 , x2 ∈ S si pentru orice α ∈ [0, 1] avem αx1 + (1 − α)x2 ∈ S.

(1)

Figure 1: Exemplu de multime convexa (stanga) si neconvexa (dreapta). Intr-o formulare mai simpla, o multime este convexa daca pentru oricare doua puncte din multime, segmentul care le uneste se afla, de asemenea, in multime. Definitie 2. Fie p puncte x1 , · · · , xp , o combinatie convexa intre aceste p P P puncte se defineste ca αi xi , unde scalarii αi satisfac αi ≥ 0 si i αi = 1. i=1

Definitie 3. Acoperirea convexa a unei multimi S (notatie conv(S)), este definita de multimea: X X conv(S) = { αi xi : xi ∈ S, αi = 1, αi ≥ 0}. i

i∈I,If inita

Teorema 1. Fie o multime convexa S ⊆ Rn . Atunci, orice element din multimea S este o combinatie convexa de cel mult n + 1 vectori din S.

1.1

Exemple de multimi convexe

1. Hiperplanul reprezinta multimea convexa, definita sub forma:  H = x ∈ Rn : aT x = b , n

unde a ∈ R , a 6= 0, b ∈ R. 2

(2)

Exercitiul 1. Sa se arate ca hiperplanul este o multime convexa.  Rezolvare. Consideram un hiperplan H = x ∈ Rn : aT x = b . Pentru a demonstra ca o multime este convexa se considera oricare doua puncte din multime si se arata ca segmentul ce le uneste se afla, de asemenea, in multime. Fie doua puncte x1 , x2 ∈ H, atunci din definitia hiperplanului avem aT x1 = b si aT x2 = b. Se verifica daca xα = αx1 + (1 − α)x2 ∈ H, ∀α ∈ [0, 1]. aT xα = aT (αx1 + (1 − α)x2 ) =

2. Semispatiul este o multime convexa, definita astfel: 

x ∈ R n : aT x ≥ b



sau

 x ∈ R n : aT x ≤ b ,

unde a ∈ Rn , a 6= 0, b ∈ R.

Figure 2: Semispatiul (caz scalar) - zona superioara ax ≥ b, zona inferioara ax ≤ b

3

3. Bila de raza r > 0 si centrul in x0 ∈ Rn este un alt exemplu de multime convexa si se defineste ca: B(x0 , r) = {x ∈ Rn : kx − x0 k ≤ r} = {x ∈ Rn : x = x0 + ru, kuk ≤ 1} . (3) Exercitiul 2. Sa se arate ca bila este este o multime convexa. Rezolvare. Fie x1 , x2 ∈ B(x0 , r). Din relatia (3) rezulta ca x1 si x2 satisfac: kx1 − x0 k ≤ r, kx2 − x0 k ≤ r. Notam xα = αx1 + (1 − α)x2 . Se verifica daca xα ∈ B(x0 , r) pentru orice α ∈ [0, 1]. kαx1 + (1 − α)x2 − x0 k = kαx1 + (1 − α)x2 − αx0 − (1 − α)x0 k = kα(x1 − x0 ) + (1 − α)(x2 − x0 )k ≤ α kx1 − x0 k + (1 − α) kx2 − x0 k ≤ αr + (1 − α)r = r In ultima inegalitate am folosit presupunerea ca x1 ∈ B(x0 , r) si x2 ∈ B(x0 , r). Am aratat ca xα ∈ B(x0 , r), ∀α ∈ [0, 1]. 4. Elipsoidul este multimea convexa definita ca: n o T −1 n x ∈ R : (x − x0 ) Q (x − x0 ) ≤ 1 = { x0 = Lu : kuk ≤ 1} (4) pentru care Q > 0 (pozitiv definita), si L = Q dat de factorizarea Cholesky. 1 2

Exercitiul 3. Demonstrati ca elipsoidul este o multime convexa. 5. Poliedronul este multimea convexa definita astfel: (n ) n2 1 X X X (αi vi ) + (βj rj ) : αi = 1, αi ≥ 0, βj ≥ 0 i=1

j=1

(5)

i

unde vi sunt varfuri si rj sunt raze ale poliedronului. Observatie: Un poligon este un poliedron marginit. In acest caz razele lipsesc, si de aceea avem doar combinatii convexe de varfuri. 4

Figure 3: Poliedron

1.2

Conuri

Definitie 4. O multime K se numeste con daca pentru orice x ∈ K, si α > 0, α ∈ R atunci, de asemenea, αx ∈ K. (∀)x ∈ K ⇒ αx ∈ K Definitie 5. Fie Ppp puncte x1 , x2 , · · · , xp . O combinatie conica a acestora este definita ca i=1 (αi xi ), unde αi ≥ 0, i = 1, · · · , n. Definitie 6. Acoperirea conica a unei multimi S, este prin definitie: ( ) X conv(S) = (αi xi ) : xi ∈ S, αi ≥ 0 i∈X ,X f init

Observatie: Acoperirea conica a multimii S este cea mai mica multime conica, care contine multimea data S. Definitie 7. Se da un con K. Conul dual al conului K, notat K? , este definit de: K? = {y ∈ Rn : hx, yi ≥ 0, ∀x ∈ K}

5

Figure 4: Acoperire conica in R2

Remarca. Reamintim egalitatea hx, yi = kxkkyk cos ∠(x, y). Daca hx, yi ≥ 0 atunci cos ∠(x, y) ≥ 0 si implicit ∠(x, y) ∈ [0, π2 ]. Pornind de la premisa ca K ? este un con, si ca exista un y ∈ K ? care satisface hy, xi ≥ 0, ∀x ∈ K, atunci ∀α ≥ 0, avem αy ∈ K ? si hαy, xi ≥ 0. Cu alte cuvinte, daca toti vectorii din conul K fac un unghi ascutit cu y ∈ K? atunci vor face un unghi ascutit si cu toti vectorii paraleli cu y. Observatie: Daca K satisface conditia K= K? , atunci conul K se numeste con dual propriu. 1.2.1

Exemple de conuri primale si duale

1. Spatiul Rn este con, iar conul dual Rn? = 0 . 2. Subspatiul Rn + = {x ∈ Rn : x ≥ 0} se numeste con ortant si este con dual propriu. n o T 3. Multimea Ln = [xT t] ∈ Rn+1 : kxk ≤ t este numita con Lorentz sau con de ordin II; de asemenea, este con dual propriu. 4. Multimea S n + = {X ∈ S n : X ≥ 0} este numita con semidefinit, si este dual propriu. Demonstratie.

?

1. Fie y ∈ Rn . Aratam ca y = 0.

6

Presupunem y 6= 0, iar din dualitate avem hx, yi ≥ 0, ∀x ∈ Rn . Deoarece ultima relatie are loc ∀x ∈ Rn atunci este valabila si pentru h−y, yi = −kyk2 ≥ 0. Stiind ca norma ia doar valori pozitive sau nule rezulta y = 0. 2. Fie x ∈ Rn+ , x ≥ 0, atunci pentru un scalar α ≥ 0 avem αx ≥ 0 si, deci αx ∈ Rn+ . De aceea, Rn+ este con. Aratam ca e dual propriu, prin dubla incluziune: ?

(1) Pentru orice x ∈ Rn+ : hx, yi ≥ 0, ∀y ≥ 0, deci x ≥ 0, ?

si am obtinut Rn+ ⊂ Rn+ . ?

(2) Fie y ∈ Rn+ : hy, xi ≥ 0, ∀x ≥ 0 atunci y ∈ Rn+ . ?

Atunci, Rn+ ⊂ Rn+ . Din (1) si (2) rezulta Rn+ este con dual propriu. 3.  In cazul Lorentz ∀y ∈ Ln∗ : hx, yi ≥ 0, ∀x ∈ Ln . Fie y =   conului  x1 y1 ∈ Rn+1 . Inlocuind pe x si y in relatia precedenta ,x = t v de dualitate obtinem: hx, yi = y1T x1 + vt ≥ 0

(6)

n Din x ∈ L kxk ≤ t. Demonstram ca kyk ≤ v alegand x =   avem y1  − x1 ky1 k = . In relatia (6) inlocuim forma lui x si obtinem: t 1   y1 T y1 − +v ≥0 ky1 k 2

1k +v ≥ 0, din care rezulta ca −ky1 k+v ≥ 0 deci, ky1 k ≤ v. Adica, − ky ky1 k

Aratam ca Ln este con dual propriu, prin dubla incluziune : (1)”Ln ⊆ Ln∗ ” :     y1 x1 n Fie y = ∈ L ,x = ∈ Ln , unde kx1 k ≤ t si ky1 k ≤ v. v t Din inegalitatea Cauchy-Schwartz |hx, yi| ≤ kxkkyk, putem scrie : y1T x1 > −ky1 kkx1 k + vt ≥ −vt + vt = 0. 7

(2.)”Ln ⊇ Ln∗ ” :     y1 x1 n∗ Fie y = ∈ L ,x = ∈ Ln , atunci: hx, yi = y1T x1 + v t v T t ≥ 0, kx1 k ≤ t. Din inegalitatea Cauchy-Schwartz |hx, yi| ≤ kxkkyk rezulta y1T x1 + v T t ≥ −ky1 kkx1 k + vt ≥ 0 deci, ky1 k ≤ v. Din (1.) si (2.) rezulta ca Ln este con dual propriu. 4. Prin dubla incluziune : (1) Fie Y ∈ (S+n )? ⇒ hY, Xi ≥ 0, ∀X ∈ S+n . Aratam ca Y ≥ 0 prin urmatoarea serie de transformari: xT Y x = T race(xT Y X) = T race(Y xxT ) = T race(Y X) = hX, Y i ≥ 0, deci Y ∈ S+n . (2)Fie Y ∈ S+n . O proprietate a matricilor pozitiv-semidefinite afirma hY, Xi ≥ 0, ∀X ∈ S+n .

1.3

Operatii care conserva convexitatea multimilor

• Intersectia de multimi convexe este o multime convexa • Suma unor multimi convexe este, de asemenea, o multime convexa • Daca S este o multime convexa si α ∈ R , atunci multimea {αx : x ∈ S} este, de asemenea, multime convexa • Translatia unei multimi convexe genereaza o multime convexa Caz general: Fie multimea convexa S si o functie afina f , atunci multimea f (S) = {f (x) : x ∈ S} este convexa si reprezinta imaginea multimii S prin functia f . In mod similar, preimaginea f −1 (S) = {x : f (x) ∈ S} este, de asemenea, convexa. • Inchiderea si deschiderea unei multimi convexe S sunt de asemenea multimi convexe.

8

Proof. Fie x, y ∈ cl(S) (unde cl(S) reprezinta inchiderea multimii S) si doua siruri xk → x, xk ∈ S si yk → y, yk ∈ S. Atunci multimea S fiind convexa, αxk + (1 − α)yk ∈ S, ∀α ∈ (0, 1). Observam ca αxk +(1−α)yk → αx+(1−α)y, deci αx+(1−α)y ∈ cl(S). Am aratat ca multimea cl(S), este o multime convexa. Mai mult, fie x, y ∈ int(S) (unde int(S) reprezinta deschiderea multimii S), i.e. exista un r > 0 astfel incat B(x, r), B(y, r) ⊆ S. Vom arata ca λx + (1 − λ)y ∈ int(S). Intr-adevar ∀z, w ∈ B(0, r), i.e.kzk ≤ r, kwk ≤ r avem λ(z + x) + (1 − λ)(y + w) = λz + (1 − λ)w + (λx + (1 − λ)y) ∈ S. Deci in termeni generali, va avea loc z + (λx + (1 − λ)y) ∈ S, ∀z ∈ B(0, r). De aici concluzionam ca B(λx + (1 − λ)y, r) ⊂ S.

• Daca S convexa si α scalar atunci αS este, de asemenea multime, convexa • Daca S1 si S2 sunt multimi convexe atunci α1 S1 + α2 S2 este, de asemenea, multime convexa pentru orice α1 , α2 ≥ 0.

1.4

Inegalitati liniare de matrice

Fie matricele A0 , A1 , ..., Am ∈ S n , atunci relatia de forma: X A0 + (xi Ai ) > 0 i

se numeste inegalitate liniara de matrice (LMI). P Multimea {x ∈ Rn : A0 + i (xi Ai ) > 0} este convexa. Demonstratia este lasata ca exercitiu cititorului.

9

2

Functii convexe

2.1

Definitii

Definitie 8. O functie f: Rn → R se numeste convexa, daca domeniul efectiv al functiei f este multime convexa, si are loc urmatoarea inegalitate : f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y) , ∀x, y ∈ dom(f ), α ∈ [0, 1].

(7)

Definitie 9. Domeniul efectiv al unei functii f este definit de multimea: dom(f ) = {x ∈ Rn : f (x) < ∞} .

(8)

Definitie 10. O functie f: Rn → R se numeste strict convexa, daca are loc inegalitatea: f (αx + (1 − α)y) < αf (x) + (1 − α)f (y), ∀x, y ∈ dom(f ), α ∈ (0, 1).

(9)

Corolar. O functie f : Rn → R este convexa, daca si numai daca functia restrictionata la orice linie care intersecteaza domeniul, este de asemenea, convexa. Pe scurt , functia f : Rn → R este convexa ⇔ ∀x ∈ dom(f ) si ∀d ∈ Rn , functia : g(α) = f (x+αd) este convexa pe multimea : {α ∈ R : x + αd ∈ dom(f )}. Observatie. O functie f este concava, daca −f este convexa.

2.2 2.2.1

Conditii de convexitate Conditii de ordinul I

Definitie 11. Fie f ∈ C 1 , cu domeniul efectiv dom(f ) multime convexa. Functia f este convexa daca si numai daca f (y) ≥ f (x) + ∇f (x)T (y − x), ∀x, y ∈ dom(f ). 2.2.2

Conditii de ordinul II

Definitie 12. Fie f ∈ C 2 , cu domeniul dom(f ) multime convexa. Functia f este convexa ∇2 f (x) ≥ 0, ∀x ∈ dom(f ) (Cu alte cuvinte, hessiana functiei in orice punct din domeniul efectiv, este pozitiv semidefinita). 10

2.2.3

Exemple

a) f (x) = − log x, dom(f ) = R+ . Dem. f ”(x) =

1 x2

⇒ f convexa conform conditiilor de ordin II.

b) f (x) = 12 xT Qx + q T x + r, unde Q ≥ 0. Dem. Observam ca ∇2 f (x) = Q ≥ 0 si se constata ca f este convexa, din nou, folosind conditiile de ordin II. c) f (x, t) =

xT x , t

convexa pe multimea Rn × (0, ∞). 

2

Dem. Aratam ca hessiana ∇ f (x, t) =

2 I t n −2 x t2

−2s x t2 2 T x x 3 T T

 este pozitiv semi-

definita. In acest scop alegem un vector v = [z s] ∈ Rn+1 , si se observa egalitatea 2 v T ∇2 f (x, t)v = 3 ktz − svk2 . t Avand in vedere ca t ∈ (0, ∞) rezulta v T ∇2 f (x, t)v ≥ 0, ∀v ∈ Rn+1 . Definitie 13. Fie f: Rn → R o functie convexa, multimea subnivel in punctul c care se defineste ca : {x ∈ dom(f ) : f (x) ≤ c} este multime convexa. n Exercitiul 4. Fie f : S++ → R. Aratati ca f(X)= − log det(X), X pozitiv definita, este functie convexa. n Rezolvare. Fie g(α) = − log det(X + αD), unde X ∈ S++ si D ∈ S n . Din prelucrarea functiei g, avem: 1

1

1

1

g(α) = − log det(X 2 (In + αX − 2 DX − 2 )X 2 ) 1

1

1

1

= − log det(X 2 ) det(In + αX − 2 DX − 2 ) det(X 2 ) 1

1

= − log det(X) det(In + αX − 2 DX − 2 ) 1

1

= − log det(X) − log det(In + αX − 2 DX − 2 ), 11

1

unde X 2 este factorul Cholesky al matricii X. 1 1 Notam Z = X − 2 DX − 2 si valorile proprii ale matricei Z cu λi . Se observa ca valorile proprii ale matricei In + αZ vor fi de forma 1 + αλi . Din egalitatea Y det(In + αZ) = (1 + αλi ) i

rezulta g(α) = − log det(X) − log

Y (1 + αλi ) i

= − log det(X) −

X

log(1 + αλi ).

i

Se observa ca g 00 (α) ≥ 0, de aceea functia g este convexa. In concluzie, pe baza corolarului de mai sus putem afirma ca functie f este convexa.

2.3

Operatii care conserva convexitatea functiilor

1. Fie functiile f1 , f2 convexe si scalarii α1 , α2 ≥ 0 ,atunci functia α1 f1 + α2 f2 este convexa . 2. Fie functia convexa f si g(x) = f (ax + b) compunerea functiei f cu o functie afina. Atunci, g este functie convexa. 3. Orice functie afina f (x) = aT x + b este si convexa si concava , fiind singura clasa de functii cu aceasta proprietate. 4. Fie f : R2n → R astfel incat f (x, y) este convexa in primul argument, adica pentru un y fixat ∈ Rn , f (?, y) este convexa. Atunci, g(x) = supy∈S f (x, y) este convexa.

12

3

Probleme propuse

Problema 1. Se da f : Rn → R. Numim conjugata lui f functia f ? , definita de: f ? (y) = supx∈Rn (y T x − f (x)) = supx∈Rn F (x, y) Aratati ca f ? este o functie convexa. Indicatie. Folosind punctul 4 din subsectiunea 2.3, daca F (x, y) este liniara in x, va fi convexa. Problema 2. Fie f (x) = 12 xT Qx. Aratati ca functia conjugata a lui f , f ? (y) = 21 y T Q−1 y, este convexa.

13