7
$\begingroup$

I have a PDE optimization problem, and a scalar field (which I am optimizing over) is supposed to be nonnegative everywhere in the domain. Since I am working in Fourier space for solving this problem numerically, I need to convert this non-negative constraint into Fourier domain (i.e. constraint on Fourier coefficients).

Assuming the solution is smooth, what is best way to go about it? I really can't think of anything more complicated than just choosing a (large?) grid of points in space, say $\mathbf{x_l}, l=1,2...,M$, and adding M linear constraints of the type:

$$f(\mathbf{x_l})=\sum_{j=1}^N\hat f_\mathbf{j}e^{i2\pi \mathbf{j}.\mathbf{x_l}}\geq 0.$$

I believe the smoothness of $f$ will ensure that this suffices.

Does anyone have any other ideas? Thoughts on this?

$\endgroup$
  • $\begingroup$ What kind of PDE are you trying to optimise. My understanding is that you use Fourier transform whenever you have oscillatory behaviour, otherwise I would use Z transform. $\endgroup$ – ilciavo Jul 9 '15 at 3:35
2
+100
$\begingroup$

This is more of a comment, but I believe the more common name for this is "positive trigonometric polynomial", so this book might be helpful.

One approach (http://www.mit.edu/~parrilo/cdc03_workshop/Vandenberghe.pdf) is to use the result that the polynomial $$ x(t) = r_0 + 2r_1\cos t + \cdots + 2r_n \cos nt $$ is nonnegative if and only if there is an $(n+1)\times(n+1)$ positive semidefinite matrix $Y\succeq 0$ such that $$ r_k = \mathrm{tr}(E^k Y) = \sum_{0\leq j\leq n-k} Y_{j+k,j}, \qquad E = \begin{pmatrix}0&I_n\\0&0\end{pmatrix}.$$

I'm not really too familiar with this, unfortunately, and there exist other characterizations as well.

$\endgroup$
1
$\begingroup$

This is really a comment, but I am one point short of being able to comment.

Can you show us the rest of your optimization problem, to include clearly identifying all optimization (a.k.a decision) variables, as well as other constraints?

Are your f(x1) actually linear in the optimization variables? Can you evaluate the gradient of the objective function by PDE solve as opposed to requiring finite differences?

How much (magnitude and locations) of nonnegativity violation can you tolerate? Can your objective function be evaluated if nonnegativity is violated?

Why are you assuming the solution is smooth, and even if it is, why does that mean there will not be "smooth" violations between grid points? Perhaps you want an adaptive or multi-grid approach in which the grid is made finer as the overall algorithm progress to a solution, or for instance, after initial convergence of the optimization algorithm, put in a finer grid and re-optimize, using the final solution from the coarser grid optimization as your starting value for a new optimization using a finer grid.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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