MATEMATICA APLICATA IN INFORMATICA - PROBLEME DE OPTIMIZARE CONVEXA

MATEMATICA APLICATA IN INFORMATICA

PROBLEME DE OPTIMIZARE CONVEXA

1.Notiuni introductive

1.1.Metode Lagrange

Fie P(b) o problema de optimizare:

Minimizarea f(x), pentru h(x)=b, .

Fie Spunem ca x este realizabil daca .

Definim operatorul Lagrange ca:

Tipic, cu unde este numit multiplicator Lagrange

Teorema 1.1. Teorema de suficienta Lagrange

Daca este realizabil pentru P(b) si exista astfel incat

Pentru , atunci este optim pentru P(b).

Demonstratie:

Pentru toti si avem

Acum daca si prin presupunere

pentru toti .

Atunci x este optim pentru problema de optimizare P(b).

Exemplu: Minimul pentru cu .

Aici . Consideram problema:

Minimizarea []

Aceasta are un punct in care

Acum alegem astfel incat . Aceasta se intampla

Astfel avem minimul deoarece

Cu aceasta valoare a lui , conditiile de suficienta Lagrange sunt satisfacute si valoarea optima este la

1.2.Problema duala

Definim:

pentru si

Atunci pentru toate

Deci este margine inferioara pe deci o margine inferioara pe solutia din P(b).

Dorim sa maximizam aceasta margine inferioara    pentru care .

Aceasta constituie problema duala, definite ca:

Maximizarea , pentru , pentru

1.3.Hiperplane

Un hiperplan este dat de:

Exista o intersectie in cu axa verticala prin b si are panta .

Consideram urmatoarea modalitate de cautare a

1. Pentru fiecare , gasim     astfel incat hiperplanul se afla complet sub graficul lui .
2. Acum sa alegem pentru a maximiza .

Metodele Lagrange functioneaza pentru cazul a. din cauza existentei unei tangente la b.

Sa definim un hiperplan in b astfel:

, unde pentru toate .

De fapt, . Pentru a demonstra aceasta, folosim:

Deci avem problema duala sub forma max.

2.Programarea Lineara

2.1.Convexitate si metode Lagrange

Definitii:

1. Un set S este un set convex daca pentru toate

2. f este o functie convexa, daca pentru toate si avem

3. Un punct x este un punct extreme din S, daca pentru

, pentru valori si 0<<1 atunci x=y=z.

Teorema 2.1 (Suport pentru hiperplane)

Presupunem este convex si b se afla in interiorul setului de puncte unde este finit. Atunci exista un hiperplan de sustinere (care nu este vertical) la in b.

Ne intereseaza conditiile problemei care fac convex.

Teorema 2.2. Considerand problema P(b), definite ca

pentru

Daca X este un set convex si f si h sunt convexe atunci si este convex.

Demonstratie:

Luam si , pentru 0<<1 cu in asa fel incat este definit.

Luam realizabil pentru P() pentru i=1,2 si consideram

Atunci X convex, implica ca . De asemenea, h convex implica

Daca x este realizabil pentru P(b) si f convex

Aceasta e valabil pentru toti si asa ca minimul reprezinta:

asa ca este convex.

2.2. Programe Lineare

Vom studia probleme de forma

minimizarea unde x si c sunt vectori cu n elemente si b este un vector cu m elemente. A este o matrice mxn.

Un exemplu de problema in programarea lineara este problema dietei.

Se dau n alimente , care contin fiecare m substante nutritive

Atunci este continutul din substanta in alimentul

reprezinta meniul, cantitate din alimentul , pentru j=1,n

reprezinta minimul din substanta nutritive pe care dorim sa o aiba meniul.

este pretul unitar

Problema lineara este determinarea unui meniu care sa respecte necesarul de substante nutritive si sa minimizeze cheltuiala, adica:

, pentru i=1,n si

Minimizarea , pentru i=1,n

