A new infeasible-interior-point algorithm for linear programming over symmetric cones

作者：Liu, Chang-he; Shang, You-lin^*; Han, Ping

来源：Acta Mathematicae Applicatae Sinica-English Series, 2017, 33(3): 771-788.

DOI：10.1007/s10255-017-0697-7

• symmetric cone
• Euclidean Jordan algebra
• interior-point methods
• linear programming
• polynomial complexity

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(tau (1), tau (2), eta), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r (1.5)log epsilon (-1)) for the Nesterov-Todd (NT) direction, and O(r (2)log epsilon (-1)) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and epsilon > 0 is the required precision. If starting with a feasible point (x (0), y (0), s (0)) in N(tau (1), tau (2), eta), the complexity bound is for the NT direction, and O(rlog epsilon (-1)) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.

• 出版日期2017-7
• 单位山东科技大学; 河南大学