In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. | Yugoslav Journal of Operations Research 25 (2015) Number 2, 233-250 DOI: A POLYNOMIAL-TIME ALGORITHM FOR LINEAR OPTIMIZATION BASED ON A NEW KERNEL FUNCTION WITH TRIGONOMETRIC BARRIER TERM B. KHEIRFAM1, M. MOSLEMI2 Department of Mathematics Azarbaijan Shahid Madani University Tabriz, Iran Received: November 2013 / Accepted: March 2014 Abstract: In this paper, we propose a large-update interior-point algorithm for linear optimization based on a new kernel function. New search directions and proximity measure are defined based on this kernel function. We show that if a strictly feasible starting point is available, then the new algorithm has ( log ) iteration complexity. Keywords: Kernel function, Interior-point algorithm, Linear optimization, Polynomial complexity, Primal-dual method. МSC: 90C05, 90C51. 1. INTRODUCTION In this paper, we consider linear optimization (LO) problem in the standard form: min . . = , ( ) ≥ 0, × where ∈ is a real problem of (P) is given by × matrix of rank 1 Corresponding author: 2 , and , ∈ , ∈ . The dual 234 , / A Polynomial-Time Algorithm max . . + = , ( ) ≥ 0, with ∈ and ∈ . In 1984, Karmarkar [12] proposed a polynomial-time algorithm, the so-called interior-point method (IPM) for linear optimization (LO). This method and its variants are frequently extended for solving wide classes of optimization problems, for example, quadratic optimization problem (QOP), semidefinite optimization (SDO) problem, second-order cone optimization (SOCO) problem, ∗ ( ) linear complementarity problems (LCPs), and convex optimization problem (CP). IPM is the most efficient method from computational point of view. Also, its promising performance in solving large-scale linear programming problems caused it to be used in practical issues. Usually, if parameter in this method is a constant, which is independent of the dimension of the problem, then the .
