Beam-steering lens arrays enable solar tracking using millimeter-scale relative translation between a set of lens arrays. This may represent a promising alternative to the mechanical bulk of conventional solar trackers, but until now a thorough exploration of possible configurations has not been carried out. We present an approach for designing beam-steering lens arrays based on multi-objective optimization, quantifying the trade-off between beam divergence and optical efficiency. Using this approach, we screen and optimize a large number of beam-steering lens array configurations, and identify new and promising configurations. We present a design capable of redirecting sunlight into a <2° divergence half-angle, with 73.4% average yearly efficiency, as well as a simplified design achieving 75.4% efficiency with a <3.5° divergence half-angle. These designs indicate the potential of beam-steering lens arrays for enabling low-cost solar tracking for stationary solar concentrators.