Fonctionne avec Indico
v3.2.9
The feasible set in a conic program is the intersection of a convex cone with an affine space. In this talk, I will be interested in the feasibility problem of conic programming : How to decide whether an affine space intersects a convex cone or, viceversa, that the intersection is empty? Can we compute certificates of infeasibility? The problem is harder than expected since in (non-linear) conic programming, several types of infeasibility might arise. In the first part I will introduce the problem and discuss the case of LP essentially based on Farkas' Lemma. In the second part, I will discuss a new contribution joint with R. Sinn (https://arxiv.org/abs/1810.11792), in which we revisit the classical facial reduction algorithm from the point of view of projective geometry. This leads us to a homogenization strategy for the general conic program that eliminates the phenomenon of weak infeasibility. For semidefinite programs, this yields infeasibility certificates that can be checked in polynomial time. We also propose a refined type of infeasibility, which we call "stable infeasibility” for which rational infeasibility certificates exist.