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

Question

xinyu 2013-2-22

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/64467-how-can-i-do-linear-programming-with-a-piecewise-objective-function

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

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

请先登录，再进行评论。

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

Answer 1

Alan Weiss 2013-2-22

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/64467-how-can-i-do-linear-programming-with-a-piecewise-objective-function#answer_76123

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 2013-2-23

编辑：xinyu 2013-2-23

在 MATLAB Online 中打开

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 2013-2-27

在 MATLAB Online 中打开

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 2013-2-27

在 MATLAB Online 中打开

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

请先登录，再进行评论。

Answer 2

Matt J 2013-2-27

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/64467-how-can-i-do-linear-programming-with-a-piecewise-objective-function#answer_76740

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.