Minimize $x^*(A+A^*)x$ such that $x^*A^*Ax=1$ and $x^*x=1$

Question

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.

Answer 1

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