Optimization problem with non convex constraints
11 ビュー (過去 30 日間)
古いコメントを表示
Hi everybody,
I am developing an optimization problem where cost function is linear and I have non convex constraints for the optimization variable.
To give a short example:
min -f*x where a<=x<=b OR c<=x<=d, that is x cannot be something between b and c (note that : a<b<c<d).
I am using linprog (I was using fmincon, then moved to linprog).
Is there a way to write these constraints so that they could be feasible for fmincon, linprog? Or, how should I write the problem?
thanks a lot!
0 件のコメント
回答 (1 件)
Matt J
2024 年 4 月 17 日
編集済み: Matt J
2024 年 4 月 17 日
Is there a way to write these constraints so that they could be feasible for fmincon, linprog?
There is, but it is generally not helpful to do so, because it normally leads to a formulation with a discontiguous feasible set.
The reliable way would be to solve two separate linear programs, in this case with linprog,
(1) min -f*x s.t a<=x<=b
(2) min -f*x s.t c<=x<=d
and you would select the solution giving the best objective function value.
However, because your real problem is hidden from us, we cannot say whether this is computationally tractable outside of this example.
2 件のコメント
Matt J
2024 年 4 月 17 日
編集済み: Matt J
2024 年 4 月 17 日
If you are saying that each x(i) independently must be constrained to
then it means your feasible set is the union of have
disjoint hyper-rectangles. A continuous optimizer like fmincon cannot be relied upon to choose which region of a discontiguous feasible set will lie in, so you would have to solve 2^n problems and that could be intractable.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1671436/image.png)
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1671441/image.png)
However, one other thing to consider is whether your problem can be separably decomposed. Itdoesn't seem from the problem description that the different x(i) are coupled together at all in the optimization. Your objective function as you've presented it is additively separable in the x(i). Likewise, it sounds like each x(i) is constrained independently of any other x(j). So, conceivably you could optimize each x(i) independently, which would be O(n).
参考
カテゴリ
Help Center および File Exchange で Get Started with Optimization Toolbox についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!