# Matlab taking too much time to give output

19 views (last 30 days)
Pushkar Khatri on 30 May 2018
Commented: Walter Roberson on 4 Jun 2018
I'm solving a convex optimization problem which has to minimize a variable matrix of 498x498 size. As I run it, it is taking forever to give final value of x. When I terminate the process in between it shows like this
my code is
function f= coheren(x)
Z = (D)*(D');
[V, U,W]=svd(Z);
a = mtimes(U,V');
b = mtimes(V,U);
f = (norm(U-(a*(x')*(x)*b)))^2;
end
function [c,ceq] = cohcon(x)
[m,n]= size(D);%size(x)
k = D*(D');
T = (x)*k*(x');
[V1,U1,W1] =svd(T);
ceq = rank(U1)-m;
c= [];
end

Walter Roberson on 30 May 2018
Never load() inside a cost function. Load the data outside the function and pass the data in.
In your case, for coheren(), you could pre-calculate U, a, and b, and pass those all in. For cohcon, you could pre-calculate k = D*(D') and pass that in.

Walter Roberson on 3 Jun 2018
Do you have a comment on the analysis I did for the nonlinear constraints?
Pushkar Khatri on 4 Jun 2018
First of all, thanks a lot for your help!! The rank of the dictionary,used here, is 221 and after svd the diagonal matrix(here matrix U) formed is not a full rank matrix. Guessing in the analogous way,I also think <=0 constraint will allways be true for x. But fmincon requires at least one constraint to carry on the convex optimization. Without that case, hour can it possibly operate
Walter Roberson on 4 Jun 2018
Convex optimization would be more associated with linear constraints rather than with nonlinear constraints.

Aakash Deep on 31 May 2018
Hey Pushkar,
Solving a convex optimization problem is a big task. Yes, it can take a long time to converge. You can not minimize the time of the algorithm but what you can do is, you can change your converging threshold.
As you know, the convergence plot of convex optimization problem decrease exponentially and hence the major components are already gets covered in the starting. So, you can give a threshold (try to keep the threshold at or below 0.1) such that whenever your error value gets below the threshold then stop the algorithm.

Walter Roberson on 1 Jun 2018
Aakash Deep, I actually executed the code. Before the second iteration ('sqp') or before the first iteration ('interior-point') the error message is given,
Requested 248004x248004 (458.3GB) array exceeds maximum array size preference. Creation of arrays greater than this limit may take a long time and cause MATLAB to become unresponsive. See array size limit or preference panel for more
information.
248004 is exactly 498^2, which is the number of variables involved because zeros(498) is passed as the x value to fmincon. Hessian estimation requires estimating the effect of each variable with respect to each other variable, which would lead to a 248004 x 248004 matrix, which is 458.3GB . I know that I do not have that much memory!
Aakash Deep on 1 Jun 2018
Yes, I agree with your point. So in that case, is there any solution for this problem?
Walter Roberson on 1 Jun 2018
The only hope I see while using fmincon() is if the algorithm can be expressed for use in large scale solvers.
When I look at the nonlinear constraint, after some thinking, it looks to me as if it testing whether the matrix is singular in the sense of having at least one zero singular value. It calculates the rank of the 498 x 498 diagonal matrix, with the rank being the same as the number of non-zero diagonal elements, and it subtracts off the number of rows of the D matrix (498) and returns that. That would be negative in the case where there was at least one zero singular value, and would be 0 in the cast where the passed in matrix had no non-zero singular values.
... But -- nonlinear inequalities are consider satisfied if the output is <= 0, which is always going to be the case because rank minus 498 with rank maximum 498, can never be positive. With the two cases distinguished in theory seeming to be either singular or not, then I suspect that 1 should have been added to the result of the test so that the result would be positive in the case where the input was full rank.
When I look at https://www.mathworks.com/help/matlab/ref/svd.html#bu2_4_9 it says you can calculate the rank of a matrix by calculating the number of non-zero singular values -- which is what appears to be happening here. But it also says that rank() is provided for that purpose. This suggest that even if the nonlinear constraint is still required, that the SVD calculation followed by finding the rank of the diagonal, could be replaced by simply calling rank() on the matrix.
As I look through the way that matrix is being constructed, rank(Z) is 215, and I do not think it is possible for the calculations it is doing to create a greater rank matrix. So my thought is that at least for this D matrix, that the nonlinear constraint will always return negative (meaning constraint not violated). If my logic is correct then the nonlinear constraint call could be removed. That could be important for the purpose of converting to large scale algorithms.
Unfortunately at the moment I have no idea how one would calculate the hessian pattern for the large scale algorithms.

Rishabh Rathore on 4 Jun 2018
Edited: Rishabh Rathore on 4 Jun 2018
For the convergence problem, the upper bound could be used on the number of iterations, as suggested by Aakash. As for the problem with size of array being too large, Tall arrays could be used to overcome the issue as Tall arrays are not loaded in the memory at once.
You could refer:- Tall Arrays
Note:- the computation would take time since the size of the data to be manipulated and the number of calculations to be performed is very high.