how can I do linear programming with a piecewise objective function?

2013 2 22
2 个回答
5 次查看（30 天）

1 个投票

hello
I have done a linear programming code.And now the objective function of the problem will become a piece-wise function, but still linear in every part of the function.Also， all the constrains are linear as well.
which order can I use to solve the optimizing problem? still the linprog? if yes, how to write the objective function，AKA f. If not, which order can I turn to？
I have tried the fmincon order, but the example in help seems wrong, because I errors happened when I was trying to run it. Is also seems that the description of 'medium-scale programming' in help of linprog suits my requirements, but I cannot figure out how to right the objective function.
thanks
zech

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

回答（2 个）

Alan Weiss
Alan Weiss 2013-2-22

0 个投票

Optimization Toolbox solvers generally assume that objective functions are smooth, meaning twice differentiable. They can have difficulty with nonsmooth functions.
That said, there should be no errors even with nonsmooth objectives. If you show us some code we might be able to help diagnose what is going on with your objective or constraint functions.
linprog is unsuitable because it does not handle piecewise-defined objectives and constraints.
It is possible that patternsearch, in Global Optimization Toolbox, is most suitable, because it does not care about smoothness.
Alan Weiss
MATLAB mathematical toolbox documentation

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

xinyu
xinyu 2013-2-23
编辑：xinyu 2013-2-23
Thank you for answering my question. I'll provide some details of my problem as you required, see if you can help me one step further.
The original problem:
min f(x)=30x1+50x2
where x=[x1,x2,theta1,theta2,theta3]
st:please see the code for sepecific. Because it shouldn't be a problem,and all of them are linear. This is a typical linear programming problem.
In this case, the following code is written and everything seems working well.
f=[50,30,0,0,0];% objective function
A=[0,0,-10, 10, 0;
0,0, 10, -10, 0;
0,0, 5, 0, -5;
0,0, -5, 0, 5;
0,0, 0, 10/3,-10/3;
0,0, 0,-10/3,10/3]; % matrix for inequalities
b=[10;10;10;10;10;10];
Aeq=[1,0,-15, 10, 5;
0,1, 10,-40/3, 10/3;
0,0, 5, 10/3,-25/3]; % matrix for equalities
beq=[0;0;3]; % vector for equalities
lb=[0;0;-10^(-6);-1000;-1000];
ub=[5;5;10^(-6);1000;1000]; %upper and lower limits
[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub)
The problem I come across now is I want to change the objective function to a piece-wise function: say:
f(x)=30x1+50x2 when(x1<=1 and x2<=1.5)
f(x)=30+50(x1-1)+50x2 when (x1>=1 and x2<=1.5)
f(x)=30x1+75+60(x2-1.5); when (x1<=1 and x2>=1.5)
f(x)=30+50(x1-1)+75+60(x2-1.5);when (x1>=1 and x2>=1.5)
and the constrains stays the same. IN this case how can I find the minimum value of f(x)?
xinyu
xinyu 2013-2-23
编辑：xinyu 2013-2-23
this seems can be done with fminimax, as no matter what the case is the function that suitable for the situation will be the largest one. In this case the problem becomes a minimax problem.
xinyu
xinyu 2013-2-23
The method I said earlier should be right, because I get an answer that I was expecting. But, I'm now a little bit struggling with the new function :).
xinyu
xinyu 2013-2-24
It seens that the fminmax function could only oprovid a local optimization solution rather than a global one. I have tried to fina a function in the global optimizeing toolbox as you suggested, the result was the gamultiobj. The help doc just says it will provide a local Pareto set X. I don't understand the Pareto set at the moment.
Alan Weiss
Alan Weiss 2013-2-25
If fminimax works for you locally, then you should probably use it to search globally. Simply set different start points and see if you obtain different results. See, for example, this section of the documentation.
In particular, since you have bounds on all your components, you can try the following as random start points:
x0 = lb + rand(size(lb)).*(ub - lb);
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
xinyu
xinyu 2013-2-27
the fminimax can also be used as
x= fminimax(fun,x,A,b,Aeq,beq,lb,ub)
x0 is the initial guess, what is x supposed to be?
Alan Weiss
Alan Weiss 2013-2-27
Sorry, you found a typo in the documentation. I'll fix that. The syntax is supposed to be
x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub)
Alan Weiss
MATLAB mathematical toolbox documentation

请先登录，再进行评论。

Matt J
Matt J 2013-2-27

0 个投票

If your problem size isn't too large (you say it's "medium scale"), you could try a brute force approach. Since your feasible set consists of polygonal pieces, you could find try to find the vertices of all the polygons using
http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
The piecewise linear objective has to be optimized at one of the vertices, so you could just search the values at all vertices to find the optimum.

类别

在 帮助中心 和 File Exchange 中查找有关 Solver Outputs and Iterative Display 的更多信息

标签

提问:

xinyu
xinyu
2013-2-22

Community Treasure Hunt

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

Start Hunting!

Translated by