How to write a code "RANK MINIMIZATION PROBLEM"

1

I have to minimize the objective function like this: minimize( Trace[X(k-1)+𝛿 I]^-1*X(k )
k represents for k-th iteration, X is symmetric positive semi-definite and I is the identity matrix.
At iteration 0: X(0)=I (identity matrix).
My problem is: i dont know how to write in CVX, because it automatically solve for matrix X. And how can i know the value of previous X(k-1) at iteration k.
Thank you!

2

I’m not sure I understand what you are trying to do. Are you trying to solve a sequence of convex optimization problems, each of which includes the argmin of the previous iteration as input data?

Is this what you want, perhaps with a different criterion on termination out of the loop?

X_old = eye(n);
for i=1:m
cvx_begin
variable X(n,n) semidefinite
minimize(trace(inv(X_old - delta*eye(n))*X))
cvx_end
X_old = X;
end
3

Can we know the X(0) X(1) …X(optimized) inside the cvx_begin AND cvx_end? i mean iterations inside the cvx_begin AND cvx_end. we do not need to create loop outside the cvx_begin and end.

4

If you need to solve more than one optimization problem, you need a separate cxv_begin … code … cvx_end for each optimization problem. I have done that within a for loop, or you might want to use a while loop. After you have exited CVX (cvx_end), the optimal values of the CVX variables are available until they are overwritten. The next time through the loop, if you declare the same variable name in CVX, the old value will no longer be available. You can save all the argmin (matrix) values in a 3D array, for instance; this would allow you to use all former argmins in the current CVX problem. But in the problem description you provided, you only seem to need to use the immediately preceding argmin. Do you have other constraints you didn’t mention?

5

Thank you for you kind reply!
The full problem is: Minimize (nothing) subject to: Trace(QiX(k)) belong to Ci where i=1,2,…,M (just sampling the region C into M samples) and X(k)>0. X,Q are symmetric positive semi-definite and ( X=xx’ ). I is identity matrix. But i need X* (denote for optimized X) must be low-rank to convert to x using approximated x=sqrt(largest eigenvalue of X*)(corresponding eigenvector). [the approximation is right only when X have low-rank after satisfy the condition Trace(QiX(k)) belong to Ci].
So, in order to have low rank X after reading some papers i saw two ways:
** First is minimize Trace(X).
** Second is Trace ( [X(k-1)+𝛿 I]^-1X(k ) ).
And inside the cvx_begin and cvx_end, the final optimized value is shown only when status is SOLVED, i can not see the value X at each step that CVX solve.
======first one======
cvx_begin
Min(Trace(X))
subject to
Trace(QiX) belong to Ci with i=1,2,…,M
cvx_end
======second one====
cvx_begin
Minimize ( Trace[X(k-1)+𝛿 I]^-1X(k) )
subject to
Trace(QiX) belong to Ci with i=1,2,…,M
cvx_end

For second one, i would like to know the value of X at each step that CVX solve when they export in the command matlab windows:
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|5.7e-01|3.3e+00|1.3e+02| 6.736097e+00 0.000000e+00| 0:0:00| chol 1 1
1|0.913|1.000|4.9e-02|4.4e-02|1.1e+01|-1.857634e+00 -1.075686e+01| 0:0:00| chol 1 1
2|1.000|0.944|1.0e-07|1.2e-02|1.3e+00|-7.117529e-01 -1.728173e+00| 0:0:00| chol 1 1
3|0.989|0.988|2.8e-08|5.7e-04|1.5e-02|-9.966884e-01 -9.985982e-01| 0:0:00| chol 1 1
4|0.989|0.989|7.6e-09|5.0e-05|1.7e-04|-9.999622e-01 -9.989878e-01| 0:0:00| chol 1 1
5|0.991|0.985|1.3e-10|7.4e-07|2.3e-06|-9.999994e-01 -9.999847e-01| 0:0:00| chol 1 1
6|1.000|0.977|4.7e-13|1.7e-08|1.0e-07|-1.000000e+00 -9.999997e-01| 0:0:00| chol 1 1
7|1.000|1.000|5.8e-15|1.0e-12|5.0e-09|-1.000000e+00 -1.000000e+00| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
I do not want to run many cvx_begin and cvx_end loops, because one loop cvx_begin and cvx_end takes 10 minutes, if i run 100 loops, it can be too long.

Thank you and best regards,

6

I don’t understand what you are doing. i have no idea what the Ci are (what does Trace(QiX) belong to Ci with i=1,2,…,M mean? Is that a lower and upper bound on the scalar value Trace(QX).?)

CVX will never tell you the intermediate value of the CVX variables at the iterations of the solver, nor do I see how they could be relevant to your problem.

What follows is my guess as to maybe approximately what your 2nd approach should be. “Tough luck” if it takes too long to go through the many iterations of the for loop - perhaps that is because it is a difficult problem and/or inefficient algorithm… Remember that you are solving a sequence of convex optimization problems as a way of trying to solve a (difficult) non-convex optimization problem. CVX will likely not be the fastest way, in computer execution time, to solve such a problem, but it is designed to allow you to model and solve problems with ease of use and relatively little human time.

X_old = eye(n);
for i=1:m
cvx_begin
variable X(n,n) semidefinite
minimize(trace(inv(X_old - delta*eye(n))X))
lower_bound(i) <= trace(CX) <= upper_bound(i) % or whatever trace(CX) in Ci is supposed to be
cvx_end
X_old = X;
end

I don’t understand why Ci would be different for different i. Perhaps your index i isn’t the same as index k, in which case I don’t know what you’re doing. trace(Q*X) is a scalar, so i don’t see how constraining it to simultaneously be in different (whatever) Ci 's (are) makes sense. I don’t come away with confidence that you are understanding whatever papers you are reading.

7

Thought that CVX can tell the intermediate value.
Thank you for your explanation!