We present a neural network approach for approximating the value function of high- dimensional stochastic control problems. Our training process simultaneously updates our value function estimate and identifies the part of the state space likely to be visited by optimal trajectories. Our approach leverages insights from optimal control theory and the fundamental relation between semi-linear parabolic partial differential equations and forward-backward stochastic differential equations. To focus the sampling on relevant states during neural network training, we use the stochastic Pontryagin maximum principle (PMP) to obtain the optimal controls for the current value function estimate. By design, our approach coincides with the method of characteristics for the non-viscous Hamilton-Jacobi-Bellman equation arising in deterministic control problems. Our training loss consists of a weighted sum of the objective functional of the control problem and penalty terms that enforce the HJB equations along the sampled trajectories. Importantly, training is unsupervised in that it does not require solutions of the control problem. Our numerical experiments highlight our scheme’s ability to identify the relevant parts of the state space and produce meaningful value estimates. Using a two-dimensional model problem, we demonstrate the importance of the stochastic PMP to inform the sampling and compare to a finite element approach. With a nonlinear control affine quadcopter example, we illustrate that our approach can handle complicated dynamics. For a 100-dimensional benchmark problem, we demonstrate that our approach improves accuracy and time-to-solution and, via a modification, we show the wider applicability of our scheme.
more »
« less
Numerical Methods for Integral Equations of the Second Kind with NonSmooth Solutions of Bounded Variation
This paper develops a finite approximation approach to find a non-smooth solution of an integral equation of the second kind. The equation solutions with non-smooth kernel having a non-smooth solution have never been studied before. Such equations arise frequently when modeling stochastic systems. We construct a Banach space of (right-continuous) distribution functions and reformulate the problem into an operator equation. We provide general necessary and sufficient conditions that allow us to show convergence of the approximation approach developed in this paper. We then provide two specific choices of approximation sequences and show that the properties of these sequences are sufficient to generate approximate equation solutions that converge to the true solution assuming solution uniqueness and some additional mild regularity conditions. Our analysis is performed under the supremum norm, allowing wider applicability of our results. Worst-case error bounds are also available from solving a linear program. We demonstrate the viability and computational performance of our approach by constructing three examples. The solution of the first example can be constructed manually but demonstrates the correctness and convergence of our approach. The second application example involves stationary distribution equations of a stochastic model and demonstrates the dramatic improvement our approach provides over the use of computer simulation. The third example solves a problem involving an everywhere nondifferentiable function for which no closed-form solution is available.
more »
« less
- Award ID(s):
- 1763035
- PAR ID:
- 10491096
- Publisher / Repository:
- SIAM
- Date Published:
- Journal Name:
- SIAM Journal on Numerical Analysis
- Volume:
- 60
- Issue:
- 5
- ISSN:
- 0036-1429
- Page Range / eLocation ID:
- 2751 to 2780
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract We study the (characteristic) Cauchy problem for the Maxwell‐Bloch equations of light‐matter interaction via asymptotics, under assumptions that prevent the generation of solitons. Our analysis clarifies some features of the sense in which physically‐motivated initial‐boundary conditions are satisfied. In particular, we present a proper Riemann‐Hilbert problem that generates the unique
causal solution to the Cauchy problem, that is, the solution vanishes outside of the light cone. Inside the light cone, we relate the leading‐order asymptotics to self‐similar solutions that satisfy a system of ordinary differential equations related to the Painlevé‐III (PIII) equation. We identify these solutions and show that they are related to a family of PIII solutions recently discovered in connection with several limiting processes involving the focusing nonlinear Schrödinger equation. We fully explain a resulting boundary layer phenomenon in which, even for smooth initial data (an incident pulse), the solution makes a sudden transition over an infinitesimally small propagation distance. At a formal level, this phenomenon has been described by other authors in terms of the PIII self‐similar solutions. We make this observation precise and for the first time we relate the PIII self‐similar solutions to the Cauchy problem. Our analysis of the asymptotic behavior satisfied by the optical field and medium density matrix reveals slow decay of the optical field in one direction that is actually inconsistent with the simplest version of scattering theory. Our results identify a precise generic condition on an optical pulse incident on an initially‐unstable medium sufficient for the pulse to stimulate the decay of the medium to its stable state. -
null (Ed.)We consider differentiability issues associated to the problem of minimizing the accumulation of a granular cohesionless material on a certain surface. The design variable or control is determined by source locations and intensity thereof. The control problem is described by an optimization problem in function space and constrained by a variational inequality or a non-smooth equation. We address a regularization approach via a family of nonlinear partial differential equations, and provide a novel result of Newton differentiability of the control-to-state map. Further, we discuss solution algorithms for the state equation as well as for the optimization problem.more » « less
-
more » « less
It is well known that the Painlevé equations can formally degenerate to autonomous differential equations with elliptic function solutions in suitable scaling limits. A way to make this degeneration rigorous is to apply Deift-Zhou steepest-descent techniques to a Riemann-Hilbert representation of a family of solutions. This method leads to an explicit approximation formula in terms of theta functions and related algebro-geometric ingredients that is difficult to directly link to the expected limiting differential equation. However, the approximation arises from an outer parametrix that satisfies relatively simple conditions. By applying a method that we learned from Alexander Its, it is possible to use these simple conditions to directly obtain the limiting differential equation, bypassing the details of the algebro-geometric solution of the outer parametrix problem. In this paper, we illustrate the use of this method to relate an approximation of the algebraic solutions of the Painlevé-III (D$_7$) equation valid in the part of the complex plane where the poles and zeros of the solutions asymptotically reside to a form of the Weierstraß equation.
-
We study stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. Building upon the recent advances in algorithmic high-dimensional robust statistics, in each SGD iteration, master employs a non-trivial decoding to estimate the true gradient from the unbiased stochastic gradients received from workers, some of which may be corrupt. We provide convergence analyses for both strongly-convex and non-convex smooth objectives under standard SGD assumptions. We can control the approximation error of our solution in both these settings by the mini-batch size of stochastic gradients; and we can make the approximation error as small as we want, provided that workers use a sufficiently large mini-batch size. Our algorithm can tolerate less than 1/3 fraction of Byzantine workers. It can approximately find the optimal parameters in the strongly-convex setting exponentially fast, and reaches to an approximate stationary point in the non-convex setting with linear speed, i.e., with a rate of 1/T, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1137/22M1480422
