A self-concordant exponential kernel function for primal-dual interior-point algorithm

作者：Bai, Yan-Qin^*; Zhang, Jing; Ma, Peng-Fei; Zhang, Lian-Sheng

来源：Optimization, 2014, 63(6): 931-953.

DOI：10.1080/02331934.2013.845777

• linear optimization problem
• interior-point methods
• self-concordant function
• 90C05
• 90C51

Self-concordant (SC) function is essential to analyzing primal-dual interior-point methods with polynomial-time complexity bound. In this paper, we introduce an exponential kernel function and prove that it is an SC function. Furthermore, we investigate its properties and find it is neither an eligible kernel function nor an SC barrier function. Nevertheless, based on this SC exponential kernel function, we present primal-dual interior-point algorithm for solving linear optimization problems. We analyse the algorithm and derive the complexity bound for large-update methods, which coincides with that of the algorithm based on the logarithmic function. Finally, the comparative numerical results are reported.

• 出版日期2014-6-3
• 单位上海大学