We provide a new modeling framework and adopt modern optimization tools to attack an important open problem in statistics. In particular, we consider the optimal adaptive trial design problem in personalized medicine. Adaptive enrichment designs involve preplanned rules for modifying enrollment criteria based on accruing data in a randomized trial. We focus on designs where the overall population is partitioned into two predefined subpopulations, e.g., based on a biomarker or risk score measured at baseline for personalized medicine. The goal is to learn which populations benefit from an experimental treatment. Two critical components of adaptive enrichment designs are the decision rule for modifying enrollment, and the multiple testing procedure. We provide a general framework for simultaneously optimizing these components for two-stage, adaptive enrichment designs through Bayesian optimization. We minimize the expected sample size under constraints on power and the familywise Type I error rate. It is computationally infeasible to directly solve this optimization problem due to its nonconvexity and infinite dimensionality. The key to our approach is a novel, discrete representation of this optimization problem as a sparse linear program, which is large-scale but computationally feasible to solve using modern optimization techniques. Applications of our approach produce new, approximately optimal designs. In addition, we shall further discuss several extensions to solve other related statistical problems.