Primal–dual interior-point method for linear optimization based on a kernel function with trigonometric growth term

Abstract

In this paper, we propose a large-update primal–dual interior-point algorithm for linear optimization problems based on a new kernel function with a trigonometric growth term. By simple analysis, we prove that in the large neighbourhood of the central path, the worst case iteration complexity of the new algorithm is bounded above by , which matches the currently best known iteration bound for large-update methods. Moreover, we show that, most of the so far proposed kernel functions can be rewritten as a kernel function with trigonometric growth term. Finally, numerical experiments on some test problems confirm that the new kernel function is well promising in practice in comparison with some existing kernel functions in the literature.

Keywords:

• Kernel function
• linear optimization
• trigonometric growth term
• primal–dual interior-point methods
• Large-update methods

Acknowledgements

The authors would like to thank Professors Cornelis Roos and Tamas Terlaky for their valuable comments and suggestions on the earliest draft of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

S. Fathi-Hafshejani http://orcid.org/0000-0003-1855-2287

Additional information

Funding

The authors would also like to thank the Research Council of K.N. Toosi University of Technology, Shahrekord University, York University and Shiraz University of Technology for supporting the work.