Re: Speeding up FindMinimum setup

*To*: mathgroup at smc.vnet.net*Subject*: [mg86672] Re: [mg86652] Speeding up FindMinimum setup*From*: Carl Woll <carlw at wolfram.com>*Date*: Mon, 17 Mar 2008 00:23:16 -0500 (EST)*References*: <200803160939.EAA27599@smc.vnet.net>

Art wrote: >I am having trouble with the time FindMinimum takes to make it's first >step in an optimization. I am doing something wrong but I am not sure >what. This is a repost of a previous question that I phrased poorly. > >I am minimizing a convex f: R^n->R with derivative df: R^n->R^n using >FindMinimum. A toy example, > >n = 1000; >f[k_] := k.k >df[k_] := 2k > >I find the minimal k starting at random k0: > >k0 = RandomReal[1, n]; >ker = Array[k, n]; > >min = Reap[ > t0 = AbsoluteTime[]; > FindMinimum[f[ker], Transpose[{ker, k0}], Gradient -> df[ker], > StepMonitor :> Sow[AbsoluteTime[] - t0]] >]; > >min[[2,1]] gives the times of the steps > >(Above is a bad example as it converges in one step.) > >For my particular convex f, FindMinimum takes a very long time before >it makes it's first step but then proceeds very quickly. And time >scales superlinearly with n. It takes so long that I have resorted to >a C Mathlink function that does BFGS or ConjugateGradient (from Press >et al., Numerical Recipes, v3) and calls f and df through Mathlink. > >What is FindMinimum doing during this time before the first step? >Compiling f and df? It does this even when I precompile f and df and >specify Method. How do I specify my problem so it works faster? I >would like it to just start making optimization steps because it's >surprisingly efficient even with n large when it gets going. > >Also, thanks to whoever wrote all the excellent tutorial documentation >for the optimization functions in Mathematica and the examples in >UnconstrainedProblems.m. > >Art. > > Perhaps you could try using a vector variable approach: Clear[f, df] f[k_List] := k.k df[k_List] := 2 k k0 = RandomReal[1, 1000]; min = FindMinimum[f[v], {v, k0}, Gradient -> df[v]]; Or, a slightly less trivial example: Clear[f, df] f[k_List] := (k.k - 2)^2 df[k_List] := 4 k (k.k - 2) k0 = RandomReal[1, 1000]; min = FindMinimum[f[v], {v, k0}, Gradient -> df[v]]; Carl Woll Wolfram Research

**References**:**Speeding up FindMinimum setup***From:*Art <grenander@gmail.com>