7
$\begingroup$

This is an example from the documentation:

FindMinimum[Sin[x] Sin[2 y], {x, y}, 
 Gradient -> {Cos[x] Sin[2 y], 2 Cos[2 y] Sin[x]}, Method -> "Newton"]

We can compile the objective function and the gradient:

f = Compile[{{x, _Real}, {y, _Real}}, Sin[x] Sin[2 y], 
  "RuntimeOptions" -> {"EvaluateSymbolically" -> False}]

g = Compile[{{x, _Real}, {y, _Real}}, {Cos[x] Sin[2 y], 
   2 Cos[2 y] Sin[x]}, 
  "RuntimeOptions" -> {"EvaluateSymbolically" -> False}]

and use them in FindMinimum:

FindMinimum[f[x, y], {{x, 10}, {y, -.5}}, Gradient -> g[x, y], 
 Method -> "Newton"]

The speed-up is about 50%.

What about problems that are more expensive to compute? For example, suppose that Sin[x] was very expensive to calculate. We would want to compute it once in the above example. However, it gets computed twice at each iteration because the objective function and the gradient compute it.

Can anyone see a way to combine the gradient and objective function calculations so that they don't duplicate work?

$\endgroup$

1 Answer 1

6
$\begingroup$
(* compile target & gradient with expression optimization *)
ClearAll[cf] ;
cf = Compile[
{{x, _Real}, {y, _Real}}, 
{Sin[x] Sin[2 y], Cos[x] Sin[2 y],2 Cos[2 y] Sin[x]},
RuntimeOptions -> {"Speed" , "EvaluateSymbolically" -> False},
CompilationOptions -> {"ExpressionOptimization" -> True}
] ;
(* << CompiledFunctionTools` ; *)
(* CompilePrint[cf] *)

(* wrapper with memorization *)
ClearAll[mf] ;
mf[x_, y_] :=mf[x, y] = cf[x, y]  ;

ClearAll[target] ;
target[x_?NumericQ, y_?NumericQ] := First[mf[x, y]] ;

ClearAll[gradient] ;
gradient[x_?NumericQ, y_?NumericQ] := Rest[mf[x, y]] ;

FindMinimum[target[x, y], {{x, 10}, {y, -.5}}, Gradient -> gradient[x, y], Method -> "Newton"]
(* {-1.`,{x->4.712388980379484`,y->0.7853981634000688`}} *)

(* memorized values *)
(* ?mf *)
$\endgroup$
3
  • $\begingroup$ Yes. Thanks. I should have thought of memoization. I am accepting it as a solution. However, my problem is minimizine over 10^2-10^3 3D points. Won't memoization and look-ups become a computational burden? If so, is there another strategy? (other than writing my own Newton method?) $\endgroup$ yesterday
  • 1
    $\begingroup$ @CraigCarter, lookup should be relativly cheap, instead of memorization you can cache into an assosiation (constant lookup). Writing Newton your own method is sure an option, it can converge fast to a local minimum. Bayesian optimization is also sample efficient and potentily can find global minimum $\endgroup$
    – I.M.
    yesterday
  • $\begingroup$ I'll give it shot. In my application, I'm interested in the distribution of the local minima. I'm also looking at the simulated annealing and random search in NMinimize--even though that is designed to be a global minimizer. Many thanks for your help. $\endgroup$ yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.