Open Collections

Conic programming: infeasibility certificates and projective geometry

Banff International Research Station for Mathematical Innovation and Discovery

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, conversely, 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 a joint work with R. Sinn 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 feasibility problem. 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.

Mathematics; Operations research, mathematical programming; Algebraic geometry; Control/Optimization/Operation Research

video/mp4

Author affiliation: Université de Limoges

2019-11-25

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/72394

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/