Active-set prediction for interior point methods using controlled perturbations
From MaRDI portal
(Redirected from Publication:263153)
Abstract: We propose the use of controlled perturbations to address the challenging question of optimal active-set prediction for interior point methods. Namely, in the context of linear programming, we consider perturbing the inequality constraints/bounds so as to enlarge the feasible set. We show that if the perturbations are chosen appropriately, the solution of the original problem lies on or close to the central path of the perturbed problem. We also find that a primal-dual path-following algorithm applied to the perturbed problem is able to accurately predict the optimal active set of the original problem when the duality gap for the perturbed problem is not too small; furthermore, depending on problem conditioning, this prediction can happen sooner than predicting the active set for the perturbed problem or when the original one is solved. Encouraging preliminary numerical experience is reported when comparing activity prediction for the perturbed and unperturbed problem formulations.
Recommendations
- An active-set strategy in an interior point method for linear programming
- Warm-start strategies in interior-point methods for linear programming
- Active set and interior methods for nonlinear optimization
- Silving Linear Programs With Inequality Constraints Via Perturbation of Feasible Region
- Perturbed path following predictor-corrector interior point algorithms
Cites work
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- A New Unblocking Technique to Warmstart Interior Point Methods Based on Sensitivity Analysis
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
- A numerical study of limited memory BFGS methods
- A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- A two-sided relaxation scheme for Mathematical Programs with Equilibrium Constraints
- Active Set Identification in Nonlinear Programming
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An Interior Point Column Generation Method for Linear Programming Using Shifted Barriers
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- An active-set strategy in an interior point method for linear programming
- An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- Computational results of an interior point algorithm for large scale linear programming
- Degeneracy in interior point methods for linear programming: A survey
- Error bounds in mathematical programming
- Existence, uniqueness, and convergence of the regularized primal-dual central path
- Finding an interior point in the optimal face of linear programs
- Interior point methods 25 years later
- Linear and integer programming: Theory and practice.
- Linear programming with MATLAB
- Modified barrier functions (theory and methods)
- New improved error bounds for the linear complementarity problem
- On interior-point warmstarts for linear and combinatorial optimization
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Accurate Identification of Active Constraints
- On the Implementation of a Primal-Dual Interior Point Method
- On the finite convergence of interior-point algorithms for linear programming
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
- Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†
- The Linear Complementarity Problem
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
- Warm start and \(\varepsilon\)-subgradients in a cutting plane scheme for block-angular linear programs
- Warm start of the primal-dual method applied in the cutting-plane scheme
- Warm-start strategies in interior-point methods for linear programming
- Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
Cited in
(2)
This page was built for publication: Active-set prediction for interior point methods using controlled perturbations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263153)
