An entire space polynomial-time algorithm for linear programming

DOI10.1007/s10898-013-0048-zzbMath1318.90049OpenAlexW2037428873MaRDI QIDQ2442633

Da-Gang Tian

Publication date: 1 April 2014

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-013-0048-z

zbMATH Keywords

linear programmingpolynomial-time algorithmpenalty functionself-concordanceentire space

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (2)

A wide neighborhood infeasible-interior-point method with arc-search for linear programming ⋮ An exterior point polynomial-time algorithm for convex quadratic programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the convergence of the exponential multiplier method for convex programming
• Numerical experiments with an interior-exterior point method for nonlinear programming
• A new polynomial-time algorithm for linear programming
• Primal-dual nonlinear rescaling method for convex optimization
• Recursive construction of optimal self-concordant barriers for homogeneous cones
• A polynomial-time algorithm, based on Newton's method, for linear programming
• The ellipsoid method and its consequences in combinatorial optimization
• Modified barrier functions (theory and methods)
• A primal-dual infeasible-interior-point algorithm for linear programming
• A deep cut ellipsoid algorithm for convex programming: Theory and applications
• Nonlinear rescaling and proximal-like methods in convex optimization
• Nonlinear rescaling vs. smoothing technique in convex optimization
• A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems
• Primal and dual convergence of a proximal point exponential penalty method for linear programming
• On the entropic perturbation and exponential penalty methods for linear programming
• A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem
• Self-concordant functions for optimization on smooth manifolds
• 1.5-\(Q\)-superlinear convergence of an exterior-point method for constrained optimization
• New self-concordant barrier for the hypercube
• Primal-dual nonlinear rescaling method with dynamic scaling parameter update
• The complexity of self-regular proximity based infeasible IPMs
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function
• A Primal-Dual Exterior Point Method for Nonlinear Optimization
• Khachiyan’s algorithm for linear programming
• A Globally and Locally Superlinearly Convergent Non--Interior-Point Algorithm for P₀LCPs
• The interior-point revolution in optimization: History, recent developments, and lasting consequences
• SimplifiedO(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps
• Primal–dual exterior point method for convex optimization
• A Full-Newton Step O(n) Infeasible Interior-Point Algorithm for Linear Optimization
• Convex Analysis
• Complexity of a noninterior path-following method for the linear complementarity problem

This page was built for publication: An entire space polynomial-time algorithm for linear programming