An optimization problem with variables on the exponential of a complex number

Question

$$\min_t \quad\operatorname{Re} \sum\limits_{i = 1}^N {\left( {{e^{ - j2\pi {f_i}t}}{r_i}} \right)}, $$where $\operatorname{Re}$ refers to get the real part of a complex number, $\{f_i\}$ is an arithmetic progression with $i = 1,2,...,N$, ${r_i} \in \mathcal{Z}$ are with unequal modulus and angles.

This is a question from the field of signal processing, and $j$ refers to the imaginary unit, $N=128$, $f_i=f_c+\frac{B}{N}\left(i-1-\frac{N-1}{2}\right), \text { for } i=1,2, \ldots, N$, $f_c = 3*10^{11}$, $B=3*10^{10}$.

Answer 1

What I would start with is the following:

Let $x=\frac BNt$ be a new variable. Let's write the function as $$ G(x)=\Re[e^{-2\pi i Ax}P(x)],\quad P(x)=\sum_{k=1}^N r_ke^{-2\pi i (k-1-\frac N2)x} $$ with $A=\frac{f_cN}B+\frac 12$. If I take your values $f_c$ and $B$ literally, then I can say that $A=1280.5$. If they (or one of them) are actually some frequencies, you cannot be that precise, but you can still, probably, say that $1280<A<1281$.

Now what I suggest to do is just to find $P(x)$ for $2560$ equidistant points $x_j$ on $[0,1]$ (that is just 20 FFT's on 128 points each) and declare $-Q$ where $Q=\max_j |P(x_j)|$ the approximate answer.

The logic behind it is the following. $P(x)$ is a trigonometric polynomial of degree $N/2=64$, so if $M$ is the true maximum of $|P(x)|$, then within the distance $\delta=\frac 12\frac1{ 2560}$ from $M$, we have $$ |P(x)|\ge M-\frac 12\max|P''|\delta^2\ge M(1-2\pi^2(N/2)^2\delta^2)=M(1-\frac{\pi^2}8\frac 1{400}) $$ and that interval contains one of your equidistant points, so $Q$ is an underestimate of $M$ with precision about 0.3%.

Now let's return to the first factor $e^{-2\pi iAx}$. In the worst case scenario when $A$ is a half-integer (I hope that the frequency precision is enough to keep $A$ non-integer; otherwise the error estimate will quadruple and become 1.2%), you can place any particular phase within distance $1/(4A)$ from the point of maximum of $P(x)$ on some period, so, since that distance is essentially the same $\delta$ as we used before, we conclude that the true value of the minimum lies in the same range as $-Q$.

Does it make sense to shoot for higher precision? I would say "No" because if your $B$ of $f_c$ is not that exact number you mentioned but deviates from it by an arbitrarily small amount making $A$ irrational, you get the true minimum value $-M$ immediately while for a true half-integer it can deviate from $-M$ by $0.3%$ and for an integer by $1.2%$ with the ratio $A/B$ about $10$. So, unless your frequencies are absolutely exact, I wouldn't bother to go any further.