The Extended Ritz Method in Stochastic Functional Optimization: An example of Dynamic Routing in Traffic Networks

摘要

The classical Ritz method constrains the admissible solutions of functional optimization problems to take on the structure of linear combinations of fixed basis functions. Under general assumptions, the coefficients of such linear combinations become the unknowns of a finite-dimensional nonlinear programming problem. We propose to insert "free" parameters to be optimized in the basis functions, too. This justifies the term "Extended Ritz Method." If the optimal solutions of functional optimization problems belong to classes of d-variable functions characterized by suitable regularity properties, the Extended Ritz Method may outperform the Ritz method in that the number of free parameters increases moderately (e.g., polynomially) with d, whereas the latter method may be ruled out by the curse of dimensionality. Once the functional optimization problem has been approximated by a nonlinear programming one, the solution of the latter problem is obtained by stochastic approximation techniques. The overall procedure turns out to be effective in high-dimensional settings, possibly in the presence of several decision makers. In such a context, we focus our attention on large-scale traffic networks such as communication networks, freeway systems, etc. Traffic flows may vary over time. Then the nodes of the networks (i.e., the decision makers acting at the nodes) may be requested to modify the traffic flows to be sent to their neighboring nodes. Consequently, a dynamic routing problem arises that cannot be solved analytically. In particular, we address store-and-forward packet switching networks, which exhibit the essential difficulties of traffic networks. Simulations performed on complex communication networks show the effectiveness of the proposed method.