Els mètodes de punt interior per a programació lineal proporcionen algorismes de complexitat polinòmica, que els fa ser molt eficients en l’optimització a gran escala. Aquests algorismes utilitzen el mètode de Newton per a convertir les equacions d’òptim del problema, 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 xarxes multiarticle, es pot aprofitar per millorar l’eficiència de l’algorisme. Aquests problemes de xarxes pertanyen a la família més general de problemes primals bloc-angulars.
El punt de partida d’aquesta tesi va ser un fet empíric: l’observació del millor comportament computacional d’un algorisme especialitzat de punt inferior per a problemes bloc-angulars quan en la funció objectiu figurem termes quadràtics. Aquest algorisme utilitza factoritzacions de matrius per resoldre la part de les equacions associades a la zarza i el mètode del gradient conjugat precondicional per resoldre les equacions asociadse a les restriccions d’acoblament. Llavors l’objectiu original va ser buscar alguna forma d’aproximar un problema lineal per un quadràtic de manera que s’explotés el fet experimental observat sense perjudicar la convergència del problema. Posteriorment el plantejament inicial es va amplificar amb el nou objectiu de demostrar la convergència del mètode, entre altres resultats teòrics.
El marc teòric usat per poder formular matemàticament aquesta idea ha estat la regularització de la funció de barrera logarítmica associada al problema d’optimització, entenent com a tal la transformació de la funció de barrera original per una altra que inclou un terme quadràtic variable de pertorbació, que disminueix progressivament conforme l’algorisme s’atansa a l’òptim. Aqueste terme quadràtic converteix el problema lineal original en un de quadràtic, de forma que en les primeres iteracions aprofitem el comportament empíric abans esmentat i, a mesura que progressa l’algorisme, el terme quadràtic esdevé negligible, i el problema amb regularització quadràtica s’atansa al problema lineal original. La barrera regularitzada resulta ser auto-concordant, assegurant així la convergència del mètode de punt interior.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/30709 |
| Date | 29 September 2009 |
| Creators | Cuesta Andrea, Jordi |
| Contributors | Castro Pérez, Jordi, Castro Pérez, Jordi, Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Catalan |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 151 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds