Pruning error analysis for a class of curse-of-dimensionality free methods

In the context of computational nonlinear optimal control, curse-of-dimensionality (CoD) refers to the phenomenon of exponential growth of computational cost with respect to the dimension of state and input space. It is well-known that CoD is the major drawback of grid-based computational methods, which are consequently restricted their applications to low dimensional problems. Switching linear quadratic regulators (SLQR) is a class of nonlinear optimal control problems for which a CoD free method has been developed. However, it has been observed that this CoD free method suffers from a different form of computational complexity known as curse-of-complexity (CoC) which refers to the phenomenon that the number of quadratics necessary to represent the value functions of SLQR problems increases exponentially with respect to time horizon. Pruning is the key method of tackling this class of complexity at the cost of introducing pruning errors. This paper develops a framework that can be used to analyse pruning errors.