A Duality-Guided Proximal Splitting Method for Robust Constrained Best Approximation via Convex Semi-Definite Program Reformulations

Abstract In this paper, we study a broad class of constrained best approximation problems in the face of data uncertainty. Adopting the deterministic robust optimisation framework, we model uncertainty using spectrahedral sets, which unify many convex uncertainty models commonly employed in practice. In this setting, the robust best approximation problem requires the solution to satisfy all constraints for every parameter in the prescribed spectrahedral sets, giving rise to a computationally difficult infinite-dimensional problem that may also involve infinitely many constraints. To address this difficulty, we employ convex optimisation duality and semi-definite optimisation techniques, and a variable transformation to reformulate the Lagrangian dual of the robust best approximation problem into a finite-dimensional convex semi-definite program. This enables the best approximation to be found from the solution of the dual problem via a solution recovery formula. By further reformulation of the dual to a convex composite unconstrained optimisation problem using convex conjugation techniques, we present a readily implementable first-order primal-dual proximal splitting method to compute the solution to the robust best approximation problem. Finally, we present the results of numerical experiments to illustrate our proposed approach.