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: Fri, 22 Feb 2008 18:19:17 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 57
Message-ID: <fpn3n5$a8g$1@fred.mathworks.com>
References: <d6caa3cb-77bd-4e56-801c-fb7c8da92831@34g2000hsz.googlegroups.com> <fpkqkp$jn3$1@fred.mathworks.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1203704357 10512 172.30.248.35 (22 Feb 2008 18:19:17 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 22 Feb 2008 18:19:17 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:453212


"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