7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Jun 13, 2017 at 0:39
  • $\begingroup$ @fedja My bad, that is indeed what I meant. Sorry about this. I have now edited the question. $\endgroup$
    – F.G.
    Jun 13, 2017 at 0:55
  • $\begingroup$ 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. $\endgroup$
    – user35593
    Jun 13, 2017 at 5:55
  • $\begingroup$ What is the cardinality of $U$? Is it $n$? Or greater than $n$? $\endgroup$
    – Rodrigo de Azevedo
    Jun 13, 2017 at 14:26
  • $\begingroup$ @RodrigodeAzevedo It is greater than $n$ in general. $\endgroup$
    – F.G.
    Jun 13, 2017 at 14:33

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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^*$. $\endgroup$
    – Nathaniel Johnston
    Jun 13, 2017 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.