Convex Relaxations of Fixed-point Iterations and their Subgradients

Speaker: Neil Kichler, RWTH Aachen

Abstract

Deterministic global optimization typically uses convex relaxations and their subgradients for lower-bounding the solution space. Embedded fixed-point iterations are challenging to incorporate into the optimization, as they are not representable as factorable functions. Existing direct propagation techniques are akin to “differentiating through the solver” in AD. Yet from AD we know to prefer the use of “differentiation after solving” thanks to the implicit function theorem. Are similar ideas possible to exploit in the context of convex relaxations? We show that it is possible to transfer this idea into the realm of convex relaxations. By exploring new “converge then relax” algorithms, we observe orders of magnitude speedup on simple examples over existing methods with equal or tighter convex relaxations of the fixed points. A new contraction mapping theorem establishes the applicability of these methods. Furthermore, it raises questions on the applicability of AD and the implicit function theorem to obtain desirable subgradients. Similar ideas may be used in the context of convex relaxations of implicit functions or even parameterized differential equations.