A semismooth Newton based augmented Lagrangian algorithm for Lovász theta SDP problem

Lovász theta SDP problem can often be regarded as semidefinite programming (SDP) relaxation of combinatorial optimization problems in graph theory and appears in various fields. In this paper, we study a semismooth Newton based augmented Lagrangian (Ssnal) algorithm for solving Lovász theta SDP problem. There are three major ingredients in this paper. Firstly, we design efficient implementations of the Ssnal algorithm for solving dual problem of Lovász theta SDP problem. Secondly, the global convergence and local asymptotic superlinear convergence of the Ssnal algorithm are characterized under very mild conditions, in which a semismooth Newton (Ssn) method with superlinear or even quadratic convergence is applied to solve the subproblem. Finally, numerical experiments conducted on random and real data sets demonstrate that the Ssnal algorithm outperforms Sdpnal+ solver. In particular, the Ssnal algorithm can efficiently solve large-scale Lovász theta SDP problems with high accuracy, where the matrix dimension is up to 3000 and the number of equality constraints is up to 27,484.