Worst case bounds on facial reduction for conic programming

Abstract

Conic linear programming is a powerful modelling technique with many applications in engineering, planning, statistics and many others. Typically, a conic linear program (CLP) is expressed as the task of minimizing some linear function subject to linear equations and conic constraints. Sometimes, however, the CLPs can exhibit nasty theoretical behavior. This is where regularization techniques come to play. They fix ill-behaved problems and put them in a shape that solvers can successfully handle them. In this note, we present a brief account of Facial Reduction Algorithms and discuss worst case bounds for their termination.