Re: FindMinimum and picewise linear functions

*To*: mathgroup at smc.vnet.net*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*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