Let the optimization problem be
\begin{equation}
 \max\_{\phi\_n} \left|\sum\_{n=1}^N e^{i\phi\_n} a\_n \right|,
\end{equation}
where $a\_n\in\mathbb{C}$ and the optimization variables have discrete phase shifts $\phi\_n\in\{0,\frac{1}{M}2\pi\ldots,\frac{M-1}{M}2\pi\}$ for some positive integer $M$.


Can this problem's exact solution be computed efficiently?


**Edit:** By efficient I mean that complexity does not grow exponentially with $N$.



Does this simple non-convex problem involving discrete phase shifts have an exact solution?
So indeed it exists an efficient algorithm for computing the solution to this non-convex problem.


Let $\delta=2\pi/M$ and let $\angle$ denote the phase of a complex number (in radians). Upon defining $r\_n=e^{i\phi\_n}a\_n$, the optimization problem can be recast as
\begin{equation}
 \max\_{r\_n} \left|\sum\_{n=1}^N r\_n\right|,
\end{equation}
subject to $|r\_n|=|a\_n|$ and $\angle r\_n=\angle a\_n+\delta \, k\_n$ for some integer $k\_n$ and for all $n$. If this problem is solved, then the solution to the original problem is $\phi\_n=\delta \, k\_n$ for all $n$.


It is not too hard to prove (left as an exercise to the reader) that any globoal maximizer satisfies
\begin{equation}
 \left|\angle r\_n- \angle r\_p\right|\_{\text{wa}}\leq\delta
\end{equation}
for any $n,p$. Here, $|\angle r\_n- \angle r\_p|\_{\text{wa}}$ is the wrap-around phase difference, so as an example, for $\angle r\_n =\frac{3\pi}{2}$ and $\angle r\_p =0$, the phase difference is $\frac{\pi}{2}$ and not $\frac{3\pi}{2}$.


The above conclusion can be expressed as
\begin{equation}
 \psi\leq \angle r\_n \leq\psi+\delta,
\end{equation}
for an unknown $\psi$ and for all $n$ such that $a\_n \neq 0$. Furthermore, it exists only one feasible value of $r\_n$ satisfying the above condition (except if $\angle a\_n = \psi$, in which case $\angle a\_n = \psi+\delta$ is also feasible). Therefore, the problem boils down to a 1-dimensional search over $\psi$.


With this in mind, the global maximizer can be found with the following algorithm:


1. let $\Omega\_n$ be a permutation such that $0\leq \operatorname{mod}(\angle a\_{\Omega\_1},\delta)\leq\cdots\leq\operatorname{mod}(\angle a\_{\Omega\_N},\delta)$
2. set $v\_n$ such that $|v\_n|=|a\_{\Omega\_n}|$ and $\angle v\_n=\operatorname{mod}(\angle a\_{\Omega\_n},\delta)$ for $n=1,\ldots,N$
3. initialize $S=0$
4. **for** $p=1,\ldots,N$ **do**
5. $\hspace{3ex}$ **if** $|\sum\_{n=1}^N v\_n|>S$ **then**
6. $\hspace{6ex} S=|\sum\_{n=1}^N v\_n|$
7. $\hspace{6ex} \phi\_{\Omega\_n} = \angle v\_n-\angle a\_{\Omega\_n}$
8. $\hspace{3ex}$ **end if**
9. $\hspace{3ex} \angle v\_p \leftarrow \angle v\_p + \delta$
10. **end for**


