Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@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

2 Answers 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.

share|improve this answer
    
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.

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.