9
$\begingroup$

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?

  • 0
    @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.2010-10-18
  • 0
    You're right, I realized that when I started working it out, so I deleted my comment.2010-10-18
  • 0
    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.2010-10-18
  • 0
    @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.2010-10-18
  • 0
    You might want to try posting this question on the Operations Research Exchange: http://www.or-exchange.com/2010-10-18

2 Answers 2

1

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.

  • 0
    With the constraint $x^TA^TAx = 1$, it can also be modeled as Rayleigh Quotient, which can be solved exactly and efficiently. See http://en.wikipedia.org/wiki/Rayleigh_quotient2013-07-26
0

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.

  • 0
    @Mostafa: I don't think the problem is convex. When I tried to solve it with generic tools, I encountered many local minima.2010-11-09