Contributed Session Thu.2.H 0110

Thursday, 13:15 - 14:45 h, Room: H 0110

Cluster 16: Nonlinear programming [...]

Interior-point methods for linear programming


Chair: Luiz-Rafael Santos



Thursday, 13:15 - 13:40 h, Room: H 0110, Talk 1

Aurelio Oliveira
Continued iteration and simple algorithms on interior point methods for linear programming

Coauthors: Lilian Berti, Carla Ghidini, Jair Silva


Continued iteration and simple algorithms are applied between interior point iterations to speed up convergence. In the continued iteration, interior point methods search directions are projected along the blocking constraint in order to continue the iteration. The process can be repeated
while the projected direction is a good one in some measure. In a similar fashion, a few iterations of simple algorithms can be applied to the current interior point. Numerical experiments show that the combining such approaches leads to promising results, reducing the total number of iterations for the interior point methods applied to linear programming problems.



Thursday, 13:45 - 14:10 h, Room: H 0110, Talk 2

Luciana Casacio
New preconditioners for interior point methods in linear programming

Coauthors: Christiano Lyra, Aurelio R L Oliveira


We are concerned with the KKT systems arising when an interior
point method is applied to solve large-scale linear programming problems. We exploit the basic-nonbasic partition to design novel preconditioners for iterative methods applied to these systems. A two-phase iterative method is used which switches between different preconditioners. We provide a spectral analysis for the preconditioners and illustrate their practical behaviour on medium-scale problems from the Netlib collection.



Thursday, 14:15 - 14:40 h, Room: H 0110, Talk 3

Luiz-Rafael Santos
A polynomial optimization subproblem in interior-point methods

Coauthors: Aurelio Oliveira, Clovis Perin, Fernando Villas-Bôas


In this work we study a primal-dual path-following interior point method for linear programming. Our approach, based on Mehrotra's predictor-corrector methods, combines three types of directions to generate a better one by making an extensive use of real-valued polynomials on variables ( α,\mu,σ), where α is the step length, \mu defines a more general central path, and σ models the weight that a predictor direction should have. We develop a merit function that is a polynomial in ( α,\mu,σ) and that is used as a guide to combine those directions. This merit function is subjected to polynomial constraints, which are designed to keep the next point into a good neighbourhood of the central path - a generalization of Gondzio-Colombo's symmetric neighbourhood. A polynomial optimization problem (POP) arises from this approach and its global solution, in each iteration, leads to the choice of the next direction. Different methods for solving the POP are being experimented and the computational experiments are promising.


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.