1–2 Jul 2025
CERN
Europe/Zurich timezone

Extended Precision in Convex Optimisation

1 Jul 2025, 16:45
30m
40/S2-A01 – Salle Anderson (CERN)

40/S2-A01 – Salle Anderson

CERN

Speakers

David Herrera-Marti Eric Guthmuller Jerome Fereyre

Description

Semidefinite Programming is a matrix-form generalisation of linear programming, and is typically tackled using Interior Point Methods. These methods are of iterative nature and at each step, a matrix inversion needs to be performed. For small or sparse matrices, direct methods like sparse Cholesky factorisation are used. For dense matrices of larger size, like the ones that arise in convex relaxations of combinatorial problems, Krylov methods like Conjugate Gradient seem a better approach. We show how, as the dual-primal central trajectory approaches the feasible set and the tentative solution becomes rank-deficient, increasing the precision accelerates the convergence (in terms of number of CG iterations).

Presentation materials

There are no materials yet.