Maximizing the sum of rotated vectors

Question

I came across an optimization problem as \begin{equation*} \underset{\{\theta_i\}_{i=1}^n}{\max}\quad\left\Vert\mathbf{y}+\sum_{i}^ne^{\jmath\theta_i}\mathbf{x}_i\right\Vert, \end{equation*} where $\mathbf{x}_i$ and $\mathbf{y}$ are $m$-dimensional vectors. I wonder if there exists global optimal solution to this problem.

Answer 1

The set of complex numbers of the form $e^{\imath \theta}$ are exactly the complex numbers whose absolute value is $1$. Hence, your optimization problem can be written as $$ \begin{aligned} \max_{\mathbf{z}} &\quad \| \mathbf{X} \mathbf{z} + \mathbf{y} \| \\ \text{s.t.} &\quad |z_i| = 1 &i = 1, \dots, n \end{aligned} $$ where $\mathbf{X}$ is the matrix whose columns are the vectors $\mathbf{x}_i$. Looking at the real decision variables $\Re(z_i)$ and $\Im(z_i)$, this is a very hard optimization problem which has no known globally optimal solution method, except for, maybe, branch and bound methods (which may be very slow).