MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • 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