Loraine – an interior-point solver for low-rank semidefinite programming

Soodeh Habibi; Michal Kocvara; Michael Stingl

doi:10.1080/10556788.2023.2250522

Loraine – an interior-point solver for low-rank semidefinite programming

Soodeh Habibi, Michal Kocvara^*, Michael Stingl

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Downloads (Pure)

Abstract

The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.

Original language	English
Article number	2250522
Number of pages	31
Journal	Optimization Methods and Software
Early online date	23 Oct 2023
DOIs	https://doi.org/10.1080/10556788.2023.2250522
Publication status	E-pub ahead of print - 23 Oct 2023

Bibliographical note

Funding:
This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA). The second author has been partly supported by the Czech Science Foundation through project No. 22-15524S.

Keywords

Semidefinite optimization
interior-point methods
preconditioned conjugate gradients
truss topology optimization
MAXCUT problem
Lasserre relaxations
sensor network localization

Access to Document

10.1080/10556788.2023.2250522Licence: Creative Commons: Attribution (CC BY)

HabibiSS2023LoraineFinal published version, 3.25 MBLicence: Creative Commons: Attribution (CC BY)

https://www.tandfonline.com/doi/full/10.1080/10556788.2023.2250522Licence: Creative Commons: Attribution (CC BY)

H2020_ITN_POEMA
Kocvara, M.
European Commission
1/01/19 → 30/06/23
Project: EU

Cite this

@article{c86ad4bee1df4e959f4c7b94bddfd7ab,

title = "Loraine – an interior-point solver for low-rank semidefinite programming",

abstract = "The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.",

keywords = "Semidefinite optimization, interior-point methods, preconditioned conjugate gradients, truss topology optimization, MAXCUT problem, Lasserre relaxations, sensor network localization",

author = "Soodeh Habibi and Michal Kocvara and Michael Stingl",

note = "Funding: This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions, grant agreement 813211 (POEMA). The second author has been partly supported by the Czech Science Foundation through project No. 22-15524S.",

year = "2023",

month = oct,

day = "23",

doi = "10.1080/10556788.2023.2250522",

language = "English",

journal = "Optimization Methods and Software",

issn = "1055-6788",

publisher = "Taylor & Francis",

}

TY - JOUR

T1 - Loraine – an interior-point solver for low-rank semidefinite programming

AU - Habibi, Soodeh

AU - Kocvara, Michal

AU - Stingl, Michael

N1 - Funding: This work has been supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA). The second author has been partly supported by the Czech Science Foundation through project No. 22-15524S.

PY - 2023/10/23

Y1 - 2023/10/23

N2 - The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.

AB - The aim of this paper is to introduce a new code for the solution of large-and-sparse linear semidefinite programs (SDPs) with low-rank solutions or solutions with few outlying eigenvalues, and/or problems with low-rank data. We propose to use a preconditioned conjugate gradient method within an interior-point SDP algorithm and an efficient preconditioner fully utilizing the low-rank information. The efficiency is demonstrated by numerical experiments using the truss topology optimization problems, Lasserre relaxations of the MAXCUT problems and the sensor network localization problems.

KW - Semidefinite optimization

KW - interior-point methods

KW - preconditioned conjugate gradients

KW - truss topology optimization

KW - MAXCUT problem

KW - Lasserre relaxations

KW - sensor network localization

U2 - 10.1080/10556788.2023.2250522

DO - 10.1080/10556788.2023.2250522

M3 - Article

SN - 1055-6788

JO - Optimization Methods and Software

JF - Optimization Methods and Software

M1 - 2250522

ER -

Loraine – an interior-point solver for low-rank semidefinite programming

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Projects

H2020_ITN_POEMA

Cite this