Varianta duala a problemei lineara este cea a farmacistului care are substante concentrate si trebuie sa stabileasca preturi unitare , astfel incat castigul lui sa fie maxim iar cheltuiala comparatorului sa nu depaseasca costul variantei cu meniul de alimente. Adica:

, pentru j=1,n si

Maximizarea

In acest sens rezulta teoremele de dualitate.

Notam cu P, multimea solutiilor posibile a problemei lineare

Si , multimea solutiilor posibile pentru problema lineara duala

Teorema 2.2.1.

Teorema 2.2.2.

a)      Daca P este multime vida atunci functia obiectiv pentru este nemarginita superior cand este nevida.

b)      Daca este multime vida, atunci functia obiectiv pentru P este nemarginita inferior cand P este nevida

Pe baza teoriilor de dualitate, algoritmul simplex permite rezolvarea problemelor P si .

3.Algoritmul Simplex

Se reduce la urmatorii pasi:

1. Incepe cu o solutie de baza, realizabila
2. Testeaza daca este optima
3. Daca DA, atunci stop.
4. Daca NU, atunci mutare spre o solutie adiacenta, mai buna si continua cu pasul 2.

3.1.Punctul de vedere algebric

O baza B, este un vector de m variabile, diferite de 0.

Pentru orice x care satisface Ax=b, putem scrie:

, unde este o matrice mxm si este o matrice mx(n-m)

si b sunt vectori de marime m si este un vector de marime (n-m).

O solutie de baza are =0, , iar o solutie de baza realizabila are =0, si .

Asa cum am vazut, daca exista un optim finit, atunci exista si o solutie de baza realizabila care este optima.

3.2.Tabelul Simplex

Pentru orice x cu Ax=b, avem .

Deci: f(x)=

Acestea se pot grupa intr-un tabel:

3.3.Testarea optimului

Sa presupunem ca vrem sa maximizam si gasim

si

Atunci pentru toti x, realizabil ()

Dar pentru un de baza realizabil, si avem

Deci este optim, oferind astfel posibilitatea verificarii ca o solutie de baza, realizabila este optima.

3.4.Alegerea unei noi solutii

Alternativ, daca este pozitiv, atunci putem mari valoarea functiei obiectiv, prin marirea valorii .

Se doreste marirea lui cu cat mai mult posibil, dar cu satisfacerea conditiilor. Daca modificam marimea lui , atunci si celelalte variabile se modifica si trebuie sa ne oprim daca una devine 0.

3.5.Algoritmul Simplex

I. Gaseste o solutie initiala realizabila cu baza B

II.Verifica semnul , pentru Toate elementele sunt pozitive?

III.Daca DA, atunci avem un optim. Stop.

IV.Daca NU, prin urmarirea conditiei >0, cu , marim pe cat posibil.

Aceasta marirea poate fi infinita, ceea ce inseamna ca maximul nu poate fi atins. Stop

Sau, o variabila devine 0, ceea ce da o noua solutie realizabila. Atunci se repeta incepand de la pasul II.

Sub forma de tabel avem:

Atunci constrangerile sunt:

Ceea ce se poate scrie ca Ax+z=b,

Si sa luam solutia initiala realizabila x=0, z=b

Ne putem gandi ca o extindere a lui x la (x,z) si sa setam

Pas1.Alegerea unei variabile ca baza

Cautam un j astfel incat >0. Coloana j este numita coloana pivot si variabila corespunzatoare coloanei j ca forma baza. Daca pentru toti atunci solutia curenta este cea optima.

Daca exista mai multe >0 vom alege una. O regula comuna este alegerea lui j pentru care are valoarea pozitiva cea mai mare.

Pas2.Cautarea unei variabile care sa fie eliminate din baza

Alegem i care minimizeaza / din setul de valori pozitive >0. Randul i se numeste rand pivot. Daca pentru toti i, atunci problema nu este marginita, iar functia obiectiv poate fi crescuta fara limita.

In exemplu de mai jos avem in acest punct:

Pas3.Pivotarea elementului

