Finding an interior point in the optimal face of linear programs

DOI10.1007/BF01585180zbMath0803.90089MaRDI QIDQ1319020

Sanjay Mehrotra, Yinyu Ye

Publication date: 3 January 1995

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

strict complementarityoptimal partitioninterior pointprimal-dual methodsoptimal face

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items (41)

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure. ⋮ A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming ⋮ Asymptotic convergence in a generalized predictor-corrector method ⋮ A stable primal-dual approach for linear programming under nondegeneracy assumptions ⋮ Unnamed Item ⋮ Finding a maximal element of a non-negative convex set through its characteristic cone: an application to finding a strictly complementary solution ⋮ ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING ⋮ Fairness and the set of optimal rankings for the linear ordering problem ⋮ A simplified homogeneous and self-dual linear programming algorithm and its implementation ⋮ A lower bound on the number of iterations of long-step primal-dual linear programming algorithms ⋮ A general parametric analysis approach and its implication to sensitivity analysis in interior point methods ⋮ Finite termination of a Newton-type algorithm for a class of affine variational inequality problems ⋮ Facial Reduction and Partial Polyhedrality ⋮ Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs ⋮ A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation ⋮ A new kind of simple kennel function yielding good iteration bounds for primal-dual interior-point methods ⋮ Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization ⋮ Finite termination of a Newton-type algorithm based on a new class of smoothing functions for the affine variational inequality problem ⋮ On the finite convergence of Newton-type methods for \(P_{0}\) affine variational inequalities ⋮ A path to the Arrow-Debreu competitive market equilibrium ⋮ Fortran subroutines for network flow optimization using an interior point algorithm ⋮ Relaxing the strong triadic closure problem for edge strength inference ⋮ POSITIVE SENSITIVITY ANALYSIS IN LINEAR PROGRAMMING ⋮ Interior Point Methods for Nonlinear Optimization ⋮ On the finite convergence of interior-point algorithms for linear programming ⋮ On free variables in interior point methods ⋮ An easy way to teach interior-point methods. ⋮ Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices ⋮ Symbolic implementation of interior point method for linear programming problem ⋮ Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity ⋮ Finite termination of a smoothing-type algorithm for the monotone affine variational inequality problem ⋮ A smoothing Newton algorithm for the LCP with a sufficient matrix that terminates finitely at a maximally complementary solution ⋮ The rankability of weighted data from pairwise comparisons ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization ⋮ Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ The Rankability of Data ⋮ On the finite termination of an entropy function based non-interior continuation method for vertical linear complementarity problems ⋮ Active-set prediction for interior point methods using controlled perturbations

Uses Software

• NETLIB LP Test Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the finite convergence of interior-point algorithms for linear programming
• Convergence behavior of interior-point algorithms
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• A geometric view of parametric linear programming
• Solving symmetric indefinite systems in an interior-point method for linear programming
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Quadratic Convergence in a Primal-Dual Method
• A Low Complexity Interior-Point Algorithm for Linear Programming
• On Finding Primal- and Dual-Optimal Bases
• Implementing the Simplex Method: The Initial Basis
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• A Study of Indicators for Identifying Zero Variables in Interior-Point Methods

This page was built for publication: Finding an interior point in the optimal face of linear programs