The extended Ritz method for functional optimization: overview and applications to single-person and team optimal decision problems

Abstract

Functional optimization problems entail minimization of functionals with respect to admissible solutions belonging to infinite-dimensional spaces of functions. The extended Ritz method (ERIM) searches for suboptimal solutions expressed as linear combinations of basis functions with ‘free’ parameters that are optimized, together with the coefficients of the linear combinations, by solving finite-dimensional nonlinear programming problems and exploiting stochastic approximation techniques. The first part of the paper gives an overview of the ERIM and introduces the concept of polynomially complex optimizing sequences. Their elements are given by the solutions of the nonlinear programming problems obtained using an increasing number of basis functions. Under some conditions, the optimizing sequences epi-converge to the optimal solution and for a given approximation accuracy, the number of free parameters increases moderately (e.g. polynomially) with the number of variables in the admissible solutions. Therefore, the ERIM may avoid the curse of dimensionality, i.e. an exponential growth of the number of parameters. In the second and third parts of the paper, the ERIM and the stochastic approximation algorithms are specialized to the solution of stochastic T-stage single-person and stochastic team decision problems, respectively. Numerical results are given for the optimal management of systems of water reservoirs and for the dynamic routing problem in communication networks. In the reservoirs management application, the ERIM is compared with dynamic programming (DP) using random sampling of the state space. The dynamic routing application considers the presence of several destinations and classes of traffic, which are useful to address quality of service requirements. Here, the ERIM is compared with an algorithm based on the open shortest path first protocol.

Keywords:

• curse of dimensionality
• suboptimal solutions
• dynamic programming
• stochastic T-stage decision problems
• water reservoirs management
• dynamic routing

AMS Subject Classifications :

• Primary: 41A25
• 49M15
• 49J30
• 49N35
• 65K99
• 91A12
• 91A35
• 90B99
• Secondary: 46N10
• 68T05
• 90C30
• 93E20
• 93E35

OR/MS Subject Classifications :

• Primary: decision analysis: applications, theory
• games/group decisions: teams. Secondary: dynamic programming/optimal control: applications

Acknowledgements

This work was supported in part by PRIN grants of the Italian Ministry for University and Research, Projects New Techniques for the Identification and Adaptive Control of Industrial Systems and Models and Algorithms for Robust Network Optimization.

Notes

The distinction between scalar and vectorial quantities (variables and functions) will require the reader's special attention: the dimensions of some vectors, particularly those representing the arguments of the admissible functions (candidate at providing the optimal solutions), will play a basic role throughout the paper, particularly with reference to issues related to the ‘curse of dimensionality’ 14. Hence we have chosen to point out the vectorial nature by using boldface symbols.

The subscript ’ν’ in the vector is introduced to put into evidence the dimension of this vector. Indeed, such a dimension, which is proportional to ν, will always play a central role throughout the paper since it is strictly related to the ‘enemy’ we are always fighting against, that is, the curse of dimensionality. The presence of ν in the function γ_ν (and, later on, in other definitions) denotes the dependence of the ‘structure’ of γ_ν on the dimension of .

The Witsenhausen's counterexample 62 addresses the following problem. Two DMs, DM₁ and DM₂ generate their decisions u ₁ and u ₂ by the functions μ₁ (y ₁) and μ₂ (y ₂), respectively; (we have written ). The information structure is given by , where , and η ∼ N(0, 1). Let us state the following problem.

Problem W Find the optimal control functions and that minimize the cost functional , where .

Witsenhausen 62 proved that the optimal solution exists for any k 2>0 and that, although the LQG hypotheses are verified, the best linear solution to Problem W is not guaranteed to be the optimal one. So the difficulty of the problem is due to the lack of a partially nested structure. Note that the optimal solution has not yet been found. The difficulty of finding an optimal solution was explained in 50 by demonstrating that the discretized Problem W, stated in decisional form, is NP-complete. The expression ‘Problem W stated in decisional form’ means to wonder whether, given an integer constant B, there exist control functions μ₁ and μ₂, such that . For numerical solutions to Problem W via the ERIM, see 10.