Thread Subject:

Fmincon with system of nonlinear inequalities

Hi Everybody,

I have an optimization problem and i use fmincon to solve it. I have three different nonlinear system of inequalities as my constraints.

1- f(x,y)>R1
2- g(x,y)>R2
3- x^2+y^2<=1

where f(x,y)>R1 and g(x,y)>R2 are two systems of nonlinear inequalities. x and y are unknown parameters and R1 and R2 are known. It is easy to write first and second constraints in fmincon by using nonlinear constraints option. However in my problem my constraints are complement of 1 and 2. So, constraint that i want to write are

1- (f(x,y)>R1)^c
2- (g(x,y)>R2)^c
3- x^2+y^2<=1

where A^c is the complement set of set A.

I am a little confused about writing complement of a set in fmincon as nonlinear constraints.

Any suggestion for this issue?

Regards

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1jc76$eqf$1@newscl01ah.mathworks.com>...
>
> I am a little confused about writing complement of a set in fmincon as nonlinear constraints.
>
================

But isn't it true that

 {f(x,y)>R1}^c = {f(x,y)<=R1}

And isn't f(x,y)<=R1 easy to express in FMINCON syntax?

"Matt J" wrote in message <k1jcm7$gc9$1@newscl01ah.mathworks.com>...
> "kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1jc76$eqf$1@newscl01ah.mathworks.com>...
> >
> > I am a little confused about writing complement of a set in fmincon as nonlinear constraints.
> >
> ================
>
> But isn't it true that
>
> {f(x,y)>R1}^c = {f(x,y)<=R1}
>
> And isn't f(x,y)<=R1 easy to express in FMINCON syntax?

f(x,y)>R1 is a system of individual nonlinear inequalities. (f(x,y)>R1)^c is the complement of the set of intersection of all these individual inequalities. I am not sure whether i can write as you said or not? Giving a simple example

x>5 and x>6 and the intersection of these two is x>6 the complement of this is x<=6

However, x<=5 and x<=6 and the intersection of these is x<=5

So they are not same!!!

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1jdvp$l07$1@newscl01ah.mathworks.com>...
>
> f(x,y)>R1 is a system of individual nonlinear inequalities. (f(x,y)>R1)^c is the complement of the set of intersection of all these individual inequalities. I am not sure whether i can write as you said or not? Giving a simple example
>
> x>5 and x>6 and the intersection of these two is x>6 the complement of this is x<=6
>
> However, x<=5 and x<=6 and the intersection of these is x<=5
>
> So they are not same!!!
=================

OK. Well, I doubt it's possible in general to find inequalities describing the complement, at least differentiable ones. Take the unit square for example

-.5<=x(1)<=.5
-.5<=x(2)<=.5

You could write its complement as

norm(x,inf)>=.5

but that's not differentiable. I suppose if I faced a problem like this, I would decompose the problem into 5 regions. I would first minimize outside the circle that circumscribes the square

norm(x)^2>=.5

Then I would look at the disconnected regions inside the circle but outside the square. Each of those regions are describable by differentiable inequalities.

We'd have to see your inequalities to know how well this idea extends.

On 8/28/2012 5:42 PM, kamuran turksoy wrote:
> "Matt J" wrote in message <k1jcm7$gc9$1@newscl01ah.mathworks.com>...
>> "kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message
>> <k1jc76$eqf$1@newscl01ah.mathworks.com>...
>> >
>> > I am a little confused about writing complement of a set in fmincon
>> as nonlinear constraints.
>> > ================
>>
>> But isn't it true that
>> {f(x,y)>R1}^c = {f(x,y)<=R1}
>>
>> And isn't f(x,y)<=R1 easy to express in FMINCON syntax?
>
> f(x,y)>R1 is a system of individual nonlinear inequalities.
> (f(x,y)>R1)^c is the complement of the set of intersection of all
> these individual inequalities. I am not sure whether i can write as
> you said or not? Giving a simple example
>
> x>5 and x>6 and the intersection of these two is x>6 the complement of
> this is x<=6
>
> However, x<=5 and x<=6 and the intersection of these is x<=5
> So they are not same!!!
I have been wondering whether I should document this sort of thing.

In general, fmincon takes constraints with an implicit AND:

Case A: constraint 1 AND constraint 2 AND constraint 3 are all satisfied.

However, in your case (and I imagine others) you really want an OR:

Case B: constraint 1 OR constraint 2 OR constraint 3 is satisfied.

These are not logically equivalent, and there is no way, in general, to
express Case B in terms of Case A.

However, nonlinear constraints are extremely flexible, and you can
probably cobble together a nonlinear constraint function that works. Let
F be the set of feasible points, and d(x) be the distance of the point x
to the boundary of F. Let u(x) = 1 if x is in F, and u(x) = -1 if x is
not in F. Then
-u(x)*d(x)
is a function that is zero on the boundary of F, is negative when x is
in F, and is positive when x is not in F.
This function might not be differentiable, depending on the shape of F
and the particular distance function. But it might work. Maybe
-u(x)*d(x)*d(x)
would be smoother.

Anyhow, I hope you see the idea: while you cannot, in general, translate
from AND constraints to OR constraints, a nonlinear constraint function
can model any possible constraints.

Alan Weiss
MATLAB mathematical toolbox documentation

There may in fact be ways to write differentiable inequalities for the complement by introducing extra variables that affect the constraints, but not the objective function. As an example, suppose you want the complement of the region

