Polynomiality of infeasible-interior-point algorithms for linear programming
From MaRDI portal
Publication:1340070
DOI10.1007/BF01582216zbMath0828.90086OpenAlexW1985332751MaRDI QIDQ1340070
Publication date: 11 December 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582216
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)
Related Items (56)
An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization ⋮ An infeasible interior-point algorithm for linear optimization over Cartesian symmetric cones ⋮ On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems ⋮ A new infeasible interior-point algorithm with full step for linear optimization based on a simple function ⋮ A wide neighborhood infeasible-interior-point method with arc-search for linear programming ⋮ A predictor-corrector infeasible-interior-point algorithm for linear programming ⋮ The practical behavior of the homogeneous self-dual formulations in interior point methods ⋮ Infeasible interior-point methods for linear optimization based on large neighborhood ⋮ A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ A generalized homogeneous and self-dual algorithm for linear programming ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ A modified and simplified full Nesterov-Todd step \(\mathcal {O}(N)\) infeasible interior-point method for second-order cone optimization ⋮ A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems ⋮ Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs ⋮ An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution ⋮ An infeasible-interior-point algorithm using projections onto a convex set ⋮ An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence ⋮ New infeasible interior-point algorithm based on monomial method ⋮ A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming ⋮ A primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils ⋮ A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems ⋮ A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems ⋮ Design of continuous-time recurrent neural networks with piecewise-linear activation function for generation of prescribed sequences of bipolar vectors ⋮ An adaptive infeasible interior-point algorithm with full Nesterov-Todd step for semidefinite optimization ⋮ Estimating the probability that a given vector is in the convex hull of a random sample ⋮ Full Nesterov-Todd step infeasible interior-point method for symmetric optimization ⋮ A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming ⋮ A modified infeasible-interior-point algorithm for linear optimization problems ⋮ New complexity analysis of IIPMs for linear optimization based on a specific self-regular function ⋮ A new class of infeasible interior-point algorithm for linear complementarity problem ⋮ An infeasible interior-point algorithm with full-Newton step for linear optimization ⋮ Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming ⋮ An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization ⋮ Convergence of the homotopy path for a full-Newton step infeasible interior-point method ⋮ A full-Newton step infeasible interior-point algorithm based on darvay directions for linear optimization ⋮ SimplifiedO(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps ⋮ Improved full-Newton step \(O(nL)\) infeasible interior-point method for linear optimization ⋮ Primal-Dual Interior-Point Methods for Domain-Driven Formulations ⋮ The complexity of self-regular proximity based infeasible IPMs ⋮ A Class of Infeasible Interior Point Algorithms for Convex Quadratic Programming ⋮ A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization ⋮ Simplified infeasible interior-point algorithm for linear optimization based on a simple function ⋮ An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem ⋮ A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems ⋮ A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems ⋮ A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step ⋮ New complexity analysis of full Nesterov-Todd step infeasible interior point method for second-order cone optimization ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming ⋮ Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗ ⋮ A MODIFIED FULL-NEWTON STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR LINEAR OPTIMIZATION ⋮ Interior-point methods for linear programming: a review
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Feasibility issues in a primal-dual interior-point method for linear programming
- Computational experience with a primal-dual interior point method for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- A polynomial-time algorithm for a class of linear complementarity problems
- A primal-dual infeasible-interior-point algorithm for linear programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
- An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
This page was built for publication: Polynomiality of infeasible-interior-point algorithms for linear programming
