A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
arXiv:1601.07277
Abstract
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.
arXiv comment39 pages, 7 figures
References in corpus (12)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
- Embedded Online Optimization for Model Predictive Control at Megahertz Rates
- Consensus-ADMM for General Quadratically Constrained Quadratic Programming
- Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
- Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
- An Improved Three-Weight Message-Passing Algorithm
- A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
- Fast Approximate Quadratic Programming for Large (Brain) Graph Matching
- Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
- Graph matching: relax or not?
- A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming
Cited by in corpus (5)
- Weighted Sum-Rate Optimization for Intelligent Reflecting Surface Enhanced Wireless Networks
- Workflow Optimization for Parallel Split Learning
- A nonconvex optimization approach to IMRT planning with dose-volume constraints
- Inferring Parameters Through Inverse Multiobjective Optimization
- Optimal control of linear systems with limited control actions: threshold-based event-triggered control