Full text
| |
| Author(s): |
Lilian Ferreira Berti
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Ciência da Computação |
| Defense date: | 2016-01-25 |
| Examining board members: |
Aurelio Ribeiro Leite de Oliveira;
Francisco de Assis Magalhães Gomes Neto;
Marta Inês Velazco Fontova;
Roberto Quirino do Nascimento;
Jair da Silva
|
| Advisor: | Carla Taviane Lucke da Silva Ghidini; Aurelio Ribeiro Leite de Oliveira |
| Abstract | |
The interior point methods have been extensively used to solve large-scale linear programming problems. Among all variations of interior point methods, the predictor corrector with multiple centrality corrections is the method of choice due to its efficiency and fast convergence. This method requires solving linear systems, to determine the search direction corresponding to the step that requires more processing time, in each iteration. In this work, the continued iteration is presented and introduced to the predictor corrector method with multiple centrality corrections, in order to reduce the number of iterations and the computational time to determine the linear programming problems solution. The continued iteration consists of determining a new direction combined with the search direction of the interior point methods. Two new continued directions and two different ways of being used, increasing of the steps sizes taken in the search direction, speeding up the convergence of the method. In addition, we use the optimal adjustment algorithm for p coordinates to determine the best starting point for the interior point method in conjunction with the continued iteration. Computational experiments were performed and the results achieved by incorporating the continued iteration in the predictor corrector interior point method and multiple centrality corrections outperform the traditional approach. Using the optimal adjustment algorithm for p coordinates leads to similar results (AU) | |
| FAPESP's process: | 11/20623-7 - Interior Point Methods Iteration Count Reduction Using Continued Iteration and Simple Algorithms |
| Grantee: | Lilian Ferreira Berti |
| Support Opportunities: | Scholarships in Brazil - Doctorate |