Optimization Online


Continuous trajectories for primal-dual potential-reduction methods

Reha H. Tutuncu (reha***at***andrew.cmu.edu)

Abstract: This article considers continuous trajectories of the vector fields induced by two different primal-dual potential-reduction algorithms for solving linear programming problems. For both algorithms, it is shown that the associated continuous trajectories include the central path and the duality gap converges to zero along all these trajectories. For the algorithm of Kojima, Mizuno, and Yoshise, there is a a surprisingly simple characterization of the associated trajectories. Using this characterization, it is shown that all associated trajectories converge to the analytic center of the primal-dual optimal face. Depending on the value of the potential function parameter, this convergence may be tangential to the central path, tangential to the optimal face, or in between.

Keywords: linear programming, potential functions, potential-reduction methods

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Research Report No. 01-CNA-012 Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213 September 2001

Download: [Compressed Postscript][PDF]

Entry Submitted: 09/14/2001
Entry Accepted: 09/14/2001
Entry Last Modified: 09/14/2001

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society