Repeated solution of a parametric rootfinding problem

Specific Domains Optimization (Mathematical)
1

For a given set of parameters \theta, I am solving

f(x, \theta) \approx 0

numerically for x(\theta), then obtain simulated moments S(x(\theta)) (which is stochastic), minimizing

\min_x \| S(x(\theta)) - D \|

where D is the data moments.

The most costly step is solving the rootfinding problem in the first equation — I found that of course having a good starting point helps.

I am wondering about the following heuristic solution: maintain a list of (x_i, \theta_i) pairs I solved for, and for a new \theta', use the x_i from the “nearest” \theta_i, or a convex combination of several nearest ones.

This is the part I need help with: I can of course find the nearest x_i's numerically, but I am wondering if there is an existing data structure/implementation that would make it easier.

As for the dimensionality of the problem: x, \theta \in \mathbb{R}^7.

2

Check GitHub - KristofferC/NearestNeighbors.jl: High performance nearest neighbor data structures and algorithms for Julia. for the nearest neighbor bit. If f and S are analytic functions, you can also try throwing the whole thing in a JuMP model and send it to Ipopt to solve for x and \theta simultaneously.

2 Likes
3

If a linear interpolation of the function x, theta → f is appropriate, you can also try to reuse that information to help your root solver (eg to seed the jacobian in a quasi Newton algorithm)

1 Like