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's gravatar image

RDjM
3316
accept rate: 0%

edited 24 Aug '15, 19:12

Are in constraints all polynomials are concave?

(25 Aug '15, 16:40) Slavko

@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.

(25 Aug '15, 19:07) RDjM

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.

(26 Aug '15, 06:10) Slavko

I am aware of the heuristics, but I was thinking about obtaining a guaranteed optimal solution (for a given tolerance).

(26 Aug '15, 06:29) RDjM
2

If the polynomial functions appear in equality constraints, it does not help that they are convex. The feasible set is still non-convex.

Global solvers, e.g., Baron or SCIP, apply (linear) outer approximation and spatial branching to solve these kinds of problems.

(27 Aug '15, 11:51) rschwarz

@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.

(28 Aug '15, 03:25) RDjM
1

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.

(28 Aug '15, 04:03) rschwarz
showing 5 of 7 show 2 more comments
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×79
×3
×1

Asked: 24 Aug '15, 19:09

Seen: 576 times

Last updated: 28 Aug '15, 07:16

OR-Exchange! Your site for questions, answers, and announcements about operations research.