Algorithms and Software for Structured Semidefinite Optimization

Habibi, Soodeh (2024). Algorithms and Software for Structured Semidefinite Optimization. University of Birmingham. Ph.D.

Preview

Habibi2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (4MB) | Preview

Abstract

The goal of this thesis is to find solutions to large-and-sparse linear Semidefinite Programs (SDPs) with low-rank solutions and/or low-rank data, and we introduce a new code for the solution of these problems. We are investigating an Interior-Point (IP) approach to solve these problems. A general bottleneck of IP methods is assembling the so-called Schur complement equation and finding a solution for it, in which the matrix becomes increasingly ill-conditioned as the interior-point method makes progress toward the solution. To tackle this challenge, instead of the direct solver (Cholesky factorization), we suggest using a Preconditioned Conjugate Gradient (PCG) method within an interior-point semidefinite program algorithm and introduces a novel and efficient preconditioner that fully utilizes the low-rank information. Efficient preconditioners allow PCG to converge to an approximate solution of the linear equation in a few iterations, independent of the ill-conditioning of the Schur complement matrix. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems of growing dimension which is formulated as large-scale SDP with the low-rank solution and the sensor network localization problems. The numerical re-sults demonstrate that our preconditioner is working better than preconditioners recently proposed by Zhang and Lavaei, based on a similar idea. Also, our Matlab implementation outperforms MOSEK and other available IP-based software. Furthermore, we use this IP approach to solve linear SDPs arising from higher-order Lasserre relaxations of Unconstrained Binary Quadratic optimization Problems (UBQPs). For these problems, the preconditioner makes use of the low-rank structure of the solution of the relaxations. Thus, we re-write the moment relaxations and use an l1-penalty approach within the IP solver to deal with the arising linear equality constraints.
The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.
In addition to this study, we look at how Polynomial Optimization techniques can be applied to Geometric Modeling problems. We discuss some examples of geometric modeling problems, and how they can be solved utilizing polynomial optimization tools. At the end, we report and analyze some experimental findings.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):