Showing 1–50 of 65 results for author: De Lara, M

A Unified View of Polarity for Functions

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: We propose a unified view of the polarity of functions, that encompasses all specific definitions, generalizes several well-known properties and provides new results. We show that bipolar sets and bipolar functions are isomorphic lattices. Also, we explore three possible notions of polar subdifferential associated with a nonnegative function, and we make the connection with the notion of alignemen… ▽ More We propose a unified view of the polarity of functions, that encompasses all specific definitions, generalizes several well-known properties and provides new results. We show that bipolar sets and bipolar functions are isomorphic lattices. Also, we explore three possible notions of polar subdifferential associated with a nonnegative function, and we make the connection with the notion of alignement of vectors. △ Less

Submitted 22 October, 2024; originally announced October 2024.

A Two-Timescale Decision-Hazard-Decision Formulation for Storage Usage Values Calculation

Authors: Camila Martinez Parra, Michel de Lara, Jean-Philippe Chancelier, Pierre Carpentier, Jean-Marc Janin, Manuel Ruiz

Abstract: The penetration of renewable energies requires additional storages to deal with intermittency. Accordingly, there is growing interest in evaluating the opportunity cost (usage value) associated with stored energy in large storages, a cost obtained by solving a multistage stochastic optimization problem. Today, to compute usage values under uncertainties, an adequacy resource problem is solved usin… ▽ More The penetration of renewable energies requires additional storages to deal with intermittency. Accordingly, there is growing interest in evaluating the opportunity cost (usage value) associated with stored energy in large storages, a cost obtained by solving a multistage stochastic optimization problem. Today, to compute usage values under uncertainties, an adequacy resource problem is solved using stochastic dynamic programming assuming a hazard-decision information structure. This modelling assumes complete knowledge of the coming week uncertainties, which is not adapted to the system operation as the intermittency occurs at smaller timescale. We equip the twotimescale problem with a new information structure considering planning and recourse decisions: decision-hazard-decision. This structure is used to decompose the multistage decision-making process into a nonanticipative planning step in which the on/off decisions for the thermal units are made, and a recourse step in which the power modulation decisions are made once the uncertainties have been disclosed. In a numerical case, we illustrate how usage values are sensitive as how the disclosure of information is modelled. △ Less

Submitted 30 August, 2024; originally announced August 2024.

Multistage stochastic optimization of a mono-site hydrogen infrastructure by decomposition techniques

Authors: Raian Lefgoum, Sezin Afsar, Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara

Abstract: The development of hydrogen infrastructures requires to reduce their costs. In this paper, we develop a multistage stochastic optimization model for the management of a hydrogen infrastructure which consists of an electrolyser, a compressor and a storage to serve a transportation demand. This infrastructure is powered by three different sources: on-site photovoltaic panels (PV), renewable ene… ▽ More The development of hydrogen infrastructures requires to reduce their costs. In this paper, we develop a multistage stochastic optimization model for the management of a hydrogen infrastructure which consists of an electrolyser, a compressor and a storage to serve a transportation demand. This infrastructure is powered by three different sources: on-site photovoltaic panels (PV), renewable energy through a power purchase agreement (PPA) and the power grid. We consider uncertainties affecting on-site photovoltaic production and hydrogen demand. Renewable energy sources are emphasized in the hydrogen production process to ensure eligibility for a subsidy, which is awarded if the proportion of nonrenewable electricity usage stays under a predetermined threshold. We solve the multistage stochastic optimization problem using a decomposition method based on Lagrange duality. The numerical results indicate that the solution to this problem, formulated as a policy, achieves a small duality gap, thus proving the effectiveness of this approach. △ Less

Submitted 1 July, 2024; originally announced July 2024.

Learning with Fitzpatrick Losses

Authors: Seta Rakotomandimby, Jean-Philippe Chancelier, Michel de Lara, Mathieu Blondel

Abstract: Fenchel-Young losses are a family of convex loss functions, encompassing the squared, logistic and sparsemax losses, among others. Each Fenchel-Young loss is implicitly associated with a link function, for mapping model outputs to predictions. For instance, the logistic loss is associated with the soft argmax link function. Can we build new loss functions associated with the same link function as… ▽ More Fenchel-Young losses are a family of convex loss functions, encompassing the squared, logistic and sparsemax losses, among others. Each Fenchel-Young loss is implicitly associated with a link function, for mapping model outputs to predictions. For instance, the logistic loss is associated with the soft argmax link function. Can we build new loss functions associated with the same link function as Fenchel-Young losses? In this paper, we introduce Fitzpatrick losses, a new family of convex loss functions based on the Fitzpatrick function. A well-known theoretical tool in maximal monotone operator theory, the Fitzpatrick function naturally leads to a refined Fenchel-Young inequality, making Fitzpatrick losses tighter than Fenchel-Young losses, while maintaining the same link function for prediction. As an example, we introduce the Fitzpatrick logistic loss and the Fitzpatrick sparsemax loss, counterparts of the logistic and the sparsemax losses. This yields two new tighter losses associated with the soft argmax and the sparse argmax, two of the most ubiquitous output layers used in machine learning. We study in details the properties of Fitzpatrick losses and in particular, we show that they can be seen as Fenchel-Young losses using a modified, target-dependent generating function. We demonstrate the effectiveness of Fitzpatrick losses for label proportion estimation. △ Less

Submitted 23 May, 2024; originally announced May 2024.

Decomposition Methods for Dynamically Monotone Two-Time-Scale Stochastic Optimization Problems

Authors: Tristan Rigaut, Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara

Abstract: In energy management, it is common that strategic investment decisions (storage capacity, production units) are made at a slow time scale, whereas operational decisions (storage, production) are made at a fast time scale: for such problems, the total number of decision stages may be huge. In this paper, we consider multistage stochastic optimization problems with two time-scales, and we propose a… ▽ More In energy management, it is common that strategic investment decisions (storage capacity, production units) are made at a slow time scale, whereas operational decisions (storage, production) are made at a fast time scale: for such problems, the total number of decision stages may be huge. In this paper, we consider multistage stochastic optimization problems with two time-scales, and we propose a time block decomposition scheme to address them numerically. More precisely, our approach relies on two assumptions. On the one hand, we suppose slow time scale stagewise independence of the noise process: the random variables that occur during a slow time scale interval are independent of those at another slow time scale interval. This makes it possible to use Dynamic Programming at the slow time scale. On the other hand, we suppose a dynamically monotone property for the problem under consideration, which makes it possible to obtain bounds. Then, we present two algorithmic methods to compute upper and lower bounds for slow time scale Bellman value functions. Both methods rely respectively on primal and dual decomposition of the Bellman equation applied at the slow time scale. We assess the methods tractability and validate their efficiency by solving a battery management problem where the fast time scale operational decisions have an impact on the storage current capacity, hence on the strategic decisions to renew the battery at the slow time scale. △ Less

Submitted 7 March, 2023; originally announced March 2023.

Contributions on complexity bounds for Deterministic Partially Observed Markov Decision Process

Authors: Cyrille Vessaire, Jean-Philippe Chancelier, Michel de Lara, Pierre Carpentier, Alejandro Rodríguez-Martínez

Abstract: Markov Decision Processes (Mdps) form a versatile framework used to model a wide range of optimization problems. The Mdp model consists of sets of states, actions, time steps, rewards, and probability transitions. When in a given state and at a given time, the decision maker's action generates a reward and determines the state at the next time step according to the probability transition function.… ▽ More Markov Decision Processes (Mdps) form a versatile framework used to model a wide range of optimization problems. The Mdp model consists of sets of states, actions, time steps, rewards, and probability transitions. When in a given state and at a given time, the decision maker's action generates a reward and determines the state at the next time step according to the probability transition function. However, Mdps assume that the decision maker knows the state of the controlled dynamical system. Hence, when one needs to optimize controlled dynamical systems under partial observation, one often turns toward the formalism of Partially Observed Markov Decision Processes (Pomdp). Pomdps are often untractable in the general case as Dynamic Programming suffers from the curse of dimensionality. Instead of focusing on the general Pomdps, we present a subclass where transitions and observations mappings are deterministic: Deterministic Partially Observed Markov Decision Processes (Det-Pomdp). That subclass of problems has been studied by (Littman, 1996) and (Bonet, 2009). It was first considered as a limit case of Pomdps by Littman, mainly used to illustrate the complexity of Pomdps when considering as few sources of uncertainties as possible. In this paper, we improve on Littman's complexity bounds. We then introduce and study an even simpler class: Separated Det-Pomdps and give some new complexity bounds for this class. This new class of problems uses a property of the dynamics and observation to push back the curse of dimensionality. △ Less

