Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function

DOI10.1016/J.AMC.2005.09.079MaRDI QIDQ2493765zbMATH OpenOpenAlexFDO

Authors Keyvan Amini, M. Reza Peyghami

Publication date 16 June 2006

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2005.09.079

zbMATH Keywords

kernel functionlarge update methodlinear optimizationpolynomial complexityprimal-dual interior point methodproximity function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Linear programming (90C05) Interior-point methods (90C51)

Review text

The authors suggest and study a class of interior-point methods for solving the linear optimization problem \(\min \{ c^T x: Ax=b, x \geq 0 \}\). Estimates for the complexity of the methods are derived.

Recommendations

• Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function
• An interior-point algorithm for linear optimization based on a new kernel function
• Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term
• A polynomial-time algorithm for linear optimization based on a new class of kernel functions
• Complexity analysis of interior point methods for linear programming based on a parameterized kernel function

Cites work

• A new and efficient large-update interior-point method for linear optimization
• A new class of polynomial primal-dual methods for linear and semidefinite optimization
• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 3972641 (Why is no real title available?)
• scientific article; zbMATH DE number 4126998 (Why is no real title available?)
• scientific article; zbMATH DE number 1017028 (Why is no real title available?)
• scientific article; zbMATH DE number 1047679 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 1862745 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Self-regular functions and new search directions for linear and semidefinite optimization

Cited in

(7)

• A class of large-update and small-update primal-dual interior-point algorithms for linear optimization
• A generic kernel function for interior point methods
• Interior point methods with self-regular proximities
• A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods
• A Complexity Analysis for Interior-Point Algorithms Based on Karmarkar’s Potential Function
• Sharper analysis of upper bound for the iteration complexity of an interior-point method using primal-dual full-Newton step algorithm
• Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

This page was built for publication: Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2493765)