Suprafete si planuri tangente

SUPRAFETE SI PLANURI TANGENTE

Aproximarea prin serie Taylor determina pentru vectorul gradient o importanta interpretare geomatrica. Consideram ecuatia unei suprafete intr-un spatiu n-dimensional, de forma:

, unde c este o constanta

Pentru un punct arbitrar, , aproximarea liniara a lui f este :

Daca punctul este pe suprafata, atunci si astfel, pentru oricare punct de pe sufrafata avem relatiile :

, sau unde

Aceste relatii exprima faptul ca produsul scalar dintre vectorul gradient si oricare alt vector, este zero pentru punctele de pe suprafata. Din definitia produsului scalar aceasta inseamna ca vectorul gradient este normal la suprafata. Si mai mult, din punctul de vedere al tehnicilor de optimizare, se poate spune ca de-a lungul directiei ectorului gradient valoarea functiei are cea mai rapida crestere.

Ecuatia planului tangent la o suprafata in punctul este data de ecuatia :

EXEMPLUL 1 : se considera functia de doua variabile . Pentru anumite valori, graficele functiei sunt cercuri centrate in jurul originii. Consideram conturul care are ecuatia . Punctul de coordonate (1,1) satisface ecuatia si este pe contur. Gradientul functiei in punctul (1,1) este:

Ecuatia tangentei la contur in punctul (1,1) este :

sau

Figura curbei, gradientul si tangenta sunt prezentate in fig :

EXEMPLUL 2 : se considera functia de 3 variabile . Pentru valori specifice ecuatia reprezinta sfere cu centrul in origine. Daca se considera cazul f3, ecuatia este . Punctul de coordonate (1,1,1) satisface ecuatia si este pe contur. Gradientul functiei in punctul (1,1,1) este:

,                 

Ecuatia tangentei la contur in punctul (1,1,1) este :

sau

REZOLVAREA SISTEMELOR DE ECUATII NELINIARE (METODA NEWTON-RAPHSON)

Dezvoltarea in serie Tazlor a fost aplicata la o matoda de rezolvare a sistemelor de ecuatii neliniare, metoda ce se numeste Newton-Raphson. Consideram sistemul de ecuatii neliniare:

…

Metoda N-R porneste dintr-un punct initial ales iar iteratiile succesive incearca sa-l deplaseze cit mai aproape de solutia sistemului de ecuatii. Iteratia de baza are forma urmatoare:

unde iar punctul initial este

Imbunatatirea se obtine prin dezvoltare in serie Taylor:

…

Daca scriem toate cele n ecuatii in forma matriceala, se obtine:

sau intr-o forma concentrata:

unde matricea J a derivatelor partiale a functiilor se mai numeste si matricea Jacobianul sau jacobianul sistemului. In aceste conditii, inbunatatirea se poate obtine folosind expresia inversei matricei jacobianului:

Cu fiecare noua iteratie se imbunatateste solutia generala a sistemului. Astfel, convergenta algoritmului poate fi definita folosind norma vectorului :

, unde tol este o valoare mica a tolerantei

Algoritmul Newton-Raphson converge foarte rapid la solutia corecta daca punctul de star este ales in proximitatea acesteia. Oricum, se cunoaste despre aceaqsta metoda ca poate avea un traseu divergent, adica nu converge catre solutia sistemului, daca matricea jacobian a sistemului este aproape singulara. O alta problema este faptul ca algoritmul conduce doar la solutia care se afla aproape de punctul de start, la un maxim local. Dar cum sistemele neliniare pot avea mai multe solutii, singura varianta prin care se acestea se pot determina este sa pornim algoritmul din mai multe puncte de start diferite intre ele. Sau, mai este posibila varianta utilizarii altor algorimi proveniti din analiza numerica.

EXEMPLUL 3 : sa se verifice solutia sistemului neliniar de ecuatii prin metoda N-R, daca se foloseste ca punct de pornire, de start, valoarea si se cunoaste o solutie obtinuta printr-o rutina care implementeaza metoda

