3
$\begingroup$

I am interested in an optimization problem of the form $$\min_{\boldsymbol z} \max_j \vert f_j(\boldsymbol z) \vert = \min_{\boldsymbol z} \Vert f_j(\boldsymbol z) \Vert_\infty. $$ Here, the optimization/decision variables are $\boldsymbol z \in \mathbb C^{N} $ and $f_i: \mathbb C^N \to \mathbb C$.

The $f_j$ are essentially polynomials in $\lambda_j \in \mathbb C$ $$f_j(\boldsymbol z ) = \prod_{k=1}^N \big(1 - z_k \lambda_j\big).$$

To provide some more context, I am essentially trying to optimize the common roots of complex polynomials. Write the polynomial $p(\lambda) $ with $p(0) = 1$ as $$p(\lambda) = \prod_{k=1}^N \bigg(1 - \frac{ \lambda}{\tilde z_k} \bigg)$$ where $\tilde z_k$ are the roots of the polynomial. For $z_k := 1/\tilde z_k$ you obtain the representation above.

In principle, one has also to enforce that the roots come in complex-conjugated pairs which would give a linear constraint like $$A \boldsymbol z = \boldsymbol 0.$$

$\endgroup$
3
  • $\begingroup$ Of relevance: Application of complex numbers in Linear Programming? $\endgroup$
    – TheSimpliFire
    Jun 17 at 12:22
  • $\begingroup$ Without additional constraints, I don't see how the maximum could exist. Let $\boldsymbol{z}_0 \in \mathbb C^{N}$ be such that $\vert f(\boldsymbol{z}_0) \vert \leq 1.$ Then for any $\alpha > 1,$ $ \vert f(\alpha \boldsymbol{z}_1) \vert \leq 1,$ where $\boldsymbol{z}_1 = \boldsymbol{z}_0 / \alpha.$ $\endgroup$
    – prubin
    Jun 17 at 15:17
  • $\begingroup$ @prubin Yeah you are absolutely right. I re-formulated the problem. $\endgroup$
    – Dan Doe
    Jun 18 at 10:14

1 Answer 1

1
$\begingroup$

I sat down and worked a bit on this. Since I am only interested in the magnitude of the polynomial it might be helpful to employ the polar representation, i.e., $1 - z_j \lambda = r_j e^{i\phi_j}$. Then,

\begin{align} &\left \vert \prod_{j=1}^N 1 - z_j \lambda \right\vert = \left \vert \prod_{j=1}^N r_j e^{i\phi_j}\right\vert = \left \vert \left(\prod_{j=1}^N r_j \right) \cdot \exp \left( \sum_{j=1}^N i\phi_j\right)\right\vert \\ =&\left \vert \left(\prod_{j=1}^N r_j \right) \right \vert \cdot \left \vert \exp \left( \sum_{j=1}^N i\phi_j\right)\right\vert = \left \vert \left(\prod_{j=1}^N r_j \right) \right \vert \cdot 1= \prod_{j=1}^N r_j \end{align}

Now let's take a closer look on the $r_j$. Write $z_j = a_j + b_j i $, $\lambda = c+d i$. Then, $$r_j = \sqrt{\big[1 - \text{Re} (z_j \lambda)\big]^2 + \text{Im}^2 (z_j \lambda)}$$ Note that $$\text{Re} (z_j \lambda) = a_jc -b_jd, \text{Im} (z_j \lambda) = a_jd + b_j c $$ one obtains a formulation with no complex variables involved at all! The optimization is now over $\boldsymbol a, \boldsymbol b$. While the problem is of course highly nonlinear and most likely very complicated, my main concern could be lifted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.