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>
- Speeding up FindMinimum setup