This study develops a data-driven approach to solve constrained optimization problems in which the decision maker does not have an analytic form for the objective function but knows what decision variables affect the function. The approach makes direct use of the available data, rather than first using the data to estimate the objective function and then solving the problem as a traditional optimization problem. The difficulty in first estimating the unknown objective function is that the decision maker needs to have sufficient knowledge of its properties that are necessary to guide the estimation process. Thus, our approach is appropriate for situations where such structural knowledge is absent, either because the domain is very complex or because the knowledge is deliberately hidden by a partner firm that has a vested interest in the outcome of the decision. Our approach comes with a worst-case performance guarantee that improves with the characteristics (size, pervasiveness) of the available data. We illustrate our technique on a traffic-stream mixing problem encountered by a supply side Internet advertising network that wishes to optimize the click revenue earned from ads. A head-to-head comparison (with the existing method used) on real data shows a significant increase (≥10%, on average) in the revenue. We also demonstrate the value of our approach under more general conditions. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0818 .