A general system for heuristic minimization of convex functions over non-convex sets
A general system for heuristic minimization of convex functions over non-convex sets
复制标题
DOI：
10.1080/10556788.2017.1304548
复制
发表时间：
2018-01-01
影响因子：
2.2
通讯作者：
Boyd, S.
中科院分区：
文献类型：
--
作者：
Diamond, S.;Takapoui, R.;Boyd, S.
我们描述了一种通用启发式算法，可以近似地解决具有非凸集上的凸目标变量和决策变量的各种问题。启发式算法采用了凸松弛、凸约束、局部邻域搜索法和乘子交替方向法，只需要解决少量的凸性问题，并且不需要太多的调整就可以应用于一般问题。我们在一个名为NCVX的程序包中描述了这些方法的实现，作为CVXPY的扩展，CVXPY是一个用于描述和求解凸优化问题的Python程序包。我们研究了几个众所周知的非凸问题的例子，并表明我们的通用启发式算法在寻找各种问题的近似解方面是有效的。
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.