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
    Commented 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.
    Commented 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
    Commented Jun 13, 2017 at 5:55
  • $\begingroup$ What is the cardinality of $U$? Is it $n$? Or greater than $n$? $\endgroup$
    – Rodrigo de Azevedo
    Commented Jun 13, 2017 at 14:26
  • $\begingroup$ @RodrigodeAzevedo It is greater than $n$ in general. $\endgroup$
    – F.G.
    Commented 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
    Commented Jun 13, 2017 at 13:45

You must log in to answer this question.

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