Machine Learning for Real-Time Constrained Optimization

Optimization problems subject to hard constraints are common in time-critical applications such as autonomous driving, communications, networking, and power grid operation. However, existing iterative solvers often face difficulties in solving these problems in real-time. In this talk, we advocate a machine learning approach — to employ NN’s approximation capability to learn the input-solution mapping of a problem and then pass new input through the NN to obtain a quality solution, orders of magnitude faster than iterative solvers. To date, the approach has achieved promising empirical performance and exciting theoretical development. A fundamental issue, however, is to ensure NN solution feasibility with respect to the hard constraints, which is non-trivial due to inherent NN prediction errors. To this end, we present two approaches, predict-and-reconstruct and homeomorphic projection, to ensure NN solution strictly satisfies the equality and inequality constraints, respectively. In particular, homeomorphic projection is a low-complexity scheme to guarantee NN solution feasibility for optimization over any set homeomorphic to a unit ball, covering all compact convex sets and certain classes of nonconvex sets. The idea is to (i) learn a minimum distortion homeomorphic mapping between the constraint set and a unit ball using an invertible NN (INN), and then (ii) perform a simple bisection operation concerning the unit ball so that the INN-mapped final solution is feasible with respect to the constraint set with minor distortion-induced optimality loss. We prove the feasibility guarantee and bound the optimality loss under mild conditions. Simulation results, including those for computation-heavy SDP problems and non-convex AC-OPF problems for grid operations, show that homeomorphic projection outperforms existing methods in solution feasibility and run-time complexity, while achieving similar optimality loss. We will also discuss open problems and future directions. Speaker(s): , Minghua Room: 3038, Bldg: Macleod Building, 2356 Main Mall, Vancouver, British Columbia, Canada, V6T1Z4