Limiting behavior of the affine scaling continuous trajectories for linear programming problems |
| |
Authors: | Ilan Adler Renato D. C. Monteiro |
| |
Affiliation: | (1) Department of Industrial Engineering and Operations Research, University of California, 94720 Berkeley, CA, USA;(2) Systems and Industrial Engineering Department, The University of Arizona, 85721 Tucson, AZ, USA |
| |
Abstract: | We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called centered optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm. |
| |
Keywords: | Interior-point methods linear programming Karmarkar's algorithm logarithmic barrier function affine scaling algorithms continuous trajectories for linear programming |
本文献已被 SpringerLink 等数据库收录! |
|