[R] Finding Optimum of Stochastic Function

[Prof J C Nash (U30A)]

Most of the stochastic optimization methods are directed at multiple
optima. You appear to have an imprecisely determined function e.g., time
taken for racing driver to get round the track, and indeed this is a
different form of stochastic optimization.

With Harry Joe of UBC I did quite a bit of work about 20 years ago on
response surface minimization, but none of this is (to my knowledge)
translated to R. David Wagstaff at Penn State just sent me a msg that
he's making some progress translating our Fortran 77 to Fortran 95 (I
think to R might actually be easier). I believe Harry had at least a
partial C version.

reference is Statistics and Computing 13: 277–286, 2003 "Numerical
optimization and surface estimation with imprecise function evaluations"

Our approach was to generate some points and model them as a paraboloid
and then search near the minimum of that model. All the "smarts" are in
choosing which points to add to or remove from the set of points for
modelling the surface. Clearly there are no guarantees, but for some
applications we found this worked not too badly.

JN

On 15-05-19 06:00 AM, r-help-request at r-project.org wrote:
> Message: 11
> Date: Mon, 18 May 2015 14:47:49 -0700
> From: ivo welch <ivo.welch at anderson.ucla.edu>
> To: r-help at r-project.org
> Subject: [R] Finding Optimum of Stochastic Function
> Message-ID:
> 	<CAPr7RtV99V3=3QUMKAmLridyECOr2MAq6cqXRV3929MadCU7XQ at mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
> 
> Could someone please point me to an optimizer for stochastic functions?
>    (In http://cran.r-project.org/web/views/Optimization.html, I saw methods
> that use random directions for deterministic functions, which is not the
> kind of stochastic I need.)
> 
> For clarification, say I have an outcome function f(x), where x is a vector
> of, say, 3 choices.  f(x) yields a simulated result that depends on random
> draws.  That is, if I run it twice, it will give me different answers.  I
> want to find the value of x that has the highest average f(x).
> 
> There are apparently well-defined algorithms, such as Robbins-Monro,
> Kiefer-Wolfowitz, and Spall, although I don't know how they work nor do I
> need to know much.  Presumably, a good algorithm knows not to draw too many
> points at a given x too early (when far away from the optimum), but to
> start more scattershot; and not to try to climb too aggressively.
> Intuitively, I probably want to start from a point, draw in a cloud around
> this point, and slowly sample-crawl into the direction where values tend to
> be higher.  Ideally, the algorithm would try to solve an updatable
> least-squares problem to determine its next sample.
> 
> Pointers appreciated.
> 
> regards, /iaw
> ----
> Ivo Welch (ivo.welch at gmail.com)
> 
> 	[[alternative HTML version deleted]]