Finding the maximum of a random forest
Apparently, it's NP-hard.  See the following paper:

Evasion and Hardening of Tree Ensemble Classifiers.  Alex Kantchelian, J.D. Tygar, Anthony D. Joseph.  ICML 2016.

Section 4.2 says that solving the problem exactly is NP-hard.  However, the paper then goes on to develop techniques that, in practice, might often find an approximate maximum, using integer linear programming.

For a proof of NP-hardness, see Section 5.2 of Kantchelian's PhD dissertation.