Multimi Si Functii Convexe

MULTIMI ȘI FUNCȚII CONVEXE

CUPRINS

Introducere

I.Mulțimi convexe

1. Mulțimi afine

2. Mulțimi și conuri convexe

3. Algebra mulțimilor convexe

II.Funcții convexe

Concepte de bază

Operații funcționale

III.Aplicații

IV. Bibliografie

Introducere

În studiul poblemelor de extreme din mai multe domenii ale matematicii aplicate convexitatea a avut în ultimii ani o importanță crescândă.

Scopul alegerii acestei teme este de a pune în evidență diferențele și conexiunile dintre mulțimile și funcțiile convexe. Această temă conține conceptele mulțimilor și funcțiilor convexe și caracteristicile acestora.

Ideea fundamentală ce trebuie înțeleasă este ca funcțiile convexe pe pot fi identificate cu anumite submulțimi convexe ale lui (epigraficele lor), în timp ce mulțimile convexe din pot fi identificate cu anumite funcții convexe pe (indicatorii lor). Pe baza acestor identificări se poate trece ușor de la o abordare geometrică la una analitică și invers.

De obicei, când se lucrează cu funcții se gândește geometric cu ajutorul graficelor lor, însă în cadrul funcțiilor convexe este mai utilă imaginea epigraficelor acestora.

Lucrarea începe cu definirea conceptelor de mulțime și funcție convexă și este structurată în trei capitole.

Primul capitol poartă numele de “Mulțimi convexe”. În prima parte a capitolului intervine algebra liniară cu “Mulțimile afine”, iar în restul capitolului sunt prezentate “Mulțimi și conuri convexe” și ”Algebra mulțimilor convexe”.

Al doilea capitol se numește “ Funcții convexe”. Acest capitol începe cu o generalizare a funcției convexe, apoi câteva “Concepte de bază”, iar spre final sunt prezentate “Operații funcționale”.

Ultimul capitol constituie aplicații referitoare la tema aleasă.

Fundamentele teoriei generale a mulțimilor și funcțiilor convexe au fost puse la începutul acestui secol, mai ales de către Minkowski.

MULȚIMI ȘI FUNCȚII CONVEXE

Mulțimile și funcțiile convexe joacă un rol important în analiza matematică și au numeroase aplicații. De altfel există o ramură importantă a analizei matematice, numită analiză convexă.

Cap I. MULȚIMI CONVEXE

Definiție: O mulțime A 2 se numește convexă dacă oricare ar fi punctele (x1,y1),(x2,y2)A segmentul care le unește {(tx1+(1-t)x2, ty1+(1-t)y2)}; t[0,1]} este de asemenea inclus în A.

Mulțimi afine

Pe parcursul întregii lucrări se va nota cu mulțimea numerelor reale, iar n va fi spațiul vectorial uzual al sistemelor de n numere reale x = (1,…,n). Spațiul vectorial în care se lucrează este n, dacă nu se specifică alceva în mod expres. Produsul scalar a doi vectori x și x* din n se exprimă prin:

〈 x,x* 〉 =11*+…+nn* .

Se utilizează același simbol A pentru a desemna atât o matrice cu elemente reale de dimensiuni m n, cât și transformarea liniară de la n m corespunzătoare aplicației x Ax. Matricea transpusă și transformarea adjunctă corespunzătoare, definită de la m lan, se notează A*; deci avem identitatea

〈Ax,y*〉 =〈x,Ay*〉.

Asteriscul * nu are nici un fel de semnificație operațională într-un simbol ce desemnează un vector. Se utilizează * în notația unui vector doar pentru a evidenția dualitatea uzuală dintre vectorii priviți ca puncte și vectorii priviți ca sisteme de coeficienți ai unor funcții liniare.

Definiție 1: Dacă x și y sunt puncte distincte din n, atunci mulțimea punctelor de forma

(1-)x +y = x+ (x-y), ,

se numește dreapta ce trece prin x și y.

Definiție 2: O submulțime M din n se numește mulțime afină dacă (1-)x +y M pentru orice xM, yși .

Exemple de mulțimi afine : – mulțimea vidă

-spațiul n

În general, o mulțime afină trebuie să conțină, odată cu două puncte distincte, întreaga dreaptă ce trece prin acele puncte.

Geometria formală a mulțimilor afine poate fi construită prin subspațiile lui n. Corespondența precisă existentă între mulțimile afine și subspațiile lui n este descrisă în următoarele două teoreme:

TEOREMA 1.1: Subspațiile lui n coincid cu acele mulțimi afine care conțin originea.

Demonstrație:Orice subspațiu este mulțime afină întrucât conține originea și este stabilă la adunare și la împărțirea cu scalari.

Fie M o mulțime afină care îl conține pe 0. Pentru orice x M și avem

x = (1- )0 + x M,

deci M este stabilă și la înmulțirea cu scalari. În plus, dacă x M și y M avem

(x+y)= x + y M ,

deci

x+y=2((x+y) ) M.

Astfel, M este stabilă și la adunare, deci este subspațiu. ■

Definiție 3: Pentru Mn și a n , translatata lui M cu a este mulțimea

M+a = {x+a | xM }.

Definiție 4: O mulțime afină M se numește paralelă cu o mulțime afină L dacă L=M+a pentru un a n. Relația ,, M este paralelă cu L” definește o relație de echivalență pe mulțimea părților afine ale lui n.

Observație: În această definiție nu se încadrează ideea de dreaptă paralelă cu un plan.

TEOREMA 1.2: Fiecare mulțime afină nevidă M este paralelă cu un unic subspațiu L determinat prin

L =M – M= { x-y | x M , y M } .

Demonstrație. Unicitatea: Arătăm mai întâi că M nu poate fi paralelă cu două subspații distincte. Două subspații L1 și L2 paralele cu M ar trebui să fie paralele între ele. Aceasta înseamnă că L2= L1 + a, pentru un anumit a. Cum 0 L2, atunci ar trebui să avem –a L1 , deci a L1 . Dar atunci se obține L1 L1+a = L2. Dacă L2 L1 rezultă că L1= L2 .

Se observă că pentru orice y , M – y = M + (- y) este o translatată a lui M care îl conține pe 0. Conform teoremei anterioare și a ceea ce tocmai s-a demonstrat , această mulțime afină este unicul subspațiu L paralel cu M. Cum L= M – y pentru y M arbitrar rezultă că L= M – M. ■

Definiție 5: Dimensiunea unei mulțimi afine nevide este dimensiunea unuicului subspațiu paralel cu această mulțime.

Prin convenție,dimensiunea lui ∅ este -1. În mod natural, mulțimile afine de dimensiune 0, 1 sau 2 sunt numite puncte, drepte , respectiv plane .

Definiție 6 : O mulțime afină de dimensiune (n-1) din n este numită hiperplan. Hiperplanele sunt foarte importante deoarece joacă în geometria n- dimensională au rol dual celor jucat de puncte.

Hiperplanele și alte mulțimi afine pot fi reprezentate prin funcții și ecuații liniare.

Definiția 5: Fie un subspațiu L dimensional al lui n, complementul ortogonal al lui L , notat , este mulțimea vectorilor x cu xL , adică x y pentru orice y L. este subspațiu și

din L + dim = n.

