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
->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

```

• Prev by Date: Re: How to simplify transposed terms?
• Next by Date: Re: Import/Export of data to/from Mma and Excel.
• Previous by thread: Re: FindMinimum and picewise linear functions
• Next by thread: Re: Smith Normal Form Algorithm