A numerical optimization problem with a convolution in the constraint

Question

I have a problem of the following form:

minimize $\|Dx\|_2$

subject to $\|x*x\|_2 = 1$

where $x\in\mathbb R^n$, $D$ is a given diagonal matrix of positive entries, and $*$ represents convolution, i.e., $(x*x)\_n = \sum \limits_{i+j=n}x_ix_j$ and $x*x\in\mathbb R^{2n-1}$.

What approach could be used in dealing with this problem numerically? Could this problem be converted to one of the known problem classes that have available solvers?

Answer 1

I think this can easily be formulated as a QCQP that with a Positive Definite matrix. Therefore the problem is convex and can be solved using interior point methods.

Answer 2

Square the cost function and solve the equivalent problem using SOCP algorithms. And you can lose the convolution by using the DFT matrix and Parseval's theorem:

$$ \|x * x\|_2 = 1 \Rightarrow (Ax)^T (Ax) = x^T A^T A x = 1 $$

where $A$ is the DFT matrix.