An active-set strategy in an interior point method for linear programming
The author presents a potential reduction method for linear programming, where only active constraints (i.e. constraints with relatively small dual slacks) are taken into account to form the ellipsoid constraint at each iteration of the process. It is proved that the algorithm converges to the optimal feasible solution in \(O(\sqrt n L)\) iterations with the same polynomial bound as in the full constraint case, where \(n\) is the number of variables and \(L\) is the data length. The advantage of the proposed active-set strategy is that the cost of each iteration may be reduced.
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- scientific article; zbMATH DE number 4197744
- A potential reduction algorithm for linearly constrained convex programming
- A potential-reduction variant of Renegar's short-step path-following method for linear programming
- Potential-reduction methods in mathematical programming
- A Centered Projective Algorithm for Linear Programming
- A new polynomial-time algorithm for linear programming
- A relaxed version of Karmarkar's method
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- scientific article; zbMATH DE number 4131946 (Why is no real title available?)
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 3301975 (Why is no real title available?)
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
- Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value
- Active set and interior methods for nonlinear optimization
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Identifying an optimal basis in linear programming
- A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme
- Active-set prediction for interior point methods using controlled perturbations
- A comparison of a Moreau-Yosida-based active set strategy and interior point methods for constrained optimal control problems
- scientific article; zbMATH DE number 4126605 (Why is no real title available?)
- A constraint-reduced variant of Mehrotra's predictor-corrector algorithm
- Adaptive constraint reduction for convex quadratic programming
- A polynomial time constraint-reduced algorithm for semidefinite optimization problems
- Infeasible constraint-reduced interior-point methods for linear optimization
- An active set strategy based on the multiplier function or the gradient.
This page was built for publication: An active-set strategy in an interior point method for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687036)
