Finding the maximum of a random forest If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension. 

It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.

If the leaf values are taken from $\{0, 1\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.

Any thoughts?
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.