Convex duality contracts for production-grade mathematical optimization

Deploying mathematical optimization in autonomous production systems requires precise contracts for objects returned by an optimization solver. Unfortunately, conventions on dual solution and infeasibility certificates (rays) vary widely across solvers and classes of problems. This paper presents the theoretical framework used by MathOpt (a domain-specific language developed and used at Google) to unify these notions. We propose an abstract primal-dual pair based on a simplified Fenchel duality scheme that allows for the mechanical derivation of dual problems and associated contracts for all classes of problems currently supported by MathOpt (including those with linear and quadratic objectives plus linear, conic, quadratic, and two-sided linear constraints). We also show how these contracts can improve clarity of complementary-slackness based optimality conditions for certain classes of problems.

Article

Download

View PDF