skip to main content

Title: A min-plus fundamental solution semigroup for a class of approximate infinite dimensional optimal control problems
By exploiting min-plus linearity, semiconcavity, and semigroup properties of dynamic programming, a fundamental solution semigroup for a class of approximate finite horizon linear infinite dimensional optimal control problems is constructed. Elements of this fundamental solution semigroup are parameterized by the time horizon, and can be used to approximate the solution of the corresponding finite horizon optimal control problem for any terminal cost. They can also be composed to compute approximations on longer horizons. The value function approximation provided takes the form of a min-plus convolution of a kernel with the terminal cost. A general construction for this kernel is provided, along with a spectral representation for a restricted class of sub-problems.
Award ID(s):
Publication Date:
Journal Name:
Proceedings of the American Control Conference
Page Range or eLocation-ID:
Sponsoring Org:
National Science Foundation
More Like this
  1. Many imaging problems can be formulated as inverse problems expressed as finite-dimensional optimization problems. These optimization problems generally consist of minimizing the sum of a data fidelity and regularization terms. In Darbon (SIAM J. Imag. Sci. 8:2268–2293, 2015), Darbon and Meng, (On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:1906.09502, 2019), connections between these optimization problems and (multi-time) Hamilton-Jacobi partial differential equations have been proposed under the convexity assumptions of both the data fidelity and regularization terms. In particular, under these convexity assumptions, some representation formulas for a minimizer can be obtained. From amore »Bayesian perspective, such a minimizer can be seen as a maximum a posteriori estimator. In this chapter, we consider a certain class of non-convex regularizations and show that similar representation formulas for the minimizer can also be obtained. This is achieved by leveraging min-plus algebra techniques that have been originally developed for solving certain Hamilton-Jacobi partial differential equations arising in optimal control. Note that connections between viscous Hamilton-Jacobi partial differential equations and Bayesian posterior mean estimators with Gaussian data fidelity terms and log-concave priors have been highlighted in Darbon and Langlois, (On Bayesian posterior mean estimators in imaging sciences and Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:2003.05572, 2020). We also present similar results for certain Bayesian posterior mean estimators with Gaussian data fidelity and certain non-log-concave priors using an analogue of min-plus algebra techniques.« less
  2. Motivated by various distributed control applications, we consider a linear system with Gaussian noise observed by multiple sensors which transmit measurements over a dynamic lossy network. We characterize the stationary optimal sensor scheduling policy for the finite horizon, discounted, and long-term average cost problems and show that the value iteration algorithm converges to a solution of the average cost problem. We further show that the suboptimal policies provided by the rolling horizon truncation of the value iteration also guarantee geometric ergodicity and provide near-optimal average cost. Lastly, we provide qualitative characterizations of the multidimensional set of measurement loss rates formore »which the system is stabilizable for a static network, significantly extending earlier results on intermittent observations.« less
  3. We consider the problem of finite-horizon optimal control of a discrete linear time-varying system subject to a stochastic disturbance and fully observable state. The initial state of the system is drawn from a known Gaussian distribution, and the final state distribution is required to reach a given target Gaussian distribution, while minimizing the expected value of the control effort. We derive the linear optimal control policy by first presenting an efficient solution for the diffusion-less case, and we then solve the case with diffusion by reformulating the system as a superposition of diffusion-less systems. We show that the resulting solutionmore »coincides with a LQG problem with particular terminal cost weight matrix.« less
  4. This work considers the replacement of a full-state feedback controller by a static output feedback controller employing a finite number of point sensors. This is achieved by the approximation of the feedback kernel associated with the full state feedback operator. The feedback kernel is partitioned into equiareal cells and an appropriately selected centroid within each cell serves as the sensor location. This allows one to approximate the inner product of the feedback kernel and the full state by the finite weighted sum of static output feedback measurements. By equating the feedback kernel with the density of a hypothetical sensor network,more »the problem of approximating the sensor density becomes that of partitioning the sensor density using the proposed computational-geometry based decomposition that is based on a modification of Centroidal Voronoi Tessellations. When the control is considered over a finite horizon and/or the actuator itself is repositioned within the spatial domain, the resulting feedback kernel is rendered time-varying. This requires its partitioning at each time leading to mobile sensors within the spatial domain. Two guidance policies are proposed: one uses the partitioning of the kernel method at each time to find the optimal sensors thus resulting in moving sensors. The other method uses the kernel partitioning only at the initial time and subsequently uses the sensor density as the initial condition for an advection PDE that represents the evolution of the sensor density. This advection PDE is solved for the velocity thereby providing the velocity of the density of the sensor network. Projecting the sensor density velocity onto the same partitioning used for the kernel provides the sensor velocities. A numerical example of an advection diffusion PDE is presented to provide an understanding of this computational geometry based partitioning of feedback kernels.« less
  5. We consider a general class of finite-horizon online decision-making problems, where in each period a controller is presented a stochastic arrival and must choose an action from a set of permissible actions, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems including bin packing, generalized assignment, and network revenue management. In such settings, we study a natural model-predictive control algorithm that in each period, acts greedily based on an updated certainty-equivalent optimization problem. We introduce a simple, yet general, condition under which this algorithm obtains uniformmore »additive loss (independent of the horizon) compared to an optimal solution with full knowledge of arrivals. Our condition is fulfilled by the above-mentioned problems, as well as more general settings involving piece-wise linear objectives and offline index policies, including an airline overbooking problem.« less