how to judge that the function is non-convex or convex

Question

For example：(6-z)(x1+x2+x3)＜40. z is a positive integer variable.x1,x2 and x3 are all real variables. Then how can I judge that whether the function is convex or non-convex.

Answer 1

This is actually a more complicated question than one would expect.

1. This is not a function but a constraint.

2. A constraint should never have a < but rather a <=.

3. One definition of a convex constraint f(x) <= c is that f(lambda*x1+(1-lambda)*x2) <= lambda*f(x1)+(1-lambda)*f(x2) for all x1,x2,0<lambda<1. (Strict convexity requires < instead of <=)

4. Often easier is to prove that the matrix of second derivatives (the Hessian) is symmetric and positive-semi definite, for all x.

5. For quadratic constraints, like in your example, form the constraint x'Qx + a'x <= c (this is just a different notation) and prove Q is positive-semi definite. E.g. by looking at the eigenvalues.

6. Another way is to try to solve the problem using CVXPY. It will complain if the problem is not convex.

7. If the model converges to different solutions (with different objective values) depending on the starting point, the problem is non-convex.

8. Another heuristic I often use: throw into global solver such as Baron, and inspect the log and see if it does any branching. If it does, the problem is non-convex.

9. For quadratic problems: throw it at Cplex or Gurobi and see if it complains about non-convexity. Gurobi has an option to solve non-convex quadratic problems (but it requires setting an option).

10. For some problem classes we know whether the problem is convex or not (be familiar with the literature on this).

11. Constraints with integer variables are convex if the relaxation is convex (i.e. ignore the integer restrictions).

12. Constraints with integer/binary variables can often be reformulated into a set of linear inequalities.