MATLAB Central Newsreader - Non-linear regression to find minimum

Non-linear regression to find minimum

Thomas.Courl@gmail.com — Thu, 21 Feb 2008 13:13:05 -0500

Hi all !

I need to find the minimum of a multiple variables non-linear discrete
function, and I'm not a mathematician...

More specifically: I have a few hundreds thousands of data points
(X1,X2,...,Xn,Y) where the Xn are the variables and Y is the result of
the function that I would like to minimize.

My guess is that the best approach would be to do a non-linear
regression and then find the minimum: would that be the right
approach?

If yes, is MatLab the right tool to do this?

Many thanks for your help!
Regards,
Thomas

PS: my function has 23 variables but, if this is a limitation, I could
reduce it (and have a more rough approach).

Re: Non-linear regression to find minimum

Roger Stafford — Thu, 21 Feb 2008 21:32:09 -0500

Thomas.Courl@gmail.com wrote in message <d6caa3cb-77bd-4e56-801c-
fb7c8da92831@34g2000hsz.googlegroups.com>...
> Hi all !
>
> I need to find the minimum of a multiple variables non-linear discrete
> function, and I'm not a mathematician...
>
> More specifically: I have a few hundreds thousands of data points
> (X1,X2,...,Xn,Y) where the Xn are the variables and Y is the result of
> the function that I would like to minimize.
>
> My guess is that the best approach would be to do a non-linear
> regression and then find the minimum: would that be the right
> approach?
>
> If yes, is MatLab the right tool to do this?
>
> Many thanks for your help!
> Regards,
> Thomas
>
> PS: my function has 23 variables but, if this is a limitation, I could
> reduce it (and have a more rough approach).
-------
  This is a difficult question you have posed, Thomas. It is my guess that
what you need is to be able to find the average gradient in suitably small
neighborhoods within your data. By gradient I mean a vector consisting of
the set of first partial derivatives of Y with respect to the 23 variables.

  Probably starting with the discrete minimum in Y which you can easily find,
determine a neighborhood of this point which possesses well over 23+1
points from the given data set, and find the gradient of the least-squares
best-fitting plane to these points using matlab's matrix division (slash or
back slash.) You can probably devise some function which automatically
determines the size of a 23-dimensional sphere (or ellipsoid?) around a
central point which contains enough points and then computes the best-fit
gradient therein. Armed with such a function you can hopefully use it in
some steepest descent method to arrive at a true local minimum. Of course
this gradient will itself be a discrete-valued function since the points are
added or removed discretely as the neighborhood center is moved, so the
steepest descent method you adopt must be able to work properly under
those conditions.

  Note that steepest descent methods can be notoriously slow when
encountering "long valleys" in the data, but with the huge number of variables
involved I doubt if mere hundreds or thousands of data points would suffice
to make such a problem solvable with suitable accuracy having long 23-
dimensional valleys in it.

  Note also that for your problem to be remotely solvable, the underlying
function and its first partial derivatives must be reasonably continuous.
Crossing "cliffs" and "sharp ridges" would not be nice for a steepest descent
algorithm to encounter. Also the given data should be reasonably free of
inaccuracies and noise.

Roger Stafford

Re: Non-linear regression to find minimum

Roger Stafford — Fri, 22 Feb 2008 18:19:17 -0500

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fpkqkp$jn3$1@fred.mathworks.com>...
> Thomas.Courl@gmail.com wrote in message
<d6caa3cb-77bd-4e56-801c-
> fb7c8da92831@34g2000hsz.googlegroups.com>...
> > I need to find the minimum of a multiple variables non-linear discrete
> > function, and I'm not a mathematician...
> > ........
>
> This is a difficult question you have posed, Thomas. It is my guess that
--------
  Thomas, I wish to retract an important part of the advice I gave you
yesterday. I spoke of the gradient of a best-fitting plane (hyperplane)
through 24 or more data points in neighborhoods and using some kind of
steepest descent method. On reflection, it occurs to me that using planes in
this manner is not a good idea. The minimum Y-value on any section of a
plane cutting through a neighborhood must necessarily lie on the boundary
of that section. By the very linearity of planes, they can have no interior
minimum. If one is to do better then the discrete Y-minimum possessed by
the data points themselves, then at least second degree surfaces must be
involved. For example, with just one X-variable and three data points, a
unique quadratic expression can be found running through the points, and if
it forms an upward curving parabola, it would have a minimum different in
general from the minimum Y of the three points.

  Hence, one can conceive of a procedure analogous to the above single
variable case, applied to the 23 variables. Unfortunately, there are some
formidable difficulties involved in such an approach. It requires 300
coefficients to define a general quadratic expression with 23 variables.
Finding a best-fitting quadratic surface through a set of N >= 300 points in a
neighborhood would involve the use of matrix division involving an N x 300
or 300 x N matrix. That operation in itself can undoubtedly be performed,
but finding out whether such a surface possesses a valid minimum within the
neighborhood seems like a very time-consuming action. In the case of a
quadratic with two variables, y = Ax1^2+Bx1x2+Cx2^2+Dx1+Ex2+F, it has
a valid minimum somewhere if A>0, C>0, and B^2<4AC. I have no idea what
criterion would apply to the 300 coefficient case. Probably one of the non-
linear optimization functions like 'fmincon' or 'quadprog' would be needed,
but I don't know how well these would cope with 300 coefficients nor how
much time would be consumed.

  Presumably, if such a neighborhood minimum were found to lie at or near
its boundary, then the neighborhood location would be shifted in that
direction and the above operation repeated until a valid interior minimum
were found.

  However, in a practical sense, I think the very best thing you can do is to
greatly reduce the number of variables you are dealing with. Having an
adequate number of data points to properly characterize a function of 23
variables would in my opinion involve far, far more than the mere hundreds
or thousands you mentioned. If you imagine for a moment that your X-data
were arranged in a 23-dimensional grid with, say, just four distinct values
occurring along each dimension, that would amount to 4^23 or some 70
trillion data points needed altogether!

Roger Stafford