Submitted 20 January, 2023; originally announced January 2023.

Differentiability and Regularization of Parametric Convex Value Functions in Stochastic Multistage Optimization

Authors: Adrien Le Franc, Jean-Philippe Chancelier, Pierre Carpentier, Michel de Lara

Abstract: In multistage decision problems, it is often the case that an initial strategic decision (such as investment) is followed by many operational ones (operating the investment). Such initial strategic decision can be seen as a parameter affecting a multistage decision problem. More generally, we study in this paper a standard multistage stochastic optimization problem depending on a parameter. When t… ▽ More In multistage decision problems, it is often the case that an initial strategic decision (such as investment) is followed by many operational ones (operating the investment). Such initial strategic decision can be seen as a parameter affecting a multistage decision problem. More generally, we study in this paper a standard multistage stochastic optimization problem depending on a parameter. When the parameter is fixed, Stochastic Dynamic Programming provides a way to compute the optimal value of the problem. Thus, the value function depends both on the state (as usual) and on the parameter. Our aim is to investigate on the possibility to efficiently compute gradients of the value function with respect to the parameter, when these objects exist. When nondifferentiable, we propose a regularization method based on the Moreau-Yosida envelope. We present a numerical test case from day-ahead power scheduling. △ Less

Submitted 6 February, 2023; v1 submitted 20 December, 2022; originally announced December 2022.

Duality Between Lagrangians and Rockafellians

Authors: Michel de Lara

Abstract: In his monograph \emph{Conjugate Duality and Optimization}, Rockafellar puts forward a ``perturbation + duality'' method to obtain a dual problem for an original minimization problem. First, one embeds the minimization problem into a family of perturbed problems (thus giving a so-called perturbation function); the perturbation of the original function to be minimized has recently been called… ▽ More In his monograph \emph{Conjugate Duality and Optimization}, Rockafellar puts forward a ``perturbation + duality'' method to obtain a dual problem for an original minimization problem. First, one embeds the minimization problem into a family of perturbed problems (thus giving a so-called perturbation function); the perturbation of the original function to be minimized has recently been called a Rockafellian. Second, when the perturbation variable belongs to a primal vector space paired, by a bilinear form, with a dual vector space, one builds a Lagrangian from a Rockafellian; one also obtains a so-called dual function (and a dual problem). The method has been extended from Fenchel duality to generalized convexity: when the perturbation belongs to a primal set paired, by a coupling function, with a dual set, one also builds a Rockafellian from a Lagrangian. Following these paths, we highlight a duality between Lagrangians and Rockafellians. Where the material mentioned above mostly focuses on moving from Rockafellian to Lagrangian, we treat them equally and display formulas that go both ways. We propose a definition of Lagrangian-Rockafellian couples. We characterize these latter as dual functions, with respect to a coupling, and also in terms of generalized convex functions. The duality between perturbation and dual functions is not as clear cut. △ Less

Submitted 10 March, 2023; v1 submitted 23 November, 2022; originally announced November 2022.

Time Consistency for Multistage Stochastic Optimization Problems under Constraints in Expectation

Authors: Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara

Abstract: We consider sequences-indexed by time (discrete stages)-of families of multistage stochastic optimization problems. At each time, the optimization problems in a family are parameterized by some quantities (initial states, constraint levels.. .). In this framework, we introduce an adapted notion of time consistent optimal solutions, that is, solutions that remain optimal after truncation of the pas… ▽ More We consider sequences-indexed by time (discrete stages)-of families of multistage stochastic optimization problems. At each time, the optimization problems in a family are parameterized by some quantities (initial states, constraint levels.. .). In this framework, we introduce an adapted notion of time consistent optimal solutions, that is, solutions that remain optimal after truncation of the past and that are optimal for any values of the parameters. We link this time consistency notion with the concept of state variable in Markov Decision Processes for a class of multistage stochastic optimization problems incorporating state constraints at the final time, either formulated in expectation or in probability. For such problems, when the primitive noise random process is stagewise independent and takes a finite number of values, we show that time consistent solutions can be obtained by considering a finite dimensional state variable. We illustrate our results on a simple dam management problem. △ Less

Submitted 29 August, 2022; originally announced August 2022.

Accelerating high order discontinuous Galerkin solvers using neural networks: 3D compressible Navier-Stokes equations

Authors: Fernando Manrique de Lara, Esteban Ferrer

Abstract: We propose to accelerate a high order discontinuous Galerkin solver using neural networks. We include a corrective forcing to a low polynomial order simulation to enhance its accuracy. The forcing is obtained by training a deep fully connected neural network, using a high polynomial order simulation but only for a short time frame. With this corrective forcing, we can run the low polynomial order… ▽ More We propose to accelerate a high order discontinuous Galerkin solver using neural networks. We include a corrective forcing to a low polynomial order simulation to enhance its accuracy. The forcing is obtained by training a deep fully connected neural network, using a high polynomial order simulation but only for a short time frame. With this corrective forcing, we can run the low polynomial order simulation faster (with large time steps and low cost per time step) while improving its accuracy. We explored this idea for a 1D Burgers' equation in (Marique and Ferrer, CAF 2022), and we have extended this work to the 3D Navier-Stokes equations, with and without a Large Eddy Simulation closure model. We test the methodology with the turbulent Taylor Green Vortex case and for various Reynolds numbers (30, 200 and 1600). In addition, the Taylor Green Vortex evolves with time and covers laminar, transitional, and turbulent regimes, as time progresses. The proposed methodology proves to be applicable to a variety of flows and regimes. The results show that the corrective forcing is effective in all Reynolds numbers and time frames (excluding the initial flow development). We can train the corrective forcing with a polynomial order of 8, to increase the accuracy of simulations from a polynomial order 3 to 6, when correcting outside the training time frame. The low order correct solution is 4 to 5 times faster than a simulation with comparable accuracy (polynomial order 6). Additionally, we explore changes in the hyperparameters and use transfer learning to speed up the training. We observe that it is not useful to train a corrective forcing using a different flow condition. However, an already trained corrective forcing can be used to initialise a new training (at the correct flow conditions) to obtain an effective forcing with only a few training iterations. △ Less

Submitted 23 July, 2022; originally announced July 2022.

HORSES3D: a high-order discontinuous Galerkin solver for flow simulations and multi-physics applications

Authors: E. Ferrer, G. Rubio, G. Ntoukas, W. Laskowski, O. A. Mariño, S. Colombo, A. Mateo-Gabín, F. Manrique de Lara, D. Huergo, J. Manzanero, A. M. Rueda-Ramírez, D. A. Kopriva, E. Valero

Abstract: We present the latest developments of our High-Order Spectral Element Solver (HORSES3D), an open source high-order discontinuous Galerkin framework, capable of solving a variety of flow applications, including compressible flows (with or without shocks), incompressible flows, various RANS and LES turbulence models, particle dynamics, multiphase flows, and aeroacoustics. We provide an overview of t… ▽ More We present the latest developments of our High-Order Spectral Element Solver (HORSES3D), an open source high-order discontinuous Galerkin framework, capable of solving a variety of flow applications, including compressible flows (with or without shocks), incompressible flows, various RANS and LES turbulence models, particle dynamics, multiphase flows, and aeroacoustics. We provide an overview of the high-order spatial discretisation (including energy/entropy stable schemes) and anisotropic p-adaptation capabilities. The solver is parallelised using MPI and OpenMP showing good scalability for up to 1000 processors. Temporal discretisations include explicit, implicit, multigrid, and dual time-stepping schemes with efficient preconditioners. Additionally, we facilitate meshing and simulating complex geometries through a mesh-free immersed boundary technique. We detail the available documentation and the test cases included in the GitHub repository. △ Less

Submitted 20 June, 2022; originally announced June 2022.

Optimization of a domestic microgrid equipped with solar panel and battery: Model Predictive Control and Stochastic Dual Dynamic Programming approaches

Authors: François Pacaud, Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara

Abstract: In this study, a microgrid with storage (battery, hot water tank) and solar panel is considered. We benchmark two algorithms, MPC and SDDP, that yield online policies to manage the microgrid, and compare them with a rule based policy. Model Predictive Control (MPC) is a well-known algorithm which models the future uncertainties with a deterministic forecast. By contrast, Stochastic Dual Dynamic Pr… ▽ More In this study, a microgrid with storage (battery, hot water tank) and solar panel is considered. We benchmark two algorithms, MPC and SDDP, that yield online policies to manage the microgrid, and compare them with a rule based policy. Model Predictive Control (MPC) is a well-known algorithm which models the future uncertainties with a deterministic forecast. By contrast, Stochastic Dual Dynamic Programming (SDDP) models the future uncertainties as stagewise independent random variables with known probability distributions. We present a scheme, based on out-of-sample validation, to fairly compare the two online policies yielded by MPC and SDDP. Our numerical studies put to light that MPC and SDDP achieve significant gains compared to the rule based policy, and that SDDP overperforms MPC not only on average but on most of the out-of-sample assessment scenarios. △ Less

