Search

Braess' paradox is a classical result in the theory of congestion games. It motivates theoretically why adding a resource (e.g., an arc) to a network may sometimes worsen, rather than improve, the overall network performance. Differently from previous literature, which studies Braess' paradox in a non-cooperative game-theoretic setting, in this work, a framework is proposed to investigate its occurrence by exploiting cooperative games with transferable utility (TU games) on networks. In this way, instead of focusing on the marginal contribution to the network utility provided by the insertion of an arc when a single initial scenario is considered, the arc average marginal utility with respect to various initial scenarios, that is, its Shapley value in a suitably-defined TU game, is evaluated. It is shown that, for choices of the utility function of the TU game modeling congestion, there are cases for which the Shapley value associated with an arc is negative, meaning that its average marginal contribution to the network utility is negative.

In the theory of congestion games, the Braess’ paradox shows that adding one resource to a network may sometimes worsen, rather than improve, the overall network performance. Here the paradox is investigated under a cooperative game-theoretic setting, in contrast to the non-cooperative one typically adopted in the literature. A family of cooperative games on networks is considered, whose utility function, defined in terms of a traffic assignment problem and the associated Wardrop equilibrium, expresses the average quality of service perceived by the network users.

The work reports ongoing research about a computational method, based on cooperative games on graphs, aimed at detecting the perceived origin of full-body human movement and its propagation. Compared with previous works, a larger set of movement features is considered, and a ground truth is produced, able to assess and compare the effectiveness of each such feature. This is done through the use of the Shapley Value as a centrality index. An Origin of Movement Continuum is also defined, as the basis for creating a repository of movement qualities.

This chapter addresses discrete-time deterministic problems, where optimal controls have to be generated at a finite number of decision stages. No random variables influence either the dynamic system or the cost function. Then, there is no necessity of estimating the state vector. Such optimization problems are stated for their intrinsic practical importance and to describe the basic concepts of dynamic programming. As the problems are formulated under very general assumptions, their optimal solutions cannot be found in an analytical form. Therefore, we resort to an approximation consisting of the discretization of the state space into suitable grids at each decision stage. The discretization by regular grids is the simplest approach (and the one most widely used until some time ago). However, unless a small dimension of the state space is considered, this approach leads to an exponential growth of the number of samples, and thus to the curse of dimensionality. Therefore, the discretization by deterministic sequences of samples is addressed, which spread the samples in the most uniform way. Specifically, low-discrepancy sequences are considered, like quasi-Monte Carlo sequences. We also point out that the optimization problem can even be viewed as a nonlinear programming problem solvable by gradient-based descent techniques.

First, well-known concepts from Statistical Learning Theory are reviewed. In reference to the problem of modelling an unknown input/output (I/O) relationship by fixed-structure parametrized functions, the concepts of expected risk, empirical risk, and generalization error are described. The last error is then split into approximation and estimation errors. Four quantities of interest are emphasized: the accuracy, the number of arguments of the I/O relationship, the model complexity, and the number of samples generated for the estimation. The possibility of generating such samples by deterministic algorithms like quasi-Monte Carlo methods, orthogonal arrays, Latin hypercubes, etc. gives rise to the so-called Deterministic Learning Theory. This possibility is an intriguing alternative to the random generation of input data, typically obtained by using Monte Carlo techniques, since it enables one to reduce the number of samples (under the same accuracy) and to obtain upper bounds on the errors in deterministic terms rather than in probabilistic ones. Deterministic learning relies on some basic quantities such as variation and discrepancy. Special families of deterministic sequences called “low-discrepancy sequences” are useful in the computation of integrals and in dynamic programming, to mitigate the danger of incurring the curse of dimensionality deriving from the use of regular grids.

Neural Approximations for Optimal Control and Decisionprovides a comprehensive methodology for the approximate solution of functional optimization problems using neural networks and other nonlinear approximators where the use of traditional optimal control tools is prohibited by complicating factors like non-Gaussian noise, strong nonlinearities, large dimension of state and control vectors, etc. Features of the text include: • a general functional optimization framework; • thorough illustration of recent theoretical insights into the approximate solutions of complex functional optimization problems; • comparison of classical and neural-network based methods of approximate solution; • bounds to the errors of approximate solutions; • solution algorithms for optimal control and decision in deterministic or stochastic environments with perfect or imperfect state measurements over a finite or infinite time horizon and with one decision maker or several; • applications of current interest: routing in communications networks, traffic control, water resource management, etc.;and • numerous, numerically detailed examples.

