Is there a way to get the same results for linprog & fmincon given the same optimization problem?
4 views (last 30 days)
Show older comments
Konrad Marthaler
on 23 Jul 2021
Commented: John D'Errico
on 23 Jul 2021
Hey Everyone
I am solving a linear optimization problem.
which provided reasonable solutions.
One update in the project required some constants from the linear objective function to change according to a table which takes one of the decision variables (among others as an input). Therefor, a function handle was used to describe the updated objective function:
obj_fun = @(x)objective_function(x, input1, input2, input3)
which constructs the objective function as follows:
function obj_fun = objective_function(x, input1, input2, input3)
f_const = zeros(size(x,2));
f_const(1) = table(x(1), input1, input2, input3); %constant for optimization that needs to be read out of a table
f_const(2:3) = [2 3]; %example values but constant
obj_fun = 0;
for i = 1:size(x,2)
obj_fun = obj_fun + f_const(i) * x(i);
end
Eventhough the problem is linear for each iteration, using values from the table for the constants meant that the solver had to be changed to accept input from functions:
x = fmincon(obj_fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options);
As a first test, I tried solving the initial system with fmincon:
function obj_fun = objective_function(x, input1, input2, input3)
f_const = zeros(size(x,2));
f_const = [1 2 3]; %example values but constant
obj_fun = 0;
for i = 1:size(x,2)
obj_fun = obj_fun + f_const(i) * x(i);
end
x = fmincon(obj_fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options);
However, the results were not comparable to the results of linprog and it took around 8h to complete the calculations wheareas before it took around a minute.
For some of the results the fallowing warning was printed:
Warning: Matrix is close to singular or badly scaled. Results may be
inaccurate. RCOND = 1.931564e-16.
> In backsolveSys
In solveKKTsystem
In computeTrialStep
In barrier
In fmincon (line 824)
In order to avoid singularieties I tried different starting points. However for some of the surrounding conditions the warning didn't disappear.
Is there any different solver that you could recommend?
Or do you know of a way how some of the constants in linprog could be read out from a table that depends on some decision variables?
Thank you in advance & Kind Regards
Konrad
2 Comments
Matt J
on 23 Jul 2021
Well, in order to comment on the behavior you see, we need a runnable example that reproduces it . The outline code that you posted does not run. It throws many errors different from what you mention.
Just off the top of my head though, if the coefficients of the linear program are becoming linear functions of the x(i), it means your objective is in fact quadratic, and you should therefore probably be using quadprog instead of linprog.
Accepted Answer
John D'Errico
on 23 Jul 2021
Well, NO. You cannot insure exactly the same solution will arise from both solvers. I can think of several ways for the two solvers to produce totally different results.
- Fmincon is an iterative scheme, that moves from point to point and eventually terminates, based on a convergence criiterion. fmincon will produce a result that can be subtly different based on distinct sets of start points. In some cases, the difference can be truly significant, yielding totally different local minima. Any solution will certainly be a function of the convergence tolerance.
- Linear programming works by different methods, that will yield a solution at a node of the bounding simplex. (There are different methods offered in linprog, of course.)
As a quick example...
format long g
f = [1 0];
[xval,fval,exitflag] = linprog(f,[],[],[],[],[0 0],[1 1])
So linprog has found a nodal solution at the origin.
F = @(X) dot(X,[1 0]);
[xval,fval,exitflag] = fmincon(F,[.5 .5],[],[],[],[],[0 0],[1 1])
Yet fmincon gave something completely different.
So a totally different solution by the two solvers, to the same probem. Admittedly, I chose a simple example where the value of x(2) is completely irrelevant. But you should note that linprog gave an exact zero, whereas fmincon produces a value that is only within its convergence tolerance. It got close enough, and then accepted the result.
Give me some time, and I can easily cook up different examples. But the point is, two different solvers will not be required OR expected to produce exactly the same results.
2 Comments
John D'Errico
on 23 Jul 2021
I chose an example where there are infinitely many valid solutions. But see that fmincon did not converge exactly to zero, so it failed in that respect too. So I picked a case that exposed two reasons at once why the two codes can differ.
At the same time, the error message that you got:
Warning: Matrix is close to singular or badly scaled. Results may be
inaccurate. RCOND = 1.931564e-16.
is symptomatic of problem where there can be infinitely many solutions, all equivalent. That warning message should indicate an objective function that is virtually flat in some subspace, so it can move anywhere along a line or plane at no cost in the objective.
See the example I gave, here the solution is clearly not a function of x(2), so it is flat along that path in space. And this would certainly explain why the solvers can generate different solutions as I showed.
To your question about linprog, THEN fmincon, I honestly don't see how using two solvers in tandom can help. If linprog has generated an optimal solution for a linear problem (which it darn well should) then fmincon will simply go nowhere. You should expect to see fmincon stop with no gain made, and so you would have wasted CPU time for no gain.
More Answers (0)
See Also
Categories
Find more on Get Started with Optimization Toolbox in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!