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

Question

Jamais avenir 2015-6-5

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/222590-how-to-find-the-feasible-solution-space-of-a-nonlinear-constraint-optimization-problem

评论： Matt J 2015-6-14

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2015-6-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/222590-how-to-find-the-feasible-solution-space-of-a-nonlinear-constraint-optimization-problem#answer_182641

编辑：Matt J 2015-6-14

在 MATLAB Online 中打开

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.

2 个评论
显示无隐藏无

Jamais avenir 2015-6-14

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 2015-6-14

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

请先登录，再进行评论。

Answer 2

Alan Weiss 2015-6-5

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/222590-how-to-find-the-feasible-solution-space-of-a-nonlinear-constraint-optimization-problem#answer_181698

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

5 个评论
显示 3更早的评论隐藏 3更早的评论

Jamais avenir 2015-6-5

在 MATLAB Online 中打开

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 2015-6-8

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.

Construct a large number of initial points x0 in your solution space.
For each initial point, use fmincon to solve the auxiliary nonlinear problem of minimizing the function @(x)0 subject to all of your constraints.
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.
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 2015-6-14

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.

请先登录，再进行评论。

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

2 个评论
显示无隐藏无

更多回答（1 个）

5 个评论
显示 3更早的评论隐藏 3更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

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

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

2 个评论 显示 无隐藏 无

更多回答（1 个）

5 个评论 显示 3更早的评论隐藏 3更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

2 个评论
显示无隐藏无

5 个评论
显示 3更早的评论隐藏 3更早的评论