# Is the solution of this optimization problem always positive semidefinite?

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.

• Erm... When you say "basis", do you actually mean "a complete system" (the linear span is the entire space but there is no linear independence requirement). Otherwise I have difficulty seeing how the optimal solution can exist except in the most trivial cases like $x\in U$, in which case, if $U$ is an orthonormal basis, say, there is a positive definite solution $H=I$ but also a whole bunch of others (put anything you want outside the diagonal) so you should be rather careful with the exact way you state the problem. Jun 13 '17 at 0:39
– F.G.
Jun 13 '17 at 0:55
• Maybe it helps to see that your optimization problem is a linear program, i.e. we have linear constraints and a linear functional to optimize. Jun 13 '17 at 5:55
• What is the cardinality of $U$? Is it $n$? Or greater than $n$? Jun 13 '17 at 14:26
• @RodrigodeAzevedo It is greater than $n$ in general.
– F.G.
Jun 13 '17 at 14:33

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.
• One sufficient (and maybe necessary?) condition is that $xx^*$ is in the cone generated by $u_1u_1^*, \ldots, u_ku_k^*$ (where there are $k$ vectors in $U$). That is, there exists a linear combination with non-negative coefficients such that $xx^* = c_1u_1u_1^* + \cdots + c_ku_ku_k^*$. Jun 13 '17 at 13:45