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
    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^TA$x$ = 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 do$n$'t thi$n$k the problem is co$n$vex. When I tried to solve it with generic tools, I encountered m$a$$n$y local mi$n$ima.2010-11-09