A Polynomial-Time Algorithm for Linear Optimization Based on a New Kernel Function With Trigonometric Barrier Term


B. Kheirfam, M. Moslemi




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 $O(n^{\frac{3}{4}} \log \frac{n}{\epsilon})$ iteration complexity.