I would like to solve the following optimization problem. With scalar $R$ and nine (mutually orthogonal) $9$-dimensional column vectors $\vec v_i$ all given ($\vec v_i\!'$ is the row vector Hermitian conjugate to $\vec v_i$) and with $9\times9$ identity matrix $I$,

minimize $Tr(D) - \max_i(\vec v_i\!' * D * \vec v_i)$

subject to

(1) $\vec v_i\!' * D *\vec v_j = 0$ for all $i\ne j$

(2) $||I - X|| = R$ (using any matrix norm here that will work)

(3) $X\ge0$

(4) $D\ge0$

(5) $X + D - \sum_i (\vec v_i\!' * X * \vec v_i) \vec v_i*\vec v_i\!'\ge0$

(6) $X$ is a tensor product of some (unknown) pair of $3\times3$ matrices.

Constraint (5) essentially just subtracts off the diagonal elements (in the basis of the $\vec v_i$) of $X$, replacing them with those of $D$. For this particular case, the $\vec v_i$ are real, if that matters. But $X$ can be complex.

$X$ and $D$ are the ($9\times9$ matrix) variables, and without the last constraint involving the tensor product, it appears to almost be a semidefinite, or at least a convex, program. The constraint involving $R$, confining things to a spherical shell centered on the identity, may also be problematic. I've tried using cvx to solve this, but without luck, apparently because of these two issues.

Is there a way to deal with these issues to obtain a solution that we know is a global, and not just a local, minimum? Any help would be greatly appreciated.

  • $\begingroup$ It is also the case that the $\vec v_i$ are product vectors, with the same tensor structure as is required for $X$. That is, they are each a product of a pair of $3$-dimensional vectors, though I'd guess this doesn't really make things much easier. $\endgroup$ – Scott Aug 1 '15 at 22:27
  • $\begingroup$ Yes, constraint 2 is not convex, and cannot be made so. You could relax it to $\le$. I see no easy solution for 6. $\endgroup$ – Michael Grant Aug 2 '15 at 12:54
  • $\begingroup$ Thanks for your comments Michael. I was actually hoping you might see this. Constraint 6 is unfortunately the key point of what I'm working on. I also cannot relax 2 to $\le$, because taking $X=I$ leads to $D=0$ and the minimum of the objective is then also zero, a not very helpful result. I could relax it to $0<R_1\le ||I-X|| \le R_2$, but I don't suppose that would be convex, either. So convex programming won't work, I guess, but do you (or anyone else) know of another approach to be sure of getting a global minimum, even if it is not an "efficient" method? $\endgroup$ – Scott Aug 2 '15 at 19:47
  • $\begingroup$ I'm afraid not. See, one of the nice things about being a convex optimization specialist is that once I conclude that something is hopelessly non-convex, I have the perfect excuse to set it aside and move on :-) $\endgroup$ – Michael Grant Aug 2 '15 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.