5
$\begingroup$

The objective is as follows:

$\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$

$s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$

where $a$ and $p$ are scalars, $\mathbf{b}$ is $1 \times N$ real vector, $\mathbf{d}$ is $N\times 1$ real vector, $\mathbf{C}$ is $N \times N$ Hermitian transpose matrix, $\mathbf{F}$ is $N \times N$, $\Sigma$ is $N\times N$.

It is obvious that if all the variables are scalars, the optimal $F^\ast$ is either $0$ or $p$. So how about the matrix case?

Thanks!

$\endgroup$
3
  • $\begingroup$ Has $\mathbf{F}$ to be Hermitian? $\endgroup$ Jul 30, 2014 at 12:41
  • $\begingroup$ Do you expect a closed-form solution? This problem is non-convex, and even if it were convex it seems unlikely to have a closed-form solution. $\endgroup$ Jul 31, 2014 at 5:30
  • $\begingroup$ There is a closed form! See my solution! $\endgroup$ Jul 31, 2014 at 19:10

2 Answers 2

2
$\begingroup$

there is a solution to your problem. First of all, let us consider the problem $$\mathcal{P}:\\ z : = \max_{\mathbf{F}} Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\} {\rm ~~s.t.~~~} Tr(\mathbf{F} \mathbf{F}^H) \leq p. $$

Let $\mathbf{F}_\star$ the solution to the above problem. It is clear that if $ z < a Tr(\mathbf{F}_\star \mathbf{F}_\star^H) $, then $\mathbf{F} = \mathbf{0}$ is the solution to your problem. Otherwise, $\mathbf{F}_\star$ is the also the solution to your problem and $Tr(\mathbf{F}_\star {\mathbf{F}_\star}^H) = p$.

Now have a deeper look at $\mathcal{P}$. As $\mathbf{C}$ is a Hermitian matrix, there exists the eigendecomposition $\mathbf{C} = \mathbf{U} \Sigma \mathbf{U}^H $, where $\mathbf{U}$ is an orthonormal matrix and $\Sigma $ is a diagonal matrix with real-valued entries $\sigma_1,\dots,\sigma_N$. For simplification, and without loss of generality we assume that $\mathbf{F} = \mathbf{U} \mathbf{H}$. Then, we can rewrite $\mathcal{P}$ as $$ \mathcal{Q}: \\ \max_{\mathbf{H}} Re\{\mathbf{b}\mathbf{H}^H \Sigma \mathbf{H} \mathbf{d}\} {\rm ~~s.t.~~~} Tr(\mathbf{H} \mathbf{H}^H) = p. $$ here we have exploited the fact that $ \mathbf{U}^H \mathbf{U} = \mathbf{I}$ and $ tr( \mathbf{FF}^H)= tr( \mathbf{U}\mathbf{H} ( \mathbf{U} \mathbf{H})^H) = tr(\mathbf{HH}^H$). As $\Sigma$ is diagonal we can reformulate the cost function as $ Re\{\mathbf{b}\mathbf{H}^H \Sigma \mathbf{H} \mathbf{d}\} = Re\{\sum_{n=1}^N \sigma_i \mathbf{b} \mathbf{h}_n^H \mathbf{h}_n \mathbf{d} \} = \sum_{n=1}^N Re\{\sigma_n \mathbf{h}_n \mathbf{d} \mathbf{b} \mathbf{h}_n^H \}$, where $\mathbf{h}_n$ is the $n$th column of $\mathbf{H}$. Further, we see that $Re\{\sigma_n \mathbf{h}_n \mathbf{d} \mathbf{b} \mathbf{h}_n^H \} = \mathbf{h}_n(\sigma_n\frac{1}{2}(\mathbf{d} \mathbf{b} +\mathbf{b} \mathbf{d})) \mathbf{h}_n^H$. Defining the matrix $\mathbf{Q}_n:= \sigma_n\frac{1}{2}(\mathbf{d} \mathbf{b} +\mathbf{b}^H \mathbf{d}^H)$, we can finally rewrite $\mathcal{Q}$ as
$$ \mathcal{R}: \\ \max_{\{\mathbf{h}_n\}_{n=1}^N} \sum_{n=1}^N \mathbf{h}_n\mathbf{Q}_n \mathbf{h}_n^H {\rm ~~s.t.~~~} \sum_{n=1}^N \| \mathbf{h}_n\|^2 = p. $$ From the definition it is clear that each $\mathbf{Q}_n$ is a Hermitian matrix of rank two. All of these matrices have the (same) two eigenvectors $\mathbf{q}_1$ and $\mathbf{q}_2$ with (different ) eigenvalues $\lambda_{1,n}$ and $\lambda_{2,n}$. It is clear that vector components in $\mathbf{h}_n$ that are orthogonal to $\mathbf{q}_1$ and $\mathbf{q}_2$ have no influence on the cost function of $\mathcal{R}$ but increase the constraint value. Therefore, we assume without loss of optimality that $\mathbf{h}_n = c_{1,n}\mathbf{q}_1 +c_{2,n} \mathbf{q}_2 $. Then $\mathcal{R} $ boils down to $$ \max_{\{{c}_{1,n},{c}_{2,n}\}_{n=1}^N} \sum_{n=1}^N (\lambda_{1,n}|c_{1,n}|^2+\lambda_{2,n}|c_{2,n}|^2) {\rm ~~s.t.~~~} \sum_{n=1}^N (|c_{1,n}|^2+|c_{2,n}|^2) = p. $$ Solution

The solution to the above problem is simple: Let $i_\star,n_\star = \arg \max \lambda_{i,n}$, then $|c_{i_\star,n_\star}|^2= p $ and $|c_{i,n}|^2= 0 $. Consequently, the solution matrix $\mathbf{H}_\star$ has only one non-zero row (the $n_\star$th row) which is given by $(p)^{0.5} \mathbf{q}_{i_\star}$.

Consequently, $\mathbf{F}_\star =\mathbf{U} \mathbf{H}_\star $ and $z = p \lambda_{i_\star,n_\star} $.

All the best, Ert

$\endgroup$
9
  • $\begingroup$ I do not understand your claim 'It is clear that...': for which (F) are you assuming the inequality (for all, or there exists)? $\endgroup$ Aug 1, 2014 at 15:57
  • $\begingroup$ I've corrected some mistakes in my post, maybe it is clearer now. $\endgroup$ Aug 1, 2014 at 18:25
  • $\begingroup$ I wish I was :-) You are welcome. $\endgroup$ Aug 3, 2014 at 9:24
  • $\begingroup$ Correct me if I am wrong, but $F^HCF\neq H^H\Sigma H$, since $F^HCF=(HU)^H U\Sigma U^H HU=U^H HU\Sigma U^H HU$ (unless $U$ and $H$ commute, which is not true in general). $\endgroup$ Aug 4, 2014 at 4:16
  • $\begingroup$ You are right. It should be $F = UH$ and not the other way around. Thank you for improving my answer! $\endgroup$ Aug 4, 2014 at 8:19
0
$\begingroup$

Consider the following argument. The cost function is a quadratic in the optimization variables and the constraint is the same as well.

Such optimization problems can be solved in polynomial time (see "https://epubs.siam.org/doi/10.1137/S105262340139001X"), using SDP relaxation. What is essentially proved in the paper is that the relaxation gap is zero in such optimization problems, even when the cost function and/or constraint are non-convex quadratics.

$\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.