Semidefinite Programming Using CVX in Matlab

Question

I have the following optimization problem

$$\begin{align} &\min_{ X_{1}, \dots,X_{k} } \max_{ \theta, \phi } \left|P_{d}(\theta,\phi) - \sum_{k=1}^K \operatorname{Tr}(a_{k}(\theta,\phi)a_{k}^{H}(\theta,\phi)X_{k})\right|\\ &\text{subject to} \sum_{k=1}^K \operatorname{diag}(X_{k}) = \frac{E}{M_{t}N_{t}-(K-1)} 1_{M_{t}N_{t}\times 1}\\ &X_{k} \succeq 0, k = 1,2, \dots,K \end{align}$$

I am pretty sure that this optimization problem is convex (a SDP) so I can use cvx to solve it. However, I am not sure how I can express it in cvx language. I am not sure how can sweep through both $\theta$ and $\phi$ to solve the optimization problem. They are defined as

theta = linspace(0, 180, 181);
phi = linspace(0, 360, 361);

where

• $K = 5$, $M_{t}=5$, $N_{t} = 5$ and $E$ is some constant.
• $P_{d}(\theta,\phi)$ is a $181\times361$ matrix ($\theta$ for rows, $\phi$ for columns)
• $a_{k}(\theta,\phi)$ is a $25\times1$ column vector and $(\cdot)^H$ denotes the Hermitian transpose.
• $X_{k}$ is the complex optimization variable which is a $25\times25$ matrix.
• $1_{M_{t}N_{t}\times 1}$ is a vector of ones with given dimensions.

I tried to define $a_{k}(\theta,\phi)$ as a 4D vector with $(181, 361, K, 25)$ and store the values for every instance of $\theta$ and $\phi$ but then I couldn't figure out how I can implement $$\sum_{k=1}^K \operatorname{Tr}(a_{k}(\theta,\phi)a_{k}^{H}(\theta,\phi)X_{k})$$ so that it will generate a $181\times 361$ matrix.

Answer 1

It's not too difficult to formulate a problem like this in CVX, but unfortunately your instances are too large to be solved in practice by the primal-dual interior point solvers used by CVX. The problem here is in the minimax objective function, which CVX will convert into

$\min t$

subject to

$| P_{d}(\theta,\phi)-\mbox{stuff} | \leq t$

for each $\theta$, $\phi$ pair.

Each absolute value inequality further gets converted to two linear inequalities. There are over 65,000 $\theta$, $\phi$ pairs, so you'll end up with an SDP with over 130,000 constraints, which is outside the practical range of solvability (it requires the storage of a dense 130K by 130K matrix which would require over 135 gigabytes of RAM.) Furthermore, you might well run out of memory simply assembling this problem in CVX.

Would you be interested in solving this for a much smaller range of $\theta$, $\phi$ pairs?