MATLAB Answers

Is there a way to get the same results for linprog & fmincon given the same optimization problem?

5 ビュー (過去 30 日間)
Konrad Marthaler
Konrad Marthaler 2021 年 7 月 23 日
コメント済み: John D'Errico 2021 年 7 月 23 日
Hey Everyone
I am solving a linear optimization problem.
The following form is used according to the matlab documentation:
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 件のコメント
Konrad Marthaler
Konrad Marthaler 2021 年 7 月 23 日
Thank you a lot for your response. I'll have to check whether the output of the table leads to an objective function that can be solved by quadprog but it is a very good suggestion that I haven't thought of yet.
Regarding the code: Unfortunately, I am not sure if I am allowed to share the code but if I can I will update the post.

サインインしてコメントする。

採用された回答

John D'Errico
John D'Errico 2021 年 7 月 23 日
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.
  1. 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.
  2. 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])
Optimal solution found.
xval = 2×1
0 0
fval =
0
exitflag =
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])
Local minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the value of the optimality tolerance, and constraints are satisfied to within the value of the constraint tolerance.
xval = 1×2
1.00079962618689e-07 0.5
fval =
1.00079962618689e-07
exitflag =
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 件のコメント
John D'Errico
John D'Errico 2021 年 7 月 23 日
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.

サインインしてコメントする。

その他の回答 (0 件)

製品


リリース

R2019b

Community Treasure Hunt

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

Start Hunting!

Translated by