Many naturally occurring and artificial materials exhibit significant heterogeneities in their properties at length scales that are well above atomic scales (e.g the fibers in a rubber composite, or the grains in an ice polycrystal). For this reason, it is of interest to be able to generate constitutive relations for the average or macroscopic response of these heterogeneous materials. This is a challenging task, especially when the microstructures are random and multi-scale, and the properties of the elementary constituents are nonlinear (e.g., plasticity, or finite-strain elasticity). In this presentation, I will discuss a general “homogenization” approach that is based on appropriately designed variational principles for the properties of “linear comparison composites.” Such “variational linear comparison” methods provide optimal linearization schemes depending on the field statistics and allowing the direct conversion of robust homogenization estimates for linear composites into corresponding estimates for nonlinear composites. We will consider several examples, including strongly nonlinear composites and polycrystals. The objective will be to show how these methods can be used to generate relatively simple constitutive models for the macroscopic response incorporating appropriate statistical information on the microstructure in the form of “internal variables” that evolve in time with the deformation. The resulting models are sufficiently accurate to predict the macroscopic response, field statistics and microstructure evolution in these materials, as well as the possible development of material instabilities. In addition, they can be implemented numerically in standard finite element codes for efficient computations at higher (structural) length scales.