Active-set prediction for interior point methods using controlled perturbations
From MaRDI portal
Publication:263153
DOI10.1007/S10589-015-9791-ZzbMATH Open1364.90356arXiv1404.6770OpenAlexW2079232806MaRDI QIDQ263153FDOQ263153
Publication date: 4 April 2016
Published in: Computational Optimization and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1404.6770
Cites Work
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Implementation of a Primal-Dual Interior Point Method
- Title not available (Why is that?)
- Title not available (Why is that?)
- Interior point methods 25 years later
- A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- Computational results of an interior point algorithm for large scale linear programming
- Modified barrier functions (theory and methods)
- Warm start of the primal-dual method applied in the cutting-plane scheme
- Warm start and \(\varepsilon\)-subgradients in a cutting plane scheme for block-angular linear programs
- Degeneracy in interior point methods for linear programming: A survey
- Finding an interior point in the optimal face of linear programs
- New improved error bounds for the linear complementarity problem
- Error bounds in mathematical programming
- A numerical study of limited memory BFGS methods
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
- An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming
- Linear and integer programming: Theory and practice.
- Warm-start strategies in interior-point methods for linear programming
- On Interior-Point Warmstarts for Linear and Combinatorial Optimization
- The Linear Complementarity Problem
- A New Unblocking Technique to Warmstart Interior Point Methods Based on Sensitivity Analysis
- Active Set Identification in Nonlinear Programming
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†
- On the Accurate Identification of Active Constraints
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- An Interior Point Column Generation Method for Linear Programming Using Shifted Barriers
- Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
- Title not available (Why is that?)
- A two-sided relaxation scheme for Mathematical Programs with Equilibrium Constraints
- Existence, uniqueness, and convergence of the regularized primal-dual central path
- An active-set strategy in an interior point method for linear programming
- On the finite convergence of interior-point algorithms for linear programming
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
Cited In (2)
Uses Software
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)