Submitted 16 May, 2022; originally announced May 2022.

Comments: arXiv admin note: substantial text overlap with arXiv:1801.06479

Multistage Optimization of a Petroleum Production System with Material Balance Model

Authors: Cyrille Vessaire, Jean-Philippe Chancelier, Michel de Lara, Pierre Carpentier, Alejandro Rodríguez-Martínez, Anna Roberts

Abstract: In this paper, we propose a mathematical formulation for the management of an oil production network as a multistage optimization problem. The reservoir is modeled as a controlled dynamical system by using material balance equations. We use a dynamic programming algorithm to solve the optimization problem. Two numerical applications illustrate our work: the first one consists in optimizing the pro… ▽ More In this paper, we propose a mathematical formulation for the management of an oil production network as a multistage optimization problem. The reservoir is modeled as a controlled dynamical system by using material balance equations. We use a dynamic programming algorithm to solve the optimization problem. Two numerical applications illustrate our work: the first one consists in optimizing the production of a gas reservoir, whereas the second one tackles an oil reservoir with water injection. △ Less

Submitted 20 September, 2022; v1 submitted 4 January, 2022; originally announced January 2022.

The Capra-subdifferential of the l0 pseudonorm

Authors: Adrien Le Franc, Jean-Philippe Chancelier, Michel de Lara

Abstract: The l0 pseudonorm counts the nonzero coordinates of a vector. It is often used in optimization problems to enforce the sparsity of the solution. However, this function is nonconvex and noncontinuous, and optimization problems formulated with l0 in the objective function or in the constraints are hard to solve in general. Recently, a new family of coupling functions - called Capra (constant along p… ▽ More The l0 pseudonorm counts the nonzero coordinates of a vector. It is often used in optimization problems to enforce the sparsity of the solution. However, this function is nonconvex and noncontinuous, and optimization problems formulated with l0 in the objective function or in the constraints are hard to solve in general. Recently, a new family of coupling functions - called Capra (constant along primal rays) - has proved to induce relevant generalized Fenchel-Moreau conjugacies to handle the l0 pseudonorm. In particular, under a suitable choice of source norm on the Euclidean space used in the definition of the Capra coupling - the function l0 is Capra-subdifferentiable, hence is Capra-convex. In this article, we give explicit formulations for the Capra subdifferential of l0, when the source norm is a lp norm with p larger that 1. We illustrate our results with graphical visualizations of the Capra subdifferential of l0 for the Euclidean source norm. △ Less

Submitted 18 August, 2022; v1 submitted 31 December, 2021; originally announced December 2021.

Causal Inference Theory with Information Dependency Models

Authors: Benjamin Heymann, Michel de Lara, Jean-Philippe Chancelier

Abstract: Inferring the potential consequences of an unobserved event is a fundamental scientific question. To this end, Pearl's celebrated do-calculus provides a set of inference rules to derive an interventional probability from an observational one. In this framework, the primitive causal relations are encoded as functional dependencies in a Structural Causal Model (SCM), which are generally mapped into… ▽ More Inferring the potential consequences of an unobserved event is a fundamental scientific question. To this end, Pearl's celebrated do-calculus provides a set of inference rules to derive an interventional probability from an observational one. In this framework, the primitive causal relations are encoded as functional dependencies in a Structural Causal Model (SCM), which are generally mapped into a Directed Acyclic Graph (DAG) in the absence of cycles. In this paper, by contrast, we capture causality without reference to graphs or functional dependencies, but with information fields and Witsenhausen's intrinsic model. The three rules of do-calculus reduce to a unique sufficient condition for conditional independence, the topological separation, which presents interesting theoretical and practical advantages over the d-separation. With this unique rule, we can deal with systems that cannot be represented with DAGs, for instance systems with cycles and/or 'spurious' edges. We treat an example that cannot be handled-to the extent of our knowledge-with the tools of the current literature. We also explain why, in the presence of cycles, the theory of causal inference might require different tools, depending on whether the random variables are discrete or continuous. △ Less

Submitted 9 August, 2021; v1 submitted 6 August, 2021; originally announced August 2021.

Topological Conditional Separation

Authors: Michel de Lara, Jean-Philippe Chancelier, Benjamin Heymann

Abstract: Pearl's d-separation is a foundational notion to study conditional independence between random variables. We define the topological conditional separation and we show that it is equivalent to the d-separation, extended beyond acyclic graphs, be they finite or infinite. Pearl's d-separation is a foundational notion to study conditional independence between random variables. We define the topological conditional separation and we show that it is equivalent to the d-separation, extended beyond acyclic graphs, be they finite or infinite. △ Less

Submitted 6 August, 2021; originally announced August 2021.

Conditional Separation as a Binary Relation. A Coq Assisted Proof

Authors: Jean-Philippe Chancelier, Michel de Lara, Benjamin Heymann

Abstract: The concept of d-separation holds a pivotal role in causality theory, serving as a fundamental tool for deriving conditional independence properties from causal graphs. Pearl defined the d-separation of two subsets conditionally on a third one. In this study, we present a novel perspective by showing i) how the d-separation can be extended beyond acyclic graphs, possibly infinite, and ii) how… ▽ More The concept of d-separation holds a pivotal role in causality theory, serving as a fundamental tool for deriving conditional independence properties from causal graphs. Pearl defined the d-separation of two subsets conditionally on a third one. In this study, we present a novel perspective by showing i) how the d-separation can be extended beyond acyclic graphs, possibly infinite, and ii) how it can be expressed and characterized as a binary relation between vertices. Compared to the typical perspectives in causality theory, our equivalence opens the door to more compact and computational proofing techniques, because the language of binary relations is well adapted to equational reasoning. Additionally, and of independent interest, the proofs of the results presented in this paper are checked with the Coq proof assistant. △ Less

Submitted 2 April, 2024; v1 submitted 6 August, 2021; originally announced August 2021.

Minimization Interchange Theorem on Posets

Authors: Jean-Philippe Chancelier, Michel de Lara, Benoît Tran

Abstract: Interchange theorems between minimization and integration are useful in optimization, especially in optimal control and in stochastic optimization. In this article, we establish a generalized minimization interchange theorem, where integration is replaced by a monotone mapping between posets (partially ordered sets). As an application, we recover, and slightly extend, classical results from the li… ▽ More Interchange theorems between minimization and integration are useful in optimization, especially in optimal control and in stochastic optimization. In this article, we establish a generalized minimization interchange theorem, where integration is replaced by a monotone mapping between posets (partially ordered sets). As an application, we recover, and slightly extend, classical results from the literature, and we tackle the case of the Choquet integral. Our result provides insight on the mechanisms behind existing interchange results. △ Less

Submitted 13 July, 2021; originally announced July 2021.

Decentralized Multistage Optimization of Large-Scale Microgrids under Stochasticity

Authors: François Pacaud, Michel de Lara, Jean-Philippe Chancelier, Pierre Carpentier

Abstract: Microgrids are recognized as a relevant tool to absorb decentralized renewable energies in the energy mix. However, the sequential handling of multiple stochastic productions and demands, and of storage, make their management a delicate issue. We add another layer of complexity by considering microgrids where different buildings stand at the nodes of a network and are connected by the arcs; some b… ▽ More Microgrids are recognized as a relevant tool to absorb decentralized renewable energies in the energy mix. However, the sequential handling of multiple stochastic productions and demands, and of storage, make their management a delicate issue. We add another layer of complexity by considering microgrids where different buildings stand at the nodes of a network and are connected by the arcs; some buildings host local production and storage capabilities, and can exchange with others their energy surplus. We formulate the problem as a multistage stochastic optimization problem, corresponding to the minimization of the expected temporal sum of operational costs, while satisfying the energy demand at each node, for all time. The resulting mathematical problem has a large-scale nature, exhibiting both spatial and temporal couplings. However, the problem displays a network structure that makes it amenable to a mix of spatial decomposition-coordination with temporal decomposition methods. We conduct numerical simulations on microgrids of different sizes and topologies, with up to 48 nodes and 64 state variables. Decomposition methods are faster and provide more efficient policies than a state-of-the-art Stochastic Dual Dynamic Programming algorithm. Moreover, they scale almost linearly with the state dimension, making them a promising tool to address more complex microgrid optimal management problems. △ Less

Submitted 8 June, 2021; originally announced June 2021.

