A General System for Heuristic Solution of Convex Problems over Nonconvex Sets

Understand

We describe general heuristics to approximately solve a wide variety of problems with convex objective and decision variables from a nonconvex set.

• The heuristics, which employ convex relaxations, convex restrictions, local neighbor search methods, and the alternating direction method of multipliers (ADMM), require the solution of a modest number of convex problems, and are meant to apply to general problems, without much tuning.
• We describe an implementation of these methods in a package called NCVX, as an extension of CVXPY, a Python package for formulating and solving convex optimization problems.
• We study several examples of well known nonconvex problems, and show that our general purpose heuristics are effective in finding approximate solutions to a wide variety of problems.