Re: FindMinimum and picewise linear functions
- Subject: [mg2719] Re: FindMinimum and picewise linear functions
- From: rubin at msu.edu (Paul A. Rubin)
- Date: Sat, 9 Dec 1995 01:55:37 -0500
- Approved: usenet@wri.com
- Distribution: local
- Newsgroups: wri.mathgroup
- Organization: Michigan State University
In article <4a0s03$ce1 at dragonfly.wri.com>,
sinan at u.washington.edu (Sinan Karasu) wrote:
->
->I define a piecewise linear function with If statements,
->and then sample the function on a list. And then I try
->to do an optimization on it (sum of squares...)
->FindMinimum always complains about not being able
->to find the gradient. Has anyone come up with a way
->to do this?
->
-> Let us say I define (0,1)->R^2 to be a triangle
->Then I sample it on say {0.1,0.3,0.5,0.7,0.9} and then
->I come up with another sampling, say {0.1,0.3,0.4,0.7,0.9}
->
->Now if I do Sum[(triangle1samples[[i]]-triangle2samples[[i]])^2,{i,1,5}]
->and then perturb {0.1,0.3,0.t+4,0.7,0.9} and do a minimization
->of Sum over the second sample (i.e. t) FindMinimum complains
->about not being able to take the gradient. I unserdtand why
->it does, the question is, can I circumvent this somehow????
->
->Sinan
->
FindMinimum uses gradient search (steepest descent), and you function is
not differentiable at the values of t corresponding to a corner of the
triangle. If you currently call FindMinimum in the format
FindMinimum[ f, {t, 0} ]
where f is the summation expression, you might try switching to the
alternate format
FindMinimum[ f, {t, {0, 0.01}} ]
(the choices of 0 and 0.01 are arbitrary on my part). The first format
attempts to symbolically differentiate f, which is doomed if the chain rule
crashes into an If statement; the second format replaces symbolic
differentiation with numerical differentiation. That still won't make your
function differentiable, but you might catch a break and have it skip over
the discontinuities in the derivative.
Failing that, I have a package for handling piecewise-smooth functions
which might solve your problem. In lieu of using If[] constructs, you
would have to recode the triangle using a mechanism specific to the
package, which amounts to making a list of pairs {interval, formula} where
each formula is a smooth function. If you think it would help, I could
hang the package on our ftp server. (I think. It's part of a forthcoming
book, so I would have to check on copyright permissions first.)
Paul Rubin
**************************************************************************
* Paul A. Rubin Phone: (517) 432-3509 *
* Department of Management Fax: (517) 432-1111 *
* Eli Broad Graduate School of Management Net: RUBIN at MSU.EDU *
* Michigan State University *
* East Lansing, MI 48824-1122 (USA) *
**************************************************************************
Mathematicians are like Frenchmen: whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different. J. W. v. GOETHE