A polynomial-time algorithm for linear optimization based on a new class of kernel functions

DOI10.1016/j.cam.2008.05.027zbMath1162.65031OpenAlexW2095236018MaRDI QIDQ1002187

I. Ivanov, J. B. M. Melissen, M. El Ghami, Trond Steihaug, Cornelis Roos

Publication date: 25 February 2009

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cam.2008.05.027

zbMATH Keywords

kernel functionlinear optimizationpolynomial complexitypolynomial algorithmslarge-update methodsmall-update methodprimal-dual interior-point algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Interior-point methods (90C51)

Related Items

An infeasible interior-point algorithm with full-Newton steps for \(P_*(\kappa)\) horizontal linear complementarity problems based on a kernel function, Interior-point methods for symmetric optimization based on a class of non-coercive kernel functions, The accuracy of interior-point methods based on kernel functions, Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier, Complexity analysis of interior point methods for linear programming based on a parameterized kernel function, A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm, Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions, A Numerical Implementation of an Interior Point Methods for Linear Programming Based on a New Kernel Function, A new kind of simple kennel function yielding good iteration bounds for primal-dual interior-point methods, Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, New complexity analysis of interior-point methods for the Cartesian \(P_\ast ({\kappa})\)-SCLCP, Complexity of interior point methods for a class of linear complementarity problems using a kernel function with trigonometric growth term, A PRIMAL-DUAL INTERIOR-POINT ALGORITHM BASED ON A NEW KERNEL FUNCTION, A generic kernel function for interior point methods, An interior-point algorithm for linear optimization based on a new barrier function, Polynomial interior-point algorithms for \(P_*(\kappa )\) horizontal linear complementarity problem, An interior point method for \(P_*(\kappa)\)-horizontal linear complementarity problem based on a new proximity function, An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a finite exponential-trigonometric barrier term, Research Article: On Extending Primal-Dual Interior-Point Method for Linear Optimization to Convex Quadratic Symmetric Cone Optimization

Uses Software

• McIPM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• On the Implementation of a Primal-Dual Interior Point Method
• Path-Following Methods for Linear Programming
• A primal‐dual interior-point method for linear optimization based on a new proximity function
• A New Efficient Large-Update Primal-Dual Interior-Point Method Based on a Finite Barrier
• A Comparative Study of Kernel Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization
• Linear programming. Foundations and extensions