Theories of quantum gravity suggest that Lorentz invariance, the fundamental symmetry of the Theory of Relativity, may be broken at the Planck energy scale. While any deviation from conventional Physics must be minuscule in particular at attainable energies, this hypothesis motivates ever more sensitive tests of Lorentz symmetry. In the photon sector, astrophysical observations, in particular polarization measurements, are a very powerful tool because tiny deviations from Lorentz invariance will accumulate as photons propagate over cosmological distances. The Standard-Model Extension (SME) provides a theoretical framework in the form of an effective field theory that describes low-energy effects due to a more fundamental quantum gravity theory by adding additional terms to the Standard Model Lagrangian. These terms can be ordered by the mass dimension d of the corresponding operator and lead to a wavelength, polarization, and direction dependent phase velocity of light. Lorentz invariance violation leads to an energy-dependent change of the Stokes vector as photons propagate, which manifests itself as a rotation of the polarization angle in measurements of linear polarization. In this paper, we analyze optical polarization measurements from 63 Active Galactic Nuclei (AGN) and Gamma-ray Bursts (GRBs) to search for Lorentz violating signals. We use both spectropolarimetric measurements, which directly constrain the change of linear polarization angle, as well as broadband spectrally integrated measurements. In the latter, Lorentz invariance violation manifests itself by reducing the observed net polarization fraction. Any observation of non-vanishing linear polarization thus leads to constraints on the magnitude of Lorentz violating effects. We derive the first set limits on each of the 10 individual birefringent coefficients of the minimal SME with d = 4 , with 95% confidence limits on the order of 10−34 on the dimensionless coefficients.