Large-Scale Linear Programming

Hi Programmers,

I have faced an essential problem when I try to start linprog optimizer with 48 variables and 30 inequality constraints and 48 variable constraints (side constraints); it doesn't accept my initial points (starting points)!

It gives the following message: Large scale (interior point) algorithm uses a built-in starting point; ignoring user-supplied X0.

My question is: Is there any way to let MATLAB to accept the starting points for the large-scale (not medium-scale) linear programming instead of using its built-in starting points?

It is very essential for me to let linprog to optimize the high-dimensional problem with the given supplied starting points

Thanks a lot

Answer 1

[Alan Weiss]

As stated on the linprog function reference page:

 x = linprog(f,A,b,Aeq,beq,lb,ub,x0) sets the starting point to x0. linprog uses x0 only with the active-set algorithm. linprog ignores x0 with the interior-point and simplex algorithms.

However, 48 variables, or even 100, is not a big problem. You can use any algorithm you like, all should work just fine with that small a problem, though the interior-point algorithm is likely to be the fastest.

If your real problem is much larger, meaning many thousands of variables and constraints, then indeed you should use the interior-point (large-scale) algorithm. I am not sure why you think you need to include a starting point, linear programs are convex problems, and so any answer is going to be a global optimum.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ali]

Thanks Alan

Yes I have gotten the above message, but by default MATLAB translates my problem to be considered as a large-scale problem, because it shows to me a message that it will ignore my starting points and instead will use its built-in starting points

To answer your question about why I want to use my x0, because this linprog algorithm is used as a sub-algorithm to re-tune the results that are obtained by an evolutionary algorithm, like GA or PSO .. So, without considering x0 "which is supplied from the first stage, by GA or PSO", the objective of this hybridization (GA-LP or PSO-LP) will not be satisfied.

[Alan Weiss]

I am not sure that I understand you very well. What do you mean "by default MATLAB translates my problem to be considered as a large-scale problem"? If you want to choose the linprog algorithm, just pass in an options structure containing the appropriate setting of the Algorithm option.

I also do not understand what you mean when you say you need x0. As I understand it, either you need to update your constraints for linprog, or you will get the same answer every time you run linprog. And if you do update your constraints, you do not need a new x0, because linear programs basically come up with the same solution from any starting point. But it is quite possible that I continue to misunderstand what you mean.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ali]

Hi Alan & thanks again

What I mean for the first part is: when I run linprog the above message appears to me: Large scale (interior point) algorithm uses a built-in starting point; ignoring user-supplied X0.

That message doesn't appear if I run linprog for 12 variables with 6 inequality constraints .. whch means that MATLAB will accept that the 48 variables problem as a large-scale, am I correct?

The second part: all what I mean is: can I let linprog run with user defined X0 instead of the buuilt-in X0?

Thanks again

[Alan Weiss]

I am afraid that you have some misunderstandings about how linprog )or any other Optimization Toolbox solver) works.

The solver does not pick an algorithm. You pick an algorithm. If you do not pick an algorithm, the solver uses the default algorithm, which for linprog is interior-point.

If for some reason you really don't want to use the interior-point algorithm, then set the algorithm using the optimset function:

 % For R2013a and later
 opts = optimset('Algorithm','active-set');
 % Or for R2012b and earlier
 opts = optimset('LargeScale','off');
 % Then make sure you include the options in your call:
 x = linprog(f,A,b,Aeq,beq,lb,ub,x0,opts);

If you don't want to see the warning about x0 not being used, then don't pass x0, pass [] instead. Seriously, passing x0 will almost certainly NOT change the ultimate answer, the option exists onoy because sometimes you can speed up the active-set solver by giving a good starting value. Let me reiterate: using ANY algorithm and ANY starting point should give you the SAME ANSWER, so there is, to my mind, no reason for choosing do do either.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ali]

I think the solution with active-set method, which is not included in my version "R2012a"

Thanks Alan again & I appreciate your effort

Regards,

[Matt J]

the option exists onoy because sometimes you can speed up the active-set solver by giving a good starting value.

Seems to me, though, that you should also be able to speed up the interior-point algorithm in the same way. I find it curious that any iterative algorithm would be absent an option to take advantage of a good initial guess, when available.

[Alan Weiss]

Matt, a characteristic of interior-point solvers that they have a different idea of what a good initial point is than you might think. If you give a point on the boundary as an initial point, an interior-point method thinks it a horrrible point, because it wants to stay away from boundaries (in many interior-point codes there is a large penalty for being close to the boundary). So it is usually better to allow interior-point algorithms to choose their own starting points, or at least to substantially modify any point you pass in. And if it is going to substantially modify the point, well, maybe the algorithm should just not accept a start point.

Alan Weiss

MATLAB mathematical toolbox documentation