A computationally-efficient strength optimization method tailoring novel composite laminates using lamination parameters is developed. The method adopts a global p-norm approach to aggregate local failure indices into a global failure index, based on the Tsai-Wu failure criterion. For design purposes, the novel composite laminates are characterized via lamination parameters that can subsequently be transformed into locally variable fiber orientations in an existing three-step optimization method. An elliptical formulation of the conservative failure envelope is applied to represent the Tsai-Wu criterion in terms of lamination parameters. A lamination-parameter-based two-level approximation for the global failure index is derived, which guarantees the anticipated conservativeness and convexity in a gradient-based optimization framework. Numerical results show that the computational efficiency of the proposed strength optimization method improves remarkably with a proper value of p, compared to the existing local-based min-max method. The method is also shown to be robust and generate converged optimum designs even in the presence of stress concentrations and singularities.