Comments: arXiv admin note: substantial text overlap with arXiv:1912.10902

Decomposition-Coordination Method for Finite Horizon Bandit Problems

Authors: Michel de Lara, Benjamin Heymann, Jean-Philippe Chancelier

Abstract: Optimally solving a multi-armed bandit problem suffers the curse of dimensionality. Indeed, resorting to dynamic programming leads to an exponential growth of computing time, as the number of arms and the horizon increase. We introduce a decompositioncoordination heuristic, DeCo, that turns the initial problem into parallelly coordinated one-armed bandit problems. As a consequence, we obtain a com… ▽ More Optimally solving a multi-armed bandit problem suffers the curse of dimensionality. Indeed, resorting to dynamic programming leads to an exponential growth of computing time, as the number of arms and the horizon increase. We introduce a decompositioncoordination heuristic, DeCo, that turns the initial problem into parallelly coordinated one-armed bandit problems. As a consequence, we obtain a computing time which is essentially linear in the number of arms. In addition, the decomposition provides a theoretical lower bound on the regret. For the two-armed bandit case, dynamic programming provides the exact solution, which is almost matched by the DeCo heuristic. Moreover, in numerical simulations with up to 100 rounds and 20 arms, DeCo outperforms classic algorithms (Thompson sampling and Kullback-Leibler upper-confidence bound) and almost matches the theoretical lower bound on the regret for 20 arms. △ Less

Submitted 21 May, 2024; v1 submitted 2 June, 2021; originally announced June 2021.

Best Convex Lower Approximations of the l 0 Pseudonorm on Unit Balls

Authors: Thomas Bittar, Jean-Philippe Chancelier, Michel de Lara

Abstract: Whereas the norm of a vector measures amplitude (and is a 1-homogeneous function), sparsity is measured by the 0-homogeneous l0 pseudonorm, which counts the number of nonzero components. We propose a family of conjugacies suitable for the analysis of 0-homogeneous functions. These conjugacies are derived from couplings between vectors, given by their scalar product divided by a 1-homogeneous norma… ▽ More Whereas the norm of a vector measures amplitude (and is a 1-homogeneous function), sparsity is measured by the 0-homogeneous l0 pseudonorm, which counts the number of nonzero components. We propose a family of conjugacies suitable for the analysis of 0-homogeneous functions. These conjugacies are derived from couplings between vectors, given by their scalar product divided by a 1-homogeneous normalizing factor. With this, we characterize the best convex lower approximation of a 0-homogeneous function on the unit ''ball'' of a normalization function (i.e. a norm without the requirement of subadditivity). We do the same with the best convex and 1-homogeneous lower approximation. In particular, we provide expressions for the tightest convex lower approximation of the l0 pseudonorm on any unit ball, and we show that the tightest norm which minorizes the l0 pseudonorm on the unit ball of any lp-norm is the l1-norm. We also provide the tightest convex lower convex approximation of the l0 pseudonorm on the unit ball of any norm. △ Less

Submitted 31 May, 2021; originally announced May 2021.

Rank-Based Norms, Capra-Conjugacies and the Rank Function

Authors: Paul Barbier, Jean-Philippe Chancelier, Michel de Lara, Valentin Paravy

Abstract: We consider the space of matrices, with given number of rows and of columns, equipped with the classic trace scalar product. With any matrix (source) norm, we associate a coupling, called Capra, between the space of matrices and itself. Then, we compute the Capra conjugate and biconjugate of the rank function. They are expressed in function of a sequence of rank-based norms, more precisely general… ▽ More We consider the space of matrices, with given number of rows and of columns, equipped with the classic trace scalar product. With any matrix (source) norm, we associate a coupling, called Capra, between the space of matrices and itself. Then, we compute the Capra conjugate and biconjugate of the rank function. They are expressed in function of a sequence of rank-based norms, more precisely generalized r-rank and dual r-rank matrix norms associated with the matrix source norm. We deduce a lower bound of the rank function given by a variational formula which involves the generalized r-rank norms. In the case of the Frobenius norm, we show that the rank function is equal to the variational formula. △ Less

Submitted 6 February, 2023; v1 submitted 31 May, 2021; originally announced May 2021.

A vehicle routing problem for biological sample transportation in healthcare: mathematical formulations and a metaheuristic approach

Authors: Mario Benini, Paolo Detti, Garazi Zabalo Manrique de Lara

Abstract: In this paper, a real-world transportation problem is addressed, concerning the collection and the transportation of biological sample tubes from sampling points to a main hospital. Blood and other biological samples are collected in different centers during morning hours. Then, the samples are transported to the main hospital, for their analysis, by a fleet of vehicles located in geographically d… ▽ More In this paper, a real-world transportation problem is addressed, concerning the collection and the transportation of biological sample tubes from sampling points to a main hospital. Blood and other biological samples are collected in different centers during morning hours. Then, the samples are transported to the main hospital, for their analysis, by a fleet of vehicles located in geographically distributed depots. Each sample has a limited lifetime and must arrive to the main hospital within that time. If a sample cannot arrive to the hospital within the lifetime, either is discarded or must be processed in dedicated facilities called Spoke Centers.Two Mixed Integer Linear Programming formulations and an Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm have been developed for the problem. Computational experiments on different sets of instances based on real-life data provided by the Local Healthcare Authority of Bologna, Italy, are presented. A comparison on small instances with the optimal solutions obtained by the formulations shows the effectiveness of the proposed ALNS algorithm. On real-life instances, different batching policies of the samples are evaluated. The results show that the ALNS algorithm is able to find solutions in which all the samples are delivered on time, while in the real case about the 40% [5] of the samples is delivered late. △ Less

Submitted 12 March, 2021; originally announced April 2021.

Conditional Infimum and Hidden Convexity in Optimization

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: Detecting hidden convexity is one of the tools to address nonconvex minimization problems. After giving a formal definition of hidden convexity, we introduce the notion of conditional infimum, as it will prove instrumental in detecting hidden convexity. We develop the theory of the conditional infimum, and we establish a tower property, relevant for minimization problems. Thus equipped, we provide… ▽ More Detecting hidden convexity is one of the tools to address nonconvex minimization problems. After giving a formal definition of hidden convexity, we introduce the notion of conditional infimum, as it will prove instrumental in detecting hidden convexity. We develop the theory of the conditional infimum, and we establish a tower property, relevant for minimization problems. Thus equipped, we provide a sufficient condition for hidden convexity in nonconvex minimization problems. We illustrate our result on nonconvex quadratic minimization problems. We conclude with perspectives for using the conditional infimum in relation to the so-called S-procedure, to couplings and conjugacies, and to lower bound convex programs. △ Less

Submitted 12 April, 2021; originally announced April 2021.

Kuhn's Equivalence Theorem for Games in Product Form

Authors: Benjamin Heymann, Michel de Lara, Jean-Philippe Chancelier

Abstract: We propose an alternative to the tree representation of extensive form games. Games in product form represent information with $σ$-fields over a product set, and do not require an explicit description of the play temporality, as opposed to extensive form games on trees. This representation encompasses games with a continuum of actions, randomness and players, as well as games for which the play or… ▽ More We propose an alternative to the tree representation of extensive form games. Games in product form represent information with $σ$-fields over a product set, and do not require an explicit description of the play temporality, as opposed to extensive form games on trees. This representation encompasses games with a continuum of actions, randomness and players, as well as games for which the play order cannot be determined in advance. We adapt and prove Kuhn's theorem-regarding equivalence between mixed and behavioral strategies under perfect recall-for games in product form with continuous action sets. △ Less

Submitted 13 July, 2022; v1 submitted 12 April, 2021; originally announced April 2021.

A Fresh Geometrical Look at the General S-Procedure

Authors: Michel de Lara, Jean-Baptiste Hiriart-Urruty

Abstract: We revisit the S-procedure for general functions with "geometrical glasses". We thus delineate a necessary condition, and almost a sufficient condition, to have the S-procedure valid. Everything is expressed in terms of convexity of augmented sets (convex hulls, conical hulls) of images built from the data functions. We revisit the S-procedure for general functions with "geometrical glasses". We thus delineate a necessary condition, and almost a sufficient condition, to have the S-procedure valid. Everything is expressed in terms of convexity of augmented sets (convex hulls, conical hulls) of images built from the data functions. △ Less

Submitted 12 May, 2021; v1 submitted 11 February, 2021; originally announced February 2021.

Optimal Joint Allocation of Efforts in Inclusive Fitness by Related Individuals

Authors: Michel de Lara