Scopul este de a aduce ecuatiile intr-o forma apropiata pentru o noua solutie de baza, realizabila.

- Inmultim randul i cu 1/.

- Adunam rand(i) la fiecare rand , inclusiv randul functiei obiectiv

Noua forma a tabelului este:

Acum ne intoarcem iar de la Pasul 1.

In exemplul nostru, urmatoarea iteratie ne aduce valoarea optima.

Aceasta corespunde solutiei .

3.6. Algoritmul Simplex Dual

Consideram problema de programare lineara definite in sectiunea 2.2., definite ca:

Minimizarea cu duala

Maximizarea

La fiecare pas a algoritmului simplex avem urmatorul table:

Acum avem o solutie de baza, realizabila pentru problema lineara primara si

O solutie de baza (nu neaparat realizabila) pentru varianta duala .

Pentru exemplul urmator dorim sa minimizam pentru

Se observa ca , pentru toti i. Fie variabilele astfel incat sa obtinem:

Algoritmul in cazul problemei lineare primare trebuie sa foloseasca doua faze, de vreme ce , nu este o solutie realizabila. Insa tabelul contine o solutie pentru problema lineara duala: si .

Pentru liniile i cu <0 alegem o coloana cu <0 pentru a minimiza /-. Pivotand pe avem:

Si apoi pe

Deci valoarea optima este , cu

Probleme de forma pot fi scrise astfel:

Ax-z=b cu

Rezulta:

Deci variabilele duale pot fi gasite in randul functiei obiectiv in cadrul tabelului de optim (exemplu )

4.Complexitatea Algoritmilor

4.1. Teoria complexitatii algoritmilor

O instanta a unei probleme de optimizare este definite prin datele de intrare. De exemplu, o instanta a unei probleme de programare lineara cu n variabile si m constangeri este definite de parametrii de intrare c,A si b. Sunt mxn+m+n numere si daca toate pot fi exprimate in cel mult k biti, atunci instanta poate di descrisa intr-un sir de (mxn+m+n)k biti. Aceasta este marimea instantei.

O problema de optimizare este rezolvata printr-un algoritm, in genului unui set de instructiuni. Timpul de rulare a algoritmului depinde de programare si viteza hardware. O instanta mare, cum ar fi o problema lineara poate fi rezolvata usor, daca A=I. Insa, timpul de rulare a unui algoritm creste cu marimea instantei.

Ignorand detaliile de implementare , timpul de rulare depinde de numarul de operatii implicate.

De exemplu, un sistem linear Ax=b, cu A de marime nxn, poate fi rezolvat de catre algoritmul de eliminare Gaussian, folosind operatii de adunare, scadere, inmultire si impartire.

Bineinteles ca inmultirea este mai dificila decat adunarea si necesita mai mult timp de calcul, deci mai multe instructiuni elementare. Fie T(n) cel mai rau caz de rulare a unui algoritm pe toate instantele de marime n. T(n) este cateodata polinomial in marimea problemei

pentru toate n, pentru un polinom (ex. sau ).

Algoritmul se spune ca ruleaza in timp polinomial.

Probleme P si NP

Spunem ca o problema, care ia forma unei intrebari cu raspuns tip Da/Nu, apartine lui P, daca poate fi rezolvata de un algoritm care ruleaza in timp polinomial.

Spunem ca o problema apartine lui NP, daca fiecare instanta Da, are un certificate, a carei validitate poate fi verificata in timp polinomial.

NP reprezinta nondeterministic polinomial, adica un polinomial nedeterminist. O problema de decizie apartine lui NP, daca poate fi rezolvata pe un calculator nedeterminist. Un calculator nedeterminist consta dintr-un numar exponential de calculatoare care lucreaza in paralel, oricare dintre ele poate raspunde Da, intr-un timp polinomial, fara a se consulta cu celelalte.

Putem vorbi de cele mai grele probleme in NP. O problema este grea in NP, daca fiecare problema din NP poate fi redusa la ea. Se spune ca este completa NP, daca . Deci, toate probleme NP complete poate fi redusa una la alta si sunt la fel de grele ca orice problema in NP.

Sunt multe probleme NP complete. O problema lineara este NP completa , daca toate variabilele sunt restranse la 0 sau 1. Problema comisului voiajor este NP completa, la fel si determinarea lanturilor hamiltoniene in grafuri.

5.Complexitatea computationala a problemei lineare

5.1.Timpul de rulare a unui algoritm simplex

Cel mai rau caz de rulare

Algoritmul simplex trece de la o solutie de baza realizabila, la alta, de fiecare data imbunatatind valoarea functiei obiectiv. Din pacate, poate necesita un numar exponential destul de mare de pasi pentru a termina.

Presupunem ca o regiune realizabila este un cub in definit de constangerile:

cu i=1,.,d

Cautam sa maximizam Sunt noduri. Drumul de mai jos viziteaza toate nodurile inainte de a termina la (0,0,.,1).

d=2 d=3

Fie dat atunci cubul dat de constrangerile:

cu i=2,.,d

Se poate verifica ca, costul functiei creste cu fiecare miscare de-a lungul drumului. De exemplu, pentru d=2 avem:

   

Observam ca creste pe secventa ABCD. Asa ca daca regula de pivotare este sa ne mutam la solutia adiacenta realizabila, pentru care cresterea functiei obiectiv este mica, atunci algoritmul simplex va avea nevoie de -1 pasi de pivotare inainte de terminare.

Cu aceasta regula de pivotare, algoritmul simplex prezinta o complexitate exponentiala maxima. Se observa ca nodul initial sic el final sunt adiacente si o regula diferita de pivotare poate reusi intr-un singur pas. Oricum, pentru toate regulile comune de pivotare, exista instante pentru care numarul de pasi este exponential. Nu se stie daca exista o regula de pivotare care sa faca algoritmul simplex mai eficient.

5.2. Complexitatea Problemei LP

Vom investiga algoritmi alternative pentru rezolvarea problemei de programare lineare. In particular, cautam un algoritm polinomial.

Marimea unei instante LP

Orice intreg r, cu poate fi scris in forma binara

unde sunt 0 sau 1.

Numarul k poate fi maxim Folosind inca un bit pentru semn, putem reprezenta orice intreg r unde prin maxim biti.

O instanta a problemei LP este data de o matrice A mxn, un vector b de marime m si un vector c de marime n. Atunci marimea instantei LP are marimea in biti de:

(mn+m+n)( ).

6.Concluzii

6.1.Optimizarea convexa

O problema de optimizare convexa este una de forma:

Minimizarea pentru , cu i=1.m

Unde functiile sunt convexe, adica satisfac:

pentru toti si , .

Problema de programare lineara este un caz special a problemei de optimizare convexa.

6.2.Rezolvarea problemelor de optimizare convexa

Nu exista in general o formula analitica pentru solutia problemelor de optimizare convexa, dar ca si in cazul problemei de programare lineara, exista metode eficiente pentru rezolvarea lor.

Metodele punctelor interioare merg foarte bine in practica si in cateva cazuri rezolva problema cu o acuratete destul de buna, intr-un numar de operatii care nu depasesc dimensiunea polinomiala.

Am vazut ca se poate rezolva o problema intr-un numar de pasi care variaza de obicei de la 2 la 100.

Folosirea optimizarii convexe, este din punct de vedere conceptual, similara cu rezolvarea problemei celor mai mici patrate sau a problemei de programare lineara.

Insa recunoasterea unei probleme de optimizare convexa este destul de dificil.

Pe langa aceasta, exista trucuri in transformarea unei probleme convexe.

Recunoasterea unei probleme de optimizare convexa sau una care poate fi transformata intr-o problema convexa este o provocare.

Exista o varietate de aplicatii ale optimizarii convexe, in domenii precum probabilitatea si statistica, geometria de calcul si ajustarea de date.