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

The authors deal with primal-dual interior-point methods for solving the standard linear optimization problem \[ \text{minimize }c^T x\text{ subject to }Ax= b,\;x\geq 0 \] and its dual \[ \text{maximize }b^T y\text{ subject to }A^T y+ s= c,\;s\geq 0, \] where \(x,s\in \mathbb{R}^n\), \(y\in\mathbb{R}^m\). New polynomial algorithms of this class are presented. The algorithms are based on a new class of kernel functions. The proposed kernel functions have a finite value at the boundary of the feasible region. The authors investigate properties of such a class of kernel functions and show favorable polynomial complexity of the interior-point algorithms based on them.