Complementul ortogonal ( al lui este egal cu L. Daca b1,…,bm este o bază al lui L, atunci condiția x L este echivalentă cu x b1,…,x bm . În particular, subspațiile (n – 1)- dimensional ale lui n sunt complementele ortogonale ale subspațiilor de dimensiune 1. Subspațiile (n – 1)-dimensioneale sunt exact mulțimile de forma unde b ≠0. Hiperplanele sunt translatatele acestor mulțimi.

Însă +a== = , unde =〈a,b〉.Acesta conduce la următoarea caracterizare a hiperplanelor.

TEOREMA 2. Fiind dați și un vector nenul b , mulțimea

H=

câte un hiperplan din n. În plus, orice hiperplan poate fi reprezentat în acest mod cu b și β unic determinați, modulo multiplicarea cu același scalar nenul.

Observație: Din teorema 2 spunem că vectorul b este normal la hiperplanul H. Orice vector normal la H este de forma b cu scalar pozitiv sau negativ.

Următoarea teoremă caracterizează submulțimile afine ale lui n ca mulțimi ale soluțiilor unor sisteme de ecuații liniare în n variabile.

TEOREMA 3. Fiind dați bm și o matrice reală B de dimensiuni m × n , mulțimea

M = {x n| Bx =b }

este o mulțime afină din n. În plus, orice mulțime afină poate fi reprezentată în acest mod.

Demonstrație: Dacă x M, y M și atunci , pentru z = (1- )x + y, avem

Bz= (1- )Bx + By = (1 – )b + b = b,

deci z M. Astfel, mulțimea dată M este mulțime.

Pe de altă parte, pornind de la o mulțime afină nevidă M diferită de n, considerăm subspațiul L paralel cu M. Fie b1,…,bm o bază în . Atunci

L = = {x| x b1, … , xbm} =

= {x| 〈x,bi〉= 0, i= 1,…,m}={x|Bx=0},

unde B este matricea de dimensiuni m× n având liniile b1,…,bm . Cum M este paralelă cu L, există a n astfel încât

M = L + a = {x| B(x – a )= 0}={x| Bx = b},

cu b = Ba. ■

Observație: Din teorema 3 avem

M = {x | 〈x , bi〉= i ,i=1,…,m }= i ,

unde bi este linia i a lui B, i este complementa a i-a a vectorului b iar Hi ={x| 〈x,bi〉=i }.

Fiecare Hi este fie un hiperplan (dacă bi ), fie mulțimea vidă (dacă bi = 0, i 0 ), fie n (dacă bi = 0,i = 0).

Mulțimea afină M poate fi exprimată cu ajutorul coloanelor b1’ ,…,bn’ astfel:

M= {x = (1,…,n)|1 b1’+…+n bn’= b}.

Intersecția unei familii arbitrare de mulțimi afine este o mulțime afină.

Corolar 1: Orice mulțime afină din n este intersecția unei familii finite de hiperplane.

Definiție 6 : Pentru orice S n există și este unică cea mai mică mulțime afină ce conține pe S. Această mulțime se numește acoperirea afină a lui S și se notează “aff S” .

Definiție 7 : Elementele unei mulțimi cu m + 1 puncte b0,b1,….,bm se numesc afin independente dacă aff{ puncte b0,b1,….,bm } este m-dimensional.

Observație: Orice mulțime de m + 1 puncte afine independente poate fi completată la o mulțime de n+1 puncte afine independente. De asemenea, orice mulțime afină m-dimensională se poate scrie ca acoperirea afină a m + 1 puncte afine independente.

Dacă M= aff {b0,b1,…,bm}, vectorii din subspațiul L paralel cu M sunt combinații liniare de b1-b0,…, bm-b0. Vectorii din M se pot exprima sub forma

x = 1(b1-b0)+…+m(bm-b0)+b0,

sau, echivalent,

x=0b0+…+mbm , 0+1+…+m=1.

În fiecare astfel de exprimare a lui x, coeficienții sunt unic determinați dacă și numai dacă b0,…bm sunt afini independenți.

Definiție 8 : Considerând 1 , …,m ca parametrii se definește ceea ce se numește sistem de coordonate baricentrice asociat lui M.

Definiție 9: O aplicație T : x ↦ Tx de la n la m se numește transformare afină dacă

T((1 – )x + y)= (1 – )Tx + Ty

pentru orice x,y din n și

TEOREMA 4: Transformările afine de la n la m sunt aplicații T de forma Tx= Ax +a , unde A este transformare liniară și a m.

Demonstrație : Dacă Teste afină, fie a = T0 și Ax = Tx – a. Atunci A este transformare afină și A0 =0.

Reciproc, dacă T este de forma Tx = Ax + a cu A liniară, avem

T((1 – )x + y)= (1 – )Ax + Ay + a= ( 1 – )Tx + Ty.

Astfel , T este afină. ■

TEOREMA 5: Fie {b0,b1,…,bm} și {b0’,b1’,…,bm’} mulțimi de puncte afin independente din n . Atunci există o transformare afină bijectivă T a lui n pe el însuși astfel încât T bi=bi’ pentru i=0,…,m. Dacă m=n , atunci T este unică.

Demonstrație: Completând cele două mulțimi de puncte afin independente problema se reduce la cazul m=n .Există o transformare liniară A a lui n pe el însuși care duce baza b1-b0, …,bn-b0 a lui n în baza b1’ – b0’ , …,bn’ – b0’. Transformarea afină căutată va fi dată atunci de Tx =Ax +a , unde a=b0’ – Ab0. ■

Corolar 2 : Fie M1, M2 două mulțimi afine din n având aceeași dimensiune. Atunci există o transformare liniară a lui n pe el însuși astfel încât TM1=M2.

Demonstrație: Orice mulțime m- dimensională poate fi exprimată ca acoperirea afină a unei mulțime m + 1 puncte afin independente. În plus, transformările afine păstrează acoperirile afine. ■

Propoziție : Graficul unei trasformări afine T de la n la m este o submulțime afină n+m. Dacă Tx=Ax +a și notăm b= -a , iar B este transformarea liniară de la n+m la m dată prin (x,y)↦ Ax-y, atunci graficul lui T este format din vectorii z=(x,y), xn , y m, cu Bz=b.

Îm particular , graficul unei transformări liniare x ↦ Ax de la n la m este o submulțime afină conținând originea din n+m , deci este un subspațiu L al lui n+m . Complementul ortogonal al lui L este dat prin

={(x*,y*)|x*n,y*m , x*=-A*y*},

adică este graficul transformării – A*. Într-adevăr, z*=(x*,y*) dacă și numai dacă

0=〈z,z* 〉=〈x,x*〉 + 〈y,y*〉

pentru deci este un subspațiu L al lui n+m . Complementul ortogonal al lui L este dat prin

={(x*,y*)|x*n,y*m , x*=-A*y*},

adică este graficul transformării – A*. Într-adevăr, z*=(x*,y*) dacă și numai dacă

0=〈z,z* 〉=〈x,x*〉 + 〈y,y*〉

pentru orice z=(x,y) cu y=Ax. Cu alte cuvinte , (x*,y*) dacă și numai dacă

0=〈x,x* 〉 +〈 Ax,y*〉 = 〈x,x* 〉+〈x,A*y*〉=〈x,x*+ A*y*〉

pentru orice xn. Aceasta înseamnă x*+ A*y* =0, deci x*= – A*y*.

Orice mulțime afină netrivială poate fi scrisă în mai multe moduri ca grafic de transformare afină.Fie M o mulțime afină n-dimensională din N cu 0nN . Mulțimea M o putem exprima ca fiind mulțimea vectorilor x=(1,…,N) ale căror coordonate satisfac un anumit sistem de ecuații liniare

i11+…+ iNn=i, i=1,…k.

Dacă M este n-dimensional atunci matricea coeficienților B=(ij) are nucleul n-dimensional și rangul m=N-n.

Definiție 10 : Fie sistemul = i1 + … + in + i, i=1,…,m . Acest sistem se numește reprezentarea Tucker pentru mulțimea afină .

Reprezentarea Tucker exprimă M ca graficul unei anumite transformări afine de la n la m . Există doar un număr finit de reprezentări Tucker pentru M. Reprezentările Tucker pentru un subspațiu sunt omogene:

= i1 + … + in + i, i=1,…,m .

Dându-se o astfel de reprezentare a lui L ca grafic al unei transformări liniare A, rezultă că corespunde graficului lui –A*. Astfel, x*= (1*,…,N*) aparține lui dacă și numai dacă

– = 1j + … + mj, j =1,…,n.

Acest sistem furnizează o reprezentare Tucker pentru . Astfel, există o corespondență simplă și utilă între reprezentările Tucker ale unui subspațiu dat și cele ale complementului său ortogonal.

2.Mulțimi și conuri convexe

Definiție 1: O mulțime C a lui n se numește convexă dacă ( 1 – )x + y pentru orice x , y și 0 1 .

Definiție 2: Mulțimile convexe sunt mai generale decât cele afine deoarece, odată cu două puncte distincte x și y, ele trebuie să conțină doar o porțiune a dreptei ce trece prin x și y, și anume

{(1 – )x + y| 0≤ 1}.

Această porțiune este numită segmentul de dreaptă (închis) dintre x și y. Elipsoizii solizi și cuburile din 3 sunt mulțimi convexe fără a fi afine.

Definiție 3 : Semispațiile constituie exemple importante de mulțimi convexe. Pentru orice b n nenul și orice , mulțimile

{x|}, {x | },

se numesc semispații închise. Mulțimile

{x|}, {x | },

se numesc semispații deschise. Toate cele patru mulțimi sunt nevide și convexe.

TEOREMA 1: Intersecția unei familii arbitrare de mulțimi convexe este convexă.

Corolar 1: Fie bi n și i pentru i I, unde I este o mulțime de indici arbitrară. Atunci mulțimea

C = {xn|〈 x,bi〉≤ i , i I }

este convexă.

Demonstrație: Fie Ci = {x|〈 x,bi〉≤ i }. Atunci Ci este fie un semispațiu închis, fie n sau ∅ și

Definiție 4 : O mulțime ce poate fi exprimată ca intersecția unei familii finite de semispații închise ale lui n este numită mulțime convexă poliedră. Astfel de mulțimi au un comportament considerabil mai bun decât acela al mulțimilor convexe de tip general, în principal din cauza absenței ,,curburii”.

Definiție 5 : O sumă de vectori

1×1+ … + mxm

este numită combinație convexă de x1, … , xm dacă toți coeficienții i sunt pozitivi și

1 + … + m = 1.

Observație : În numeroase situații unde apar combinații convexe în matematica aplicată, 1 + … + m se pot interpreta ca probabilități sau ca proporții.

Exemplu: Dacă m particule cu masele 1, … , m sunt amplasate ca puncte x1, … , xm din 3, atunci centrul de greutate al sistemului este punctul 1×1+ … + mxm, unde i = i/ (1+ … +m). În această combinație convexă, i este proporția din greutatea totală care este amplasată în xi .

TEOREMA 2: O submulțime a lui n este convexă dacă și numai dacă ea conține toate combinațiile convexe ale elementelor sale.

Demonstraței: Prin definiție o mulțime C este convexă dacă și numai dacă 1×1+ … + mxm C pentru x1C , x2 C , 1 0, 2 0 și 1 + 2 = 1. Cu alte cuvinte, convexitatea lui C înseamnă că mulțimea C este închisă în raport cu luarea de combinații convexe pentru m = 2. Trebuie să arătăm că aceasta implică faptul că mulțimea C este închisă și la luarea de combinații convexe pentru m 2. Luăm m 2 și facem ipoteza de inducție că mulțimea C este închisă la luarea tuturor combinațiilor convexe cu mai puțin de m vectori. Fiind dată o combinație convexă x = 1×1+ … +mxm de elemente ale lui C, cel puțin unul dintre scalarii i este diferit de 1 ( altfel 1+ … +m = m 1). Fie

y = 2’ x2 + … + m’ xm , i’ = i / (1 – 1) .

Atunci i 0 pentru i = 2, … , m și

2’ + … + m’ = ( 2 + … + m) / ( 2 + … + m)=1.

Astfel, y este o combinație convexă de m – 1 elemente ale lui C și y C conform ipotezei de inducție. Cum x = ( 1 – 1 )y + 1×1, rezultă că x C. ■

Definiție 6: Intersecția tuturor mulțimilor convexe conținând o submulțime dată S a lui n se numește acoperirea convexă a lui S și se notează conv S. Ea este mulțimea convexă conform teoremei 1, și anume cea mai mică dinte mulțimile convexe care conține S.

TEOREMA 3: Pentru orice S n, conv S este mulțimea tuturor combinațiilor convexe de elemente ale lui S.

Demonstrație: Elementele lui S aparțin lui conv S, deci toate combinațiile lor convexe aparțin lui conv S, conform teoremei 2. Pe de altă parte, fie două combinații convexe x = 1×1+ … +mxm și y =1y1 + … + ryr, unde xi S și yj S. Vectorul

( 1 – ) x + y = (1 – )1×1 + … + (1 – )mxm +…+ 1y1 + … + ryr ,

unde 0 1, este o combinație convexă de elemente ale lui S. Astfel, mulțimea combinațiilor convexe de elemente ale lui S este ea însăși o mulțime convexă. Ea o conține pe S, trebuie să coincidă cu cea mai mică mulțime convexă, conv S. ■

Corolar 2: Acoperirea convexă a unei submulțimi finite {b0,…,bm} a lui n constă în toți vectorii de forma 0b0+ … +mbm , cu 0 0, … , m 0 și 0+ … +m = 1.

Demonstrație: Orice combinație convexă de elemente alese din {b0,…,bm} poate fi exprimată ca o combinație convexă de b0,…,bm prin includerea vectorilor nefolosiți bi cu coeficienți nuli. ■

Definiție 7: O mulțime care este acoperirea convexă a unui număr finit de puncte se numește politop.

Definiție 8 : Dacă mulțimea {b0,…,bm} este afin independentă, atunci acoperirea sa convexă se numește simplex m – dimensional, iar punctele b0,…,bm se numesc vârfurile simplexului. Fiecare punct al simplexului se poate exprima în mod unic ca o combinație convexă a vârfurilor, prin intermediul coordonatelor baricentrice asociate lui

aff {b0,…,bm }.

Definiție 9: Punctul 0b0+ … +mbm pentru care avem 0= … =m = 1 / (m + 1) este numit centrul de greutate sau baricentrul simplexului. Când m = 0, 1, 2 sau 3, simplexul este un punct, un segment de dreaptă (închis ), un triunghi sau un tetraedru.

Observație : În general, prin dimensiunea unei mulțimi convexe C se înțelege dimensiunea acoperiri afine a lui C. Un disc convex este bidimensional, indiferent de dimensiunea spațiului în care este scufundat. Dimensiunea unei mulțimi afine sau a unui simplex coincide cu dimensiunea ca mulțime convexă.

TEOREMA 4: Dimensiunea unei mulțimi convexe C este maximul dimensiunilor simplexe care sunt incluse în C.

Demonstrație: Apropierea convexă a oricărei submulțimi a lui C este inclusă în C. Astfel, dimensiunea maximă a simplexelor inclusă în C este cel mai mare număr m pentru care C conține o mulțime afină independentă cu m + 1 elemente. Fie {b0,…,bm} o astfel de mulțime cu m maximal și fie M acoperirea sa afină. Atunci, dim M = m și M aff C. În plus C M deoarece, dacă C \ M ar conține un element b, atunci mulțimea celor m + 2 elemente b0,…,bm , b ale lui C ar fi afin independente, ceea ce ar contrazice maximalitatea lui m, adică aff{ b0,…,bm ,b} ar include strict pe M, care astfel ar avea dimensiunea mai mare decât m. Cum affC este cea mai mică mulțime afină care conține C, rezultă affC = M, deci dim C = m. ■

Definiție 10: O submulțime K a lui n este numită con dacă este închisă la înmulțirea cu scalari pozitivi, adică x K dacă x K și 0. O astfel de mulțime este o reuniune de semidrepte ce pornesc din origine.

Definiție 11: Un con convex este un con care e mulțime convexă.

Observație : Nu trebuie neapărat să gândim un con convex ca având un vârf ascuțit. Subspațiile lui n sunt conuri convexe. La fel sunt și semispațiile deschise sau închise care corespund unui hiperplan trecând prin origine.

Propoziție : Două dintre cele mai importante conuri convexe sunt ortantul pozitiv al lui n ,

{x = (1, … , n ) | 1 0, …, n 0},

și ortantul strict pozitiv

{x = (1, … , n ) | 1 0, …, n 0}.

Aceste conuri sunt utile în teoria inecuațiilor. În mod uzual se scrie x x’ dacă x – x’ aparține ortantului pozitiv adică dacă

j j’ , j = 1, … , n.

Cu aceste notații, ortantul pozitiv constă din vectorii x cu x 0.

TEOREMA 5: Intersecția unei familii arbitrare de conuri convexe este un con convex.

Corolar 3: Fie bi n pentru i I, unde I este o familie arbitrară de indici. Atunci

K = {x n | x, bi 〉 0, i }

este un con convex.

Demonstrație: Fie Ki = {x| x, bi 〉 0}. Atunci Ki este fie o submulțime închisă , fie n și

TEOREMA 6: O submulțime a lui n este con convex dacă și numai dacă este închisă la adunare și la înmulțirea cu scalari strict pozitivi.

Demonstație: Fie K un con. Fie x K și y . Dacă mulțimea K este convexă, atunci vectorul z =(1/2)(x + y) aparține lui K, închisă la adunarea și dacă 0 1 atunci (1 – )x și y aparțin lui K, deci (1 – )x + y K. Astfel, K este convexă dacă și numai dacă este închisă la adunare. ■

Corolar 4: O submulțime a lui n este con convex dacă și numai dacă ea conține toate combinațiile liniare strict pozitive (combinațiile liniare de forma 1×1 + … + nxn cu toți coeficienții stict pozitivi ) ale elementelor sale.

Corolar 5: Fie S o submulțime arbitrară a lui n și fie K mulțimea tuturor combinațiilor strict pozitive ale lui S. Atunci K este cel mai mic con convex care conține submulțimea S.

Demonstrație: Mulțimea K este închisă și la adunare și la înmulțirea cu scalari strict pozitivi, S K.

Pe de altă parte, orice con convex conținând S trebuie să includă și pe K. ■

În cazul în care S este o mulțime convexă este posibilă o descriere mai simplă și anume:

Corolar 6: Fie C o mulțime convexă și fie

K = {x | > 0, x }.

Atunci K este cel mai mic con convex care conține mulțimea C.

Demonstrație: Afirmația rezultă din corolarul precedent în felul următor. Orice combinație liniară strict pozitivă de elemente ale lui C este un multiplu scalar strict pozitiv al unei combinații convexe de elemente ale lui C și în concluzie este un element al lui K. ■

Definiție 12: Conul convex care se obține prin adăugarea originii la conul din corolarul 5 sau corolarul 6 este cunoscut sub numele de conul generat de S sau C și este notat coneS.

Observație: Conul convex generat de S nu este același cu cel mai mic con convex care conține pe S, decât dacă acest din urmă con conține originea.

Definiție 13: Dacă S , atunci coneS este mulțimea tuturor combinațiilor liniare pozitive (nu numai strict pozitive) de elemente din S. Este clar că

cone S = conv ( ray S),

unde ray S este reuniunea originii și a diverselor raze (adică semidrepte de forma generate de vectori nemuli y ).

Exemplu: Un disc eliptic poate fi privit ca o secțiune a unui anume con convex K din . Într – adevăr, fie K conul generat de mulțimea perechilor din cu Intersecția lui K cu hiperplanul poate fi indentificată cu mulțimea C. Acest fapt furnizează un mod alternativ de obținere a multor teoreme generale despre mulțimi convexe,din teoremele corespunzătoare privind conurile convexe.

Definiție 14: Se spune că un vector este normal la un con convex C într- un punct , dacă nu face un unghi ascuțit cu nici un segment de dreaptă din C având un capăt din a, adică dacă pentru orice .

Exemplu: Dacă C este semispațiul și a satisface , atunci b este normal la C în a.

Definiție 15: Mulțimea tuturor vectorilor normali la C în a este numită conul normal la C în punctul a.

Exemplu de con convex : conul barieră al unei mulțimi convexe C

Definiție 16: Conul barieră este mulțimea tuturor vectorilor astfel încât, pentru un anumit , avem pentru orice x .

TEOREMA 7: Fie K un con convex care conține 0. Atunci un cel mai mic subspațiu care îl conține pe K, anume

K – K = = aff K,

și există un cel mai mare subspațiu conținul în K, anume ( – K ) K.

Demonstrație: Conform teoremei 6, K este închis atât la adunare cât și la înmulțirea cu scalari pozitivi. Pentru a fi subspațiu, o mulțime trebuie în plus să conțină 0 și să fie închisă la înmulțirea cu – 1. În mod clar, K – K este cea mai mică astfel de mulțime care îl conține pe K, iar ( – K ) K cea mai mică astfel de mulțime care este conținută în K. Prima dintre aceste mulțimi trebuie să coincidă cu aff K, deoarece , conform teoremei 1.1 , acoperirea afină a unei mulțimi conține 0 este un subspațiu. ■

Algebra mulțimilor convexe

Clasa mulțimilor convexe este închisă în raport cu o largă varietate de operații algebrice.

Exemplu: Dacă C este o mulțime convexă în , atunci la fel este fiecare translatată

C + a și fiecare multiplu scalar , unde

Observație: În limbaj geometric, dacă , atunci este imaginea mulțimii C prin

transformarea care îl dilată (contractă) pe cu raportul și lasă originea pe loc.

Definiție 1: Reflexia simetrică a lui C în raport cu originea este – C = ( – 1 )C. O mulțime convexă C se numește simetrică dacă –C = C . O astfel de mulțime trebuie să conțină originea. Aceasta deoarece, odată cu un vector x mulțimea trebuie să conțină, pe lângă –x, și întregul segment de dreaptă cu extremitățile în x și –x.

TEOREMA 1: Dacă C1 și C2 sunt mulțimi convexe din , atunci suma lor C1 + C2, definită prin

C1 + C2 = ,

este de asemenea convexă.

Demonstrație: Fie x și y puncte din C1 + C2. Există vectorii x1, y1 din C1 și x2, y2 din C2, astfel încât

.

pentru 0 avem

,

iar din convexitatea mulțimilor C1 și C2

Rezultă că aparține mulțimii . ■

Observație: este o mulțime convexă arbitrară și este ordonatul pozitiv, atunci suma lor este

Propoziție: Dacă sunt mulțimi convexe, atunci la fel este și combinația liniară

În mod natural, dacă și mulțimea C se numește combinație convexă a mulțimilor În acest caz, o imagine geometrică potrivită a mulțimii C ar fi aceea a unui soi de amestec al mulțimilor

EXEMPLU: Fie și un triunghi și, respectiv, un disc circular din . Când crește de la 0 spre 1,

se transformă într-un triunghi cu colțurile rotunjite. Rotunjirea predomină din ce în ce mai mult până când, în cele din urmă avem un disc circular.

Observație: Pentru o mai bună intuiție geometrică, uneori este util să privim ca fiind reuniunea tuturor translatelor cu x.

Proprietăți algebrice: a)

