Abstract:

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming (SOCP) by using the Alizadeh--Haeberly--Overton (AHO) search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an ε-approximate solution of an SOCP in at most O(\sqrt{n}\ln(ε₀/ε)) iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

Key words: Second-order cone programming, infeasible-interior-point algorithm,
predictor-corrector algorithm, global convergence