Optimal control problems over an infinite number of decision stages are considered with emphasis on the deterministic scenario. Both the open-loop and the closed-loop formulations are given and conditions for the existence of a stationary optimal control law are provided. Unless strong assumptions are made on the dynamic system and on the random variables (if present), the design of the optimal infinite-horizon controllers is an almost impossible task. Then, the well-known “receding-horizon” (RH) approximation is considered and the optimal control problem is restated accordingly. In the second part of the chapter, we consider the fundamental issue of closed-loop stability that arises owing to the infinite number of decision stages. More specifically, we address the stability properties of the closed-loop deterministic system under the action of approximate RH control laws obtained by the “extended Ritz method” and implemented through fixed-structure parametrized functions containing vectors of “free” parameters. Conditions are established on the maximum allowable approximation errors so as to ensure the boundedness of the state trajectories.

We consider discrete-time stochastic optimal control problems over a finite number of decision stages in which several controllers share different information and aim at minimizing a common cost functional. This organization can be described within the framework of “team theory.” Unlike the classical optimal control problems, linear-quadratic-Gaussian hypotheses are sufficient neither to obtain an optimal solution in closed-loop form nor to understand whether an optimal solution exists. In order to obtain an optimal solution in closed-loop form, additional suitable assumptions must be introduced on the “information structure” of the team. The “information structure” describes the way in which each controller’s information vector is influenced by the stochastic environment and by the decisions of the other controllers. Dynamic programming cannot be applied unless the information structure takes particular forms. On the contrary, the “extended Ritz method” (ERIM) can be always applied. The ERIM consists in substituting the admissible functions with fixed-structure parametrized functions containing vectors of “free” parameters. The ERIM is tested in two case studies. The former is the well-known Witsenhausen counterexample. The latter is an optimal routing problem in a store-and-forward packet-switching network.

Neural approximations of the optimal stationary closed-loop control strategies for discounted infinite-horizon stochastic optimal control problems are investigated. It is shown that for a family of such problems, the minimal number of network parameters needed to achieve a desired accuracy of the approximate solution does not grow exponentially with the number of state variables. In such a way, neural-network approximation mitigates the so-called “curse of dimensionality”. The obtained theoretical results point out the potentialities of neural-network based approximation in the framework of sequential decision problems with continuous state, control, and disturbance spaces.

Network connectivity is an important aspect of any transportation network, as the role of the network is to provide a society with the ability to easily travel from point to point using various modes. A basic question in network analysis concerns how “important” each node is. An important node might, for example, greatly contribute to short connections between many pairs of nodes, handle a large amount of the traffic, generate relevant information, represent a bridge between two areas, etc. In order to quantify the relative importance of nodes, one possible approach uses the concept of centrality. A limitation of classical centrality measures is the fact that they evaluate nodes based on their individual contributions to the functioning of the network. The present paper introduces a game theory approach, based on cooperative games with transferable utility. Given a transportation network, a game is defined taking into account the network topology, the weights associated with the arcs, and the demand based on an origin-destination matrix (weights associated with nodes). The network nodes represent the players in such a game. The Shapley value, which measures the relative importance of the players in transferable utility games, is used to identify the nodes that have a major role. For several network topologies, a comparison is made with well-known centrality measures. The results show that the suggested centrality measures outperform the classical ones, and provide an innovative approach for transportation network analysis.