Abstract: Families are places of affection and cooperation, but also of conflict. In his famous paper Parent-Offspring Conflict, Robert L. Trivers builds upon W. D. Hamilton's concept of inclusive fitness to argue for genetic conflict in parent-offspring relationships, and to derive numerical predictions on the intensity of the conflict. We propose a mathematical model of game theory that depicts how each m… ▽ More Families are places of affection and cooperation, but also of conflict. In his famous paper Parent-Offspring Conflict, Robert L. Trivers builds upon W. D. Hamilton's concept of inclusive fitness to argue for genetic conflict in parent-offspring relationships, and to derive numerical predictions on the intensity of the conflict. We propose a mathematical model of game theory that depicts how each member of a family allocates her resource budget to maximize her inclusive fitness; this latter is made of the sum of personal fitness plus the sum of relatives fitnesses weighted by Wright's coefficients of relationship. We define an optimal allocation profile as a Nash equilibrium, and we characterize the solutions in function of resource budgets, coefficients of relationship and derivatives of personal fitnesses. △ Less

Submitted 17 November, 2020; originally announced November 2020.

Constant Along Primal Rays Conjugacies and Generalized Convexity for Functions of the Support

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: The support of a vector in R d is the set of indices with nonzero entries. Functions of the support have the property to be 0-homogeneous and, because of that, the Fenchel conjugacy fails to provide relevant analysis. In this paper, we define the coupling Capra between R d and itself by dividing the classic Fenchel scalar product coupling by a given (source) norm on R d. Our main result is that, w… ▽ More The support of a vector in R d is the set of indices with nonzero entries. Functions of the support have the property to be 0-homogeneous and, because of that, the Fenchel conjugacy fails to provide relevant analysis. In this paper, we define the coupling Capra between R d and itself by dividing the classic Fenchel scalar product coupling by a given (source) norm on R d. Our main result is that, when both the source norm and its dual norm are orthant-strictly monotonic, any nondecreasing finite-valued function of the support mapping is Capra-convex, that is, is equal to its Capra-biconjugate (generalized convexity). We also establish that any such function is the composition of a proper convex lower semi continuous function on R d with the normalization mapping on the unit sphere (hidden convexity), and that, when normalized, it admits a variational formulation, which involves a family of generalized local-K-support dual norms. △ Less

Submitted 23 October, 2020; originally announced October 2020.

Comments: arXiv admin note: text overlap with arXiv:2002.01314

Kuhn's Equivalence Theorem for Games in Intrinsic Form

Authors: Benjamin Heymann, Michel de Lara, Jean-Philippe Chancelier

Abstract: We state and prove Kuhn's equivalence theorem for a new representation of games, the intrinsic form. First, we introduce games in intrinsic form where information is represented by $σ$-fields over a product set. For this purpose, we adapt to games the intrinsic representation that Witsenhausen introduced in control theory. Those intrinsic games do not require an explicit description of the play te… ▽ More We state and prove Kuhn's equivalence theorem for a new representation of games, the intrinsic form. First, we introduce games in intrinsic form where information is represented by $σ$-fields over a product set. For this purpose, we adapt to games the intrinsic representation that Witsenhausen introduced in control theory. Those intrinsic games do not require an explicit description of the play temporality, as opposed to extensive form games on trees. Second, we prove, for this new and more general representation of games, that behavioral and mixed strategies are equivalent under perfect recall (Kuhn's theorem). As the intrinsic form replaces the tree structure with a product structure, the handling of information is easier. This makes the intrinsic form a new valuable tool for the analysis of games with information. △ Less

Submitted 26 June, 2020; originally announced June 2020.

Comparison Theorem for Viability Kernels via Conic Preorders

Authors: Michel de Lara, Pedro Gajardo, Diego Vicencio

Abstract: In natural resource management, decision-makers often aim at maintaining thestate of the system within a desirable set for all times.For instance, fisheries management procedures include keeping thespawning stock biomass over a critical threshold.Another example is given by the peak control of an epidemic outbreakthat encompasses maintaining thenumber of infected individuals below medical treatmen… ▽ More In natural resource management, decision-makers often aim at maintaining thestate of the system within a desirable set for all times.For instance, fisheries management procedures include keeping thespawning stock biomass over a critical threshold.Another example is given by the peak control of an epidemic outbreakthat encompasses maintaining thenumber of infected individuals below medical treatment capacities.In mathematical terms, one controls a dynamical system.Then, keeping the state of the system within a desirable set for all times is possible when the initial state belongs to the so-called viabilitykernel. We introduce the notion of conic quasimonotonicity reducibility.With this property, we provide a comparison theorem by inclusion between two viabilitykernels, corresponding to two control systems in the infinite horizon case. Wealso derive conditions for equality. We illustrate the method with a model for thebiocontrol of a vector-transmitted epidemic. △ Less

Submitted 21 July, 2020; v1 submitted 9 April, 2020; originally announced April 2020.

Capra-Convexity, Convex Factorization and Variational Formulations for the l0 Pseudonorm

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: The so-called l0 pseudonorm, or cardinality function, counts the number of nonzero components of a vector. In this paper, we analyze the l0 pseudonorm by means of so-called Capra (constant along primal rays) conjugacies, for which the underlying source norm and its dual norm are both orthant-strictly monotonic (a notion that we formally introduce and that encompasses the lp norms, but for the ext… ▽ More The so-called l0 pseudonorm, or cardinality function, counts the number of nonzero components of a vector. In this paper, we analyze the l0 pseudonorm by means of so-called Capra (constant along primal rays) conjugacies, for which the underlying source norm and its dual norm are both orthant-strictly monotonic (a notion that we formally introduce and that encompasses the lp norms, but for the extreme ones). We obtain three main results. First, we show that the l0 pseudonorm is equal to its Capra-biconjugate, that is, is a Capra-convex function. Second, we deduce an unexpected consequence, that we call convex factorization: the l0 pseudonorm coincides, on the unit sphere of the source norm, with a proper convex lower semicontinuous function. Third, we establish a variational formulation for the l0 pseudonorm by means of generalized top-k dual~norms and k-support dual~norms (that we formally introduce). △ Less

Submitted 6 August, 2021; v1 submitted 31 January, 2020; originally announced February 2020.

Constant Along Primal Rays Conjugacies and the l0 Pseudonorm

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: The so-called l0 pseudonorm on Rd counts the number of nonzero components of a vector. It is used in sparse optimization, either as criterion or in the constraints, to obtain solutions with few nonzero entries. For such problems, the Fenchel conjugacy fails to provide relevant analysis: indeed, the Fenchel conjugate of the characteristic function of the level sets of the l0 pseudonorm is minus inf… ▽ More The so-called l0 pseudonorm on Rd counts the number of nonzero components of a vector. It is used in sparse optimization, either as criterion or in the constraints, to obtain solutions with few nonzero entries. For such problems, the Fenchel conjugacy fails to provide relevant analysis: indeed, the Fenchel conjugate of the characteristic function of the level sets of the l0 pseudonorm is minus infinity, and the Fenchel biconjugate of the l0 pseudonorm is zero. In this paper, we display a class of conjugacies that are suitable for the l0 pseudonorm. For this purpose, we suppose given a (source) norm on Rd. With this norm, we define, on the one hand, a sequence of so-called coordinate-k norms and, on the other hand, a coupling between Rd and Rd , called Capra (constant along primal rays). Then, we provide formulas for the Capra-conjugate and biconjugate, and for the Capra subdifferentials, of functions of the l0 pseudonorm (hence, in particular, of the l0 pseudonorm itself and of the characteristic functions of its level sets), in terms of the coordinate-k norms. As an application, we provide a new family of lower bounds for the l0 pseudonorm, as a fraction between two norms, the denominator being any norm. △ Less

Submitted 1 June, 2021; v1 submitted 31 January, 2020; originally announced January 2020.

Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the L0 Pseudonorm

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: The so-called l0 pseudonorm on the Euclidean space Rd counts the number of nonzero components of a vector. We say that a sequence of norms is strictly increasingly graded (with respect to the l0 pseudonorm) if it is nondecreasing and that the sequence of norms of a vector~x becomes stationary exactly at the index l0(x). In this paper, with any (source) norm, we associate sequences of gen… ▽ More The so-called l0 pseudonorm on the Euclidean space Rd counts the number of nonzero components of a vector. We say that a sequence of norms is strictly increasingly graded (with respect to the l0 pseudonorm) if it is nondecreasing and that the sequence of norms of a vector~x becomes stationary exactly at the index l0(x). In this paper, with any (source) norm, we associate sequences of generalized top-k and k-support norms, and we also introduce the new class of orthant-strictly monotonic norms (that encompasses the lp norms, but for the extreme ones). Then, we show that an orthant-strictly monotonic source norm generates a sequence of generalized top-k norms which is strictly increasingly graded. With this, we provide a systematic way to generate sequences of norms with which the level sets of the l0 pseudonorm are expressed by means of the difference of two norms. Our results rely on the study of orthant-strictly monotonic norms. △ Less

Submitted 20 July, 2022; v1 submitted 28 January, 2020; originally announced January 2020.

EMSx: a numerical benchmark for energy management systems

Authors: Adrien Le Franc, Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara

Abstract: Inserting renewable energy in the electric grid in a decentralized manneris a key challenge of the energy transition. However, at local scale, both production and demand display erratic behavior, which makes it delicate to match them. It is the goal of Energy Management Systems (EMS) to achieve such balance at least cost. We present EMSx, a numerical benchmark for testing control algorithms for th… ▽ More Inserting renewable energy in the electric grid in a decentralized manneris a key challenge of the energy transition. However, at local scale, both production and demand display erratic behavior, which makes it delicate to match them. It is the goal of Energy Management Systems (EMS) to achieve such balance at least cost. We present EMSx, a numerical benchmark for testing control algorithms for the management of electric microgrids equipped with a photovoltaic unit and an energy storage system. EMSx is made of three key components: the EMSx dataset, provided by Schneider Electric, contains a diverse pool of realistic microgrids with a rich collection of historical observations and forecasts; the EMSx mathematical framework is an explicit description of the assessment of electric microgrid control techniques and algorithms; the EMSx software EMSx.jl is a package, implemented in the Julia language, which enables to easily implement a microgrid controller and to test it. All components of the benchmark are publicly available, so that other researchers willing to test controllers on EMSx may reproduce experiments easily. Eventually, we showcase the results of standard microgrid control methods, including Model Predictive Control, Open Loop Feedback Control and Stochastic Dynamic Programming. △ Less

Submitted 14 October, 2021; v1 submitted 2 January, 2020; originally announced January 2020.

Journal ref: Energy Systems, Springer, 2021

Upper and Lower Bounds for Large Scale Multistage Stochastic Optimization Problems: Application to Microgrid Management

Authors: Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara, François Pacaud

Abstract: We consider a microgrid where different prosumers exchange energy altogether by the edges of a given network. Each prosumer is located to a node of the network and encompasses energy consumption, energy production and storage capacities (battery, electrical hot water tank). The problem is coupled both in time and in space, so that a direct resolution of the problem for large microgrids is out of r… ▽ More We consider a microgrid where different prosumers exchange energy altogether by the edges of a given network. Each prosumer is located to a node of the network and encompasses energy consumption, energy production and storage capacities (battery, electrical hot water tank). The problem is coupled both in time and in space, so that a direct resolution of the problem for large microgrids is out of reach (curse of dimensionality). By affecting price or resources to each node in the network and resolving each nodal sub-problem independently by Dynamic Programming, we provide decomposition algorithms that allow to compute a set of decomposed local value functions in a parallel manner. By summing the local value functions together, we are able, on the one hand, to obtain upper and lower bounds for the optimal value of the problem, and, on the other hand, to design global admissible policies for the original system. Numerical experiments are conducted on microgrids of different size, derived from data given by the research and development centre Efficacity, dedicated to urban energy transition. These experiments show that the decomposition algorithms give better results than the standard SDDP method, both in terms of bounds and policy values. Moreover, the decomposition methods are much faster than the SDDP method in terms of computation time, thus allowing to tackle problem instances incorporating more than 60 state variables in a Dynamic Programming framework. △ Less

Submitted 23 December, 2019; originally announced December 2019.

Mixed Spatial and Temporal Decompositions for Large Scale Multistage Stochastic Optimization Problems

Authors: Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara, François Pacaud

Abstract: We consider multistage stochastic optimization problems involving multiple units. Each unit is a (small) control system. Static constraints couple units at each stage. We present a mix of spatial and temporal decompositions to tackle such large scale problems. More precisely, we obtain theoretical bounds and policies by means of two methods, depending whether the coupling constraints are handled b… ▽ More We consider multistage stochastic optimization problems involving multiple units. Each unit is a (small) control system. Static constraints couple units at each stage. We present a mix of spatial and temporal decompositions to tackle such large scale problems. More precisely, we obtain theoretical bounds and policies by means of two methods, depending whether the coupling constraints are handled by prices or by resources. We study both centralized and decentralized information structures. We report the results of numerical experiments on the management of urban microgrids. It appears that decomposition methods are much faster and give better results than the standard Stochastic Dual Dynamic Programming method, both in terms of bounds and of policy performance. △ Less

Submitted 17 June, 2021; v1 submitted 23 December, 2019; originally announced December 2019.

Payoffs-Beliefs Duality and the Value of Information

Authors: Michel de Lara, Olivier Gossner

Abstract: In decision problems under incomplete information, actions (identified to payoff vectors indexed by states of nature) and beliefs are naturally paired by bilinear duality. We exploit this duality to analyze the value of information, using concepts and tools from convex analysis. We define the value function as the support function of the set of available actions: the subdifferential at a belief is… ▽ More In decision problems under incomplete information, actions (identified to payoff vectors indexed by states of nature) and beliefs are naturally paired by bilinear duality. We exploit this duality to analyze the value of information, using concepts and tools from convex analysis. We define the value function as the support function of the set of available actions: the subdifferential at a belief is the set of optimal actions at this belief; the set of beliefs at which an action is optimal is the normal cone of the set of available actions at this point. Our main results are 1) a necessary and sufficient condition for positive value of information 2) global estimates of the value of information of any information structure from local properties of the value function and of the set of optimal actions taken at the prior belief only. We apply our results to the marginal value of information at the null, that is, when the agent is close to receiving no information at all, and we provide conditions under which the marginal value of information is infinite, null, or positive and finite. △ Less

