Finding the least point of numerical range which lies on real axis

Given $$A\in\mathbb{C}^{n\times n}$$, its numerical range is $$W(A):=\{(\Re (x^*Ax),\Im(x^*Ax)) :x^*x=1\}\subseteq \mathbb{C}^2$$. $$W(A)$$ is a convex set.

An example of $$W(A)$$ plot is given in the figure below (red line is the boundary of $$W(A)$$).

$$\hspace{6cm}$$

Given $$A$$, I want to find the point on the boundary of $$W(A)$$, the point which is minimum on the real-axis (blue point on the figure).

I think we need to minimize real-coordinate and make a constraint that imaginary-coordinate is zero: $$\begin{array}{ll} \underset{x\in\mathbb{C}^{n}}{\text{min}} & \Re(x^*Ax)\\ \text{s.t.} & \Im(x^*Ax)=0,\\&x^*x=1.\end{array}$$

Since $$\Re(x^*Ax)=\frac{A+A^*}{2}$$ and $$\Im(x^*Ax)=\frac{A-A^*}{2i}$$, we get this problem

$$\begin{array}{ll} \underset{x\in\mathbb{C}^{n}}{\text{min}} & x^*(\frac{A+A^*}{2})x\qquad=&\underset{x\in\mathbb{C}^{n}}{\text{min}} & \frac{1}{2}(x^*Ax+x^*A^*x)\qquad=&\underset{x\in\mathbb{C}^{n}}{\text{min}} & x^*Ax\\ \text{ s.t.} & x^*(\frac{A-A^*}{2i})x=0,&\text{ s.t.} & x^*Ax=x^*A^*x,&\text{ s.t.} & x^*x=1\\&x^*x=1&&x^*x=1\end{array}$$

But $$x^*Ax$$ might be complex in general and minimization of $$x^*Ax$$ is not possible then, I couldn't find where I am doing wrong.

• In general $x^* A x \neq x^* A^* x$. You need to write $x^* A x = \overline{x^* A^* x}$ Commented Sep 1, 2021 at 15:02
• @obareey yes in general $x^* A x \neq x^* A^* x$, but can't we write that because of the $\Im(x^*Ax)=x^*(\frac{A-A^*}{2i})x=0$ constraint?
– Lee
Commented Sep 2, 2021 at 3:00

I believe you cannot directly substitute the constraint into the optimization problem. This is not a complete answer but at least it reduces the search space to one dimension. Firstly we can convert the problem into a real one by defining $$A=B+iC$$ and $$x=y+iz$$ where entities of $$B,C,y,z$$ are real. Now

\begin{align*} x^*Ax &= (y^T-iz^T)(B+iC)(y+iz)\\ &= \left[ y^TBy+z^TBz+z^T(C-C^T)y\right]+i\left[y^TCy+z^TCz+y^T(B-B^T)z\right]\\ &= \begin{bmatrix}y^T&z^T\end{bmatrix}\begin{bmatrix}B&0\\C-C^T&B\end{bmatrix}\begin{bmatrix}y\\z\end{bmatrix}+i\begin{bmatrix}y^T&z^T\end{bmatrix}\begin{bmatrix}C&B-B^T\\0&C\end{bmatrix}\begin{bmatrix}y\\z\end{bmatrix} \end{align*}

which is now equivalent to the problem

$$\min_{u \in \mathbb{R}^n} u^T X u ~~~~ s.t.~~ u^T Y u = 0,~~ u^T u = 1$$

for real $$X$$ and $$Y$$. The Lagrange multipliers for this problem can be written as

$$L := u^T X u - \alpha u^T Y u - \beta (u^T u - 1)$$

The solution must satisfy

\begin{align*} \frac{\partial L}{\partial u} &= 0 \Rightarrow \left[(X+X^T)-\alpha(Y+Y^T)\right]u = 2 \beta u \\ \frac{\partial L}{\partial \alpha} &= 0 \Rightarrow u^T Y u = 0 \\ \frac{\partial L}{\partial \beta} &= 0 \Rightarrow u^T u = 1 \end{align*}

Now an algorithm to find a minimum would be calculating the eigenvectors of the matrix $$(X+X^T)-\alpha(Y+Y^T)$$ for varying $$\alpha$$ and checking if $$u^T Y u=0$$. Then the solution would be the minimum $$\beta$$ over all such eigenvectors.

• it is what you mean: \begin{array}{ll} \underset{u\in\mathbb{R}^{n},\alpha}{\text{min}} & u^T((X+X^T)-\alpha(Y+Y^T))u\\ \text{s.t.} & u^TYu=0,\\&u^Tu=1,\\&\alpha\geq0\end{array}
– Lee
Commented Sep 3, 2021 at 4:07
• This problem would give exactly the same solution as above, so I guess they are equivalent but redundant. Writing the problem like this doesn't help for calculating the solution. Commented Sep 3, 2021 at 9:34
• thanks for your answer. I am trying to understand how I can program it. Since $\alpha$ is varying from zero to infinity, calculating all eigenvectors looks impossible.
– Lee
Commented Sep 3, 2021 at 9:40