5
$\begingroup$

Given $A\in\mathbb{C}^{n\times n}$, such that it has singular values larger than $1$ and smaller than $1$,

\begin{array}{ll} \underset{x\in\mathbb{C^n}}{\text{minimize}} & x^*(A+A^*)x.\\ \text{subject to} & x^*A^*Ax=1,\\&x^*x=1\end{array}


My attempt: I couldn't get anything done for general $A$. Assume $A$ is hermitian, then $A=U\Sigma U^*$, where $U$ is unitary and $\Sigma$ is real diagonal. Let $y=U^*x$, then

\begin{array}{ll} \underset{y\in\mathbb{C^n}}{\text{minimize}} & 2y^*\Sigma y.\\ \text{subject to} & y^*\Sigma^2y=1,\\&y^*y=1\end{array}

Using Lagrange multiplier, we can find: $L(y,\lambda_1,\lambda_2)=2y^*\Sigma y-\lambda_1(y^*\Sigma^2y-1)-\lambda_2(y^*y-1)$. Then

\begin{align} &\frac{\partial L(y,\lambda_1,\lambda_2)}{\partial y}=4\Sigma y-2\lambda_1\Sigma^2y-2\lambda_2y=0 \end{align}

gives us $y_i=0$ or $\lambda_1\sigma_i^2-2\sigma_i+\lambda_2=0$ for all $i=1,2,\ldots,n.$

From $\lambda_1\sigma_i^2-2\sigma_i+\lambda_2=0$, we can get $\sigma_i=\frac{1\pm\sqrt{1-\lambda_1\lambda_2}}{\lambda_1}$, so here I think that if there are many distinct $\sigma_i$'s, then we will get $\sigma_{j_1}=\frac{1+\sqrt{1-\lambda_1\lambda_2}}{\lambda_1}$, $\sigma_{j_2}=\frac{1-\sqrt{1-\lambda_1\lambda_2}}{\lambda_1}$ (here $j_i$ is any number from $1$ to $n$), and $y_k=0$ for all $k\neq j_2$ and $k\neq j_1$.

From $\sigma_{j_1}=\frac{1+\sqrt{1-\lambda_1\lambda_2}}{\lambda_1}$, $\sigma_{j_2}=\frac{1-\sqrt{1-\lambda_1\lambda_2}}{\lambda_1}$, we can find that $\lambda_1=\frac{2}{\sigma_{j_1}+\sigma_{j_2}}$ and $\lambda_2=\frac{2\sigma_{j_1}\sigma_{j_2}}{\sigma_{j_1}+\sigma_{j_2}}$.

From this observations, I got impression that for Hermitian $A$, original problem is equivalent to

\begin{array}{ll} \underset{y\in\mathbb{C^2}}{\text{minimize}} & 2y^*\begin{bmatrix} \sigma_{j_1} & \\ & \sigma_{j_2} \end{bmatrix} y\quad=\quad\underset{\sigma_{j_1},\sigma_{j_2}}{\text{minimize}} &\sigma_{j_1}\sqrt{\frac{1-\sigma_{j_2}^2}{\sigma_{j_1}^2-\sigma_{j_2}^2}}+\sigma_{j_2}\sqrt{\frac{\sigma_{j_1}^2-1}{\sigma_{j_1}^2-\sigma_{j_2}^2}}\\ \text{subject to} & y^*\begin{bmatrix} \sigma_{j_1} & \\ & \sigma_{j_2} \end{bmatrix}^2y=1,&\sigma_{j_1}>1\\&y^*y=1&\sigma_{j_2}<1\end{array}

when $y_1=\sqrt{\frac{1-\sigma_{j_2}^2}{\sigma_{j_1}^2-\sigma_{j_2}^2}}$ and $y_2=\sqrt{\frac{\sigma_{j_1}^2-1}{\sigma_{j_1}^2-\sigma_{j_2}^2}}$.


Can you please tell me if the above calculations make sense? Any help on solving (analytically or numerically) the original problem for general $A$ would be appreciated.

$\endgroup$
3
  • $\begingroup$ You may well be familiar with this, but just in case, this seems relevant: en.wikipedia.org/wiki/Rayleigh_quotient $\endgroup$
    – Blitzer
    Jun 12, 2021 at 6:17
  • 2
    $\begingroup$ When $A$ is general, it boils down to finding $\min x^{\ast} B x$ subject to $x^{\ast}Dx = 1$ and $x^{\ast}x = 1$? You may find literature for QCQP with two constraints. $\endgroup$
    – River Li
    Jun 14, 2021 at 2:30
  • $\begingroup$ @RiverLi thanks, I got semidefinite relaxation of original problem using your tip $\endgroup$
    – Lee
    Jun 15, 2021 at 2:47

