1 Complexity Analysis of the Primal-Dual Interior Point Method for Second-order Cone Optimization Problem

By Bo Kyung Choi and Gue Myung Lee.

The purpose of this talk is to extend the Bai et al.’s complexity results for a linear program to a second-order cone optimization (SOCO) problem. We define a proximity function for SOCO by a kernel function introduced by Bai et al. [SIAM J. Optim., 13(2003), 766-782] and using the proximity function, we formulate an algorithm for a large-update primal-dual interiorpoint method (IPM) for SOCO and give its complexity analysis, and then we show that the worst-case iteration bound for our IPM is O(\sqrt{N} log N log \frac{N}{ϵ}).