polynomial complexity

In this paper, we present a second-order corrector infeasibleinterior-point method for linear optimization in a largeneighborhood of the central path. The innovation of our method is tocalculate the predictor directions using a specific kernel functioninstead of the logarithmic barrier function. We decompose thepredictor direction induced by the kernel function to two orthogonaldirections of the corresponding to the negative and positivecomponent of the right-hand side vector of the centering equation.The method then considers the new point as a linear combination ofthese directions along with a second-order corrector direction. Theconvergence analysis of the proposed method is investigated and itis proved that the complexity bound is Ο(n5/4 log ε-1).

An infeasible interior-point algorithm for mixed symmetric cone linear complementarity problems is proposed. Using the machinery of Euclidean Jordan algebras and Nesterov-Todd search direction, the convergence analysis of the algorithm is shown and proved. Moreover, we obtain a polynomial time complexity bound which matches the currently best known iteration bound for infeasible interior-point methods.

An infeasible interior-point algorithm for solving the $P_*$-matrix linear complementarity problem based on a kernel function with trigonometric barrier term is analyzed. Each (main) iteration of the algorithm consists of a feasibility step and several centrality steps, whose feasibility step is induced by a trigonometric kernel function. The complexity result coincides with the best result for infeasible interior-point methods for $P_*$-matrix linear complementarity problem.

We present an improved version of a full Nesterov-Todd step infeasible interior-point method for linear complementarity problem over symmetric cone (Bull. Iranian Math. Soc., 40(3), 541-564, (2014)). In the earlier version, each iteration consisted of one so-called feasibility step and a few -at most three - centering steps. Here, each iteration consists of only a feasibility step. Thus, the new algorithm demands less work in each iteration and admits a simple analysis of complexity bound. The complexity result coincides with the best-known iteration bound for infeasible interior-point methods.

In this paper, we propose a feasible interior-point algorithm for mixed symmetric cone linear complementarity problems which are a general class of complementarity problems. The symmetrization of the search directions used in this paper is based on Nesterov and Todd scaling scheme. By using Euclidean Jordan algebra, we prove the convergence analysis of the proposed algorithm and show that the complexity bound of the algorithm matches the currently best known iteration bound for feasible interior-point methods.

We present a modified version of the infeasible-interior- We present a modified version of the infeasible-interior-point algorithm for monotone linear complementary problems introduced by Mansouri et al. (Nonlinear Anal. Real World Appl. 12(2011) 545--561). Each main step of the algorithm consists of a feasibility step and several centering steps. We use a different feasibility step, which targets at the $mu^+$-center. It results a better iteration bound.