M(cid:19)etodos de pontos interiores aplicados ao problema de regress~ao pela norma L p Daniela Renata Cantane Orientador: Prof. Dr. Aurelio Ribeiro Leite de Oliveira Dissertac(cid:24)a~o apresentada ao Instituto de Ci^encias Matema(cid:19)ticasedeComputac(cid:24)a~o-ICMC-USP,comoparte dos requisitos para obtenc(cid:24)a~o do t(cid:19)(cid:16)tulo de Mestre em (cid:19) Ci^encias - Area: Ci^encias da Computac(cid:24)a~o e Matema(cid:19)tica Computacional. USP - Sa~o Carlos - SP Setembro/2004 (cid:18) A minha fam(cid:19)(cid:16)lia. ii Agradecimentos (cid:18) A Deus, por estar sempre abenc(cid:24)oando minha vida e iluminando meus caminhos du- rante toda essa caminhada. Aos meus pais, Cidinha e Carlinhos e aos meus irma~os, Daniel e Diego, pelo apoio e incentivo aos meus estudos. Agradec(cid:24)o por estarem sempre presentes em minha vida. Ao meu namorado, Daniel, pela compreensa~o nos momentos que estive ausente, pelo seu amor, carinho e amizade durante todos estes anos. Ao meu orientador, pela paci^encia e dedicac(cid:24)a~o ao longo do desenvolvimento do pro- jeto e por ter me concedido esta oportunidade. Aos professores e funciona(cid:19)rios da USP que contribuiram para a minha formac(cid:24)a~o de uma forma em geral. (cid:18) As minhas amigas \irma~zinhas", Aline, Lilian, Kelly, Cec(cid:19)(cid:16)lia, Glaucia e So^nia que sempre estiveram dispostas a ajudar quando necessitei. (cid:18) A FAPESP - Fundac(cid:24)a~o de Amparo e Apoio a(cid:18) Pesquisa do Estado de Sa~o Paulo, pelo apoio (cid:12)nanceiro. iii Resumo Neste trabalho a fam(cid:19)(cid:16)lia de m(cid:19)etodos de pontos interiores barreira logar(cid:19)(cid:16)tmica (cid:19)e desen- volvida para o problema de regressa~o pela norma L e a estrutura matricial resultante (cid:19)e p exploradaobjetivandoumaimplementac(cid:24)a~oe(cid:12)ciente. Apresentamosalgunsconceitossobre m(cid:19)etodos de pontos interiores necessa(cid:19)rios para o desenvolvimento do m(cid:19)etodo e descreve- mos um m(cid:19)etodo de converg^encia quadra(cid:19)tica previamente conhecido. Uma implementac(cid:24)a~o em Matlab dos m(cid:19)etodos de pontos interiores desenvolvidos (cid:19)e comparada com uma imple- mentac(cid:24)a~o do m(cid:19)etodo quadra(cid:19)tico existente, obtendo desempenho computacional superior. Abstract In this work the family of logarithmic barrier interior point methods is developed for the norm L (cid:12)tting problem and the resultant matrix structure is exploited in order p to have an e(cid:14)cient implementation. We introduce some concepts about interior point methods necessary for the development of the method and describe a previously known quadraticconvergentproblem. AnimplementationinMatlaboftheinteriorpointmethods developed is compared with an implementation of the known quadratic method obtaining better computational performance. iv Conteu(cid:19)do Resumo iv Abstract iv 1 Introduc(cid:24)~ao 1 2 M(cid:19)etodos de Pontos Interiores 4 2.1 Conceitos Iniciais sobre Pontos Interiores . . . . . . . . . . . . . . . . . . . 4 2.1.1 Otimizac(cid:24)a~o Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Otimizac(cid:24)a~o Na~o Linear . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.3 Convexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 M(cid:19)etodo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 M(cid:19)etodo de Newton para uma varia(cid:19)vel . . . . . . . . . . . . . . . . . 9 2.2.2 M(cid:19)etodo de Newton para va(cid:19)rias varia(cid:19)veis . . . . . . . . . . . . . . . 9 2.3 M(cid:19)etodo de Pontos Interiores Primal-Dual . . . . . . . . . . . . . . . . . . . 10 2.3.1 M(cid:19)etodo Primal-Dual A(cid:12)m-Escala . . . . . . . . . . . . . . . . . . . 10 2.3.2 M(cid:19)etodo Primal-Dual Cla(cid:19)ssico . . . . . . . . . . . . . . . . . . . . . 14 2.4 M(cid:19)etodo de Pontos Interiores Barreira Logar(cid:19)(cid:16)tmica . . . . . . . . . . . . . . 16 2.4.1 Crit(cid:19)erio de Converg^encia . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2 Inicializac(cid:24)a~o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 M(cid:19)etodo de Pontos Interiores Barreira Logar(cid:19)(cid:16)tmica Preditor-Corretor . . . . 20 3 O Problema de Regress~ao L 24 p 3.1 O Problema de Regressa~o pela Norma L . . . . . . . . . . . . . . . . . . . 24 p v 3.2 M(cid:19)etodos Pr(cid:19)e-Existentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.1 M(cid:19)etodos de Relaxac(cid:24)a~o por Coluna para o problema de norma m(cid:19)(cid:16)nima 26 3.2.2 M(cid:19)etodo GNCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4 M(cid:19)etodos de Pontos Interiores Aplicados ao Problema de Regress~ao pela Norma L 38 p 4.1 M(cid:19)etodo Barreira Logar(cid:19)(cid:16)tmica . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1.1 Crit(cid:19)erio de Converg^encia . . . . . . . . . . . . . . . . . . . . . . . . 44 4.1.2 Pontos Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.1.3 Algumas Considerac(cid:24)o~es . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 M(cid:19)etodo Preditor-Corretor . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.1 Algumas Considerac(cid:24)o~es . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 M(cid:19)etodo Primal-Dual Barreira Logar(cid:19)(cid:16)tmica . . . . . . . . . . . . . . . . . . 50 4.3.1 Crit(cid:19)erio de Converg^encia . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3.2 Algumas Considerac(cid:24)o~es . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4 M(cid:19)etodo Primal-Dual Preditor-Corretor . . . . . . . . . . . . . . . . . . . . 57 4.4.1 Algumas Considerac(cid:24)o~es . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5 Regressa~o Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5 Resultados Computacionais 68 6 Concluso~es e Perspectivas Futuras 97 6.1 Concluso~es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.2 Perspectivas Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 vi Lista de Tabelas 5.1 Resultados computacionais utilizando a func(cid:24)a~o f (z). . . . . . . . . . . . . 71 1 5.2 Resultados computacionais utilizando a func(cid:24)a~o f (z). . . . . . . . . . . . . 71 2 5.3 Utilizando a func(cid:24)a~o f (z): z = u;z = v. . . . . . . . . . . . . . . . . . . . 73 1 u v 5.4 Utilizando a func(cid:24)a~o f (z): z = u;z = v. . . . . . . . . . . . . . . . . . . . 73 2 u v 5.5 Utilizando a func(cid:24)a~o f (z) e z = z = e. . . . . . . . . . . . . . . . . . . . . 74 1 u v 5.6 Utilizando a func(cid:24)a~o f (z) e z = z = e. . . . . . . . . . . . . . . . . . . . . 74 2 u v 5.7 Utilizando a func(cid:24)a~o f (z) e z = (((cid:21)+1)=2)e e z = (((cid:21) 1)=2)e. . . . . . 75 1 u v (cid:0) 5.8 Utilizando a func(cid:24)a~o f (z) e z = (((cid:21)+1)=2)e e z = (((cid:21) 1)=2)e. . . . . . 75 2 u v (cid:0) 5.9 Resultados computacionais utilizando a func(cid:24)a~o sinx. . . . . . . . . . . . . 85 5.10 Resultados computacionais utilizando a func(cid:24)a~o sinx. . . . . . . . . . . . . 85 5.11 Resultados computacionais utilizando a func(cid:24)a~o sinx. . . . . . . . . . . . . 86 5.12 Resultados computacionais utilizando a func(cid:24)a~o sinx. . . . . . . . . . . . . 86 5.13 Resultados computacionais utilizando a func(cid:24)a~o sinhx. . . . . . . . . . . . . 87 5.14 Resultados computacionais utilizando a func(cid:24)a~o sinhx. . . . . . . . . . . . . 87 5.15 Resultados computacionais utilizando a func(cid:24)a~o sinhx. . . . . . . . . . . . . 88 5.16 Resultados computacionais utilizando a func(cid:24)a~o sinhx. . . . . . . . . . . . . 88 5.17 Resultados computacionais utilizando a func(cid:24)a~o lnx. . . . . . . . . . . . . . 89 5.18 Resultados computacionais utilizando a func(cid:24)a~o lnx. . . . . . . . . . . . . . 89 5.19 Resultados computacionais utilizando a func(cid:24)a~o lnx. . . . . . . . . . . . . . 90 5.20 Resultados computacionais utilizando a func(cid:24)a~o lnx. . . . . . . . . . . . . . 90 5.21 Resultados computacionais utilizando a func(cid:24)a~o expx. . . . . . . . . . . . . 91 5.22 Resultados computacionais utilizando a func(cid:24)a~o expx. . . . . . . . . . . . . 91 5.23 Resultados computacionais utilizando a func(cid:24)a~o expx. . . . . . . . . . . . . 92 vii 5.24 Resultados computacionais utilizando a func(cid:24)a~o expx. . . . . . . . . . . . . 92 5.25 Resultados computacionais utilizando a func(cid:24)a~o expx2. . . . . . . . . . . . . 93 5.26 Resultados computacionais utilizando a func(cid:24)a~o expx2. . . . . . . . . . . . . 93 5.27 Resultados computacionais utilizando a func(cid:24)a~o expx2. . . . . . . . . . . . . 94 5.28 Resultados computacionais utilizando a func(cid:24)a~o expx2. . . . . . . . . . . . . 94 5.29 Resultados computacionais utilizando o problema de grande porte. . . . . . 95 5.30 Resultados computacionais utilizando o problema de grande porte. . . . . . 95 5.31 Resultados computacionais utilizando o problema de grande porte. . . . . . 96 viii Cap(cid:19)(cid:16)tulo 1 Introduc(cid:24)~ao Desde o surgimento dos m(cid:19)etodos de pontos interiores para otimizac(cid:24)a~o linear, co(cid:19)digos computacionais baseados nessas id(cid:19)eias vem se apresentando como alternativas e(cid:12)cientes para soluc(cid:24)a~o de problemas de grande porte [1; 10; 15; 19]. Uma linha de pesquisa importante nesta a(cid:19)rea considera classes espec(cid:19)(cid:16)(cid:12)cas de proble- mas e explora as particularidades da estrutura matricial com o objetivo de obter imple- mentac(cid:24)o~es ainda mais e(cid:12)cientes, inclusive para problemas com restric(cid:24)o~es lineares e func(cid:24)a~o objetivo na~o linear [5; 20; 21; 22; 23; 24; 25]. O objetivo deste trabalho consiste no desenvolvimento dos m(cid:19)etodos de pontos in- teriores para o problema de regressa~o pela norma L , 1 < p < 2, no estudo da estrutura p matricial resultante e na implementac(cid:24)a~o e(cid:12)ciente do m(cid:19)etodo desenvolvido. Os resultados obtidos sera~o comparados com uma implementac(cid:24)a~o do m(cid:19)etodo proposto em [13]. Dada uma classe de problemas, a forma padra~o para o desenvolvimento de um m(cid:19)etodo de pontos interiores consiste na aplicac(cid:24)a~o do m(cid:19)etodo de Newton a(cid:18)s condic(cid:24)o~es de otimali- dade desconsiderando as restric(cid:24)o~es de capacidade. O m(cid:19)etodo resultante (cid:19)e essencialmente um m(cid:19)etodo de pontos interiores espec(cid:19)(cid:16)(cid:12)co para esta classe de problemas. Algumas al- terac(cid:24)o~es, atrav(cid:19)es da introduc(cid:24)a~o de perturbac(cid:24)o~es, sa~o necessa(cid:19)rias para obter um m(cid:19)etodo e(cid:12)ciente [29; 30]. De forma ana(cid:19)loga, desenvolve-se uma das variantes mais importantes 1 dos m(cid:19)etodos de pontos interiores, o m(cid:19)etodo preditor-corretor [16]. A etapa seguinte desta abordagem consiste na explorac(cid:24)a~o e(cid:12)ciente da estrutura matri- (cid:19) cial do problema. E sempre importante lembrar que a resoluc(cid:24)a~o de um sistema linear, em geral sim(cid:19)etrico, consiste no passo mais caro, em termos computacionais, de cada iterac(cid:24)a~o dos m(cid:19)etodos de pontos interiores. Desta forma, a explorac(cid:24)a~o da estrutura matricial pode levar a m(cid:19)etodos de pontos interiores mais e(cid:12)cientes que os m(cid:19)etodos gen(cid:19)ericos aplicados a um problema particular. As id(cid:19)eias desenvolvidas em [20; 21] para os problemas de regressa~o L e L tamb(cid:19)em podem ser adaptadas a este problema devido a(cid:18) semelhanc(cid:24)a 1 1 das estruturas matriciais com o problema de regressa~o L . p O problema de regressa~o min Ax b p x2IRm k (cid:0) kp onde A = [a ;:::;a ] IRm(cid:2)n, b IRn e n > m, tem inu(cid:19)meras aplicac(cid:24)o~es em diversas 1 n 2 2 a(cid:19)reas de ci^encias e engenharias. As normas mais utilizadas sa~o as normas L ;L e L . A 1 2 1 norma L (cid:19)e muito popular entre outros motivos por permitir uma soluc(cid:24)a~o direta. Por sua 2 vez a norma L permite diminuir o efeito de pontos discrepantes enquanto que a norma 1 L garante protec(cid:24)a~o contra o pior caso. 1 O m(cid:19)etodo IRLS iteratively reweighted least-squares [17] foi por muito tempo a u(cid:19)nica alternativa pra(cid:19)tica para a resoluc(cid:24)a~o deste problema para outros valores de p. Mais recen- temente este m(cid:19)etodo foi aperfeic(cid:24)oado, no que diz respeito a(cid:18) robustez, atrav(cid:19)es da inclusa~o de uma busca linear [13]. No mesmo trabalho, foi tamb(cid:19)em proposto um novo m(cid:19)etodo que apresenta caracter(cid:19)(cid:16)sticas similares aos m(cid:19)etodos de pontos interiores. Este m(cid:19)etodo apresentou resultados computacionais superiores ao IRLS. Ambos m(cid:19)etodos apresentados em [13] t^em uma importante desvantagem: a busca linear(cid:19)ecomputacionalmentecara. Istonosmotivouoestudodosm(cid:19)etodosdepontosinteri- ores aplicados a este problema que obt(cid:19)em resultados computacionais superiores, repetindo o desempenho obtido na minimizac(cid:24)a~o pelas normas L e L em [20; 21], respectivamente. 1 1 2