  We propose a new, nonparametric method for multivariate regression subject to
convexity or concavity constraints on the response function. Convexity
constraints are common in economics, statistics, operations research, financial
engineering and optimization, but there is currently no multivariate method
that is computationally feasible for more than a few hundred observations. We
introduce Convex Adaptive Partitioning (CAP), which creates a globally convex
regression model from locally linear estimates fit on adaptively selected
covariate partitions. CAP is computationally efficient, in stark contrast to
current methods. The most popular method, the least squares estimator, has a
computational complexity of $\mathcal{O}(n^3)$. We show that CAP has a
computational complexity of $\mathcal{O}(n \log(n)\log(\log(n)))$ and also give
consistency results. CAP is applied to value function approximation for pricing
American basket options with a large number of underlying assets.
