Interior-point algorithms for semidefinite programming based on a nonlinear formulation (Q1610312)

Conventional interior-point algorithms involving costly Newton iterations are generally not suitable for solving large-scale SemiDefinite Programming (SDP) problems, such as the ones arising when relaxing combinatorial optimization problems. Motivated by this observation, the authors of this very well written paper propose alternative SDP algorithms. The rationale behind their approach consists in converting a general linear SDP problem with matrix constraints into a NonLinear Programming (NLP) problem with scalar positive constraints and scalar inequality constraints. Properties of the nonlinear transformation are invoked to design a globally convergent first-order (gradient-based) log-barrier algorithm for solving the NLP problem. A second-order (Hessian-based) potential reduction interior-point algorithm is also described. The paper features an interesting discussion on pros and cons of both algorithms (and more generally, on first-order and second-order interior-point schemes), as well as computational results. The main conclusion is that the first-order algorithm is more suitable for solving large-scale SDP problems, especially when the number of constraints is significantly greater than the number of variables.