en
Report
English

A Generic Path-Following Algorithm with a Sliding Constraint and its Application to Linear Programming and the Computation of Analytic Centers

Collection
  • Cahiers de recherche; 1996.08
Publication date1996
Abstract

We propose a generic path-following scheme which is essentially a method of centers that can be implemented with a variety of algorithms. The complexity estimate is computed on the sole assumption that a certain local quadratic convergence property holds, independently of the specific algorithmic procedure in use, primal, dual or primal-dual. We show convergence in iterations. We verify that the primal, dual and primal-dual algorithms satisfy the local quadratic convergence property. The method can be applied to solve the linear programming problem (with a feasible strat) and to compute the analytic center of bounded polytope. The generic path-following scheme easily extends to the logarihmic barrier approach

Citation (ISO format)
VIAL, Jean-Philippe. A Generic Path-Following Algorithm with a Sliding Constraint and its Application to Linear Programming and the Computation of Analytic Centers. 1996
Identifiers
  • PID : unige:5952
456views
0downloads

Technical informations

Creation04/15/2010 12:21:33 PM
First validation04/15/2010 12:21:33 PM
Update time03/14/2023 3:27:06 PM
Status update03/14/2023 3:27:06 PM
Last indexation01/15/2024 7:46:44 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack