Session II.2 - Continuous Optimization - Semi-plenary talk
Thursday, June 15, 17:30 ~ 18:30
Algorithms for large scale semidefinite programming
Kim-Chuan Toh
National University of Singapore, Singapore - This email address is being protected from spambots. You need JavaScript enabled to view it.
Semidefinite programming (SDP) and its generalizations have found extensive applications in various domains, including combinatorial and polynomial optimization, covariance matrix estimation, and Euclidean metric embedding. This presentation introduces some algorithms developed for solving large-scale SDP problems. Specifically, we consider two types of SDPs: Type-2 SDPs with moderate variable dimension but a large number of affine constraints, and Type-3 SDPs with large variable dimension but a moderate number of affine constraints. The first part of the talk focuses on Type-2 SDPs. We present algorithmic advancements based on the proximal-point or augmented Lagrangian framework. In particular, the development and implementation of an augmented Lagrangian-based method called SDPNAL+. This method demonstrates promising results in solving SDPs of this type efficiently. In the second part, we explore the design and implementation of a smoothing Newton method for solving Type-2 SDPs. This method leverages the KKT residual mapping and provides an effective approach to address the aforementioned class of SDPs under suitable nondegenercay conditions. Lastly, we delve into recent progress in designing and implementing a rank-adaptive feasible method for Type-3 SDPs. By employing the low-rank factorization model of the underlying SDP, we demonstrate the promising potential of the new method in solving large-scale SDP problems of this category.
Joint work with Ling Liang (National University of Singapore), Tianyun Tang (National University of Singapore), Defeng Sun (Hong Kong Polytechnic University) and Xinyuan Zhao (Beijing University of Technology).