Universidade Federal de Minas Gerais Instituto de Ciˆencias Exatas Departamento de Ciˆencia da Computa¸c˜ao Algoritmos de Newton-Krylov precondicionados para m´etodos de pontos interiores Silvana Bocanegra Belo Horizonte Dezembro de 2005 Silvana Bocanegra Algoritmos de Newton-Krylov precondicionados para m´etodos de pontos interiores Orientador: Frederico Ferreira Campos, filho Tese de doutorado apresentada ao Curso de P´os-Graduac¸˜ao em Ciˆencia da Computac¸˜ao da Universidade Federal de Minas Gerais, como requisito parcial para obtenc¸˜ao do grau de Doutor em Ciˆencia da Computac¸˜ao. Belo Horizonte Dezembro de 2005 A` minha querida m˜ae, Romilda, meupai, Lamerch(in memorian). Agradecimentos Agradec¸o imensamente ao Prof. Frederico por sua inestim´avel orientac¸˜ao, tanto cient´ıfica quanto pessoal, e acima de tudo por sua amizade. Ao Prof. Marcos, por me transmitir s´olidos conhecimentos na ´area de pontos interiores, e pelo apoio nos momentos dif´ıceis encontrados durante esse per´ıodo. Ao Prof. Aur´elio por sua valiosa contribuic¸˜ao, fornecendo o c´odigo e me orientando no desenvolvimento do trabalho. A` minha m˜ae, principal respons´avel por essa vit´oria, pela sua imensa luta para me propor- cionar uma formac¸˜ao digna e pelo carinho e amor incondicionais em todos os momentos de minha vida. Aos meus irm˜aos Sandra e Sandro, por serem sempre o meu porto seguro e por colocarem em minha vida os sobrinhos maravilhosos Marcela, Willian e Isabela, que tanto amo. A` minha madrinha Cizinha pelas orac¸˜oes a mim concedidas e aos agregados da fam´ılia Silmara, Osmar e Diego pelos momentos divertidos em Araraquara. A todos os colegas do curso de doutorado, em especial aos amigos Ju´lio, Umberto, Lula e Kissia que muito me ajudaram nas disciplinas da qualificac¸a˜o e `as amigas Dri, Joyce e Karla pelo apoio e incentivo nestes u´ltimos meses. Ao amigo David pela sua grande ajuda na linguagem C e ao amigo Paulo pela companhia em muitas noites de laborat´orio. A`s amigas Dri, Lena, Kissia, Dani, Fernanda, Bianca, Mariana, Duda, Aninha e Clau´dia por serem ´otimas companheiras nos momentos de descontrac¸˜ao. A`s amigas de apartamento, Nazar´e, Simone, Dani, Kissia, Fernanda e Lena pela amizade e pelos momentos felizes que compartilhamos durante esses anos. A todos os professores, que contribu´ıram com minha formac¸˜ao, em especial aos professores Frederico, Marcos e Christiano por compartilharem suas experiˆencias como docentes. Aos funcion´arios do DCC, por serem sempre prestativos. A` CAPES e FAPEMIG, pelo imprescind´ıvel apoio financeiro. A Deus, por tudo. Resumo M´etodos de pontos interiores tˆem sido amplamente usados na soluc¸˜ao de problemas de pro- gramac¸˜ao linear de grande porte. A cada iterac¸˜ao destes m´etodos ´e necess´ario resolver um sistema de equac¸˜oes lineares para calcular a direc¸˜ao de Newton. Esta´e a tarefa que demanda a maior parte do tempo de processamento e deve ser feita de forma eficiente. A abordagem mais utilizada em m´etodos de pontos interiores implementa a fatorac¸˜ao de Cholesky. No entanto, esta fatorac¸˜ao pode ser densa em algumas classes de problemas. Nestes casos, o uso de m´etodos iterativos torna-se mais interessante, desde que sejam utilizados com precondi- cionadores eficientes. Devido `a dificuldade de encontrar estrat´egias de precondicionamento que apresentam bons resultados durante todas as iterac¸˜oes de pontos interiores estamos pro- pondo uma abordagem iterativa h´ıbrida para resolver estes sistemas. O m´etodo do gradiente conjugado ´e precondicionado nas iterac¸˜oes iniciais (fase I) usando um tipo de fatorac¸˜ao in- completa de Cholesky na qual o preenchimento pode ser controlado em termos da mem´oria dispon´ıvel e nas u´ltimasiterac¸˜oes (fase II) usando umprecondicionador baseado na fatorac¸˜ao LU que apresenta melhores resultados nas proximidades da soluc¸˜ao ´otima. A troca de fases ocorre quando a fatorac¸˜ao controlada de Cholesky comec¸a a perder eficiˆencia tornando lenta a convergˆencia pelo m´etodo do gradiente conjugado. Experimentos num´ericos revelam que a abordagem h´ıbrida apresenta desempenho superior quando comparada a abordagem direta na soluc¸˜ao de algumas classes de problemas de programac¸a˜o linear de grande porte. i Abstract Interior point methods have been widely used to solve large-scale linear programming pro- blems. The bulk of the work in these methods is computing the search direction by solving one or more linear systems. The most commom approach in interior point solvers uses Cholesky sparse factorization to solve these systems. In some problems this factorization becomes prohibitive due to storage and time limitations. Iterative approaches are more interesting in these situations. Since these systems are ill-conditioned, it is crucial to deve- lop efficient preconditioners. However it is difficult to find a preconditioning strategy that produces good performance of iterative methods over the entire course of the interior point iterations. We are proposing a hybrid approach to solve these systems. The preconditioned conjugate gradient method works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems become highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. The numerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems. ii Sum´ario 1 Introduc¸˜ao 1 2 M´etodos de pontos interiores para programa¸c˜ao linear 4 2.1 Problemas de programac¸˜ao linear . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 M´etodo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 M´etodo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Algoritmo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Algoritmo preditor-corretor . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Implementac¸˜oes de m´etodos pontos interiores . . . . . . . . . . . . . . . . . 11 3 Solu¸c˜ao do sistema de equa¸c˜oes de Newton 14 3.1 Estrat´egias de soluc¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.1 Equac¸˜oes normais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.2 Sistemas aumentados . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Abordagem direta: fatorac¸˜ao de Cholesky . . . . . . . . . . . . . . . . . . . 17 3.3 Abordagem iterativa: m´etodos do subespac¸o de Krylov . . . . . . . . . . . . 19 3.3.1 Embasamento te´orico dos m´etodos . . . . . . . . . . . . . . . . . . . 20 iii 3.3.2 M´etodo do Gradiente Conjugado . . . . . . . . . . . . . . . . . . . . 25 3.3.3 M´etodo LQ sim´etrico - SYMMLQ . . . . . . . . . . . . . . . . . . . . 28 4 Precondicionamento de sistemas lineares 31 4.1 Agrupamento dos autovalores . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.1 Escala diagonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.2 Fatorac¸˜ao incompleta de Cholesky . . . . . . . . . . . . . . . . . . . . 33 4.2 Reordenamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Precondicionadores projetados para m´etodos de pontos interiores . . . . . . . 35 5 Precondicionador h´ıbrido para problemas de programa¸c˜ao linear 42 5.1 Fatorac¸˜ao controlada de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Precondicionador separador . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Experimentos num´ericos 52 6.1 O c´odigo PCx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.1.1 Soluc¸˜ao dos sistemas lineares: vers˜ao original . . . . . . . . . . . . . . 54 6.1.2 Soluc¸˜ao dos sistemas lineares: vers˜ao modificada . . . . . . . . . . . . 55 6.2 Problemas testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.3 FCC em problemas de programac¸˜ao linear . . . . . . . . . . . . . . . . . . . 57 6.3.1 Escolha do η inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.3.2 Influˆencia do η . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.3.3 Correc¸˜ao na diagonal . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 iv 6.3.4 Reordenamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.4 Precondicionador h´ıbrido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6.4.1 Mudanc¸a de fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.4.2 Precondicionador h´ıbrido versus abordagem direta . . . . . . . . . . . 79 6.4.3 Abordagem h´ıbrida - vers˜ao modificada . . . . . . . . . . . . . . . . . 84 7 Conclus˜oes e trabalhos futuros 86 v Lista de Tabelas 4.1 KEN13: Iterac¸˜oes de m´etodo gradiente conjugado. . . . . . . . . . . . . . . . 41 5.1 Quantidade de mem´oria usada na ICD(0) e na FCC(η). . . . . . . . . . . . . 46 6.1 Problemas testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.2 Escolha do η inicial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.3 Influˆencia do η na soluc¸˜ao do problema PDS-40. . . . . . . . . . . . . . . . 61 6.4 Influˆencia do η na soluc¸˜ao de problemas PDS. . . . . . . . . . . . . . . . . . 62 6.5 Resultados do algoritmo para incremento de η. . . . . . . . . . . . . . . . . . 64 6.6 Tempos de reordenamento (ord) e precondicionamento (pre) para η = 0. . . . 66 6.7 Nu´mero de elementos n˜ao nulos para diferentes valores de η. . . . . . . . . . 67 6.8 Tempo de precondicionamento + iterac¸˜oes (s). . . . . . . . . . . . . . . . . . 68 6.9 Desempenho dos precondicionadores no problema ROU20. . . . . . . . . . . 71 6.10 Desempenho dos precondicionadores no problema QAP15. . . . . . . . . . . 73 6.11 Variac¸˜ao do tempo com incremento do η no problema ROU20. . . . . . . . . 78 6.12 Variac¸˜ao do tempo com incremento do η no problema QAP15. . . . . . . . . 78 6.13 Incremento do η nos problemas NUG12. . . . . . . . . . . . . . . . . . . . . 78 vi