Sistemul este :

iar prin utlizarea unei rutine dedicate, se obtine solutia :

FUNCTII PATRATICE

Functiile se zic ca au forma patratica daca titi termenii sunt fie patratele uneia din cele n variabile, fie sunt produse a doua variabile diferite. Citeva exemple de functii patratice sunt :

Toate sistemele de functii patratice pot fi scrise sub urmatoarea forma matriceala :

,

unde :  xvectorul variabilelor

Amatricea de tip simetric a corficientilor, care se construieste astfel :

-diagonala matricei A contine dublul valorii coeficientilor termenilor la patrat

-termenii primei coloane sunt coeficientii termenilor , pentru coloana a doua se iau coeficientii samd

EXEMPLUL 4 : sa se scrie functia de patru variabile sub forma patratica :

Matricea simetrica A asociata ei este :

Se poate verifica acum ca

Diferentialele unei functii patratice, respectiv vectorul gradient si matricea Hessian, se scriu astfel :

si

Se poate ferifica aceasta, luind o functie patratica si calculind vectorul gradient si matricea Hessian atit prin metoda directa, clasica cit si prin relatiile specifice formei patratice.

Semnul unei functii de forma patratica depinzind de semnul produsului pentru toti vectorii posibili x, se clasifica astfel :

-pozitiv definita daca pentru toti vectorii x

-negativ definita daca pentru toti vectorii x

-indefinita, daca pentru unii vectori este realtia iar pentru altii

Analiza semnului formei patratice bazata pe testarea valorilor proprii

Daca toate valorile proprii , unde , ale unei matrici simetrice de dimensiune ale unei forme patratice , sunt cunoascute, atunci semnul formei patratice se determina astfel :

-pozitiv definit daca

-pozitiv semidefinit daca

-negativ definit daca

-negativ semidefinit daca

-indefinit, daca pentru anumiti i si in alte cazuri

Testul minorilor principali pentru determinarea semnului formei patratice

Aceasta metoda implica de obicei mai putine calcule. Daca toti minorii principali , ai matricei simetrice A, de dimeniune ai unei forme patratice , sunt cunoascuti, atunci semnul formei patratice se determina astfel :

-pozitiv definit daca

-pozitiv semidefinit daca

-negativ definit daca

-negativ semidefinit daca

-nedefimit, daca nu se respecta nici un caz din cele enumerate

FUNCTII CONVEXE

O functie se numeste convexa, daca pentru 2 puncte valorile functiei satisfac urmatoarea inegalitate :

, pentru orice

In cazul in care functia f(x) este o functie de o singura variabila, spunem ca functia este convexa daca graficul ei se afla sub segmentul ce uneste oricare doua puncte ale graficului, asa cum este prezentat in figura urmatoare: In caz in care semnul inegalitatii se schimba, functia se numeste concava.

Functie convexa                    Functie nonconvexa

Pentru algoritmii de optimizare, convexitatea unei functii este un element important. Desi definitia nu este complicata, este dificil de folosit, deoarece exista o infinitate de puncte pentru care trebuiesc verificate conditiile de convexutate. Rezolvarea problemei se face apelind la matricea hessian a functiei, prin care se poate determina convexitatea unei functii, dupa algoritmul urmator :

-o functie f(x) este convexa daca matricea hessian este cel putin pozitiv semidefinita

-o functie f(x) este concava daca matricea hessian este cel putin negativ semidefinita

-o functie f(x)este nonconvexa daca matricea hessian este indefinita

Pentru functiile liniare, matricea H este formata doar din zerouri, ceea ce inseamna ca o functie liniara este in acelasi timp concava si convexa.

Asa cum s-a aratat anterior, matricea H a unei functii patratice este egala cu matricea coeficientilor in forma patratica, care implica doar numere. Este simplu de utilizat analiza minorilor principali pentru a determina semnul matricei H.

