We study the basic relationships of the pseudoplastic deformation of the particulate-filled composite materials that is caused by structural damage. The materials of this class include, specifically, the ceramics, the advanced carbon-carbon composite matrices, and the materials that are obtained by the powder metallurgy methods. We develop a mathematical model of the deformation and failure of a nonhomogeneous medium consisting of structural elements with identical elastic properties and random strength properties. Failure modeling is accomplished on the basis of an ensemble of criteria, in which the shear deformations are considered to be the basic cause of the change of the deformation characteristics of the structural elements. We obtain the dependencies of the macrostress invariants on the macrostrain invariants for various proportional macrodeformation schemes, which are the basis for constructing the constitutive relations in the strain softening stage.