Submitted 20 November, 2019; v1 submitted 5 August, 2019; originally announced August 2019.

Hidden Convexity in the l0 Pseudonorm

Authors: Jean-Philippe Chancelier, Michel de Lara

Abstract: The so-called l0 pseudonorm counts the number of nonzero components of a vector of a Euclidian space. It is well-known that the l0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, E-Capra, that has the property of being constant along primal rays like the l0 pseudonorm. The coupling E-Capra belongs to t… ▽ More The so-called l0 pseudonorm counts the number of nonzero components of a vector of a Euclidian space. It is well-known that the l0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, E-Capra, that has the property of being constant along primal rays like the l0 pseudonorm. The coupling E-Capra belongs to the class of one-sided linear couplings, that we introduce; we show that they induce conjugacies that share nice properties with the classic Fenchel conjugacy. For the E-Capra conjugacy, induced by the coupling E-Capra, we relate the E-Capra conjugate and biconjugate of the l0 pseudonorm, the characteristic functions of its level sets and the sequence of so-called top-k norms. In particular, we prove that the l0 pseudonorm is equal to its biconjugate: hence, the l0 pseudonorm is E-Capra-convex in the sense of generalized convexity. As a corollary, we show that there exists a proper convex lower semicontinuous function such that this function and the l0 pseudonorm coincide on the Euclidian unit sphere. This hidden convexity property is somewhat surprising as the l0 pseudonorm is a highly nonconvex function of combinatorial nature. We provide different expressions for this proper convex lower semicontinuous function, and we give explicit formulas in the two-dimensional case. △ Less

Submitted 17 June, 2021; v1 submitted 7 June, 2019; originally announced June 2019.

Comments: arXiv admin note: text overlap with arXiv:1902.04816

A Suitable Conjugacy for the l0 Pseudonorm

Authors: Jean-Philippe Chancelier, Michel De Lara, Ponts Paristech

Abstract: The so-called l0 pseudonorm on R d counts the number of nonzero components of a vector. It is well-known that the l0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, Caprac, having the property of being constant along primal rays, like the l0 pseudonorm. The Caprac coupling belongs to the class of one-sided… ▽ More The so-called l0 pseudonorm on R d counts the number of nonzero components of a vector. It is well-known that the l0 pseudonorm is not convex, as its Fenchel biconjugate is zero. In this paper, we introduce a suitable conjugacy, induced by a novel coupling, Caprac, having the property of being constant along primal rays, like the l0 pseudonorm. The Caprac coupling belongs to the class of one-sided linear couplings, that we introduce. We show that they induce conjugacies that share nice properties with the classic Fenchel conjugacy. For the Caprac conjugacy, induced by the coupling Caprac, we prove that the l0 pseudonorm is equal to its biconjugate: hence, the l0 pseudonorm is Caprac-convex in the sense of generalized convexity. As a corollary, we show that the l0 pseudonorm coincides, on the sphere, with a convex lsc function. We also provide expressions for conjugates in terms of two families of dual norms, the 2-k-symmetric gauge norms and the k-support norms. △ Less

