  We propose new, optimal methods for analyzing randomized trials, when it is
suspected that treatment effects may differ in two predefined subpopulations.
Such sub-populations could be defined by a biomarker or risk factor measured at
baseline. The goal is to simultaneously learn which subpopulations benefit from
an experimental treatment, while providing strong control of the familywise
Type I error rate. We formalize this as a multiple testing problem and show it
is computationally infeasible to solve using existing techniques. Our solution
involves a novel approach, in which we first transform the original multiple
testing problem into a large, sparse linear program. We then solve this problem
using advanced optimization techniques. This general method can solve a variety
of multiple testing problems and decision theory problems related to optimal
trial design, for which no solution was previously available. In particular, we
construct new multiple testing procedures that satisfy minimax and Bayes
optimality criteria. For a given optimality criterion, our new approach yields
the optimal tradeoff? between power to detect an effect in the overall
population versus power to detect effects in subpopulations. We demonstrate our
approach in examples motivated by two randomized trials of new treatments for
HIV.