x(1)<=0 AND x(2)<=0

or equivalently

 x(1)>=0 OR x(2)>=0

Then you can introduce a new variable theta and express this region using the inequalities

x(1)*cos(theta) +x(2)*sin(theta)>=0

0<=theta<=pi/2

============================================
> We'd have to see your inequalities to know how well this idea extends.

Well, Actually in f(x,y) and g(x,y) i have equations for different circles. For example

f(x,y)>R1 is like (x-a1)^2+(y-b1)^2>r11, (x-a2)^2+(y-b2)^2>r12, .... (x-an)^2+(y-bn)^2>r1n
g(x,y)>R2 is like (x-c1)^2+(y-d1)^2>r21, (x-c2)^2+(y-d2)^2>r22, .... (x-am)^2+(y-bm)^2>r2m

Where a_i, b_i r are all known. So basically my all constraints are in terms of circle inequalities. And i should say (f(x,y)>R1)^c is equal to the union of the complements of each inequalities ((x-a1)^2+(y-b1)^2>r11).

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1lf87$3pe$1@newscl01ah.mathworks.com>...
> ============================================
> > We'd have to see your inequalities to know how well this idea extends.
>
> Well, Actually in f(x,y) and g(x,y) i have equations for different circles. For example
>
> f(x,y)>R1 is like (x-a1)^2+(y-b1)^2>r11, (x-a2)^2+(y-b2)^2>r12, .... (x-an)^2+(y-bn)^2>r1n
> g(x,y)>R2 is like (x-c1)^2+(y-d1)^2>r21, (x-c2)^2+(y-d2)^2>r22, .... (x-am)^2+(y-bm)^2>r2m
>
> Where a_i, b_i r are all known. So basically my all constraints are in terms of circle inequalities. And i should say (f(x,y)>R1)^c is equal to the union of the complements of each inequalities ((x-a1)^2+(y-b1)^2>r11).
========================

OK. Well here's my next question. Since this is a low dimensional (2D) problem, can't you at least approximately solve this using exhaustive search, i.e., evaluate your objective function and constraints at every (x,y) on an appropriate grid and find the minimum using the MIN function?

Once you've done this and gotten a reasonably good approximation to the location of the solution, you should be able to narrow your search down to 1 circle, for which you can obviously write an expression for the constraints quite easily. FMINCON can then be used to refine the solution.

=====================================================
> Once you've done this and gotten a reasonably good approximation to the location of the solution, you should be able to narrow your search down to 1 circle, for which you can obviously write an expression for the constraints quite easily. FMINCON can then be used to refine the solution.

I did not get your idea totally... I was thinking about solving f(x,y) and g(x,y) as another optimization problem externally and then take the complement of them and using in real optimization. However in that case i would need to find the regions that are solutions of f(x,y)>R1 and g(x,y)>R2. But how can i find the region in matlab? If i can do that then taking complement of these region would work for my problem.

"kamuran turksoy" <kamuranturksoy@gmail.com> wrote in message <k1olg3$9h8$1@newscl01ah.mathworks.com>...
>
> I did not get your idea totally... I was thinking about solving f(x,y) and g(x,y) as another optimization problem externally and then take the complement of them and using in real optimization. However in that case i would need to find the regions that are solutions of f(x,y)>R1 and g(x,y)>R2. But how can i find the region in matlab? If i can do that then taking complement of these region would work for my problem.
================

I'll try to clarify my idea. Why don't you just take lots of discrete sample points (xi,yi) in your continuous xy space, e.g., the nodes of some discrete grid. Evaluate your objective function at all the sample (xi,yi). Evaluate your constraints at all the (xi,yi) as well. Then, you will have a list of numbers that you can just minimize over using the MIN function. Obviously, discard from this minimization all the (xi,yi) that don't satisfy the constraints.

Once you've done this, you will have a particular (xj,yj) that is probably very close to the continuous-space solution. Make the assumption that if (xj,yj) lies in a particular circle, the continuous-space solution does as well. So now, you don't have to consider anymore the entire complement of {f(x,y)>R1}, which is just the union of a bunch of circles. You can just pick one of the circles in {f(x,y)>R1}^c that contains (xj,yj) and discard all the rest. Do the same for {g(x,y)>R1}^c .

"Matt J" wrote in message <k1ompb$dp9$1@newscl01ah.mathworks.com>...
>
> Once you've done this, you will have a particular (xj,yj) that is probably very close to the continuous-space solution. Make the assumption that if (xj,yj) lies in a particular circle, the continuous-space solution does as well. So now, you don't have to consider anymore the entire complement of {f(x,y)>R1}, which is just the union of a bunch of circles. You can just pick one of the circles in {f(x,y)>R1}^c that contains (xj,yj) and discard all the rest. Do the same for {g(x,y)>R1}^c .
==================

Also note that if either {f(x,y)>R1}^c or {g(x,y)>R1}^c are not connected, then you have no choice but to do the above. Neither FMINCON nor any of the other solvers can deal with unconnected feasible sets.

By this I mean that all the circles participating in {f(x,y)>R1}^c must overlap sufficiently so that all points in {f(x,y)>R1}^c are connected to each other by a continuous curve of points that are also contained in {f(x,y)>R1}^c, and similarly for {g(x,y)>R1}^c

When your feasible set consists of disconnected pieces, you have no choice but to search each piece separately.