Submitted 13 February, 2019; originally announced February 2019.

Comments: arXiv admin note: text overlap with arXiv:1902.04813

Lower Bound Convex Programs for Exact Sparse Optimization

Authors: Jean-Philippe Chancelier, Michel De Lara, Ponts Paristech

Abstract: In exact sparse optimization problems on Rd (also known as sparsity constrained problems), one looks for solution that have few nonzero components. In this paper, we consider problems where sparsity is exactly measured either by the nonconvex l0 pseudonorm (and not by substitute penalty terms) or by the belonging of the solution to a finite union of subsets. Due to the combinatorial nature of the… ▽ More In exact sparse optimization problems on Rd (also known as sparsity constrained problems), one looks for solution that have few nonzero components. In this paper, we consider problems where sparsity is exactly measured either by the nonconvex l0 pseudonorm (and not by substitute penalty terms) or by the belonging of the solution to a finite union of subsets. Due to the combinatorial nature of the sparsity constraint, such problems do not generally display convexity properties, even if the criterion to minimize is convex. In the most common approach to tackle them, one replaces the sparsity constraint by a convex penalty term, supposed to induce sparsity. Thus doing, one loses the original exact sparse optimization problem, but gains convexity. However, by doing so, it is not clear that one obtains a lower bound of the original exact sparse optimization problem. In this paper, we propose another approach, where we lose convexity but where we gain at keeping the original exact sparse optimization formulation, by displaying lower bound convex minimization programs. For this purpose , we introduce suitable conjugacies, induced by a novel class of one-sided linear couplings. Thus equipped, we present a systematic way to design norms and lower bound convex minimization programs over their unit ball. The family of norms that we display encompasses most of the sparsity inducing norms used in machine learning. Therefore, our approach provides foundation and interpretation for their use. △ Less

Submitted 13 February, 2019; originally announced February 2019.

Fenchel-Moreau Conjugation Inequalities with Three Couplings and Application to Stochastic Bellman Equation

Authors: Jean-Philippe Chancelier, Michel De Lara

Abstract: Given two couplings between "primal" and "dual" sets, we prove a general implication that relates an inequality involving "primal" sets to a reverse inequality involving the "dual" sets.% More precisely, let be given two "primal" sets $\PRIMAL$, $\PRIMALBIS$and two "dual" sets $\DUAL$, $\DUALBIS$, together with two {coupling} functions \(\PRIMAL \overset{\coupling}{\leftrightarrow} \DUAL… ▽ More Given two couplings between "primal" and "dual" sets, we prove a general implication that relates an inequality involving "primal" sets to a reverse inequality involving the "dual" sets.% More precisely, let be given two "primal" sets $\PRIMAL$, $\PRIMALBIS$and two "dual" sets $\DUAL$, $\DUALBIS$, together with two {coupling} functions \(\PRIMAL \overset{\coupling}{\leftrightarrow} \DUAL \) and \(\PRIMALBIS \overset{\couplingbis}{\leftrightarrow} \DUALBIS \). We define a new coupling \(\SumCoupling{\coupling}{\couplingbis} \) between the "primal" product set~$\PRIMAL \times \PRIMALBIS$ and the "dual" product set $\DUAL \times \DUALBIS$. Then, we consider any bivariate function \(\kernel : \PRIMAL \times \PRIMALBIS \to \barRR \) and univariate functions \(\fonctionprimal : \PRIMAL \to \barRR \) and \(\fonctionprimalbis : \PRIMALBIS \to \barRR \), all defined on the "primal" sets. We prove that \(\fonctionprimal\np{\primal} \geq \inf\_{\primalbis \in \PRIMALBIS} \Bp{\kernel\np{\primal, \primalbis} \UppPlus \fonctionprimalbis\np{\primalbis}} \) \( \Rightarrow \SFM{\fonctionprimal}{\coupling}\np{\dual} \leq \inf\_{\dualbis \in \DUALBIS} \Bp{\SFM{\kernel}{\SumCoupling{\coupling}{\couplingbis}}\np{\dual,\dualbis} \UppPlus \SFM{\fonctionprimalbis}{-\couplingbis}\np{\dualbis}} \), where we stress that the Fenchel-Moreau conjugates \(\SFM{\fonctionprimal}{\coupling} \) and \(\SFM{\fonctionprimalbis}{-\couplingbis}\) are not necessarily taken with the same coupling. We study the equality case, after having established the classical Fenchel inequality but with a general coupling. % We display several applications. We provide a new formula for the Fenchel-Moreau conjugate of a generalized inf-convolution. We obtain formulas with partial Fenchel-Moreau conjugates. Finally, we consider the Bellman equation in stochastic dynamic programming and we provide a "Bellman-like" equation for the Fenchel conjugates of the value functions. △ Less

Submitted 10 September, 2018; v1 submitted 9 April, 2018; originally announced April 2018.

Time Blocks Decomposition of Multistage Stochastic Optimization Problems

Authors: Pierre Carpentier, Jean-Philippe Chancelier, Michel de Lara, Thomas Martin, Tristan Rigaut

Abstract: Multistage stochastic optimization problems are, by essence, complex as their solutions are indexed both by stages and by uncertainties. Their large scale nature makes decomposition methods appealing, like dynamic programming which is a sequential decomposition using a state variable defined at all stages. In this paper, we introduce the notion of state reduction by time blocks, that is, at… ▽ More Multistage stochastic optimization problems are, by essence, complex as their solutions are indexed both by stages and by uncertainties. Their large scale nature makes decomposition methods appealing, like dynamic programming which is a sequential decomposition using a state variable defined at all stages. In this paper, we introduce the notion of state reduction by time blocks, that is, at stages that are not necessarily all the original stages. Then, we prove a reduced dynamic programming equation. We position our result with respect to the most well-known mathematical frameworks for dynamic programming. We illustrate our contribution by showing its potential for applied problems with two time scales. △ Less

Submitted 28 April, 2023; v1 submitted 5 April, 2018; originally announced April 2018.

A Mathematical Framework for Resilience: Dynamics, Uncertainties, Strategies and Recovery Regimes

Authors: Michel De Lara

Abstract: Resilience is a rehashed concept in natural hazard management - resilience of cities to earthquakes, to floods, to fire, etc. In a word, a system is said to be resilient if there exists a strategy that can drive the system state back to "normal" after any perturbation. What formal flesh can we put on such a malleable notion? We propose to frame the concept of resilience in the mathematical garbs o… ▽ More Resilience is a rehashed concept in natural hazard management - resilience of cities to earthquakes, to floods, to fire, etc. In a word, a system is said to be resilient if there exists a strategy that can drive the system state back to "normal" after any perturbation. What formal flesh can we put on such a malleable notion? We propose to frame the concept of resilience in the mathematical garbs of control theory under uncertainty. Our setting covers dynamical systems both in discrete or continuous time, deterministic or subject to uncertainties. We will say that a system state is resilient if there exists an adaptive strategy such that the generated state and control paths, contingent on uncertainties, lay within an acceptable domain of random processes, called recovery regimes. We point out how such recovery regimes can be delineated thanks to so called risk measures, making the connection with resilience indicators. Our definition of resilience extends others, be they "` a la Holling" or rooted in viability theory. Indeed, our definition of resilience is a form of controlability for whole random processes (regimes), whereas others require that the state values must belong to an acceptable subset of the state set. △ Less

Submitted 1 February, 2018; originally announced February 2018.

Comments: arXiv admin note: text overlap with arXiv:1709.01389

Anticipating epileptic seizures through the analysis of EEG synchronization as a data classification problem

Authors: Paolo Detti, Garazi Zabalo Manrique de Lara, Renato Bruni, Marco Pranzo, Francesco Sarnari

Abstract: Epilepsy is a neurological disorder arising from anomalies of the electrical activity in the brain, affecting about 0.5--0.8\% of the world population. Several studies investigated the relationship between seizures and brainwave synchronization patterns, pursuing the possibility of identifying interictal, preictal, ictal and postictal states. In this work, we introduce a graph-based model of the b… ▽ More Epilepsy is a neurological disorder arising from anomalies of the electrical activity in the brain, affecting about 0.5--0.8\% of the world population. Several studies investigated the relationship between seizures and brainwave synchronization patterns, pursuing the possibility of identifying interictal, preictal, ictal and postictal states. In this work, we introduce a graph-based model of the brain interactions developed to study synchronization patterns in the electroencephalogram (EEG) signals. The aim is to develop a patient-specific approach, also for a real-time use, for the prediction of epileptic seizures' occurrences. Different synchronization measures of the EEG signals and easily computable functions able to capture in real-time the variations of EEG synchronization have been considered. Both standard and ad-hoc classification algorithms have been developed and used. Results on scalp EEG signals show that this simple and computationally viable processing is able to highlight the changes in the synchronization corresponding to the preictal state. △ Less

Submitted 24 January, 2018; originally announced January 2018.

Stochastic optimal control of a domestic microgrid equipped with solar panel and battery

Authors: François Pacaud, Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara

Abstract: Microgrids are integrated systems that gather and operate energy production units to satisfy consumers demands. This paper details different mathematical methods to design the Energy Management System (EMS) of domestic microgrids. We consider different stocks coupled together - a battery, a domestic hot water tank - and decentralized energy production with solar panel. The main challenge of the EM… ▽ More Microgrids are integrated systems that gather and operate energy production units to satisfy consumers demands. This paper details different mathematical methods to design the Energy Management System (EMS) of domestic microgrids. We consider different stocks coupled together - a battery, a domestic hot water tank - and decentralized energy production with solar panel. The main challenge of the EMS is to ensure, at least cost, that supply matches demand for all time, while considering the inherent uncertainties of such systems. We benchmark two optimization algorithms to manage the EMS, and compare them with a heuristic. The Model Predictive Control (MPC) is a well known algorithm which models the future uncertainties with a deterministic forecast. By contrast, Stochastic Dual Dynamic Programming (SDDP) models the future uncertainties as probability distributions to compute optimal policies. We present a fair comparison of these two algorithms to control microgrid. A comprehensive numerical study shows that i) optimization algorithms achieve significant gains compared to the heuristic, ii) SDDP outperforms MPC by a few percents, with a reasonable computational overhead. △ Less

