A Two-Step Pre-Processing for Semidefinite Programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00347158" target="_blank" >RIV/68407700:21230/20:00347158 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/CDC42340.2020.9304494" target="_blank" >https://doi.org/10.1109/CDC42340.2020.9304494</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/CDC42340.2020.9304494" target="_blank" >10.1109/CDC42340.2020.9304494</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Two-Step Pre-Processing for Semidefinite Programming

Popis výsledku v původním jazyce

In semidefinite programming (SDP), a number of pre-processing techniques have been developed, including procedures based on chordal decomposition, which exploit sparsity in the semidefinite program in order to reduce the dimension of individual constraints, and procedures based on facial reduction, which reduces the dimension of the problem by removing redundant rows and columns. So far, these have been studied in isolation. We show that these techniques are, in fact, complementary. In computational experiments, we show that a two-step pre-processing followed by a standard interior-point method outperforms the interior point method, with or without either of the pre-processing techniques, by a considerable margin.

Název v anglickém jazyce

A Two-Step Pre-Processing for Semidefinite Programming

Popis výsledku anglicky

In semidefinite programming (SDP), a number of pre-processing techniques have been developed, including procedures based on chordal decomposition, which exploit sparsity in the semidefinite program in order to reduce the dimension of individual constraints, and procedures based on facial reduction, which reduces the dimension of the problem by removing redundant rows and columns. So far, these have been studied in isolation. We show that these techniques are, in fact, complementary. In computational experiments, we show that a two-step pre-processing followed by a standard interior-point method outperforms the interior point method, with or without either of the pre-processing techniques, by a considerable margin.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 59th IEEE Conference on Decision and Control

ISBN

978-1-7281-7447-1

ISSN

0743-1546

e-ISSN

2576-2370

Počet stran výsledku

6

Strana od-do

384-389

Název nakladatele

Institute of Electrical and Electronics Engineers, Inc.

Místo vydání

—

Místo konání akce

Jeju Island

Datum konání akce

14. 12. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—