Narrow Results

We present a full-Newton step infeasible interior-point algorithm based on a new search direction. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. We show that the algorithm converges and finds an approximate solution in a polynomial time complexity. A numerical study is done for its numerical performance.

This paper deals with an infeasible interior-point algorithm with full-Newton step for linear optimization based on a kernel function, which is an extension of the work of the first author and coworkers (J. Math. Model Algorithms (2013); DOI 10.1007/s10852-013-9227-7). The main iteration of the algorithm consists of a feasibility step and several centrality steps. The centrality step is based on Darvay's direction, while we used a kernel function in the algorithm to induce the feasibility step. For the kernel function, the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods.

In this paper, based on the transformation $\psi (\frac{xs}{\mu })=\psi (\sqrt{\frac{xs}{\mu }})$ introduced by Darvay and Takács [New method for determining search directions for interior-point algorithms in linear optimization, Optim. Lett.12(5) (2018) 1099–1116], we present a full-Newton step interior-point method for linear optimization. They consider the case $\psi (t)=t^2$. Here, we extend this to the case $\psi (t)=t^q(q\ge 2)$ to obtain our search directions. We show that the iterates lie in the neighborhood of the local quadratic convergence of the proximity measure. Finally, the polynomial complexity of the proposed algorithm is proved.