# Matrix Least Square problem with constraints taking forever

Hello,

I am trying to solve a matrix least square problem with constraints. The problem looks like
minimise ||Y1-Y2*P|| (Frobenius norm)

subject to P(i,j)>=0 for all i,j
row sum of P is 1.

Now P is a huge (say 2000 x 2000) matrix, and Y1 and Y2 both are about (25 x 2000) real valued matrix. The CVX is taking forever to even form the problem before passing it to the chosen solver (Gurobi for instance). Is there any way to speed up this front-end overhead here, like reformatting the problem somehow? Thanks in advance.

Since you haven’t posted the actual CVX model code, we can’t say. But I’m afraid the answer is likely no. You’ll have to bypass CVX and call the solvers directly if you need better performance. But in fact, this particular problem is better suited for a good old fashioned gradient descent anyway.

Solving it using the MOSEK optimization toolbox for MATLAB should be possible. And quite quickly I would expect.

That’s great! I’d still be curious to see the original poster’s CVX model, though. It’s somewhat surprising that the formulation time would be expensive. It’s possible, certainly, but I wonder if there are unnecessary for loops.

Regardless, I’m glad to hear that MOSEK can handle it.

Thanks everyone. The cvx code is the following:

cvx_begin
variable Papprox_temp(mxmy,mxmy);
minimize norm(Psi1-PsiPapprox_temp, ‘fro’);
subject to
for i=1:mx
my
for j=1:mx*my
Papprox_temp(i,j)>= 0;
end
end

for i=1:mx*my
sum(Papprox_temp(i,:))==1;
end
cvx_end

Yes, just as I suspected!

Those for loops are the cause of your problem. Replace the first set of for loops with just

`P_approx_temp >= 0`

And replace the second for loop with

`sum(Papprox_temp) == 1`

I believe that should be
`sum(Papprox_temp,2) ==` 1

BTW, even if you wanted column sums, in which case `sum(Papprox_temp) == 1` would (usually) work, it’s better to explicitly specify `sum(Papprox_temp,1) == 1` , otherwise, MATLAB will sum across the row if the program is ever run with matrix having one row (don’t ask me how I know, ha ha, although it has nothing to do with CVX).

Thanks for the correction, Mark!

Thanks everyone. After reformulating the constraints the problem is solved by Gurobi in reasonable time with CVX front-end.