We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:


$$ \sup\_H \left\{ x^\* H x \;:\; H \text{ is Hermitian},\; 0 \leq u^\* H u \leq 1 \;\forall u \in U \right\}. $$


This optimization comes up in a problem that I have been solving numerically, and to my surprise, the optimal solution $H$ seems to always be positive semidefinite (when the supremum is actually achieved). I am trying to understand whether this is a general property of the problem.


My question is thus: is the optimal $H$ necessarily positive semidefinite? If not, is there some property of the set $U$ that guarantees that the optimal solution is positive semidefinite?


One observation is that the problem is actually unbounded when the vectors in $U$ are mutually orthogonal, so we can assume this not to be the case. However, I do not see if this by itself implies the positive semidefiniteness of the optimal $H$ somehow. I would appreciate any help.



Is the solution of this optimization problem always positive semidefinite?
No, it is not always attained at a positive semidefinite matrix. The simplest example I have been able to find to demonstrate this is as follows:


\begin{align\*}
 U = \{ (1,0), (0,1), \tfrac{1}{\sqrt{2}}(1,1), \tfrac{1}{\sqrt{2}}(1,-1) \}, \quad \mathbf{x} = (1,2)/\sqrt{5}.
\end{align\*}


For this optimization problem, the optimal value is $6/5$ (easily found by LP solvers), and here is an example of a Hermitian matrix attaining this value:
\begin{align\*}
H = \begin{bmatrix}
0 & 1/2 \\ 1/2 & 1
\end{bmatrix}.
\end{align\*}


However, there is no PSD matrix attaining the same value $6/5$. I don't see a "nice" way to see this, but if you add the constraint that $H$ is PSD, then it is now a semidefinite program (and thus solvable), and now has an optimal value of $(1+\sqrt{2})^2/5 \approx 1.165\ldots \leq 6/5 = 1.2$. This could be proved rigorously by constructing the dual of the SDP if desired.


