5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to SciComp.SE. What do you mean with the last part of the second line of the equation, i.e. "$1_{M_{t}N_{t}\times 1}$"? $\endgroup$ – nicoguaro Aug 30 '15 at 23:58
  • $\begingroup$ Thanks for the reply. It is a vector of ones with the given dimensions, ones(MtNt x 1). $\endgroup$ – user3100463 Aug 31 '15 at 4:38
  • $\begingroup$ You might add that to the text... Or use a better notation to make it more clear $\endgroup$ – nicoguaro Aug 31 '15 at 5:23
  • $\begingroup$ Done! Thanks for the suggestion. I also know that I didn't make the question as clear as I wanted because I don't even know where to start. I also don't want the whole code, I just want some directions like how I can define the 'a' vector or how I can implement the sum-trace in cvx. $\endgroup$ – user3100463 Aug 31 '15 at 6:15
  • $\begingroup$ Have you solved other problems with CVX? Have you looked at the examples, user guide, and function reference? If so, what is particularly difficult about formulating this problem in CVX? $\endgroup$ – David Ketcheson Aug 31 '15 at 6:56
4
$\begingroup$

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?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.