Consider the primal problem of minimizing the sum of two closed proper convex functions \(f\) and \(g\). If the relative interiors of the domains of \(f\) and \(g\) intersect, then the primal problem and its corresponding Fenchel dual satisfy strong duality. When these relative interiors fail to intersect, pathologies and numerical difficulties may occur. In this paper, we propose a facial reduction algorithm that outputs minimal faces of \({\rm dom\,} f\) and \({\rm dom\,} g\) containing the feasible region so that we may reformulate the primal problem in such a way that Slater’s condition is ensured and strong duality is always satisfied. More generally, given two nonempty convex sets \(C_1\), \(C_2\), our facial reduction algorithm either finds minimal faces of \(C_1\) and \(C_2\) containing the intersection \(C_1 \cap C_2\) or certifies that the intersection is empty. Along the way, we extend the notion of niceness from convex cones to general convex set and consider a suitable notion of niceness for convex functions called vertical niceness. Under these niceness assumptions, Fenchel duals arising from the application of our facial reduction algorithm have simplified expressions. Finally, inspired by Ramana’s extended dual for semidefinite programming, we then use these tools to develop extended duals for general convex problems.
Facial reduction for nice (and non-nice) convex programs
\(\)