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

Hey Everyone

I am solving a linear optimization problem.

The following form is used according to the matlab documentation:

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

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

[Matt J]

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.

[Konrad Marthaler]

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.

Answer 1

[John D'Errico]

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.

[Konrad Marthaler]

Thank you a lot for your response it was very helpful.

I somehow expected the solutions to be more similar but your explanation makes a lot of sense.

The solution is depndant on the solver, algorith and starting point.

Do you think it would be reasonable to use the linear solver and then use its result as an input into fmincon?

[John D'Errico]

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.