Asked by Pushkar Khatri
on 30 May 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)

load ('Dictionary.mat','D');

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)

load ('Dictionary.mat','D');

[m,n]= size(D);%size(x)

k = D*(D');

T = (x)*k*(x');

[V1,U1,W1] =svd(T);

ceq = rank(U1)-m;

c= [];

end

Answer by 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

Walter Roberson
on 4 Jun 2018

Sign in to comment.

Answer by 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.

Sign in to comment.

Answer by Rishabh Rathore
on 4 Jun 2018

Edited by 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.

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.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.