A general system for heuristic minimization of convex functions over non-convex sets. (2nd January 2018)

• Record Type: Journal Article
• Authors: Diamond, S.; Takapoui, R.; Boyd, S.
• Is Part Of: Optimization methods and software. Volume 33:Number 1(2018)
• Page Start: 165
• Page End: 193
• Publication Date: 2018-01-02
• Subjects: non-convex optimization -- convex approximations -- heuristics -- alternating direction method of multipliers -- modelling software; 90C59 -- 90C25 -- 90C26; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1304548
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We describe general heuristics to approximately solve a wide variety of problems with convex objective and decision variables from a non-convex set. The heuristics, which employ convex relaxations, convex restrictions, local neighbour search methods, and the alternating direction method of multipliers, 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 non-convex problems, and show that our general purpose heuristics are effective in finding approximate solutions to a wide variety of problems.