Equivalent (underdetermined) formulations yield different solutions!

1

Hello,
I have an underdetermined system of equations Y=XA
I tried to minimize the following objective functions,

  1. minimize sum(sum_square(Y-X1*A,2))
  2. minimize sum(sum_square(Y-X2*A,1))
  3. minimize norm(Y-X3*A,'fro')

The solutions (X1,X2,X3) are very different from each other.
Neither are the values to the objective functions similar.

Why is this happening? Aren’t the 3 equivalent?
Following is some sample code.

A=randn(70,100)';
A=A./norm(A);
X=rand(100);
Y=X*A;
%1
cvx_begin
variable X1(100,100)
minimize sum(sum_square(Y-X1*A,2))
cvx_end
%2
cvx_begin
variable X2(100,100)
minimize sum(sum_square(Y-X2*A,1))
cvx_end
%3
cvx_begin
variable X3(100,100)
minimize norm(Y-X3*A,'fro')
cvx_end

Thanks a lot

2

You need to square the ‘fro’ norm, for instance by applying square_pos, to be equivalent to the others.

Other than that, when I run them, I get optimal objective values which seem to be within solver tolerance variation (which I deem to be similar enough), using either SeDuMi or SDPT3 with default tolerances. What are your optimal objective values?

3

The optimal values do look almost similar, 3.9880e-12, 3.2262e-11 and 5.0159e-09 for cases 1,2 and 3 (after squaring the fro term).
However, the solution X takes very different values.
For example in one realization,

 norm(X1-X2,'fro')=0.449
 norm(X1-X3,'fro')=6.01
 norm(X2-X3,'fro')=5.59

I had assumed that equivalent forms meant that the same minima would be reached in each case. I understand that there is no unique solution here, but shouldn’t the three solutions be the same (to within a small error)?

4

The problems getting passed to the solver are not identical, even if they are mathematically equivalent optimization problems presuming exact arithmetic were being used. I defer to mcg to further explain. Given non-uniqueness of the optimal solution, I believe your assumption that argmins should necessarily basically be the same is false.

5

CVX is operating correctly.

As you say, the problems are underdetermined. The optimal value is therefore zero, and there are multiple optimal solutions. The three values returned by these formulations are all within reasonable numerical tolerances.

CVX is under no obligation to give you a specific solution when there are multiple solutions. The one it chooses will depend upon the specific formulation and the specific solver. If you favor one solution over another, that fact must be reflected in your model.

6

Okay, my bad. Thanks for the quick replies.