Submitted 19 January, 2018; originally announced January 2018.

Stochastic Optimization of Braking Energy Storage and Ventilation in a Subway Station

Authors: Tristan Rigaut, Pierre Carpentier, Jean Philippe Chancelier, Michel De Lara, Julien Waeytens

Abstract: In the Paris subway system, stations represent about one third of the overall energy consumption. Within stations, ventilation is among the top consuming devices; it is operated at maximum airflow all day long, for air quality reasons. In this paper, we present a concept of energy system that displays comparable air quality while consuming much less energy. The system comprises a battery that make… ▽ More In the Paris subway system, stations represent about one third of the overall energy consumption. Within stations, ventilation is among the top consuming devices; it is operated at maximum airflow all day long, for air quality reasons. In this paper, we present a concept of energy system that displays comparable air quality while consuming much less energy. The system comprises a battery that makes it possible to recover the trains braking energy, arriving under the form of erratic and strong peaks. We propose an energy management system (EMS) that, at short time scale, controls energy flows and ventilation airflow. By using proper optimization algorithms, we manage to match supply with demand, while minimizing energy daily costs. For this purpose, we have designed algorithms that take into account the braking variability. They are based on the so-called Stochastic Dynamic Programming (SDP) mathematical framework. We fairly compare SDP based algorithms with the widespread Model Predictive Control (MPC) ones. First, both SDP and MPC yield energy/money operating savings of the order of one third, compared to the current management without battery (our figure does not include the cost of the battery). Second, depending on the specific design, we observe that SDP outperforms MPC by a few percent, with an easier online numerical implementation. △ Less

Submitted 22 February, 2018; v1 submitted 9 January, 2018; originally announced January 2018.

Equivalence Between Time Consistency and Nested Formula

Authors: Henri Gérard, Michel de Lara, Jean-Philippe Chancelier

Abstract: You are a financial analyst. At the beginning of every week, you are able to rank every pair of stochastic processes starting from that week up to the horizon. Suppose that two processes are equal at the beginning of the week. Your ranking procedure is time consistent if the ranking does not change between this week and the next one. In this paper, we propose a minimalist definition of Time Consis… ▽ More You are a financial analyst. At the beginning of every week, you are able to rank every pair of stochastic processes starting from that week up to the horizon. Suppose that two processes are equal at the beginning of the week. Your ranking procedure is time consistent if the ranking does not change between this week and the next one. In this paper, we propose a minimalist definition of Time Consistency (TC) between two (assessment) mappings. With very few assumptions, we are able to prove an equivalence between Time Consistency and a Nested Formula (NF) between the two mappings. Thus, in a sense, two assessments are consistent if and only if one is factored into the other. We review the literature and observe that the various definitions of TC (or of NF) are special cases of ours, as they always include additional assumptions. By stripping off these additional assumptions, we present an overview of the literature where the contribution of each author is enlightened. △ Less

Submitted 17 May, 2019; v1 submitted 23 November, 2017; originally announced November 2017.

Rationally Biased Learning

Authors: Michel de Lara

Abstract: Humans display a tendency to pay more attention to bad outcomes, often in a disproportionate way relative to their statistical occurrence. They also display euphorism, as well as a preference for the current state of affairs (status quo bias). Based on the analysis of optimal solutions of infinite horizon stationary optimization problems under imperfect state observation, we show that such human p… ▽ More Humans display a tendency to pay more attention to bad outcomes, often in a disproportionate way relative to their statistical occurrence. They also display euphorism, as well as a preference for the current state of affairs (status quo bias). Based on the analysis of optimal solutions of infinite horizon stationary optimization problems under imperfect state observation, we show that such human perception and decision biases can be grounded in a form of rationality. We also provide conditions (boundaries) for their possible occurence and an analysis of their robustness.Thus, biases can be the product of rational behavior. △ Less

Submitted 23 March, 2022; v1 submitted 5 September, 2017; originally announced September 2017.

A Mathematical Framework for Resilience: Dynamics, Strategies, Shocks and Acceptable Paths

Authors: Michel De Lara

Abstract: Resilience is a rehashed concept in natural hazard management - resilience of cities to earthquakes, to floods, to fire, etc. In a word, a system is said to be resilient if there exists a strategy that can drive the system state back to "normal" (acceptable states) after a shock. What formal flesh can we put on such malleable notion? We propose to frame the concept of resilience in the mathematica… ▽ More Resilience is a rehashed concept in natural hazard management - resilience of cities to earthquakes, to floods, to fire, etc. In a word, a system is said to be resilient if there exists a strategy that can drive the system state back to "normal" (acceptable states) after a shock. What formal flesh can we put on such malleable notion? We propose to frame the concept of resilience in the mathematical garbs of control theory under uncertainty. Our setting covers dynamical systems both in discrete or continuous time, deterministic or subject to uncertainties. Our definition of resilience extends others, be they "a la Holling" or rooted in viability theory. Indeed, we require that, after a shock, the system returns to an acceptable "regime" , that is, that the state-control path as a whole must return to a set of acceptable paths (and not only the state values must belong to an acceptable subset of the state set). More generally, as state and control paths are contingent on uncertainties, we require that their tails processes must lay within acceptable domains of stochastic processes. We end by pointing out how such domains can be delineated thanks to so called risk measures. △ Less

Submitted 16 January, 2018; v1 submitted 5 September, 2017; originally announced September 2017.

Robust Viability Analysis of a Controlled Epidemiological Model

Authors: Lilian Sofia Salcedo Sepulveda, Michel De Lara

Abstract: Managing infectious diseases is a world public health issue, plagued by uncertainties. In this paper, we analyze the problem of viable control of a dengue outbreak under uncertainty. For this purpose, we develop a controlled Ross-Macdonald model in discrete time, with mosquito vector control by fumigation and with uncertainties affecting the dynamics. The robust viability kernel is the set of all… ▽ More Managing infectious diseases is a world public health issue, plagued by uncertainties. In this paper, we analyze the problem of viable control of a dengue outbreak under uncertainty. For this purpose, we develop a controlled Ross-Macdonald model in discrete time, with mosquito vector control by fumigation and with uncertainties affecting the dynamics. The robust viability kernel is the set of all initial states such that there exists at least a strategy of insecticide spraying which guarantees that the number of infected people remains below a threshold, for all times, and whatever the sequences of uncertainties (scenarios). Having chosen three nested subsets of uncertainties - a deterministic one (without uncertainty), a medium one and a large one - we can measure the incidence of the uncertainties on the size of the kernel, in particular on its reduction with respect to the de-terministic case. The numerical results show that the viability kernel without uncertainties is highly sensitive to the variability of parameters - here the biting rate, the probability of infection to mosquitoes and humans, and the proportion of female mosquitoes per person. So the robust viability kernel is a possible tool to reveal the importance of uncertainties regarding epidemics control. △ Less

Submitted 19 February, 2018; v1 submitted 28 August, 2017; originally announced August 2017.

Comments: arXiv admin note: text overlap with arXiv:1510.01055