We extend the classical Neyman-Pearson theory for testing composite hypotheses versus composite alternatives, using a convex duality approach, first employed by Witting. Results of Aubin and Ekeland from non-smooth convex analysis are used, along with a theorem of Komlós, in order to establish the existence of a max-min optimal test in considerable generality, and to investigate its properties. The theory is illustrated on representative examples involving Gaussian measures on Euclidean and Wiener space.