A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function

Abstract

In this paper, we investigate the properties of a simple locally kernel function. As an application, we present a full-step interior-point algorithm for second-order cone optimization (SOCO). The algorithm uses the simple locally kernel function to determine the search direction and define the neighbourhood of central path. The full step used in the algorithm has local quadratic convergence property according to the proximity function which is constructed by the simple locally kernel function. We derive the iteration complexity for the algorithm and obtain the best-known iteration bound for SOCO.

Keywords:

• second-order cone optimization
• interior-point algorithm
• complexity analysis
• locally kernel function

AMS Subject Classifications:

• 17C99
• 90C25
• 90C51

Acknowledgements

The author kindly acknowledge the help of Professor Tamas Terlaky and the anonymous referees in improving the readability of the paper. Zhang's research is supported by the grant from National Natural Science Foundation of China No. 11171373. Bai's research is supported by the grant from National Natural Science Foundation of China No.11071158 and Key Disciplines of Shanghai Municipality Discipline Project No: S30104. Xu's research is supported by the grant from Natural Science Foundation of Zhejiang Province No. LQ12A01024.