Cell average decomposition (CAD) plays a critical role in constructing bound-preserving (BP) high-order discontinuous Galerkin and finite volume methods for hyperbolic conservation laws. Seeking optimal CAD (OCAD) that attains the mildest BP CFL condition is highly desirable and is a fundamentally important yet difficult problem. The classic CAD, proposed in 2010 by Zhang and Shu using the Gauss-Lobatto quadrature, has been widely used over the past decade. Zhang and Shu only checked, for the 1D P2 and P3 spaces, that their classic CAD is optimal. However, we recently discovered that the classic CAD is generally not optimal for the multidimensional P2 and P3 spaces. Yet, it remained unknown for a decade what CAD is optimal for higher-degree polynomial spaces, especially in multiple dimensions.

This paper presents the first systematic analysis and establishes the general theory on the OCAD problem, which lay a foundation for designing more efficient BP schemes. The analysis is very nontrivial and involves novel techniques from several branches of mathematics, including the Carathéodory's theorem from convex geometry, and the invariant theory of symmetric group in abstract algebra. Most notably, we discover that the OCAD problem is closely related to polynomial optimization of a positive linear functional on the positive polynomial cone, thereby establishing four useful criteria for examining the optimality of a feasible CAD. Using the established theory, we rigorously prove that the classic CAD is optimal for general 1D Pk spaces and general 2D Qk spaces of an arbitrary k. For the widely used 2D Pk spaces, the classic CAD is, however, not optimal, and we develop a generic approach to find out the genuine OCAD and propose a more practical quasi-optimal CAD, both of which provide much milder BP CFL conditions