convex-optimization - 如何判断函数是非凸的还是凸的

Question

例如：(6-z)(x1+x2+x3)＜40。z 是一个正整数变量。x1,x2 和 x3 都是实变量。那么如何判断函数是凸函数还是非凸函数。

Answer 1

这实际上是一个比人们想象的更复杂的问题。

1. 这不是一个函数，而是一个约束。

2. 约束不应该有一个<，而应该有一个<=。

3. 凸约束的一种定义f(x) <= c是f(lambda*x1+(1-lambda)*x2) <= lambda*f(x1)+(1-lambda)*f(x2)对所有x1,x2,0<lambda<1. （严格凸性需要 < 而不是 <=）

4. 通常更容易证明二阶导数矩阵（Hessian）对于所有 x 都是对称的和半正定的。

5. 对于二次约束，就像在您的示例中一样，形成约束x'Qx + a'x <= c（这只是一个不同的符号）并证明Q是半正定的。例如，通过查看特征值。

6. 另一种方法是尝试使用 CVXPY 解决问题。如果问题不是凸的，它会抱怨。

7. 如果模型根据起点收敛到不同的解决方案（具有不同的目标值），则问题是非凸的。

8. 我经常使用的另一个启发式方法：放入全局求解器（例如 Baron），检查日志，看看它是否进行任何分支。如果是这样，则问题是非凸的。

9. 对于二次问题：把它扔给 Cplex 或 Gurobi，看看它是否抱怨非凸性。Gurobi 有一个解决非凸二次问题的选项（但它需要设置一个选项）。

10. 对于某些问题类别，我们知道问题是否是凸的（熟悉这方面的文献）。

11. 如果松弛是凸的（即忽略整数限制），则整数变量的约束是凸的。

12. 具有整数/二进制变量的约束通常可以重新表述为一组线性不等式。