I have a problem where the objective function is linear and the constraints have polynomials. So, my question is what are the main approaches to this issue? I can construct a small example, just to illustrate it. $$ \max \sum_{i} a_i x_i  \sum_{j} b_j y_j $$ $$\qquad c_1 x_i + c_2 x_i^2 + c_3 x_i^3 +\ldots + c_k x_i^k = \sum_{j} d_j y_j, \quad \forall i\in N $$ $$\qquad x_i \geq 0, \quad i\in N $$ $$\qquad y_j \in \{0,1\}, \quad\forall j\in M $$ asked 24 Aug '15, 19:09 RDjM
showing 5 of 7
show 2 more comments

Are in constraints all polynomials are concave?
@Slavko All polynomials have the same degree, e.g. k = 4, and all polynomials are CONVEX (sorry, I edited this comment) on the respective domains (i.e. x_i > 0). For example, this could be the polynomial: x + x^2 + x^3 + x^4. So, to do a piecewise approximation with quadratic/linear functions? Or to find some reformulation? SDP crossed my mind, but I'm not quite good with semidefinite programming. Also, I heard that there are some linearization techniques, but I'm not quite sure about that in this case.
Perhaps a set of feasible solutions to that problem is a (totally?) disconnected space. I would consider the use of evolutionary computation in solving that problem.
I am aware of the heuristics, but I was thinking about obtaining a guaranteed optimal solution (for a given tolerance).
If the polynomial functions appear in equality constraints, it does not help that they are convex. The feasible set is still nonconvex.
Global solvers, e.g., Baron or SCIP, apply (linear) outer approximation and spatial branching to solve these kinds of problems.
@rschwarz So, my only option is to use an MINLP software? I was thinking to transform the polynomial constraints, i.e to make them quadratic. Then, the next question would be is the software for MIQP better then Baron (or some other on the market) in this particular situation, and how much. The problem is that I don't have the opportunity to use MINLP software (except NEOS), to benchmark this issue. Also, I was hoping that there are some other approaches.
Sure, you can also introduce auxiliary variables and transform the problem to quadratic (and bilinear) equations. Then you might be able to apply more solvers, but nonconvex quadratically constraint problems are still solved mostly by the same method, I believe.