1 Answer 1

2
$\begingroup$

Using tip from River Li, I found the following paper.

The original problem is related to QCQPs. Following the paper, we can rewrite the original problem as

\begin{array}{ll} \underset{X\in\mathbb{C^{n\times n}}}{\text{minimize}} & \mathrm{trace}\big((A+A^*)X).\\ \text{subject to} & \mathrm{trace}(A^*A)=1,\\&\mathrm{trace}(X)=1,\\&X\geq0, \\&\mathrm{rank}(X)=1.\end{array}

First we relax the problem by removing rank constraint:

\begin{array}{ll} \underset{X\in\mathbb{C^{n\times n}}}{\text{minimize}} & \mathrm{trace}\big((A+A^*)X).\\ \text{subject to} & \mathrm{trace}(A^*A)=1,\\&\mathrm{trace}(X)=1,\\&X\geq0.\end{array}

The latest problem is called semidefinite relaxation (SDR) of original problem and it can be solved, to any arbitrary accuracy, in numerically reliable and efficient fashion.

Here is cvx code in Matlab:

A=rand(4,4)+i*rand(4,4);
n=length(A);
C=A+A';
A1=A'*A;
A2=eye(n,n);

cvx_begin
variable X(n,n) hermitian
minimize(trace(C*X));
subject to
trace(A1*X)==1;
trace(A2*X)==1;
X == semidefinite(n);
cvx_end

After we get an optimal $X$, we can find an optimal $x$ by setting $x=\sqrt{\lambda_{max}}v_{max}$, where $\lambda_{max}$ and $v_{max}$ are largest eigenvalue and corresponding eigenvector of $X$. If the choice is infeasible, we can search for the $x$ which is nearby feasible to $\sqrt{\lambda_{max}}v_{max}$.

From simulation it looks like the above method works fine for $x\in\mathbb{R^n},A\in\mathbb{R}^{n\times n}$. However, for complex matrix case, it has significant error, thus one might be careful in which application it might be used. Worst case computational complexity of SDR of general QCQP is $O(\max\{m,n\}^4n^{0.5}\log(\epsilon^{-1}))$, where $m$ is number of equality constraints and $\epsilon>0$ is a given solution accuracy.


EDIT: Let $A=\begin{bmatrix}0.0317 + 0.5409i & 0.2883 - 0.2687i & 0.3905 + 0.4125i\\ 0.0636 + 0.9737i & -0.1854 - 0.6985i & -0.3965 + 0.5332i\\ -0.7363 + 0.2243i& 0.3834 + 0.9514i & 0.6642 - 0.6453i\end{bmatrix}$

Using above cvx code, we get $\mathrm{trace}((A+A^*)X)=-0.1157$ and $X^\star=\begin{bmatrix}0.0760 & 0.2573 & 0.0637\\ 0.2573 & 0.8707 & 0.2154 \\ 0.0637 & 0.2154 & 0.0533 \end{bmatrix}$.

But for $X=xx^*$, where $x=\begin{bmatrix}-0.4494 - 0.3663i&-0.3750 + 0.7123i&0.1261 + 0.0000i\end{bmatrix}^T$, we get $\mathrm{trace}((A+A^*)X)=-1.4517.$

$\endgroup$
16
  • 1
    $\begingroup$ It is nice. I remember there are papers to ensure that there SD relaxation has the same optimal objective value as the original one, for QCQP with two constraints. $\endgroup$
    – River Li
    Jun 15, 2021 at 3:20
  • $\begingroup$ @RiverLi I was searching for the reference that will guarantee that SD relaxation of my problem will have same optimal objective as original one. I found this paper: epubs.siam.org/doi/pdf/10.1137/S105262340139001X. It is above my level of mathematical understanding, but I tried to pick up important points. Can I say that my problem is considered under Theorem 2.5? I think that Slater's regulariy condition is not satisfied in my case, because we have equality constraints, thus SDR is suboptimal? $\endgroup$
    – Lee
    Jul 9, 2021 at 10:38
  • 1
    $\begingroup$ I knew this paper. Not this one. $\endgroup$
    – River Li
    Jul 9, 2021 at 11:20
  • $\begingroup$ @RiverLi I wonder if we can chat regarding this problem? $\endgroup$
    – Lee
    Jul 14, 2021 at 8:39
  • 1
    $\begingroup$ Yes, this is one of the papers I referred to. There are some papers about this topic by these authors. $\endgroup$
    – River Li
    Jul 14, 2021 at 11:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .