I wish to model the following problem: \max \{\langle A(x),y\rangle + \frac{1}{2}\lVert Bx\rVert^2 | \quad tr(y) = 1, y \geq 0\}
where x \in \mathbb{R}^n, and A(x) = \sum_{i=1}^n x(i)A_i, for n given symmetric matrices A_i, i = 1, \dots n are given and the variable is y \in S^n.
It seems like you intend x to be a variable, but I don’t see its declaration. You have not shown us how v is actually defined (calculated). So maybe you need to declare variable x(n), and then calculate v before the maximize line. Are there any constraints on x?
No. x is actually a given vector here, the only variable is y. I put the constant term (1/2)(Bx'*Bx) on the objective function just because I want to use the computed value later.
The way I used to calculate v is by making a big matrix A_{n,m(m+1)/2} where each line of it is the vectorized form of A_i (I computed this using sdpt3’s function svec) so that A'*x is the vectorized form of \sum_{i-1}^n x_i A_i
The code I used to do this is,given the matrix Aj = [A1, \dots, A_n] which is m \times mn I did
blk{1,1}='s';blk{1,2}=redm;
for j=1:n
Aj(:,(j-1)*redm + 1:(j-1)*redm + redm) = (1/2)*(Aj(:,(j-1)*redm + 1:(j-1)*redm + redm) + Aj(:,(j-1)*redm + 1:(j-1)*redm + redm)');
a = svec(blk,Aj(:,(j-1)*redm + 1:(j-1)*redm + redm),1);
A(:,j) = a';
end
A=A';
v = A'*x;Bx = B*x;
Hopefully mcg will come along and perhaps can assess the correctness of your method for calculating v. However, it should be easy to write the code to generate v in a straightforward way more directly corresponding to the math notation (since you don’t need to do all the packing that SDPT3 requires). Have you actually verified that your computed v is correct? That is really a MATLAB matter and not a CVX matter.
I’m doing this to compute the gap of the problem
$$min_{x \in \Delta_n} max_{y \in \Omega} \langle A(x),y\rangle + \frac{1}{2}\lvert Bx\rvert^2$$,
where \Omega = \{y \in S^n | tr(y) = 1, y \geq 0\} and \Delta_n is the unit simplex in \mathbb{R}^n.
I’m calculating the gap as
$$max_{y \in \Omega} \langle A(x),y\rangle + \frac{1}{2}\lvert Bx\rvert^2 - min_{x \in \Delta_n} \langle A(x),y\rangle + \frac{1}{2}\lvert Bx\rvert^2$$
This gap theoretically should be always positive, but I’m getting negative values, hence I know that something must be wrong. By the way, I’m also using cvx for computing the other minimum, but I’m pretty sure that one is ok, because when I switch my problem to y being a vector and the set \Omega to \Delta_m then the gap is computed right.
I see. I’m gonna try if I can verify somehow whether my v is being computed right
Perhaps you should show us your CVX formulation of the minimization problem. When you get a negative gap, what x value is used in your maximization with what resulting optimal y, and what y value is used in your minimization with what resulting optimal x?
The x which I use on the max problem and the y I use on the min problem are generated by a big routine where I’m updating x and y and expecting that they converge to the solution of the minmax problem, so that the gap should converge to 0.
So you can think of x as a vector in \Delta_n and y as the vectorized form of a matrix in \Omega, using the svec function.
About the optimal values, the maximization problem is returning something of order 0.2 while the minimization is returning something of the order 17 to 20 (this testing for 100 randomly generated symmetric matrices A_j 100 by 100) I tested for different instances of matrices with the same properties and keep getting the same order on the results. The gap is then computed as 0.2 - 17 and stays negative.
As you said I just found out it was matlab error and nothing to do with cvx.
I just assumed it was cvx because it was working right with the other problem I mentioned…
Thanks for the help, I wouldn;t have found out without it.
I don’t know if I should delete this post or leave as it is now?
Leave aside the possibility of any coding errors for the moment. My use of max and min w.r.t stated variables means subject to your stated constraints on the particular variable.
If min w.r.t x of max w.r.t y < max w.r.t y of min w.r.t x, then it is possible to have a negative gap, depending on the choice of x for your max and choice of y for your min. You haven’t told us how these are chosen other than by stating that they are generated by a big routine which you expect to converge to a solution of the minimax problem. Not having details of your big routine, I can’t judge the veracity of this, and even if I did have the details, perhaps not. I presume somewhere or other in the big routine, or inputs thereto, is some kind of starting values; perhaps the performance of your overall algorithm critically depends on those. Why do you “expect” this big routine to converge, other than that it would be nice if it did?
If I have any theoretical misunderstanding, please feel free to correct me,
Edit: Our posts crossed in cyberspace, so to speak. So perhaps what I have written has been overcome by events. You may want to edit your last post and provide more details on the MATLAB error you found, especially to the extent it may have been manifested in your previous posts. In any event, I suggest you leave the thread intact.