1
$\begingroup$

Let $h_{1}, ..., h_{N} \in \mathbb{C} $

Consider minimizing the function below:

$ \min \left| \sum\limits_{i=1}^N h_{i} x_{i} \right| $

with the constraints $x_{i}^2 = 1$ i.e., $x_{i}$ can only take on the values $1$ or $-1$.

Effectively, I am trying to partition the complex elements into $2$ sets such that the sum of the complex numbers in both respective sets are close to equal to each other. Then, the difference between the sum of the 2 sets of complex numbers will be as close to $0$ as possible.

This problem can be solved using a Semi-Definite Programming (SDP) relaxation approach or using a Non-Linear Programming (NLP) approach but I am looking for a more efficient dynamic program or integer program solution which would require less than $2^n$ searches to find the optimal solution.

I have looked into the Number Partitioning Problem (Npp) (PDF) and wanted to know if there was a similar approach for a set of complex numbers rather than a set of real numbers.

$\endgroup$
3
  • $\begingroup$ It is a mixed-integer SOCP or QP. Not sure how efficient it will be though, depends on the solver. $\endgroup$
    – Michal Adamaszek
    Commented Feb 2, 2023 at 7:02
  • $\begingroup$ @MichalAdamaszek I am not sure how I can formulate it as a mixed-integer SOCP, could you please clarify that? $\endgroup$
    – CES
    Commented Feb 2, 2023 at 10:30
  • 1
    $\begingroup$ Say $x_i=2z_i-1$ where $z_i$ are binary, then let $u=\sum h_ix_i$ and treating $u$ as living in $\mathbb{R}^2$ the objective is to minimize $\|u\|_2$. $\endgroup$
    – Michal Adamaszek
    Commented Feb 2, 2023 at 10:58

0

Reset to default

You must log in to answer this question.