0
$\begingroup$

Let $\mathbf{A}_1,\dots,\mathbf{A}_L$ be $N\times N$ hermitian matrices. Define the mapping from the $N-$dimensional unit sphere to $\mathbb{R}^L$ as \begin{align} \mathcal{S}=\{\left(\mathbf{u}^H\mathbf{A}_1\mathbf{u},\dots,\mathbf{u}^H\mathbf{A}_L\mathbf{u}\right)\in\mathbb{R}^L\mid \mathbf{u}^H\mathbf{u}=1\} \end{align} $\mathcal{S}$ is defined as the joint numerical range of matrices $\mathbf{A}_i$. Let $\mathbf{x}\in\mathcal{S}$, so that $\mathbf{x}=[x_1,\dots,x_L]^T$ is a $L\times 1$ real vector and $x_i=\mathbf{u}^H\mathbf{A}_i\mathbf{u}$ for some $\mathbf{u}$ from unit sphere. Consider the optimization problem \begin{align} \min_{\mathbf{x}\in\mathcal{S}}~&f_0(\mathbf{x}) \\ \text{subject to}~~~~~~~~~~~~~~&~~f_k(\mathbf{x})\leq 0,~~k=1,\dots,K \end{align} where all $f_0(.),\dots,f_K(.)$ are affine functions of $\mathbf{x}$.

Is this a convex optimization problem? How do I approach it? Actually, I would like to address the more complicated case where $f_k(.)$ are all convex functions of $\mathbf{x}$. However any direction in this regard is also fine?

Improve this question
$\endgroup$
6
  • $\begingroup$ This paper may be of your interest: resnet.wm.edu/~cklixx/poon-1.pdf $\endgroup$
    – Tadashi
    Commented Jul 9, 2014 at 13:48
  • 1
    $\begingroup$ No, this is not a convex optimization problem in general, since the joint numerical range is not convex in general. Optimization problems of this form are NP-hard in general. In your problem, does it make sense to just explicitly optimize over the convex hull of $\mathcal{S}$ instead of $\mathcal{S}$ itself? That would turn this into a convex optimization problem (even a semidefinite program), which can be solved easily. $\endgroup$
    – Nathaniel Johnston
    Commented Jul 9, 2014 at 18:05
  • $\begingroup$ @NathanielJohnston Yes, I would like to see that. $\endgroup$
    – dineshdileep
    Commented Jul 10, 2014 at 14:44
  • $\begingroup$ The convex hull of $\mathcal{S}$ is the set $\{ (\mathrm{Tr}(A_1\rho),\ldots,\mathrm{Tr}(A_L\rho) | \mathrm{Tr}(\rho) = 1, \rho \geq 0\}$ (where by $\rho \geq 0$ I mean that $\rho$ is positive semidefinite). You can perform the optimization over this set using semidefinite programming (for example, if you download the CVX toolbox for MATLAB, you can type the problem in MATLAB almost exactly as it is written here and it will solve it). $\endgroup$
    – Nathaniel Johnston
    Commented Jul 10, 2014 at 21:01
  • $\begingroup$ So in that case, we have to adopt a relaxation, is it? How can we solve it if we can assume $\mathcal{S}$ is convex. $\endgroup$
    – dineshdileep
    Commented Jul 11, 2014 at 5:07

0

Reset to default

You must log in to answer this question.