How to find the feasible solution space of a nonlinear constraint optimization problem?

I want to find the feasible objective space of a Multi objective nonlinear constraint optimisation problem. The problem is in the following form.

    min [F1(X),F2(X)]
    hk(X)=0   k=1,...,ne % equality constraints
    gi(X)≤0   i=1,...,n  % Inequality constraints.
    Ul<X<UB % UB and UL are upper and lower bounds of X
    where X=[x1,x2,...,xj]

It should be noted that, some optimisation variables, (`some x`) are not bounded at the Ul<X<UB . But they will be restricted through the equality and inequality constraints.

SO basically as a possible solution I think that I should generate some random numbers for X=[x1,...,xn] first and then check the constraints. if generated point satisfies the constraint, so it is a feasible point in the solution space. Thus, I can pass it to the objective function to get its value [F1(X),F2(X)] in order for obtaining the feasible objective space. But I don't know how to check the constraint. Any idea?

Thanks for your help.

Answer 1

[Matt J]

Assuming for the moment that you have no equality constraints, you would have to use NDGRID to generate a grid of samples in your N-dimensional space covering your bounded region Ul<X<UB. Then you would loop through the lattice of points, check which points satisfy the other inequality constraints, and then compute [f1,f2] for those points. Depending on the form of your constraints and objectives, there may also be vectorized ways of doing this, instead of looping.

When you do have equality constraints, then you would have to eliminate them by reparametrization. For example, linear equality constraints Aeq*x=0 define a linear space with basis vectors B1,B2,B3,... You can eliminate those constraints by reparametrizing X in terms of basis coefficients c1,c2,c3...

    X=c1*B1+c2*B2+...

In other words, your vector of unknowns is now the vector c=[c1,c2,c3,...]. Rewriting your problem in terms of c eliminates the equality constraints. With non-linear equalities, this is harder to do, but I don't think you have much choice.

Finally, doing what you are attempting is only going to be possible if the dimension of the problem after eliminating equality constraints is reasonably low. Obviously, though, brute force numerical sampling is only something that was ever going to work in low dimensions. Random sampling won't work in large dimensions either. The volume of the feasible region can get very small as a fraction of an N-dimensional box as N gets large.

[Jamais avenir]

So there is no way to visualize the feasible space since I have many non-linear equality constraints as well of linear equality constraints.

[Matt J]

I never said there was no way. I just said the reparametrization would be harder.

Answer 2

[Alan Weiss]

I am not sure what you are asking. It seems to me that you check the constraints by evaluating hk(X) and gi(X).

But you are unlikely to satisfy your equality constraints with a random point. I suggest that, if this is really the way you want to proceed, you first solve a feasibility problem. Set your objective function to @(x)0, and give only your nonlinear equality constraint to fmincon. Then for every initial guess you enter, you will get a "solution" that satisfies the nonlinear equality constraints. From there you can proceed as you outlined.

But I would not do this at all. I would use fgoalattain to try to find a tradeoff curve between my two objective functions, along the lines of this example.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Jamais avenir]

Dear Alan.

Thank you for your answer. I solved the problem and found the tradoff curve (Pareto Front) of the objective functions with NBI method already. However, I will compare the results with fgoalattain as well. But now at this point I want to see how the feasible objective space looks like. As an example you can see a namely bi-objective space here. The multi objective solution approaches only give the Pareto front and not the whole objective space. However, I think you already understood what an I asking.But would you please explain more when and how I check the other constraints (linear Equality,Nonlinear and Linear Equality and Inequality) with the generated random point?

As this is only a visualization problem and not a solution method, the elapsed time and efficacy is not very important.

Thank you for your answer in advance.

[Alan Weiss]

I'm sorry, but I am not at all sure that I understand you.

If you have a linear inequality constraint of the form

 A*x <= b

then all you have to do to check it is to take your point x, and calculate A*x - b.

Similarly, if you have a set of nonlinear inequality constraints h1(x), h2(x), etc, then all you have to do is evaluate these functions at your test point x.

But you already knew that, so all this shows is why I do not understand what you are asking.

Alan Weiss

MATLAB mathematical toolbox documentation

[Jamais avenir]

Well, I think I should define something to clarify my question . I have a multi-objective obtimization problem as follows:

    min [F1(X),F2(X)]
    hk(X)=0   k=1,...,ne % equality constraints
    gi(X)≤0   i=1,...,n  % Inequality constraints.
    Ul<X<UB % UB and UL are upper and lower bounds of X
    where X=[x1,x2,...,xj]

Definition:

Objective Space is a vector space including objective functions,i.e .[f1(X),f2(X)] , of the Multiobjective Optimization problem as its dimensions. It is different from solution space, which is a vector space with decision variables,i.e .[x1,x2,...,xj], of the Multiobjective Optimization problem as the dimensions.

To find the Objective Space* we should find the feasible solution space (i.e.,the values of X=[x1,...,xj] that satisfies all constraints of the problem,) first and then map these values to objective space [f1(X),f2(X)] . So we will have a 2D plot. like the figure in my earlier comment.

   Vector space:  R^j----->R^2

My problem contains linear and nonlinear equality and inequality constraints. So as you recommended I tried to do like this:

options = optimset('Algorithm','sqp','Display','off' );
for i=1:N
X = unifrnd(Bound(:,1),Bound(:,2),405,1)';
    [Xs,Fval, FLAG] = fmincon(@(X)0,X,A_ineq,B_ineq,Aeq,Beq,...
        Bound(:,1),Bound(:,2),@(X)myCon(X,Dat),options);
if FLAG==1
   obj(:,i)=tri_funs(Xs',Dat);

end
end 
plot(obj(1,:),obj(2,:),'*r');

Unfortunately, the constraints are so tight, so a generated random guess doesn't exceed to a solution. However, with a proper initial guess, it converge to a solution.

Comment : But you already knew that, so all this shows is why I do not understand what you are asking.

I can obtain the Pareto front (Curve A,1,B in the figure in perior comment.) with a multi-objective programming method (Weighted sum,NBI,goal programming and ,...). But these methods don't give the objective space (2D region in the prior figure.). I need this for visualization of my actual problem.

[Alan Weiss]

Again, I have a great deal of trouble understanding what you mean when you say "Unfortunately, the constraints are so tight, so a generated random guess doesn't exceed to a solution. However, with a proper initial guess, it converge to a solution."

Let me reiterate my suggestion.

1. Construct a large number of initial points x0 in your solution space.
2. For each initial point, use fmincon to solve the auxiliary nonlinear problem of minimizing the function @(x)0 subject to all of your constraints.
3. Take all the resulting feasible points and plot them in your 2-D objective space. This will give you a series of dots that might cover a fair portion of your feasible objective space.
4. If you have the Pareto front, you can plot that, too, and see whether the resulting feasible points trace out something close to the front.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Jamais avenir]

Thanks for your suggestion. I think I have done the same thing as you can also check my code in prior comment. But how to generate large numbers of initial point? I have tried to use something like X=unifrnd(Bound(:,1),Bound(:,2),405,1)'; to generate a random initial guess. But fmincon doesnt find any solution with that start point. This problem is so much dependent on the initial point.

But I understand your strategy. that would work for simple problems.