Conjugate duality and the curse of dimensionality

If the functional equations of dynamic programming (DP) are viewed as convolutions, then conjugate duality can be applied to computational advantage. In particular, the ‘curse of dimensionality’ resulting from the number of state variables can be virtually eliminated by solving the additive conjugate dual of the recursive DP primal. The method is applied to discrete resource allocation problems as a relaxation technique and a numerical example is given.