Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Non-linear regression to find minimum
Date: Thu, 21 Feb 2008 21:32:09 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 58
Message-ID: <fpkqkp$jn3$1@fred.mathworks.com>
References: <d6caa3cb-77bd-4e56-801c-fb7c8da92831@34g2000hsz.googlegroups.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1203629529 20195 172.30.248.37 (21 Feb 2008 21:32:09 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 21 Feb 2008 21:32:09 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:453008


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