finding intersection of between surfaces and extended to n dimensions

Hi there,

if given a main objective function (non-linear) f(x,y) and constraints (non-linear) g1(x,y)=C1 g2(x,y)=C2 ... gn(x,y)=Cn

I can plot contours of of all the above and find the intersection visually. What mathematical technique can I use to extract a matrix that has the points of all intersections between all the surfaces? I need something that is general to extend to from 1 to n dimensions if my functions have n design variables and n design constraints.

Thanks,

Answer 1

[John D'Errico]

A bit confusing here. You tell us about an objective function, but then tell us nothing about what you will do with it. Then you start talking about intersections between a set of constraint functions.

Anyway, it is not possible for several reasons. At least not as you describe. You are apparently asking for a general solution of n nonlinear equations in n unknowns.

 - There many be a finite number of solutions, no solutions at all, or even an infinite number.

 - Since the functions are nonlinear, they may be arbitrarily nasty. No technique can exist that will return the locus of all solutions to a general nonlinear problem.

There is no magical method that will do what you want.

[Joseph]

Thanks, Fair enough. I'm thinking about this the wrong way. I'll carefully elaborate further. Perhaps you can point me to the correct approach.

I want to minimize the objective function in this case the weight of ferromagnetic core solenoid subject constraints. So what I have here is an optimization problem. So far I have 2 design variables "x" and "y" and one constraint. The process for my optimization is as follows.

1. create a vector space for design variables

    x=xmin:xmax; y=ymin:ymax

2. take contour plot for both f(x,y) g1(x,y)-C1

    [f,h1]=contour(x1,x2,f,v,'ShowText','on'); % objective
    [g1,h2]=contour(x1,x2,g1,[C1,C1],'k-','ShowText','on');

3. Visually see point of minimum use that as a guess in fmincon with upper and lower bound.

I'm aware that fmincon initial guess doesn't have to be close to the optimum solution but I'm trying to make this all automatic without user intervention on the initial guess and upper/lower bounds (want to avoid step 3) if the user decides to change some parameters.

[John D'Errico]

With ONE constraint, in two dimensions, this becomes a simple problem, almost trivial.

- contourc returns a piecewise linear polygon that represents the desired contour of your constraint function, in (x,y). A single constraint of the form g1(x,y)=C1 will return what is essentially a path embedded in the (x,y) plane. Be careful here, since that contour may actually be several disjoint polygons. For example, a given contour may be several roughly circular polygons, that are completely disjoint.

- Given a single contour polygon, evaluate the objective function f(x,y) along that path in the (x,y) plane. Choose the point which yields the mininum value of the objective function along the polygon. You can use my tool interparc to generate additional points along the polygon. Again, since the contour polygon may be several disjoint segments, you may need to do this step several times. You can find interparc on the file exchange.

You should find that this works quite reasonably well, and would be quite doable in an automatic sense. Of course, it requires you generate an initial grid, on which to evaluate the function to generate that contour polygon (or set of polygons.)

The fine-ness of that initial grid will help to determine how accurately you can find that starting point. In fact, arguably one could completely eliminate the fmincon step, if you built a sufficiently fine grid. You could eliminate the call to fmincon, just taking the best point along the interpolated contour. Or just use fzero, then minimizing the parametric function f(x(t),y(t)) along the interpolated contour path.

Since interparc offers spline approximations to such a path (as long as it is a SINGLE path, not a disjoint set of them) you could then use fzero to minimize the function f(x(t),y(t)) along the smoothly interpolated path(s). Again, if there were multiple local solutions, these would be seen as separate local minima, so subject to the start point along each path.

In higher dimensions, then with potentially multiple constraints, this will get messy. I only claimed it would be easy for the simple case. Although it is POSSIBLE to do similar things in say 3 dimensions or even higher than that, the necessary slicing operations get harder to do. As well, evaluating a list of functions on complete grids in say 6 or 7 dimensions, then doing the slicing will get EXTREMELY computationally expensive. This is what I often refer to as the curse of dimensionality. Things get exponentially complicated, and that happens FAST as the number of dimensions rises.