In order to solve this over-determined system of equations numerically: $$ f_l(\mathbf x) = \displaystyle \left \lvert \sum_{k=1}^Kx_k^2e^{-j\frac{2\pi}Np_kl} \right \rvert , \qquad P = \{p_1,p_2,\cdots,p_K\} \subset\{1,2,\cdots,N\} $$ $$ f_1(\mathbf x) = f_2(\mathbf x) = \cdots=f_{N-1}(\mathbf x) $$ I suggested minimizing this function : $$ h(\mathbf x) = \sum_{l=1}^{N-2}\left \lvert f_l(\mathbf x)-f_{l+1}(\mathbf x)\right \rvert^2 $$ I want to know what optimization method is most suitable for this function? I couldn't imagine how extremums of $h(\mathbf x)$ are distributed, to select one optimization method, Do you have any idea?

I've plotted it with respect to $x_1$ and $x_2$, for the case $\mathbf x \in \mathbb R^4$ and setting $x_3$ and $x_4$ a constant. here are plots of different views: enter image description here enter image description here enter image description here

  • 1
    $\begingroup$ I don't understand your notation for $P$. What exactly are the $p$s? Unknown integers between 1 and $N$ that are also being solved for? Can there be duplicates? What is $K$? $\endgroup$ – user7530 Jul 30 '13 at 8:38
  • $\begingroup$ $p_i$'s are distinct integers between $1$ and $N$ which are given. $K$ is an integer less than $N-2$. $\endgroup$ – user87882 Jul 30 '13 at 8:57

First, notice that since the $f$s are nonnegative, $$f_1(x) = f_2(x) = \ldots = f_{N-1}(x)$$ is equivalent to $$f_1(x)^2 = f_2(x)^2 = \ldots = f_{N-1}(x)^2.$$ This second system of equations is nicer to deal with since each term is a quartic polynomial (quadratic in $y_k = x_k^2$).

Your approach might work: try minimizing the function $\tilde{h}(y) = \sum (f_{i+1}(y)^2 - f_{i}(y)^2)^2$ using e.g. Newton's method (the Jacobian and Hessian are trivial to compute) and hope you find a global minimum (a minimum of residual zero) and not a local one.

Alternatively, you can try specialized software packages for finding solutions to polynomial equations, for instance PHCpack.

  • $\begingroup$ Which numerical optimization is best for finding global minimum and avoids local ones? Thanks $\endgroup$ – user87882 Jul 30 '13 at 18:36
  • $\begingroup$ There is no general approach. Sometimes you can prove you have found all of the critical points (univariate polynomials). Sometimes you can partition the function into convex pieces, or use branch-and-bound techniques to prove that the global minimum must lie in some (locally convex) region. You can use numerical methods like simulated annealing to try to "escape" local minima (but there are no guarantees.) $\endgroup$ – user7530 Jul 30 '13 at 18:43
  • $\begingroup$ I've developed an SD algorithm. Actually it converges, but the output is not always the real minimum which is obtained through combinatorial search. What would be the problem? $\endgroup$ – user87882 Jul 30 '13 at 18:45
  • $\begingroup$ What do you mean by SD? $\endgroup$ – user7530 Jul 30 '13 at 18:46
  • $\begingroup$ Steepest Descent $\endgroup$ – user87882 Jul 30 '13 at 18:46

You can also try direct methods that use just values of function for optimization, e.g. DIRECT, particle swarm optimization and so on. And, of course, try already written software first.

  • $\begingroup$ Would you mind telling me what are direct methods? I've taken course "Numerical Optimization" as a graduate course, but I haven't heard of that $\endgroup$ – user87882 Aug 3 '13 at 19:46
  • $\begingroup$ Well, this is a class of methods that use knowledge of only function values for optimization purposes. They don't need to know the derivatives of function or Hessian, some of them even don't approximate derivatives during the process. $\endgroup$ – Evgeny Aug 4 '13 at 5:00

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.