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

Answer 1

[Alan Weiss]

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

[xinyu]

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]

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]

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]

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]

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]

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]

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]

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.