b)

c)

d)

Mulțimea convexă care constă doar din 0 este elementul identitate pentru operația de adunare. Pentru mulțimi conținând mai mult de un punct nu există invers în raport cu adunarea; tot ce se poate spune în cazul general este că 0 dacă C ≠ ∅.

TEOREMA 2: Dacă C este o mulțime convexă și , atunci

Demonstrație: Incluziunea este adevărată chiar dacă C nu este convexă. Incluziunea inversă rezultă din relația de convexitate

prin înmulțirea cu ori de câte ori Dacă sau este 0, afirmația teoremei este trivială. ■

Propoziție: Fiind date două mulțimi și din , există o unică cea mai mare mulțime convexă inclusă atât în cât și în , și anume, precum și o unică cea mai mică mulțime convexă ce include atât pe cât și pe , și anume conv(. Același lucru este valabil dacă se pornește, în loc de o pereche, cu o familie arbitrară

Definiție 2: Mulțimea tuturor submulțimilor convexe ale lui este o latice completă în raport cu relația de ordine parțială corespunzătoare în mod natural incluziunii.

TEOREMA 3: Fie o familie arbitrară de mulțimi convexe nevide din și fie C acoperirea convexă a reuniunii acestei familii. Atunci

unde reuniunea este luată după toate combinațiile convexe finite (adică după toate alegerile coeficienților pozitivi astfel încât doar un număr finit dinte ei să fie nenuli, iar suma acestora să fie 1).

Demonstrație: Conform teoremei 3 de la “Mulțimi și conuri convexe”, C este mulțimea tuturor combinațiilor convexe unde vectorii aparțin reuniunii mulțimilor . De fapt, C se poate obține luând acele combinații în care coeficienții sunt nenuli, iar vectorii sunt aleși din mulțimi distincte. Într-adevăr , vectorii având coeficienții nuli pot fi omiși din combinație. Dacă doi dintre vectorii cu coeficienți pozitivi și aparțin aceleiași mulțimi , atunci termenul poate fi înlocuit cu , unde și

Astfel, C este reuniunea combinațiilor finite de forma

unde indicii sunt distincți doi câte doi. ■

Definiție 3: Fiind dată o transformare liniară A de la la , avem

pentru ,

pentru D .

(Notația nu trebuie înțeleasă ca implicând existența transformării liniare inverse ca aplicație universală). Mulțimea AC se numește imaginea lui C prin A, iar imaginea inversă a lui D prin A. Convexitatea se dovedește a fi păstrată prin luarea unor astfel de imagini.

TEOREMA 4:Fie A o transformare liniară de la la . Atunci AC este mulțimea convexă în pentru fiecare mulțime convexă C din , iar este o mulțime convexă din pentru fiecare mulțime convexă D din .

Observație: O interpretare a convexității mulțimii este aceea că, atunci când y descrie o mulțime convexă, soluțiile x ale sistemului de ecuații liniare Ax = y vor descrie de asemenea o mulțime convexă. Dacă D= K+a , unde K este ortantul pozitiv al lui , iar , atunci este mulțimea acestor vectori x pentru care Ax ≥ a, adică mulțimea soluțiilor unui anumit sistem de inecuații liniare în . Dacă C este ortantul pozitiv al lui atunci AC este mulțimea vectorilor pentru care există o soluție x ≥0 a ecuației Ax = y.

Corolar 1: Proiecția ortogonală a unei mulțimi convexe C pe un subspațiu L este tot o mulțime convexă.

Demonstrație: Proiecția ortogonală pe L este o transformare liniară care asociază fiecărui punct x unicul punct astfel încât (x-y). ■

TEOREMA 5: Fie C și D mulțimi convexe din și respectiv . Atunci

este o mulțime convexă din .

Definiție 4: Mulțimea C este numită sumă directă a lui C și D. Aceeași denumire este folosită și pentru o sumă în sens uzual C + D , C , D dacă fiecare vector poate fi exprimat în mod unic sub forma Aceasta se întâmplă dacă și numai dacă mulțimile convexe simetrice C – C și D – D au în comun doar vectorul nul din .

TEOREMA 6: Fie și mulțimi convexe din și fie C mulțimea vectorilor

x =(y,z) (unde y și z) pentru care există vectorii și . Atunci C este o mulțime convexă din .

Demonstrație: Fie cu ca în enunț. Fie ( și . Atunci, pentru 0, y’’=(1-)y + și z’’=, avem

z’’=

=

Astfel, vectorul

aparține lui C. ■

Observație: Această teoremă descrie o operație asociativă și comutativă pentru mulțimile convexe din . Există o infinitate de moduri de a introduce un sistem liniar de coordonate în și apoi de a reprezenta fiecare vector ca o pereche de componente și relativ la acele coordonate. Operațiile sunt diferite dacă descompunerile corespunzătoare ale lui , ca sumă directă a două subspații, sunt diferite. O operație de acest tip va fi numită adunare parțială. Adunarea în sens uzual poate fi privită drept cazul extrem corespunzător lui m=0 în timp ce intersecția corespunzătoare lui p=0. Între aceste extreme există o infinitate de adunări parțiale pentru mulțimile convexe din , fiecare fiind o operație binară și comutativă.

Observație: Fiecărei mulțimi convexe C din îi corespunde un con convex K din conținând originea și având o secțiune identificabilă cu C, și anume conul convex generat de mulțimea . Această corespondență este injectivă. Clasa conurilor K ce formează imaginea corespondenței constă în acele conuri convexe care au în comun cu semispațiul doar punctul (0,0).

Observație : Descompunerea lui în perechi () ne îndreaptă atenția spre patru adunări parțiale în . Acestea sunt: operația de adunare doar în argumentul x, operația de adunare doar în argumentul , precum și cele două cazuri extreme de adunare parțială, anume operația de adunare în ambele argumente și x, și intersecția privită ca operație de adunare “în niciunul dintre argumente”.

Definiție 5: Fie mulțimea

=

Această mulțime o vom nota cu . Operația # va fi numită adunare inversă.

TEOREMA 7: Dacă sunt mulțimi convexe din atunci la fel este și suma lor inversă .

Demonstrație: Fie K1 și K2 conuri convexe corespunzătoare mulțimilor convexe C1 și C2. Dacă efectuăm adunare parțială numai în argumentul x asupra lui K1 și K2, atunci (1,x) va aparține conului K pe care îl obținem, dacă și numai dacă x = x1 + x2 pentru anumiți (1,×1) și (1,×2). Astfel , mulțimea convexă corespunzătoare lui K va fi C = C1+ C2. Dacă efectuăm adunarea parțială în amebele argumente , (1,x) va aparține lui K dacă și numai dacă x = x1 + x2 și 1 = pentru anumiți () și

. Astfel C va fi o reuniune, după a mulțimilor , iar aceasta este conv(). Intersectăm pe K1 și K2, corespunde formării lui . Operația care mai rămâne este adunarea lor în . În acest caz, (1,x) K dacă și numai dacă () și pentru anumiți . Obținem mulțimea . ■

Observație: Adunarea inversă este o operație asociativă și comutativă pe mulțimea tuturor submulțimilor convexe ale lui . Ea se aseamănă cu adunarea în sens uzual prin ceea ce poate fi exprimată prin intermediul unei operații asupra pnctelor. Observăm că constă din toți vectorii care pot fi exprimați sub forma:

Va fi necesar ca , și să aparțină unei aceleiași raze Avem pentru anumiți și și

-1e.

x depinde de x1 și x2 și nu de alegerea lui e. Putem să numim x suma inversă a lui x1 și x2 și să îl notăm cu x1 # x2. Adunarea inversă a vectorilor este asociativă și comutativă în domeniul în care este definită, adică numai pentru vectorii aflați pe aceeași rază. Avem

în analogie cu formula pentru .

CONCLUZIE: Mulțimile conv(), și sunt conuri convexe atunci când și K sunt conuri convexe. Înmulțirea cu scalari pozitivi este o operație trivială pentru conuri, întrucât avem pentru orice Din acest motiv, în cazul conurilor, adunarea și adunarea inversă se reduc în esență la operațiile laticiale.

TEOREMA 8. Dacă mulțimile sunt conuri convexe conținând originea, atunci

conv,

.

Demonstrație: Conform teoremei 3: (Fie o familie arbitrară de mulțimi convexe nevide din și fie C acoperirea convexă a reuniunii acestei familii. Atunci

unde reuniunea este luată după toate combinațiile convexe finite (adică după toate alegerile coeficienților pozitivi astfel încât doar un număr finit dinte ei să fie nenuli, iar suma acestora să fie 1), conv este reuniunea după a mulțimilor . Aceasta din urmă este egală cu dacă cu , dacă și , respectiv, cu dacă . Cum și , include atât cât și . Astfel, conv coincide cu . Similar, este reuniune după a mulțimilor . Această din urmă mulțime este egală cu când și este egală cu {0} când sau . Astfel, . ■

O altă construcție interesantă este: Fiind date două puncte diferite , semidreapta ar putea fi gândită ca “umbra lui y produsă de o sursă de lumină aflată în x”. Reuniunea acestor semidrepte pentru y descriind o mulțime C ar fi “umbra lui C”.

Definiție 6: Pentru orice submulțimi disjuncte C și S ale lui , umbra lui C în raport cu S prin

și penumbra lui C în raport cu S prin

Cap II. FUNCȚII CONVEXE

Definiție 1: O funcție se numește convexă dacă oricare ar fi punctele avem

Propoziție 1: Fie . Atunci f este funcție convexă dacă și numai dacă supergraficul lui f,

este mulțime convexă.

Demonstrație: Fie o funcție convexă și fie

Deoarece este convexă, pentru un avem

.

Deci

Reciproc, să presupunem că este mulțime convexă. Fie . Atunci

Prin urmare

. ■

Lemă: : Fie derivabilă pe I , a,x. Atunci

Demonstrație: Putem presupune a ≠ x . Folosind definiția derivabilității, avem

Propoziție 2: Fie derivabilă pe I. Atunci următoarele afirmații sunt echivalente:

f este convexă;

f(a)+(x-a)

Demonstrație:

"

Fie . Atunci

Scăzând din ambii membri ai inegalității și împărțind la t, obținem

≤ .

Deci

≥

Fie . Atunci

De aici și din inegalitățile

obținem

Deci

sau

Prin urmare f este convexă. ■

TEOREMA 1: Fie derivabilă pe I. Atunci f este convexă dacă și numai dacă este crescătoare.

Demonstrație: vom folosi Propoziția 2. Fie Dacă f este convexă atunci

Adunând cele două inegalități, obținem

Deci

Să presupunem acum că este crescătoare. Folosind Teorema lui Lagrange a creșterilor finite ( Fie f:[a,b] continuă pe , derivabilă pe (a,b). Atunci există un punct astfel încât f(a) – f(b) = deduce că există astfel încât

În mod asemănător se arată că și dacă Deci f este convexă. ■

Corolar : Fie de două ori derivabilă pe I. Atunci f este convexă dacă și numai dacă

Demonstrație : Funcția este crescătoare pe dacă și numai dacă

. Atunci este convexă dacă și numai dacă este crescătoare.

Observație : Dacă este convexă și de două ori derivabilă pe I , atunci există două numere reale c și d astfel încât . Într-adevăr , dacă f este convexă, atunci derivata sa de ordin doi este identic nulă. Deci există un număr real c astfel încât Fie

Atunci derivata lui g este identic nulă , ceea ce atrage după sine existența unei constante d cu proprietatea că Prin urmare f(x)=cx+d,

Definiție: Fie . Un punct se numește punct de inflexiune dacă f este derivabilă în sau

și dacă există astfel încât f să fie convexă pe intervalul și pe intervalul .

Propoziție 3: Fie

f de n + 1 ori derivabilă pe I, n par. Fie astfel încât

și este continuă în . Atunci este punct de inflexiune.

Demonstrație:

Cazul

Presupunem că Deoarece este continuă în , rezultă că ( astfel încât să fie strict pozitivă pe (. Deci este strict crescătoare pe (. Deoarece este strict negativă pe ( și strict pozitivă pe (.

Cazul n-par, n

(x0)> 0 .Din raționamentul de mai sus, deducem că ()> 0 astfel încât să fie strict negativă pe ( x0-,x0 ) și strict pozitivă pe (x0,x0+). Deci > 0 pe

(x0 –, x0 +)\{x0}. Prin urmare, este strict negativă pe (x0 , x0) și strict pozitivă pe (x0, x0+). Repetând procedeul de ori, obținem că f” este strict negativă pe (x0 – , x0) și strict pozitivă pe (x0, x0+). ■

Concepte de bază

Definiție 1 : Fie f o funcție ale cărei valori sunt reale sau și al cărei domeniu de definiție este o submulțime S a lui n.Mulțimea

{(x,| x S, , f(x)}

se numește epigraficul lui f și se notează epi f. Prin definiție, f este o funcție convexă pe S dacă epi f este o submulțime convexă a lui n+1 . O funcție concavă pe S este o funcție a cărei opusă este convexă.O funcție afină pe S este o funcție care este definită,convexă și concavă.

Definiție 2 : Domeniul efectiv al unei funcții convexe f , pe care îl notăm dom f, este proiecția pe n a epigrafului lui f:

dom f ==.

Aceasta este o mulțime convexă din n, fiind imaginea mulțimii convexe epi f . Dimensiunea ei este numită dimensiunea funcției f.

Pentru clasa funcțiilor convexe care au ca domeniu efectiv comun o anumită mulțime C fixată , avem două abordări tehnice bune:

Funcții care nu iau nicăieri valoarea +, astfel că mulțimea S ar coincide cu domf.

Considerăm funcții date pe întregul , întrucât o funcție convexă f pe S se poate extinde întotdeauna la o funcție convexă pe întregul , definind pentru

A doua abordare are avantajul că unele dificultăți tehnice legate de domenii efective pot fi surprinse aproape în întregime.

Exemplu: Când o funcție convexă f este construită pe baza anumitor formule , aceleași formule precizează implicit domeniul efectiv al lui f, deoarece ele specifică unde este (sau nu este) egală . În cealaltă abordare ar trebui întotdeauna să se descrie în mod explicit domeniul efectiv al lui f , mai înainte ca valorile lui f pe acel domeniu să poată fi date.

În schimb, abordarea considerată aici conduce la calcule aritmetice în care apar și . Regulile adoptate sunt:

pentru

pentru

pentru

pentru

inf ∅sup ∅

Combinațiile și sunt nedefinite și sunt evitate. Cu aceste reguli, legile familiare ale aritmeticii

rămân valabile cu condiția că nici una dintre sumele care apar să nu fie cea interzisă (sau ).

Evitarea lui cere în mod natural o oarecare prudență, la fel ca și evitarea împărțirii la 0. În practică, prin ipoteză, unul sau altul dintre infiniți se exclude în mod automat din calcule, astfel că nu apare nici o complicație.

Definiție 3: O funcție convexă f se spune că este proprie dacă epigraful său este nevid și nu conține drepte verticale, pentru cel puțin un x și pentru orice x . Astfel, f este proprie dacă și numai dacă mulțimea C = domf este nevidă și restricția lui f la C este finită.

Observație: O funcție convexă proprie f pe se obține luând o funcție convexă finită f pe o mulțime convexă nevidă C , iar apoi extinzând-o la întregul cu pentru .

Definiție 4: O funcție convexă care nu este proprie se numește improprie.

Funcțiile convexe proprii constituie adevăratul obiect de studiu, însă funcțiile impropri apar în multe situații naturale și este mai convenabil să le admitem decât să le excludem printr-o muncă laborioasă.

Exemplu: Funcția convexă improprie, care nu este pur și simplu identică cu sau , este funcția f definită pe prin

Funcțiile convexe au o proprietate importantă de interpolare. Prin definiție, f este convexă pe S dacă și numai dacă

Aparține lui epif de îndată ce și aparțin lui epif , iar . Cu alte cuvinte sunt îndeplinite relațiile și

ori de câte ori și 0

TEOREMA 1. Fie o funcție de la C la (-],unde C este o mulțime convexă . Atunci f este convexă pe C dacă și numai dacă

f f +f , 01,

pentru orice x și y din C.

TEOREMA 2. Fie f o funcție de la la .Atunci f este convexă dacă și numai dacă

f +, 01,

ori de câte ori

TEOREMA 3.(Inegalitatea lui Jensen). Fie f o funcție pe cu valori între . Atunci f este convexă dacă și numai dacă

pentru

TEOREMA4. Fie f o funcție cu valori reale, de două ori continuu diferentiabilă pe intervalul deschis . Atunci f este convexă dacă și numai dacă derivata sa de ordin doi este pozitivă pe întregul interval .

Demonstrație: Să presupunem mai întâi ca este pozitivă pe . Pentru și avem

Cum si , avem

Multiplicând aceste două inegalități cu și respectiv cu , apoi adunându-le, obținem

Membrul stâng este tocmai , deci aceasta demonstrează convexitatea lui f pe .

Pentru afirmația reciprocă din teoremă, să presupunem că n-ar fi pozitivă pe . Atunci din motive de continuitate, ar fi negativă pe un anumit subinterval . Pe baza argumentului evident, analog celui de mai sus, pe am avea

deci

Astfel , f nu ar fi convexă pe . ■

Convexitatea funcțiilor definite pe reprezintă o consecință a teoremei anterioare:

, unde

dacă dacă unde

dacă dacă unde

dacă dacă unde

dacă , unde

dacă dacă

În cazul multidimensional , pe baza teoremei 1 ( Fie o funcție de la C la (-],unde C este o mulțime convexă . Atunci f este convexă pe C dacă și numai dacă

f f +f , 01,

pentru orice x și y din C.) este trivial faptul că fiecare funcție de forma

este convexă, chiar afină, pe .

O funcție pătratică

unde este matricea pătratică , este convexă pe dacă și numai dacă este pozitiv semidefinită, adică

pentru orice

TEOREMA5. Fie f o funcție cu valori reale, de două ori continuu diferențiabilă pe o mulțime convexă deschisă C din . Atunci f este convexă pe C dacă și numai dacă matricea sa hessiană

este pozitiv semidefinită pentru orice

Demonstrație: Convexitatea lui f pe C este echivalentă cu convexitatea restricției lui f la fiecare segment de dreaptă din C. Aceasta înseamnă convexitatea funcției pe intervalul real deschis pentru fiecare și . Un calcul direct arată că

Astfel, conform teoremei anterioare, g este convexă pentru fiecare și dacă și numai dacă pentru fiecare și ■

Pe baza teoremei 5 putem verifica convexitatea unei funcții pe care este opusa mediei geometrice:

daca

Un calcul direct arată că

pentru . Această cantitate este pozitivă deoarece și

(întrucât ) pentru orice numere reale

Una dintre cele mai importante funcții convexe pe este norma euclidiană

Când n = 1 aceasta este funcția valoare absolută. Convexitatea normei euclidiene rezultă din relațiile familiare

pentru .

Între mulțimi convexe și funcții convexe există și mai multe corespondențe utile. Cea mai simplă dintre acestea se asociază fiecărei multimi C din funcția indicator a lui C, unde

Epigraful funcției indicator este un „ semicilindru cu secțiunea transversală C ’’. Mulțimea C este convexă dacă și numai dacă este o funcție convexă pe

În analiza covexă un rol fundamental îl au funcțiile indicator, similar cu funcțiile caracteristice din celelalte ramuri ale analizei :

Funcția de suport a unei mulțimi convexe C din este definită prin

Funcția de etalonare este definită prin

.

Funcția distanță (euclidiană) este definită prin

Funcțiile convexe conduc, printr-un procedeu important, la mulțimi convexe.

TEOREMA 6. Pentru orice funcție convexă f și pentru orice , mulțimile de nivel si sunt convexe.

Demonstrație: Convexitatea mulțimii rezultă din faptul că aceasta este intersecția, după , a mulțimilor . Un mod mai geometric de a vedea această convexitate este de a observa că mulțimea este proiecția pe a intersecției lui epif cu hiperplanul orizontal din , astfel că poate fi privită ca o secțiune orizontală a lui epif. ■

Corolar 1: Fie o funcție convexă pe și un număr real pentru fiecare i, unde I este o mulțime de indici arbitrară. Atunci

este o mulțime convexă.

Demonstrație: : Fie Ci = {x|〈 x,bi〉≤ i }. Atunci Ci este fie un semispațiu închis, fie n sau ∅ și

Din teorema anterioară, în cazul în care f este o funcție convexă pătratică, putem deduce că mulțimea punctelor satisfăcând o inegaliatate pătratică

este convexă dacă Q este pozitiv semidefinită. Printre mulțimile de această formă se află toți elipsoizii și paraboloizii „silizi’’ și , în particular, bilele de forma .

Teorema 6 împreună cu corolarul 1 au o semnificație clară pentru teoria sistemelor de inegalități liniare. Dar convexitatea intră și în analiza altor aspecte ale teoriei inegalităților, deoarece diverse inegalități clasice pot fi privite drept cazuri particulare ale teoremei 3 (Fie o functie pe cu valori între . Atunci este convexă dacă și numai dacă pentru ).

Exemplu: Fie f pe egală cu opusul logaritmului. Pentru o combinație convexă a numerelor pozitive avem

,

conform teoremei 3. Înmulțind cu -1 și luând exponențiala ambilor membri deducem

În particular, pentru

(

Aceasta este celebra inegalitate dintre media aritmetică și media geometrică pentru o familie de numere pozitive.

Uneori, printr-o schimbare de variabile neliniară, se poate transforma o funcție neconvexă într-una convexă.

Un exemplu remarcabil îl constituie clasa funcțiilor algebrice (pozitive) pe ortantul strict pozitiv al lui n care sunt sume cu termeni de forma

,

unde , iar exponenții sunt numere reale arbitrare. O funcție particulară din această clasă este

Substituția transformă termenul general g în

unde . În secțiunea următoare se va vedea că h, și orice sumă de funcții de forma lui h, este convexă. Mai este de notat că aceeași schimbare de variabile transformă mulțimea într-un hiperplan

.

Despre o funcție f pe se spune că este pozitiv omogenă (de grad 1) dacă pentru orice x avem

Pozitiv omogenitatea unei funcții este echivalentă cu faptul că epigraful funcției este un con în .

Un exemplu de funcție convexă, pozitiv omogenă, care nu este pur și simplu liniară, este .

TEOREMA 7. O funcție pozitiv omogenă f de la este convexă dacă și numai dacă

pentru orice

Demonstrație: Acest lucru e implicat de teorema 6 de la ,, mulțimi și conuri convexe’’ (O submulțime a lui n este con convex dacă și numai dacă este închisă la adunare și la înmulțirea cu scalari strict pozitivi.), deoarece condiția de subativitate a lui f este echivalentă cu aceea ca epif să fie închis în raport cu adunarea. ■

Corolar 2. Dacă f este o funcție convexă, proprie și pozitivă omogenă atunci

pentru

Corolar3. Dacă f este o funcție convexă, proprie și pozitiv omogenă atunci pentru orice x.

Demonstrație: . ■

TEOREMA 8. O funcție f convexă, proprie și pozitiv omogenă este liniară pe un subspațiu L dacă și numai dacă . Pentru aceasta este suficient ca pentru fiecare vector dintr-o bază a lui L.

Demonstrație: Presupunem îndeplinită ultima condiție din teoremă. Atunci pentru orice , nu doar pentru . Pentru orice avem

deci

.

Astfel, f este liniară pe L și în particular pentru . ■

Anumite funcții convexe și pozitiv omogene sunt caracterizate ca funcții de suport și ca funcții de etalonare ale mulțimilor convexe.

2.Operații funcționale

Cum se pot obține noi funcții convexe pornind de la funcții despre care se sție deja că sunt convexe? Există multe operații ce păstrează convexitatea. Unele dintre operații, precum adunarea punctuală a funcțiilor, sunt familiare din analiza matematică elementară. Altele, ca și luarea anvelopei convexe a unei familii de funcții, sunt motivate geometric. Adesea funcția construită este exprimată ca un infimum condiționat, sugerând implicit aplicații în teoria problemelor de extremum.

Familiarizarea cu operațiile de mai jos este utilă îndeosebi atunci când avem de demonstrat convexitatea unei funcții date printr-o formulă complicată.

TEOREMA 1. Fie f o funcție convexă de la și fie o funcție convexă de la , monoton crescătoare. Atunci funcția este convexă pe ( unde se consideră ).

Demonstrație: Pentru x și y din și avem

Aplicând funcția ambilor membri ai acestei inegalități, obținem

.

Obținem că h este convexă. ■

Din teorema anterioară rezultă că dacă f este o funcție convexă proprie pe , este o funcție convexă proprie. La fel, este convexă pentru dacă f este convexă și pozitivă. Acest lucru se obține luând

În particular, este convexă pe pentru fiind norma euclidiană). Dacă g este o funcție concavă, atunci este convexă pe . Pentru a vedea aceasta, se aplică funcției convexe funcția definită prin

Luând egală cu o funcție alină pe cu panta pozitivă , obținem faptul important că este o funcție convexă proprie atunci când f este o funcție convexă proprie, iar și sunt numere reale, .

TEOREMA 2. Dacă sunt funcții convexe proprii pe atunci este convexă.

Remarcăm că dacă și numai dacă și . Astfel, domeniul efectiv al lui ar fi improprie. Ipoteza din teorema 2 că funcțiile și să fie proprii este făcută pentru evitarea situației atunci când se formeaza .

O combinație liniară de funcții convexe proprii cu corficienți pozitivi este funcție convexă.

Dacă f este o funcție convexă finită și C este o mulțime convexă nevidă, atunci

unde este funcția indicator a lui C. Adunarea lui f cu o funcție indicator conduce la restrangerea domeniului efectiv al lui f .

Un procedeu obișnuit de construire a funcțiilor convexe pe constă în construirea unei mulțimi convexe F în și apoi considerarea funcției al cărei grafic este ,, frontiera inferioară’’ a lui F în sensul teoremei următoare.

TEOREMA 3. Fie F o mulțime convexă în și fie

.

Atunci f este funcție convexă pe .

Demonstrație: Pe baza teoremei 2 de la concepte de bază (Fie f o funcție de la la .Atunci f este convexă dacă și numai dacăf +, 01,ori de câte ori ) de remarcat este utilitatea convenției ca infimumul unei mulțimi vide de numere reale să fie . ■

Ca o primă aplicație a procedeului din teoremă, introducem operația funcțională care corespunde adunării epigraficelor ca mulțimi în .

TEOREMA 4. Fie funcții convexe proprii pe și fie

.

Atunci f este o funcție convexă pe .

Demonstrație: Fie și . Atunci F este o mulțime convexă în . Prin definiție, dacă și numai dacă există , astfel încât și . Astfel funcția f definită în teoremă este exact funcția convexă ce se obține din F prin construcția din teorema 3. ■

Definiție 1: Funcția f o vom nota . Operația □ este numită convoluție infimală. Această terminologie provine din faptul că, atunci când sunt implicate numai doua funcții, □ se poate exprima astfel

iar această formulă este analoagă cu formula clasică a convoluției integrale. Convoluția infimală este duală operației de adunare a funcțiilor convexe.

Dacă pentru un anumit ( unde dacă și , atunci . Astfel , este funcția al cărei grafic se obține translatând graficul lui f cu a în direcția orizontală. Pentru o funcție g arbitrară și pentru convoluția infimală f□g exprimată, în funcție de translația infimumul pe al funcției obținute din adunarea lui g cu translatata . Domeniul efectiv al lui f □ g este suma dintre dom f și dom g.

Luând f egală cu norma euclidiană, iar g funcția indicator a unei mulțimi convexe C, obținem

Aceasta stabilește convexitatea funcției distanță .

Proprietatea funcțiilor convexe de a fi proprii nu se menține întotdeauna prin convoluția infimală, deoarece infimumul din formula din teorema anterioara poate fi . De asemenea, convoluția infimală de funcții improprii nu se definesțe prin formula amintită, pentru a evita . Totuși, se poate definii pentru orice funcții și de la la , direct, prin intermediul epigraficelor:

.

Ca operație pe familia funcțiilor de la la , convoluția infimală este comutativă, asociativă și pastrează convexitatea. Funcția acționează ca element identitate pentru această operație.

S-a subliniat deja că operația de înmulțire la stânga cu scalari pozitivi păstrează convexitatea, unde

.

Există, de asemenea, o operație utilă de înmulțire la dreapta cu scalari, care corespunde înmulțirii cu scalari a epigraficelor. Pentru orice funcție convexă f pe și orice este, prin definiție, funcția convexă obținută din teorema anterioară cu . Astfel,

în timp ce pentru avem

.

În mod trivial dacă . O funcție f este pozitiv omogenă dacă și numai dacă pentru orice .

Fie h o funcție convexă oarecare pe și fie F conul convex din generat de epih. Funcția convexă ce se obține aplicând teorema anterioară pentru F are ca epigraf un con convex din care conține originea. Ea este cea mai mare dintre funcțiile convexe pozitiv omogene f astfel încât și . Această funcție f se numește funcția convexă pozitiv omogenă generată de h. Întrucât F constă din origine și din reuniunea mulțimilor pentru , avem

când . Desigur, se poate omite din infimum dacă sau .

Pentru orice funcție convexă proprie f pe , funcția g definită pe prin

este o funcție convexă, proprie și pozitiv omogenă, anume funcția convexă pozitiv omogenă generată de

Atunci, în particular, este o funcție convexă proprie de pentru orice .

Funcția de etalonare a unei mulțimi convexe C din este funcția convexă pozitiv omogenă generată de . Într-adevăr , pentru avem , astfel că

.

TEOREMA 5. Supremumul punctual al unei familii arbitrare de funcții convexe este funcția convexă.

Demonstrație: Aceasta rezultă din faptul că intersecția unei familii de mulțimi convexe este convexă. Într-adevăr, dacă

Epigraficul lui f este intersecția epigraficelor funcțiilor . ■

Convexitatea funcției de suport a unei mulțimi C din rezultă din teorema anterioară, deoarece aceasta funcție este prin definiție supremumul punctual al unei familii de funcții liniare, anume funcțiile când y descrie mulțimea C.

Ca o altă ilustrare, să consideram funcția f care asociază fiecărui punct pe cel mai mare dintre componentele ale lui . Această funcție f este convexă conform teoremei 5 , deoarece este supremumul punctual al funcțiilor liniare , unde este vectorul ce constituie linia j a matricii identitate . Să observam că f este de asemenea pozitiv omogenă; de fapt, f este funcția de suport a simplexului

.

Convexitatea funcției

,

care este numită norma Cebîșev pe . Aceasta din urmă funcție este funcția de suport a mulțimii convexe

și în același timp este funcția de etalonare a cubului n-dimensional

.

Orice funcție de suport pozitivă este funcția de etalonare a unei mulțimi convexe închise conținând originea.

Acoperirea convexă a unei funcții neconvexe g este funcția f =conv g obținută din teorema 3, cu

F=conv(epig).

Aceasta este cea mai mare funcție convexă majorata de g. Conform teoremei 3 de la mulțimi și conuri convexe (Pentru orice S n, conv S este mulțimea tuturor combinațiilor convexe de elemente ale lui S.), un punct aparține lui F dacă și numai dacă poate fi exprimat ca o combinație convexă

unde . Astfel,

unde infimumul este luat după toate exprimările lui x ca o combinație convexă de puncte ale lui (cu condiția ca g să nu ia valoarea , astfel că sumarea nu este ambiguă).

Acoperirea convexă a unei familii arbitrare de funcții pe se notează cu

conv.

Aceasta este acoperirea convexă a infimumului punctual al familiei, adică funcția f obținută prin intermediul teoremei 3 din acoperirea convexă F a reuniunii epigraficelor funcțiilor . Ea este cea mai mare funcție convexă f (nu neapărat proprie) pe astfel încât pentru orice și orice

TEOREMA 6. Fie o familie de funcții convexe proprii pe unde I este o familie de indici arbitrară, și fie f acoperirea convexă a acestei familii. Atunci

unde infimumul se ia după toate reprezentările lui x ca o combinație convexă de elemente astfel încât doar un număr finit dintre coeficienții sunt nenuli. (Formula este de asemenea valabilă dacă fiecare aparține lui dom.)

Demonstrație: Prin definiție, f(x) este infimumul valorilor lui astfel încât

, unde F este acoperirea convexă a reuniunii mulțimilor convexe nevide . Conform teoremei 3 de la “algebra mulțimilor convexe” (Fie o familie arbitrară de mulțimi convexe nevide din și fie C acoperirea convexă a reuniunii acestei familii. Atunci unde reuniunea este luată după toate combinațiile convexe finite.), dacă și numai dacă se poate exprima ca o combinație convexă finită de forma

unde (doar un număr finit de coeficienți fiind nenuli). Astfel, este infimumul lui după toate exprimările lui x ca o combinație canvexă finită cu pentru orice i, care este același cu infimumul din enunțul teoremei. ■

Un caz util al teoremei 6 este acela în care toate funcțiile sunt de forma

și fiind elemente ale lui și , respectiv. Atunci f este cea mai mare funcție continuă convexă satisfăcând

și avem

unde infimumul se ia după toate reprezentările lui x ca o combinație convexă de elemente (având doar un număr finit de coeficienți nenuli).

O variantă mai puternică a teoremei 6 este o consecință a teoremei Carathéodory ( Fie S o mulțime oarecare de puncte și direcții din și fie . Atunci dacă și numai dacă x se poate exprima ca o combinație convexă de n+1 de puncte și direcții din S (nu neapărat distincte). În fapt, ce este reuniunea tuturor simplexelor d-dimensional generalizate ale căror vârfuri aparțin lui S, unde d=dimC.)

Formula din teorema 6 se poate exprima și prin intermediul convoluției infirmale.Pentru simplificarea notațiilor să presupunem I=.Atunci f se obține din teorema 3 din mulțimea

Unde reuniunea se ia după toate combinațiile convexe ale mulțimilor . Dar este funcția obținută via teorema 3 din mulțimea convexă in . Considerarea unei reuniuni de epigrafice în înseamna luarea infimumului punctual al funcțiilor corespunzătoare. Așadar , dacă sunt funcții convexe proprii, atunci funcția poate fi dată de asemenea prin

.

Familia funcțiilor convexe pe , privită ca o mulțime parțial ordonată relativ la ordinea punctuală ( dacă și numai dacă pentru orice x), este o latice completă. Infimimul unei familii de funcții convexe este ( relativ la această mulțime parțial ordonată particulară!) conv , în timp ce supremumul este sup .

În teorema următoare sunt considerate construcții în care intervin transformări liniare .

TEOREMA 7. Fie A o transformare liniară de la la . Atunci, pentru fiecare funcție convexă g pe , funcția gA definită prin

este convexă pe . Pentru fiecare funcție convexă h pe , funcția Ah definită prin

Este convexă pe .

Demonstrație: Verificarea este elementară, utilizând criteriul din teorema 2 de la “Concepte de bază” (Fie f o funcție de la la .Atunci f este convexă dacă și numai dacă f +, 01,ori de câte ori ). Convexitatea lui f=Ah rezultă și din aplicarea teoremei 3 pentru imaginea lui F a epigrafului lui h prin transformarea liniară . ■

Definiția 2: Funcția Ah este numită imaginea lui h prin A, în timp ce gA este numită imaginea inversă a lui g prin A.

Această terminologie este sugerată de situația în care g și h sunt funcții indicator ale unor mulțimi convexe.

Un exemplu important al operației menționând cazul în care A este proiecție. Considerând

Avem

Această funcție este convexă în y= atunci când h este convexă.

Dacă A este nesingulară avem

Adunarea parțială a epigraficelor poate fi utilizată pentru a defini o infinitate de operații liniare, asociative și comutative, pe mulțimea tuturor funcțiilor convexe pe

Exemplu: convoluția infimală parțială

unde

În cazul mulțimilor convexe există o mulțime “naturală” de patru operații ,iar acestea se reduc la două operații atunci când mulțimile sunt conuri convexe conținând originea. Aceste operații se obțin din adunările parțiale ale unor conuri convexe de forma

corespunzând mulțimilor convexe C din. În mod similar suntem conduși la opt operații binare, asociative și comutative pe familia tuturor funcțiilor convexe pe , mulțimile C fiind înlocuite prin epigrafice. Mai exact, fiecărei funcții convexe f îi asociăm conul convex K ce constituie epigraficul funcției convexe pozitiv omogene pe generate de h,

Dacă f nu este identic +,

Dacă Există opt adunări parțiale care rezultă din adunarea mulțimilor din în raport cu diversele combinații ale celor trei argumente În fiecare dintre aceste cazuri , luăm suma parțială K a corpurilor K1 și K2 care corespund la două funcții convexe f1 și f2 pe Apoi aplicăm teorema 3 pentru

pentru a obține f. Operația rezultată este în mod evident comutativă și asociativă. Se arată că patru dintre operațiile definite în această manieră se află printre cele definite anterior. Anume, adunarea în raport numai cu conduce la . Adunarea în raport numai cu x și conduce la . Adunarea în raport numai cu conduce la conv . Adunarea în nici unul dintre argumente conduce la maximul punctual al lui . Cele patru operații rămase sunt descrise în teorema care urmează.

Notația max reprezintă cel mai mare dintre cele m numere reale

TEOREMA 8. Fie f1,…,fm funcții convexe proprii pe Atunci următoarele funcții sunt, de asemenea convexe:

unde ultimul infimum este luat după toate reprezentările lui x ca o combinație convexă

Demonstrație: În sensul discuției precedente, adunara în raport doar cu x de funcție f . Adunarea în raport cu dă funcția g. Adunarea în raport doar cu dă funcția h. Adunarea ăn raport cu și x dă funcția h. ■

Prima operație din teorema anterioară se poate exprima sub forma de “convouțe ” când m=2:

Se observă că, folosind această operație,

pentru orice Cea de-a treia operație revine la adunarea inversă a epigraficelor.

CAP III. APLICAȚII

Aplicația 1

Să se demonstreze că dacă mulțimea A este convexă dacă și numai dacă este o funcție convexă.

Rezolvare: Necesitatea. Pe baza relației , trebuie să arătăm că oricare ai fi și oricare ar fi are loc :

Dacă

și Datorită faptului că și , relația are loc.

Dacă cel puțin unul dintre punctele u și v nu aparține lui A, atunci iar relația are loc și în acest caz, ceea ce ne asigură că este o funcție convexă.

Suficiența: Fie Din faptul că este funcție convexă rezultă că ceea ce implică faptul că , echivalent cu . Așadar mulțimea A este o mulțime convexă.

Aplicația 2.

Demonstrați că funcția este convexă dacă și numai dacă epif este o mulțime convexă.

Rezolvare: Necesitatea. Fie (u,a) și (v,b) două puncte arbitrare din epif și arbitrar din (0,1). Se obține atunci ceea ce implică faptul că epif. Așadar epif este mulțime convexă.

Suficiența. Considerăm u și v arbitrare din V și Vom arăta că are loc relația Dacă cel puțin unul din punctele u și v nu aparțin dom f, relația este adevărată.

Fie acum . Există echivalent cu )

Dacă f(u) și f(v) sunt finite putem considera a=f(u) și b=f(v) ceea ce ne asigură că relația are loc.

Dacă cel puțin una din valorile f(u) și f(v) este , în relația anterioară putem să facem pe a sau pe b să tindă la și rezultă atunci . Acest lucru face ca relația să fie adevărată.

Aplicația 3.

Dacă

Rezolvare:

Având simetrie în cele trei variabile, putem presupune

Avem două cazuri:

În prin caz avem ordonările:

Și avem condițiile convexe:

De unde obținem:

de unde

Din convexitatea lui f avem :

care prin adunare conduc la

de unde prin înmulțirea cu se obține

Și avem condițiile convexe:

De unde obținem:

de unde

Din convexitatea lui f avem :

care prin adunare conduc la

de unde prin înmulțirea cu se obține

Aplicația 4.

Pentru orice , o funcție f este convexă dacă și numai dacă satisface una din următoarele proprietăți echivalente:

Rezolvare:

Aplicația 5.

Dacă este convexă proprie, atunci există:

Rezolvare:

Notăm

Deoarece f este convexă ea este și subaditivă.

Din definiția marginii inferioare

Aplicația 6.

Dacă este convexă, atunci:

Rezolvare:

Aplicația 7.

este convexă , atunci pentru orice

Rezolvare:

Fie

Aplicația 8.

Dacă

Reciproc, dacă

adică funcția este convexă.

Aplicația 9.

Fie o funcție integrabilă și convexă astfel încât

Să se arate că

Rezolvare:

Șirul

Este convergent la

Pe de altă parte din integrala lui Jensen, avem:

și deci

Presupunem că ar exista pentru care pentru care

Avem

și f convexă de unde

Contradicție cu

Aplicația 10.

Fie este monoton descrescătoare.

Rezolvare:

Presupunem f convexă și fie x,h pozitivi fixați și deoarece

Adică

Aplicația 11.

Fie

Rezolvare:

iar

este strict deasupra segmentului

Aplicația 12.

Fie o funcție convexă și negativă. Atunci pentru orice avem inegalitatea:

Rezolvare:

Funcția fiind convexă, avem inegalitatea:

Deoarece

Avem:

Aplicația 13.

Fie . Construiți o funcție convexă este convexă.

Rezolvare:

Pentru I= considerăm funcția pentru care

convexă. Dacă f nu este convexă, alegem spre exemplu care este convexă. Avem:

Deci nu are același semn, deci nu poate fi convexă.

Aplicația 14

Funcția f este convexă pe I dacă și numai dacă oricare ar fi punctele M1,M2 de pe graficul lui f corespunzător lui I segmentul (M1, M2) este deasupra arcului de grafic de extremități M1 și M2.

Rezolvare:

Aplicația 15

Dacă este o funcție derivabilă și convexă (respectiv strict convexă), atunci este crescătoare (respectiv strict crescătoare).

Rezolvare:

Aplicația 16

Dacă oricare ar fi a,b,c din I , cu , atunci f este convexă pe I.

Fie f o funcție reală definită și continuă pe intervalul I din Dacă oricare ar fi și din I, , atunci f este convexă pe I.

Rezolvare:

Aplicația 17

Să se demonstreze inegalitatea:

Rezolvare:

BIBLIOGRAFIE

A.M.Fink, D.S.Mitrinovic, Classical and New Inequalities in Analysis, Editura Kluwer academic publishers, 1993

Megan, Bazele analizei matematice, Editura Eurobit, 1997;

Mihai Pascu, Analiză matematică I, Editura Universității Petrol-Gaze din Ploiești, 2007;

R. Tyrrell Rockafellar, Analiză convexă, Editura Theta din București, 2002.

Wolfgang Breckner, Dualitatea problemelor de optimizare convexă, Universitatea Babeș-Bolyai Cluj- Napoca, 1998.

Aurelia Catană, Alin Catană, Probleme de analiză matematică și observații metodologice clasele XI-XII, Editura Didactică și Pedagogică Bucuresti, 1993

BIBLIOGRAFIE

A.M.Fink, D.S.Mitrinovic, Classical and New Inequalities in Analysis, Editura Kluwer academic publishers, 1993

Megan, Bazele analizei matematice, Editura Eurobit, 1997;

Mihai Pascu, Analiză matematică I, Editura Universității Petrol-Gaze din Ploiești, 2007;

R. Tyrrell Rockafellar, Analiză convexă, Editura Theta din București, 2002.

Wolfgang Breckner, Dualitatea problemelor de optimizare convexă, Universitatea Babeș-Bolyai Cluj- Napoca, 1998.

Aurelia Catană, Alin Catană, Probleme de analiză matematică și observații metodologice clasele XI-XII, Editura Didactică și Pedagogică Bucuresti, 1993