In cazul functiilor mai complicate, matricea H va implica atit numere cit si variabile si in aceste cazuri nu este simplu de determinat semnul matricei H considerind toate valorile posibile ale variabilelor. Literatura de specialitate propune mai multe metode, observatii si rezultate prin  care sa poata fi tratate si aceste cazuri deosebite :

-daca f(x)este o functie convexa, atunci si este si ea o functie convexa pentru orice 

-suma mai multor functii convexe este si ea o functie convexa

- daca f(x)este o functie convexa iar g(y)este si ea o functie convexaa carei valoare este uniform crescatoare, atunci si functia compusa g(f(x)) este de asemenea o functie convexa.

O alta observatie importanta este ca unele functii nu sunt convexe pe intregul domeniu de definitie, ci numai pe anumite subdomenii.

EXEMPLUL 5 : sa se determine convexitatea functiei urmatoare 

unde

in acest caz hessianul este derivata a doua a functiei (functia este de o singura variabila) :

, pentru

Graficul functiei este :

EXEMPLUL 6 : determinati daca functia urmatoare este convexa :

Hessianul este :

Pentru unele valori este pozitiv, pentru altele este negativ, deci functia nu este convexa. Acest fapt se poate vedea si din reprezentare grafica :

EXEMPLUL 7 : sa se determine daca functia de doua variabile este convexa

Hessianul ei este:        

Minorii principali:        

rezulta ca functia este convexa

EXEMPLUL 8 : sa se determine daca functia de doua variabile este convexa

Hessianul ei este:

In mod evident este imposibil sa verificam semnul minorilor principali. Dar putem folosi elementele teoretice prezentate anterior pentru a arata ca functia este convexa. Astfel vom privi functia ca o suma de doua functii. Vom incerca sa aratam ca fiecare din cei doi termeni este convex si astfel va rezulta ca si suma lor este tot o functie convexa. Fiecare termen e de forma , unde z este un numar real.Folosind regula functiilor compuse legata de caracterul convex, trebuie sa aratam acum ca functiile ce reprezinta puterile lui e sunt functii convexe

Astfel si functia este convexa

Astfel si functia este convexa

Graficul functiei arata clar ca este vorba despre o functie continua, crescatoare si convexa:

PROBLEME DE OPTIMIZARE CONVEXA

O problema de optimizare de tip convex este aceea unde functia obiectiv este o functie convexa iar domeniul posibil al solutiilor este o multime de tip convex.

O multtime se numeste convexa daca orice segment ce uneste doua puncte din multime ramine complet in interiorul multimii (vezi figura urmatoare).

Multime convexa Multime nonconvexa

Este clar faptul ca problemele de optimizare liniara (programare liniara) sunt in acelasi timp si probleme convexe de optimizare. Problemele neliniare de optimizare care au functia obiectiv de tip convex si constringerile date prin ecuatii ori inecuatii de tip liniar si constringeri tip inecuasii neliniare convexe, reprezinta si ele probleme de optimizare convexa. Daca macar o singura constringere este de tip ecuatie neliniara, sistemul se numeste neconvex.

Cea mai importanta proprietate a unei probleme de optimizare convexa este faptul ca orice minim local este in acelasi timp si minim global !!!

EXEMPLUL 9: Sa se determine daca urmatoarea problema de optimizare este una de tip convex:

min

avind restrctiile:

problema contine in setul de restrictii o ecuatie neliniara, deci nu este o problema de optimizare convexa!!!

EXEMPLUL 10: Sa se determine daca urmatoarea problema de optimizare este una de tip convex:

min

avind restrictiile:

In acest caz, in locul ecuatiei neliniare din setul de constringeri, este o inegalitate. Trebuiesc verificate toate elementele problmei, functia obiectiv si setul de restrictii:

hessianul minor principal functie convexa

hessianul     minor principal functie convexa

hessianul     minor principal functie convexa

hessianul minor principal statut nedeterminat

Deoarece minorul celei de-a treia functii contine variabila y, satutul este incert.Nu putem spune despre minor ca este pozitiv ori negativ. In cazul in care se accepta ca , atunci minorul este si el pozitiv si problema este convexa!!!