We revisit facial reduction from the point of view of projective geometry. This leads us to a homogenization strategy in conic programming that eliminates the phenomenon of weak infeasibility. For semidefinite programs (and others), this yields infeasibility certificates that can be checked in polynomial time. Furthermore, we propose a refined type of infeasibility, which we call stably infeasible, for which rational infeasibility certificates exist and that can be distinguished from other infeasibility types by our homogenization.
Conic programming: infeasibility certificates and projective geometry
Naldi S
;
2021-01-01
Abstract
We revisit facial reduction from the point of view of projective geometry. This leads us to a homogenization strategy in conic programming that eliminates the phenomenon of weak infeasibility. For semidefinite programs (and others), this yields infeasibility certificates that can be checked in polynomial time. Furthermore, we propose a refined type of infeasibility, which we call stably infeasible, for which rational infeasibility certificates exist and that can be distinguished from other infeasibility types by our homogenization.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I metadati presenti in IRIS UNICA sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono protetti da diritto d'autore, salvo diversa indicazione.
