# A numerical optimization problem with a convolution in the constraint

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?

-
@Rahul: I think with a Fourier transform I can convert the constraint to the form $\|Fx\|_4 = 1$, where $F$ is some form of the orthogonal Fourier matrix. But I don't know how to proceed from here, too. – AgCl Oct 18 '10 at 19:07
You're right, I realized that when I started working it out, so I deleted my comment. – Rahul Oct 18 '10 at 19:12
Is your difficulty with the constraint only or with both the objective and the constraint? I can show you how to expressive the objective in standard quadratic programming form, but if you already know how to do that I won't bother. – Mike Spivey Oct 18 '10 at 22:13
@Mike: My main difficulty is with the constraint. I think I can convert the objective to a standard quadratic form. But I would appreciate any suggestions, possible keywords for searching the literature for L^4 norm equality constrained quadratic programming. – AgCl Oct 18 '10 at 22:56
You might want to try posting this question on the Operations Research Exchange: or-exchange.com – Mike Spivey Oct 18 '10 at 23:33

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.

-
With the constraint $x^TA^TAx = 1$, it can also be modeled as Rayleigh Quotient, which can be solved exactly and efficiently. See en.wikipedia.org/wiki/Rayleigh_quotient – Yuandong Jul 26 '13 at 12:05

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.

-
@Mostafa: I don't think the problem is convex. When I tried to solve it with generic tools, I encountered many local minima. – AgCl Nov 9 '10 at 0:48