Different optimal solution for same mathematically codes

1

Hi,
I implement one specific code in two ways, one with for loops and the other with vectorization, both are mathematically equivalent and return same value with same inputs. Nevertheless, when I use them as an objective function in optimization problem with same solver, they get same optimal-value with different optimal solution. Also, for each implemented objective function, I try mosek, sedumi and sdpt3 as a solver, all get same optimal-value but different optimal solution!
Could you help me to handle this problem?
The reproducible codes are available here:code

Thanks a lot!

2

Given computations are done using 64 bit floating numbers then that is what you can expect.

Maybe you should read

2 Likes
3

As a complement to @Erling’s answer:
If a convex optimization problem does not have a unique optimal solution, even the slightest change in inputs can result in the same solver with the same settings finding a different optimal solution (argmin or argmax). If a problem is presented differently to CVX, the problem inputs it provides a solver may change, such as changing the order of constraints or introduction of auxiliary variables or constraints. CVX often uses an epigraph formulation to essentially move the objective function to constraints. So even differences in how an objective function is constructed in CVX can cause the solver to receive a different problem (number or order of constraints, or even just different roundoff error). Any of these can cause the same solver to find a different non-unique solution.

And of course, different solvers, or the same solver with different settings, could find different non-unique solutions.

Note: I interpret “same optimal-value” to mean “same optimal objective value” and “optimal solution” to mean “argmin” or “argmax”.

4

Thanks Erling for your reply. It’s a great article, I learned new things from it. To handle my problem, I have increased Matlab digital precision from 32 to 90, and put cvx_precision to best, but nothing changed. Also, I try to use symbolic input instead of double values, but cvx can not accept objective type of sym. Do you have any suggestion to deal with this problem?

5

Thanks Mark for your reply. It’s a good hint, But my problem is a linear convex optimization, so I think it should only have one optimization solution!

6

Linear Programming (LP) problems don’t necessarily have unique solutions, because they are convex, not strictly convex. Non-unique solutions are very common in LP (and MILP).

Is MATLAB “digital precision” something used by a multiple (unlimited) precision MATLAB toolbox? Or the symbolic toolbox? In any event, not used by CVX or the solvers it calls.

I do not recommend changing cvx_precision from its default. It is sometimes a bad thing, and seems to almost never be a good thing.

7

Thanks so much. I got it. Is there any way that can make cvx to give other optimal solutions?

8

You would have to solve additional problem(s). ‘’

For instance, solve a 2nd problem which adds the constraint (if minimizing)
original objective <= optimal_objective_value_of_original_problem
and then change the objective in the 2nd problem to be something to try to encourage a different solution to be found.

Or instead of that, keep that added constraint, and the original objective function, but add additional constraint(s) to preclude the original solution (of course, you might make the problem infeasible if you try this).

9

Thanks Mark for your patience and guidance. I will try it.