A relaxed-certificate facial reduction algorithm based on subspace intersection

A “facial reduction”-like regularization algorithm is established for conic optimization problems by relaxing requirements on the reduction certificates. It requires only a linear number of reduction certificates from a constant time-solvable auxiliary problem, but is challenged by representational issues of the exposed reductions. A condition for representability is presented, analyzed for Cartesian product cones, and shown satisfiable for all exposed reductions of a single second-order cone. Should the representational condition fail at any iteration, a partially regularized problem is still obtained. Work on representing the exposed reductions, i.e., subspace intersections of conic sets, is ongoing.

Article

Download

View PDF