Optimization problem with non convex constraints

Hi everybody,

I am developing an optimization problem where cost function is linear and I have non convex constraints for the optimization variable.

To give a short example:

min -f*x where a<=x<=b OR c<=x<=d, that is x cannot be something between b and c (note that : a<b<c<d).

I am using linprog (I was using fmincon, then moved to linprog).

Is there a way to write these constraints so that they could be feasible for fmincon, linprog? Or, how should I write the problem?

thanks a lot!

Answer 1

[Matt J]

Is there a way to write these constraints so that they could be feasible for fmincon, linprog?

There is, but it is generally not helpful to do so, because it normally leads to a formulation with a discontiguous feasible set.

The reliable way would be to solve two separate linear programs, in this case with linprog,

(1) min -f*x s.t a<=x<=b

(2) min -f*x s.t c<=x<=d

and you would select the solution giving the best objective function value.

However, because your real problem is hidden from us, we cannot say whether this is computationally tractable outside of this example.

[Chiara]

Hi Matt,

first of all thanks for your rapid answer.

Your suggestion could be useful, but, as you said, maybe not appropriated for my problem to solve.

So I try to give some details:

I have to decide future plants power (x) in order to maximize the profit (prices * x).

In my prediction horizon I have to allow powers to be both [a,b] or [c,d].

If I separate the problem in two ones , I am denying the possibility to have power plan where powers belong with first set in some instants and with the second one in another.

So I should look for other ways (like other optimization variables) which should allow the power to be everything (not [b,c]), so that in the optimization problem the solution could give a mix of values belonging to the two separated bounds.

[Matt J]

If you are saying that each x(i) independently must be constrained to then it means your feasible set is the union of have disjoint hyper-rectangles. A continuous optimizer like fmincon cannot be relied upon to choose which region of a discontiguous feasible set will lie in, so you would have to solve 2^n problems and that could be intractable.

However, one other thing to consider is whether your problem can be separably decomposed. Itdoesn't seem from the problem description that the different x(i) are coupled together at all in the optimization. Your objective function as you've presented it is additively separable in the x(i). Likewise, it sounds like each x(i) is constrained independently of any other x(j). So, conceivably you could optimize each x(i) independently, which would be O(n).