A primal-dual interior-point algorithm for symmetric optimization based on a new method for finding search directions

Abstract

We introduce an interior-point method for symmetric optimization based on a new method for determining search directions. In order to accomplish this, we use a new equivalent algebraic transformation on the centring equation of the system which characterizes the central path. In this way, we obtain a new class of directions. We analyse a special case of this class, which leads to the new interior-point algorithm mentioned before. Another way to find the search directions is using barriers derived from kernel functions. We show that in our case the corresponding direction cannot be deduced from a usual kernel function. In spite of this fact, we prove the polynomial complexity of the proposed algorithm.

Keywords:

• Symmetric optimization
• interior-point methods
• polynomial complexity

Acknowledgements

We would like to thank the valuable suggestions of the referees and the editor.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

The authors dedicate this paper to Professor Goran Lesaja on the occasion of his 60th birthday. The paper was presented at the Special Section on IPM and Related Topics in honour of Goran Lesaja at the 16th International Conference on Operational Research KOI 2016, Osijek, Croatia.

Additional information

Funding

This work was supported by a grant of Ministry of Research and Innovation, CNCS - UEFISCDI, [project number PN-III-P4-ID-PCE-2016-0190], within PNCDI III.