Full text
| |
| Author(s): |
Luiz Rafael dos Santos
Total Authors: 1
|
| Document type: | Doctoral Thesis |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica |
| Defense date: | 2014-07-31 |
| Examining board members: |
Aurelio Ribeiro Leite de Oliveira;
Francisco de Assis Magalhães Gomes Neto;
Marta Inês Velazco Fontova;
Pedro Augusto Munari;
Luís Felipe Cesar da Rocha Bueno
|
| Advisor: | Aurelio Ribeiro Leite de Oliveira; Fernando Rocha Villas Bôas |
| Abstract | |
In this work we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first one is the step length, the second one defines the central path and the last one models the weight that a corrector direction must have. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better direction. The proposed method generalizes most of predictor-corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments are made, using the Netlib test set, which show that this approach is competitive when compared to well established solvers, such as PCx (AU) | |
| FAPESP's process: | 08/09685-8 - Interior Point Delayed Parameters Choice for Linear Programming |
| Grantee: | Luiz Rafael dos Santos |
| Support Opportunities: | Scholarships in Brazil - Doctorate |