5
$\begingroup$

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}$enter image description here

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.

$\endgroup$
2
  • $\begingroup$ In general $x^* A x \neq x^* A^* x$. You need to write $x^* A x = \overline{x^* A^* x}$ $\endgroup$
    – obareey
    Sep 1, 2021 at 15:02
  • $\begingroup$ @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? $\endgroup$
    – Lee
    Sep 2, 2021 at 3:00

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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} $\endgroup$
    – Lee
    Sep 3, 2021 at 4:07
  • $\begingroup$ 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. $\endgroup$
    – obareey
    Sep 3, 2021 at 9:34
  • $\begingroup$ 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. $\endgroup$
    – Lee
    Sep 3, 2021 at 9:40

You must log in to answer this question.

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