5 views (last 30 days)

Show older comments

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

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.

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.

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

Start Hunting!