Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
From MaRDI portal
The author gives an algorithm for solving a linear program \(\min \{C^ Tx| \quad Ax=b,\quad x\geq 0\},\) using a sequence of shifted-barrier problems \(\min \{C^ Tx-\epsilon \cdot \sum^{n}_{j=1}\ln (x_ j+\epsilon h_ j)| \quad Ax=b,\quad x+\epsilon h>0\}\) for a fixed shift vector \(h>0\), and a sequence of \(\epsilon >0\), that converges to zero. The advantages of the shifted-barrier algorithm are presented.
Recommendations
Cites work
- A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming
- A monotonic projective algorithm for fractional linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- An extension of Karmarkar's algorithm for linear programming using dual variables
- Conical projection algorithms for linear programming
- scientific article; zbMATH DE number 4121751 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Optimization of “\log x” Entropy over Linear Equality Constraints
- Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
Cited in
(17)- Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
- A combined phase I-phase II scaled potential algorithm for linear programming
- A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- Scaling, shifting and weighting in interior-point methods
- A combined homotopy interior point method for convex nonlinear programming
- Differential-algebraic approach to linear programming
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- The Newton modified barrier method for QP problems
- Combining phase I and phase II in a potential reduction algorithm for linear programming
- An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming
- Active-set prediction for interior point methods using controlled perturbations
- Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts
- An Interior Point Column Generation Method for Linear Programming Using Shifted Barriers
- A shifted primal-dual penalty-barrier method for nonlinear optimization
- A single-phase, proximal path-following framework
- A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds
- A little theorem of the big \({\mathcal M}\) in interior point algorithms
This page was built for publication: Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q806962)
