Contribucions als algorismes de punt interior en metodes iteratius per a sistemes d'equacions usant regularitzacions quadratiques

Resumen

Els mètodes de punt interior per a programació lineal proporcionen algorismes de complexitat polinòmica , que els fa ser mol ficients en l'optimitzaciò a gran escala, Aquests algorismes utilitzen el mètode de Newton per a convertir les equacions d'óptim del roblema, que són no lineals. en un sistema d'equacions lineals. que solen resoldre's aplicant factorizacions de matrius esparses. En aquells casos particulars en els quals el problema tè una estructura especial. com ara en els problemes d'optimització en xarxe ultiarticle, es pot aprofitar per millorar l'eficiència de l'algorisme. Aquests problemes de xarxes pertanyen a la familia mès general e problemes prima ls bloc-angulars. El punt de partida d'aquesta tesi va ser un fet empiric: l'observació del millor comportament computaciona l d'un algorisme specialitzat de punt interior per a problemes bloc-angulars quan en la funció objectiu figuren termes quadràtics. Aquest algorisme tilitza factoritzacions de matrius per resoldre la part de les equacions associades a la xarxa i el mètode del gradient conjugat recondicionat per resoldre les equacions associades a les restriccions d'acoblament. Llavors l'objectiu original va ser buscar Iguna forma d'aproximar un problema lineal per un de quadratic de manera que s'explotès el fet experimental observat sense erjud icar la convergència del problema. Posteriorment el plantejament inicial es va ampliar amb el nou objectiu de demostrar la onvergència del mètode, entre altres resultats teórics. El marc teóric usat per poder formular matematicament aquesta idea ha estat la regularització de la funció de barrera logaritm ica ssociada al problema d'optimització , entenent com a talla transformació de la funció de barrera original per una altra que inclou un erme quadratic variable de pertorbació, que disminueix progressivament conforme l'algorisme s'atansa a l'òptim. Aquest terme uadratic converteix el problema lineal original en un de quadratic. de forma que en les primeres iteracions aprofitem el omportament empiric abans esmentat i. a mesura que progressa l'algorisme, el terme quadràtic esdevê negligible. i el problema mb regularització quadratica s'atansa al problema lineal original. La barrera regularitzada resulta ser auto-concordan!. assegurant ixi la convergència del mètode de punt interior.