6
$\begingroup$

edit: tl;dr: I can coerce a lot of optimization problems to take the form of a non-linear least squares problem, but does it make sense to do so?

Suppose we have some empirical data $P=\{(x_i', y_i')\}_{i\in I}$. A non-linear least squares (NLLSQ) problem is one where we want to minimize a function of the form

$$S(\beta)=\sum_{i\in I}\left[y_i-f_\beta(x_i)\right]^2$$

where $(x_i, y_i) = (x_i', y_i')$ and $f_\beta$ is a curve with parameters $\beta$.

It seems like a lot of problems which are not naturally NLLSQ problems can be reformulated as such.

  1. If $d(x,y)$ is any metric on $\mathbb{R}$, then

    $$S_1(\beta) = \sum_{i\in I}\left[d\left(y_i',g_\beta(x_i)\right)\right]^2$$

    is almost of the above form, with $y_i=0$ and $f_\beta(x_i) = d(y_i',g_\beta(x_i))$. Unfortunately, $f_\beta$ is now a function, not only of $x_i$ but also of the index $i$, but if the $x_i$ do not repeat, then we can let $h(x)$ be any function which interpolates the points $(x_i', y_i')$ (like a linear interpolation or spline interpolation), and define

    $$S_2(\beta) = \sum_{i\in I}\left[d\left(h(x_i),g_\beta(x_i)\right)\right]^2$$

    which is now certainly in the correct form.

    (This applies if $d$ is any function really, but it seems more interesting in the case of a metric)

  2. The square can also be absorbed into $d(x,y)$ to yield

    $$S_3(\beta) = \sum_{i\in I} d\left(h(x_i),g_\beta(x_i)\right)$$

  3. Going even further, it is possible to make the sum be indexed over a singleton to yield the following:

    $$S_4(\beta) = j_\beta(P)$$

    where now $I=\{0\}$, $(x_0, y_0) = (0,0)$ and $f_\beta(x)=\sqrt{j_\beta(P)}$ where $j_\beta$ is constant in terms of x, but can be an arbitrary non-negative function with respect to $(\beta, P)$.

So it seems like we can pose quite general optimization problems as quite degenerate cases of NLLSQ. I have 2 questions.

  • In which of these settings (if any) does it still make sense to apply NLLSQ algorithms to solve the problem. (Thinking in particular of Levenberg-Marquardt).

  • What other—more general purpose—algorithms are available in the cases where NLLSQ algorithms will perform badly?

$\endgroup$
  • $\begingroup$ What is the form of $f_\beta$? If it is linear in $\beta$ this is a linear model. The functional form in terms of the $x_i$ does not matter. $\endgroup$ – Michael R. Chernick Jun 7 '12 at 13:41
  • $\begingroup$ I've posed it as a non-linear least squares problem, so in a degenerate case $f$ might be linear in $\beta$, but I am interested in the more general case. $\endgroup$ – alang Jun 7 '12 at 13:49
  • $\begingroup$ Actually, thinking about this again, the question still applies to linear least squares, in the case that $d$ is non-linear. $\endgroup$ – alang Jun 7 '12 at 15:51

Your Answer

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

Browse other questions tagged or ask your own question.