This paper investigates how current and future generations are affected by commitment-based Nash equilibrium environmental strategies when the environmental absorption efficiency is susceptible to switch from a pollution sink to a source. We formulate a two-player differential game model of transboundary pollution that includes the environmental absorption efficiency as a state variable that can be enhanced thanks to restoration efforts. Based on a logarithmic specification for the instantaneous revenue function, we characterize the cooperative solution and the commitment-based Nash equilibrium strategy, and examine their differences in terms of steady state and transient behavior. We notably show that a commitment-based Nash equilibrium strategy makes it possible to prevent a definitive switching of the environmental absorption efficiency from a pollution sink to a source but imposes greater economic sacrifices on current generations than on future generations. In comparison, the cooperative solution imposes greater sacrifices on current generations in terms of revenues but it imposes lower environmental costs on both current and future generations than commitment-based Nash equilibrium strategy.

Limitations of approximation capabilities of shallow perceptron networks are investigated. Lower bounds on approximation errors are derived for binary-valued functions on finite domains. It is proven that unless the number of network units is sufficiently large (larger than any polynomial of the logarithm of the size of the domain) a good approximation cannot be achieved for almost any uniformly randomly chosen function on a given domain. The results are obtained by combining probabilistic Chernoff–Hoeffding bounds with estimates of the sizes of sets of functions exactly computable by shallow networks with increasing numbers of units.

We report properties of fixed-structure parametrized (FSP) functions that give insights into the effectiveness of the “Extended Ritz Method” (ERIM) as a methodology for the approximate solution of infinite-dimensional optimization problems. First, we present the structure of some widespread FSP functions, including linear combinations of fixed-basis functions, one-hidden-layer (OHL) and multiple-hidden-layer (MHL) networks, and kernel smoothing models. Second, focusing on the case of OHL neural networks based on ridge and radial constructions, we report their density properties under different metrics. Third, we present rates of function approximation via ridge OHL neural networks, by reporting a fundamental theorem by Maurey, Jones, and Barron, together with its extensions, based on a norm tailored to approximation by computational units from a given set of functions. We also discuss approximation properties valid for MHL networks. Fourth, we compare the classical Ritz method and the ERIM from the point of view of the curse of dimensionality, proving advantages of the latter for a specific class of problems, where the functional to be optimized is quadratic. Finally, we provide rates of approximate optimization by the ERIM, based on the concepts of modulus of continuity and modulus of convexity of the functional to be optimized.

Discrete-time stochastic optimal control problems are stated over a finite number of decision stages. The state vector is assumed to be perfectly measurable. Such problems are infinite-dimensional as one has to find control functions of the state. Because of the general assumptions under which the problems are formulated, two approximation techniques are addressed. The first technique consists of an approximation of dynamic programming. The approximation derives from the fact that the state space is discretized. Instead of using regular grids, which lead to an exponential growth of the number of samples (and thus to the curse of dimensionality), low-discrepancy sequences (as quasi-Monte Carlo ones) are considered. The second approximation technique is given by the application of the “Extended Ritz Method” (ERIM). The ERIM consists in substituting the admissible functions with fixed-structure parametrized functions containing vectors of “free” parameters. This requires solving easier nonlinear programming problems. If suitable regularity assumptions are verified, such problems can be solved by stochastic gradient algorithms. The computation of the gradient can be performed by resorting to the classical adjoint equations, which solve deterministic optimal control problems with the addition of one term, dependent on the chosen family of fixed-structure parametrized functions.

Two topics are addressed. The first refers to the numerical computation of integrals and expected values of functions that may depend on a large number of random variables. Of course, integration includes the computation of the expected values of functions dependent on random variables. However, the latter shows peculiar nontrivial aspects that the former does not have. In case of a large number of random variables, the use of regular grids implies the risk of incurring the curse of dimensionality. Then, suitable sampling methods are taken into account to reduce such risk. In particular, Monte Carlo and quasi-Monte Carlo sequences are addressed. The second topic refers to the solution of the nonlinear programming problems obtained from the approximation of infinite-dimensional optimization problems by the Extended Ritz Method. We mention a few well-known direct techniques and gradient-based descent algorithms. In the case of nonlinear programming problems stated in stochastic frameworks, the stochastic approximation approach deserves attention and thus it is considered in some detail. Within this context, we describe the stochastic gradient algorithm enabling one to avoid the computation of integrals, hence, the computation of expected values of functions dependent on random variables. Convergence properties of that algorithm are reported.

In infinite-dimensional or functional optimization problems, one has to minimize (or maximize) a functional with respect to admissible solutions belonging to infinite-dimensional spaces of functions, often dependent on a large number of variables. As we consider optimization problems characterized by very general conditions, optimal solutions might not be found analytically and classical numerical methods might fail. In these cases, one must use suitable approximation methods. This chapter describes an approximation method that uses families of nonlinear approximators – including commonly used shallow and deep neural networks as special cases – to reduce infinite-dimensional problems to finite-dimensional nonlinear programming ones. It is named “Extended Ritz Method” (ERIM). This term originates from the classical Ritz method, which uses linear combinations of functions as an approximation tool. It does not seem that the Ritz method has met with important successes as regards problems whose admissible solutions depend on large number of variables. This might be ascribed to the fact that this method can be subject to one of the forms of the so-called “curse of dimensionality.” However, theoretical and numerical results show that the ERIM might mitigate this drawback. Examples of infinite-dimensional optimization problems are presented that can be approximated by nonlinear programming ones.

This chapter describes the approximate solution of infinite-dimensional optimization problems by the “Extended Ritz Method” (ERIM). The ERIM consists in substituting the admissible functions with fixed-structure parametrized (FSP) functions containing vectors of “free” parameters. The larger the dimensions, the more accurate the approximations of the optimal solutions of the original functional optimization problems. This requires solving easier nonlinear programming problems. In the area of function approximation, we review the definition of approximating sequences of sets, which enjoy the property of density in the sets of functions one wants to approximate. Then, we provide the definition of polynomially complex approximating sequences of sets, which are able to approximate functions provided with suitable regularity properties by using, for a desired arbitrary accuracy, a number of “free” parameters increasing at most polynomially when the number of function arguments grows. In the less studied area of approximate solution of infinite-dimensional optimization problems, the optimizing sequences and the polynomially complex optimizing sequences of FSP functions are defined. Results are presented that allow to conclude that, if appropriate hypotheses occur, polynomially complex approximating sequences of sets give rise to polynomially complex optimizing sequences of FSP functions, possibly mitigating the curse of dimensionality.

High performance of an exoskeleton depends on torque/force tracking in a proper way according to human motion. Hence, because of the importance of actuator systems in wearable robots which usually include electrical motors and transmissions, this paper proposes a solution for selection of these components for an upper-body exoskeleton. In order to perform an optimization procedure, the dynamic model of the system has been developed analytically. Accordingly, optimization criteria in terms of closed-loop system bandwidth, system power consumption and component weights have been formulated by taking technical limitations into account. Extensive simulation results are presented in order to make comparison among possible optimization results.

The choice of dictionaries of computational units suitable for efficient computation of binary classification tasks is investigated. To deal with exponentially growing sets of tasks with increasingly large domains, a probabilistic model is introduced. The relevance of tasks for a given application area is modeled by a product probability distribution on the set of all binary-valued functions. Approximate measures of network sparsity are studied in terms of variational norms tailored to dictionaries of computational units. Bounds on these norms are proven using the Chernoff–Hoeffding bound on sums of independent random variables that need not be identically distributed. Consequences of the probabilistic results for the choice of dictionaries of computational units are derived. It is shown that when a priori knowledge of a type of classification tasks is limited, then the sparsity may be achieved only at the expense of large sizes of dictionaries.

Network congestion is a well-known problem that may heavily affect the overall network performance. Congestion control approaches in Intermittently-Connected Networks (ICNs) differ from those used in classical networks, since the assumptions of “universal connectivity” of the nodes and “global information” about the network do not hold. In this paper, an analytical framework is proposed to investigate node buffer occupancy in ICNs through bulk-arrivals/bulk-services queuing models. A relation in the z -domain between the discrete probability densities of the buffer state occupancies and of the sizes of the arriving bulks is exploited to analyze two classes of forwarding strategies for ICNs. The infinite- and finite-buffer cases are investigated, simulated, and compared in terms of the concept of stochastic order, which is also used to compare models obtained for different parameter choices. The results can be exploited for buffer dimensioning and for deriving estimates of performance metrics such as average buffer occupancy, average delivery delay, and buffer overflow probability. The theoretical analysis is complemented by numerical outcomes from a network simulator and from real mobility traces.

Supervised and semi-supervised machine-learning techniques are applied and compared for the recognition of the flood hazard. The learning goal consists in distinguishing between flood-exposed and marginal-risk areas. Kernel-based binary classifiers using six quantitative morphological features, derived from data stored in digital elevation models, are trained to model the relationship between morphology and the flood hazard. According to the experimental outcomes, such classifiers are appropriate tools when one is interested in performing an initial low-cost detection of flood-exposed areas, to be possibly refined in successive steps by more time-consuming and costly investigations by experts. The use of these automatic classification techniques is valuable, e.g., in insurance applications, where one is interested in estimating the flood hazard of areas for which limited labeled information is available. The proposed machine-learning techniques are applied to the basin of the Italian Tanaro River. The experimental results show that for this case study, semi-supervised methods outperform supervised ones when—the number of labeled examples being the same for the two cases—only a few labeled examples are used, together with a much larger number of unsupervised ones.

Call admission control with two classes of users is investigated via a nonlinear stochastic knapsack model. The feasibility region represents the subset of the call space, where given constraints on the quality of service have to be satisfied. Admissible strategies are searched for within the class of coordinate-convex policies. Structural properties that the optimal policies belonging to such a class have to satisfy are derived. They are exploited to narrow the search for the optimal solution to the nonlinear stochastic knapsack problem that models call admission control. To illustrate the role played by these properties, the numbers of coordinate-convex policies by which they are satisfied are estimated. A graph-based algorithm to generate all such policies is presented.

Concepts and tools from cooperative game theory are exploited to quantify the role played by each member of a team in estimating the position of an observed point of interest. The measure of importance known as “Shapley value” is used to this end. From the theoretical point view, we propose a specific form of the characteristic function for the class of cooperative games under investigation. In the numerical analysis, different configurations of a group of individuals are considered: all individuals looking at a mobile point of interest, one of them replaced with an artificially-generated one who looks exactly toward the point of interest, and directions of the heads replaced with randomly-generated directions. The corresponding experimental outcomes are compared.

This contribution deals with the identification of flood hazards at the catchment scale. The aim is to distinguish flood-exposed areas from marginal risk ones, and to extend available information on flood hazards to cover the whole catchment. Threshold binary classifiers based on six selected quantitative morphological features, derived from data stored in digital elevation models (DEMs), are used to investigate the relationships between morphology and the flooding hazard, as described in flood hazard maps. Results show that threshold binary classifier techniques should be taken into account when one is interested in an initial low-cost detection of flood-exposed areas. This may be needed, for example, in applications related to the insurance market, in which one is interested in estimating the flood hazard of specific areas for which limited information is available, or whenever a first flood hazard delineation is required to further address detailed investigations for flood mapping purposes. The method described in the paper has been tested on the basin of the Tanaro River. Results present a high degree of accuracy: indeed, the best classifier correctly identifies about 91% of flood-exposed areas, whereas the percentage of the areas exposed to marginal risk that are incorrectly classified as flood-exposed areas is about 16%. Copyright © 2013 John Wiley & Sons, Ltd.

Optimal control theory and machine learning techniques are combined to formulate and solve in closed form an optimal control formulation of online learning from supervised examples with regularization of the updates. The connections with the classical linear quadratic gaussian (LQG) optimal control problem, of which the proposed learning paradigm is a nontrivial variation as it involves random matrices, are investigated. The obtained optimal solutions are compared with the Kalman filter estimate of the parameter vector to be learned. It is shown that the proposed algorithm is less sensitive to outliers with respect to the Kalman estimate (thanks to the presence of the regularization term), thus providing smoother estimates with respect to time. The basic formulation of the proposed online learning framework refers to a discrete-time setting with a finite learning horizon and a linear model. Various extensions are investigated, including the infinite learning horizon and, via the so-called kernel trick, the case of nonlinear models.

Model complexities of shallow (i.e., one-hidden-layer) networks representing highly varying multivariable { - 1 , 1 } -valued functions are studied in terms of variational norms tailored to dictionaries of network units. It is shown that bounds on these norms define classes of functions computable by networks with constrained numbers of hidden units and sizes of output weights. Estimates of probabilistic distributions of values of variational norms with respect to typical computational units, such as perceptrons and Gaussian kernel units, are derived via geometric characterization of variational norms combined with the probabilistic Chernoff Bound. It is shown that almost any randomly chosen { - 1 , 1 } -valued function on a sufficiently large d-dimensional domain has variation with respect to perceptrons depending on d exponentially.

Summary A technique is presented for the identification of the areas subject to flooding hazard. Starting from remote sensed elevation data and existing flood hazard maps – usually available for limited areas – the relationships between selected quantitative morphologic features and the flooding hazard are first identified and then used to extend the hazard information to the entire catchment. This is performed through techniques of pattern classification, such as linear classifiers based on quantitative morphologic features, and support vector machines with linear and Gaussian kernels. The experiment starts by discriminating between flood-prone areas and marginal hazard areas. Multiclass classifiers are subsequently used to graduate the hazard. Their designs amount to solving suitable optimization problems. Several performance measures are considered in comparing the different classifiers, such as the area under the receiver operating characteristics curve, and the sum of the false positive and false negative rates. The procedure has been validated for the Tanaro basin, a tributary to the major Italian river, the Po. Results show a high reliability: the classifier properly identifies 93% of flood-prone areas, and only 14% of the areas subject to a marginal hazard are improperly assigned. An increase of this latter value up to 19% is detected when the same structure is applied for hazard graduation. Results derived from the application to different catchments seem to qualitatively indicate the ability of the classifier to perform well also outside the calibration region. Pattern classification techniques should be considered when the identification of flood-prone areas and hazard grading is required for large regions (e.g., for civil protection or insurance purposes) or when a first identification is needed (e.g., to address further detailed flood-mapping activities).

Approximate solutions to inhomogeneous Fredholm integral equations of the second kind by radial and kernel networks are investigated. Upper bounds are derived on errors in approximation of solutions of these equations by networks with increasing model complexity. The bounds are obtained using results from nonlinear approximation theory. The results are applied to networks with Gaussian and kernel units and illustrated by numerical simulations.

Approximation capabilities of two types of computational models are explored: dictionary-based models (i.e., linear combinations of n-tuples of basis functions computable by units belonging to a set called ''dictionary'') and linear ones (i.e., linear combinations of n fixed basis functions). The two models are compared in terms of approximation rates, i.e., speeds of decrease of approximation errors for a growing number n of basis functions. Proofs of upper bounds on approximation rates by dictionary-based models are inspected, to show that for individual functions they do not imply estimates for dictionary-based models that do not hold also for some linear models. Instead, the possibility of getting faster approximation rates by dictionary-based models is demonstrated for worst-case errors in approximation of suitable sets of functions. For such sets, even geometric upper bounds hold.

Neural networks provide a more flexible approximation of functions than traditional linear regression. In the latter, one can only adjust the coefficients in linear combinations of fixed sets of functions, such as orthogonal polynomials or Hermite functions, while for neural networks, one may also adjust the parameters of the functions which are being combined. However, some useful properties of linear approximators (such as uniqueness, homogeneity, and continuity of best approximation operators) are not satisfied by neural networks. Moreover, optimization of parameters in neural networks becomes more difficult than in linear regression. Experimental results suggest that these drawbacks of neural networks are offset by substantially lower model complexity, allowing accuracy of approximation even in high-dimensional cases. We give some theoretical results comparing requirements on model complexity for two types of approximators, the traditional linear ones and so called variable-basis types, which include neural networks, radial, and kernel models. We compare upper bounds on worst-case errors in variable-basis approximation with lower bounds on such errors for any linear approximator. Using methods from nonlinear approximation and integral representations tailored to computational units, we describe some cases where neural networks outperform any linear approximator.

State estimation for a class of non-linear, continuous-time dynamic systems affected by disturbances is investigated. The estimator is assigned a given structure that depends on an innovation function taking on the form of a ridge computational model, with some parameters to be optimized. The behaviour of the estimation error is analysed by using input-to-state stability. The design of the estimator is reduced to the determination of the parameters in such a way as to guarantee the regional exponential stability of the estimation error in a disturbance-free setting and to minimize a cost function that measures the effectiveness of the estimation when the system is affected by disturbances. Stability is achieved by constraining the derivative of a Lyapunov function to be negative definite on a grid of points, via the penalization of the constraints that are not satisfied. Low-discrepancy sampling techniques, typical of quasi-Monte Carlo methods, are exploited in order to reduce the computational burden in ...

Sufficient conditions for the existence and Lipschitz continuity of optimal strategies for static team optimization problems are studied. Revised statements and proofs of some results appeared in the literature are presented. Their extensions are discussed. As an example of application, optimal production in a multidivisional firm is considered.

The approximation of the optimal policy functions is investigated for dynamic optimization problems with an objective that is additive over a finite number of stages. The distance between optimal and suboptimal values of the objective functional is estimated, in terms of the errors in approximating the optimal policy functions at the various stages. Smoothness properties are derived for such functions and exploited to choose the approximating families. The approximation error is measured in the supremum norm, in such a way to control the error propagation from stage to stage. Nonlinear approximators corresponding to Gaussian radial-basis-function networks with adjustable centers and widths are considered. Conditions are defined, guaranteeing that the number of Gaussians (hence, the number of parameters to be adjusted) does not grow “too fast” with the dimension of the state vector. The results help to mitigate the curse of dimensionality in dynamic optimization. An example of application is given and the use of the estimates is illustrated via a numerical simulation.

Suboptimal solutions to kernel principal component analysis are considered. Such solutions take on the form of linear combinations of all n-tuples of kernel functions centered on the data, where n is a positive integer smaller than the cardinality m of the data sample. Their accuracy in approximating the optimal solution, obtained in general for n = m, is estimated. The analysis made in Gnecco and Sanguineti (Comput Optim Appl 42:265–287, 2009) is extended. The estimates derived therein for the approximation of the first principal axis are improved and extensions to the successive principal axes are derived.

Complexity of Gaussian-radial-basis-function networks, with varying widths, is investigated. Upper bounds on rates of decrease of approximation errors with increasing number of hidden units are derived. Bounds are in terms of norms measuring smoothness (Bessel and Sobolev norms) multiplied by explicitly given functions a(r,d) of the number of variables d and degree of smoothness r. Estimates are proven using suitable integral representations in the form of networks with continua of hidden units computing scaled Gaussians and translated Bessel potentials. Consequences on tractability of approximation by Gaussian-radial-basis function networks are discussed.

Two methods of approximate solution are developed for T-stage stochastic optimal control (SOC) problems, aimed at obtaining finite-horizon management policies for water resource systems. The presence of uncertainties, such as river and rain inflows, is considered. Both approaches are based on the use of families of nonlinear functions, called "one-hidden-layer networks" (OHL networks), made up of linear combinations of simple basis functions containing parameters to be optimized. The first method exploits OHL networks to obtain an accurate approximation of the cost-to-go functions in the dynamic programming procedure for SOC problems. The approximation capabilities of OHL networks are combined with the properties of deterministic sampling techniques aimed at obtaining uniform samplings of high-dimensional domains. In the second method, admissible solutions to SOC problems are constrained to take on the form of OHL networks, whose parameters are determined in such a way to minimize the cost functional associated with SOC problems. Exploiting these tools, the two methods are able to cope with the so-called "curse of dimensionality," which strongly limits the applicability of existing techniques to high-dimensional water resources management in the presence of uncertainties. The theoretical bases of the two approaches are investigated. Simulation results show that the proposed methods are effective for water resource systems of high dimension.

In this paper, approximation by linear combinations of an increasing number n of computational units with adjustable parameters (such as perceptrons and radial basis functions) is investigated. Geometric upper bounds on rates of convergence of approximation errors are derived. The bounds depend on certain parameters specific for each function to be approximated. The results are illustrated by examples of values of such parameters in the case of approximation by linear combinations of orthonormal functions.

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow "fast" with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the "curse of dimensionality," which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables.