fmincon with nonlinear equality constraints

1 回表示 (過去 30 日間)
Vlad Bec
Vlad Bec 2019 年 5 月 5 日
編集済み: John D'Errico 2019 年 5 月 5 日
Hi, I have optimization problem to solve with fmincon function. The object function is x1+x2+x3+x4+x5+x6+x7, with constraints:
(1-x1)(1-x2)=0
(1-x1)(1-x2)(1-x3)(1-x6)(1-x7)=0,
(1-x2)(1-x3)(1-x4)(1-x6)=0,
(1-x3)(1-x4)(1-x5)(1-x7)=0,
(1-x4)(1-x5)=0,
(1-x2)(1-x3)(1-x6)=0,
(1-x2)(1-x4)(1-x7)=0,
x1^2-x1=0, x2^2-x2=0, x3^2-x3=0, x4^2-x4=0, x5^2-x5=0, x6^2-x6=0, x7^2-x7=0.
I know that the solutions are x2=x4=1 or x2=x5=1 (all other variables have to be zero) and in both cases object function is equals to 2.
Thanks in advance!

回答 (1 件)

John D'Errico
John D'Errico 2019 年 5 月 5 日
編集済み: John D'Errico 2019 年 5 月 5 日
This is barely an optimization problem at all.
Many of your nonlinear constraints are just a kludge, a way to use a nonlinear equality constraint to enforce the requirement that many of your variables are binary integers, thus 0 or 1.
In fact, that alone makes your problem inadmissable for solution by fmincon, because the feasible solution set becomes a list of disjoint points. Fmincon is not designed to solve binary integer probramming problems, and you cannot sneakily force it to do so by a kludge of a constraint like that. It won't work, and fmincon will fail to converge.
Thus, we have the constraints:
x1^2-x1=0, x2^2-x2=0, x3^2-x3=0, x4^2-x4=0, x5^2-x5=0, x6^2-x6=0, x7^2-x7=0.
Each of those is equlivalent to the statement that
x1==0 or x1==1
x2==0 or x2==1
...
x7==0 or x7==1
So you have a search space with 2^7 possible nodes. Do you really need to use an optimization function to solve that small of a problem?
Of those 128 possible nodes, now look at the rest of the constraints.
For example, this one
(1-x1)(1-x2)=0
implies that x1 ==1 OR x2==1, because all variables are binary. Likewise, the other constraints tell you that:
(1-x1)(1-x2)(1-x3)(1-x6)(1-x7)=0,
So ONE or more of the unknowns x1,x2,x3,x6,x7 is 1. But, we know that x1|x2 is already true by the previous constraint. So this second constraint is superfluous.
We can do the same thing for each of the other product constraints.
(1-x2)(1-x3)(1-x4)(1-x6)=0,
We can write that as x2|x3|x4|x6
(1-x3)(1-x4)(1-x5)(1-x7)=0,
We can write that as x3|x4|x5|x7. But, now look at the next constraint:
(1-x4)(1-x5)=0,
That implies x4|x5 is true. Therefore the previous constraint is superfluous, since it is implied to be true by this one. The next one:
(1-x2)(1-x3)(1-x6)=0,
Also allows us to obviate the third constraint. And, finally, we learn that
(1-x2)(1-x4)(1-x7)=0,
we must have x2|x4|x7 be true.
Essentially, we can virtually solve this problem using paper and pencil. Do I really need to do the rest, since it is so simply done?
Lets see...
We know that x1 OR x2 is 1.
We know that x4 OR x5 is 1.
So consider if x1 is 1. In this case, we cannot satisfy all of the constriants with only 2 variables equal to 1. Instead, consider the case where x2 is 1. Each of the bold faced, underlined constraints are now trivially true.
(1-x1)(1-x2)=0
(1-x1)(1-x2)(1-x3)(1-x6)(1-x7)=0
(1-x2)(1-x3)(1-x4)(1-x6)=0,
(1-x3)(1-x4)(1-x5)(1-x7)=0,
(1-x4)(1-x5)=0,
(1-x2)(1-x3)(1-x6)=0,
(1-x2)(1-x4)(1-x7)=0,
The other two constraints allow either x4 or x5 to be 1, in which case all of them are now clearly true. So the solution that minimizes the sum, x1+x2+x3+x4+x5+x6+x7 has exactly two of the unknowns equal to 1. The two possible such solutions are
(x1,x2,x3,x4,x5,x6,x7) = (0,1,0,1,0,0,0)
(x1,x2,x3,x4,x5,x6,x7) = (0,1,0,0,1,0,0)
Do you honestly, seriously need to solve it programmatically? Or is this just a kludged up trivial example problem, representing some far more complex problem that you need to solve?
The point being that if your real problem is this trivial 7 variable problem, surely assigned as homework, then the simplest solution is to just generate all 128 possible nodes, then test to see which one is best.
If your real problem is much larger, then DON'T do it this way. It is just an integer programming problem. You cannot use fmincon to solve it. You COULD use GA, from the global optimization toolbox can solve it. You could also write it to be solved using intlinprog, and intinprog would probably be the most efficient way to solve a seriously large form of this problem.
  2 件のコメント
Vlad Bec
Vlad Bec 2019 年 5 月 5 日
Yes, I know the problem is overdetermined, but that kind of system of equations could be consistent. And I know what the solution(s) is(are). My real problem is larger, this is only an example. I was wondering if I could solve it by fmincon. The last 7 equations (x^2-x=0) have been added just to single out the binary solutions and not to calculate all 128 possibilities.
John D'Errico
John D'Errico 2019 年 5 月 5 日
編集済み: John D'Errico 2019 年 5 月 5 日
NO. You cannot solve it using fmincon. And my point is that fmincon does NOT handle this class of problem. As I said, it is clear that you created those constraints in a way to try to slyly fudge fmincon to solve it. Sorry. Fmincon cannot be fooled.
As I said, the best way to solve it is to use intlinprog. You have a binary integer linear programming problem, as I said. That is...
ALL variables are binary, so 0-1. How do you now encode those constraints? For example:
Wrong: (1-x1)(1-x2)=0
Right: x1 + x2 >= 1
As you should see, the linear inequality constraint is necessary and sufficient. Just do the same for each constraint. The result will be a matrix inequality of the form
A*x >= b
intlinprog will solve it with its eyes closed. HOWEVER, it cannot return all possible equivalent solutions. If that is your goal, then the problem becomes a potentially much more complicated search.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeSolver Outputs and Iterative Display についてさらに検索

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by