Stephane Gaubert

Stephane Gaubert, William McEneaney, Zheng Qu

Max-plus based methods have been recently developed to approximate the value function of possibly high dimensional optimal control problems. A critical step of these methods consists in approximating a function by a supremum of a small number of functions (max-plus "basis functions") taken from a prescribed dictionary. We study several variants of this approximation problem, which we show to be continuous versions of the facility location and $k$-center combinatorial optimization problems, in which the connection costs arise from a Bregman distance. We give theoretical error estimates, quantifying the number of basis functions needed to reach a prescribed accuracy. We derive from our approach a refinement of the curse of dimensionality free method introduced previously by McEneaney, with a higher accuracy for a comparable computational cost.

Marianne Akian, Stephane Gaubert, Meisam Sharify

We show that the sequence of moduli of the eigenvalues of a matrix polynomial is log-majorized, up to universal constants, by a sequence of "tropical roots" depending only on the norms of the matrix coefficients. These tropical roots are the non-differentiability points of an auxiliary tropical polynomial, or equivalently, the opposites of the slopes of its Newton polygon. This extends to the case of matrix polynomials some bounds obtained by Hadamard, Ostrowski and Pólya for the roots of scalar polynomials. We also obtain new bounds in the scalar case, which are accurate for "fewnomials" or when the tropical roots are well separated.

Stephane Gaubert, Yiannis Vlassopoulos

We show that the output of a ReLU neural network can be interpreted as the value of a zero-sum, turn-based, stopping game, which we call the ReLU net game. The game runs in the direction opposite to that of the network, and the input of the network serves as the terminal reward of the game. In fact, evaluating the network is the same as running the Shapley-Bellman backward recursion for the value of the game. Using the expression of the value of the game as an expected total payoff with respect to the path measure induced by the transition probabilities and a pair of optimal policies, we derive a discrete Feynman-Kac-type path-integral formula for the network output. This game-theoretic representation can be used to derive bounds on the output from bounds on the input, leveraging the monotonicity of Shapley operators, and to verify robustness properties using policies as certificates. Moreover, training the neural network becomes an inverse game problem: given pairs of terminal rewards and corresponding values, one seeks transition probabilities and rewards of a game that reproduces them. Finally, we show that a similar approach applies to neural networks with Softplus activation functions, where the ReLU net game is replaced by its entropic regularization.

Giuseppe C. Calafiore, Stephane Gaubert, Member et al.

We show that a neural network whose output is obtained as the difference of the outputs of two feedforward networks with exponential activation function in the hidden layer and logarithmic activation function in the output node (LSE networks) is a smooth universal approximator of continuous functions over convex, compact sets. By using a logarithmic transform, this class of networks maps to a family of subtraction-free ratios of generalized posynomials, which we also show to be universal approximators of positive functions over log-convex, compact subsets of the positive orthant. The main advantage of Difference-LSE networks with respect to classical feedforward neural networks is that, after a standard training phase, they provide surrogate models for design that possess a specific difference-of-convex-functions form, which makes them optimizable via relatively efficient numerical methods. In particular, by adapting an existing difference-of-convex algorithm to these models, we obtain an algorithm for performing effective optimization-based design. We illustrate the proposed approach by applying it to data-driven design of a diet for a patient with type-2 diabetes.

Giuseppe C. Calafiore, Stephane Gaubert, Corrado Possieri

We show in this paper that a one-layer feedforward neural network with exponential activation functions in the inner layer and logarithmic activation in the output neuron is an universal approximator of convex functions. Such a network represents a family of scaled log-sum exponential functions, here named LSET. Under a suitable exponential transformation, the class of LSET functions maps to a family of generalized posynomials GPOST, which we similarly show to be universal approximators for log-log-convex functions. A key feature of an LSET network is that, once it is trained on data, the resulting model is convex in the variables, which makes it readily amenable to efficient design based on convex optimization. Similarly, once a GPOST model is trained on data, it yields a posynomial model that can be efficiently optimized with respect to its variables by using geometric programming (GP). The proposed methodology is illustrated by two numerical examples, in which, first, models are constructed from simulation data of the two physical processes (namely, the level of vibration in a vehicle suspension system, and the peak power generated by the combustion of propane), and then optimization-based design is performed on these models.

Marianne Akian, Stephane Gaubert, Asma Lakhoua

We introduce a max-plus analogue of the Petrov-Galerkin finite element method to solve finite horizon deterministic optimal control problems. The method relies on a max-plus variational formulation. We show that the error in the sup norm can be bounded from the difference between the value function and its projections on max-plus and min-plus semimodules, when the max-plus analogue of the stiffness matrix is exactly known. In general, the stiffness matrix must be approximated: this requires approximating the operation of the Lax-Oleinik semigroup on finite elements. We consider two approximations relying on the Hamiltonian. We derive a convergence result, in arbitrary dimension, showing that for a class of problems, the error estimate is of order $δ+Δx(δ)^{-1}$ or $\sqrtδ+Δx(δ)^{-1}$, depending on the choice of the approximation, where $δ$ and $Δx$ are respectively the time and space discretization steps. We compare our method with another max-plus based discretization method previously introduced by Fleming and McEneaney. We give numerical examples in dimension 1 and 2.

Marianne Akian, Stephane Gaubert, Asma Lakhoua

We develop the max-plus finite element method to solve finite horizon deterministic optimal control problems. This method, that we introduced in a previous work, relies on a max-plus variational formulation, and exploits the properties of projectors on max-plus semimodules. We prove here a convergence result, in arbitrary dimension, showing that for a subclass of problems, the error estimate is of order $δ+Δx(δ)^{-1}$, where $δ$ and $Δx$ are the time and space steps respectively. We also show how the max-plus analogues of the mass and stiffness matrices can be computed by convex optimization, even when the global problem is non convex. We illustrate the method by numerical examples in dimension 2.