Operations Research Transactions ›› 2014, Vol. 18 ›› Issue (4): 11-24.

• Original Articles • Previous Articles     Next Articles

Self-concordant exponential kernel function based interior point algorithm for second-order cone optimization

ZHANG Jing1, BAI Yanqin1,*   

  1. 1. College of Science, Shanghai University, Shanghai 200444, China
  • Received:2014-03-12 Online:2014-12-15 Published:2014-12-15

Abstract: This paper presents a primal-dual interior point algorithm for second-order cone optimization based on a new self-concordant (SC) exponential kernel function. By the special relationship between the second derivative and the third derivative of SC exponential kernel function, we use Newton direction to replace the negative gradient direction in solving the central path. Since the SC exponential kernel function does not satisfy the ``Eligible'' property, we use the technique of Newton method minimizing the unconstraint problem with SC object function  in analyzing the complexity bound of algorithm. We estimate the decrease of proximity function which is defined by SC exponential kernel function during the inner iteration. We obtain the complexity bound for large-update methods, which is O(2N \frac{\log 2N}{\varepsilon}), where N is the number of the second-order cones. This result coincides with the complexity bound in the case of linear optimization. Finally, we give some numerical examples to show the efficiency of algorithm.

CLC Number: