Back to search

University of Birmingham

Algorithms and Software for Structured Semidefinite Optimization

Abstract

dc:description.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.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Habibi, Soodeh

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Dc Identifier Grantnumber
POEMA project

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Habibi, Soodeh. Algorithms and Software for Structured Semidefinite Optimization. d_ph thesis, University of Birmingham, 2024.