I'm working on a problem that involves finding the global optimum of a function that looks like:
$U = \lambda\cdot u (x)+(1-\lambda)\cdot u(y)+V(a,b)$
I need to find values for $x$, $a$ and $b$ ($y$ is pinned down by an additional constraint) and $u$ and $V$ are typically concave.
The problem arises because $V$ is only known on a grid and has to be interpolated for the other points. Initially, I was using a second order bivariate polynomial, in which case the optimization runs very nice and fast, since it's just an application of Newton-Raphson.
However, I was recently switching to bilinear interpolation of $V$ (the fit of polynomials isn't sometimes that great). In this case, $V$ is smooth within each rectangle of the grid, but the derivative jumps at the borders. Importantly, the borders are known, since it's the grid from the bilinear interpolation.
Does anyone have an idea what the ideal way to tackle such a problem would be? I was trying the following:
1) Brute force: Set up a grid for $a$ and $b$, calculate $x$ for each point and pick the maximum. Takes ages though, because the problem has to be solved for every state of the model.
2) Grid + Simplex search: Start with a relatively coarse grid and pick a couple of points to use a starting values for the Nelder-Mead algorithm. Runs okay-ish, but sometimes the result is a bit off from the brute force benchmark.
3) Newton-Raphson within each rectangle: since I know that the derivative doesn't jump within the rectangles of the $(a,b)$ grid, I could run an interior point problem for each rectangle of that space and then pick the one with the highest function value. But then I end up running a lot of constrained problems.
I was also reading a bit about other approaches for derivate-free/non-smooth optimization and it seemed like a rather vast field, so I was wondering if there's any obvious reasonable approach? The main constraint here is the fact that the problem has to be solved very often, so each optimization shouldn't be too time-consuming. Thanks a lot for any suggestions!
