Efficient methods for stochastic optimal control

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost functional. Given the assumption of quadratic cost on the control input, it is well known that the HJB reduces to a particular partial differential equation (PDE). While powerful, this reduction is not commonly used as the PDE is of second order, is nonlinear, and examples exist where the problem may not have a solution in a classical sense. Furthermore, each state of the system appears as another dimension of the PDE, giving rise to the curse of dimensionality. Since the number of degrees of freedom required to solve the optimal control problem grows exponentially with dimension, the problem becomes intractable for systems with all but modest dimension.

In the last decade researchers have found that under certain, fairly non-restrictive structural assumptions, the HJB may be transformed into a linear PDE, with an interesting analogue in the discretized domain of Markov Decision Processes (MDP). The work presented in this thesis uses the linearity of this particular form of the HJB PDE to push the computational boundaries of stochastic optimal control.

This is done by crafting together previously disjoint lines of research in computation. The first of these is the use of Sum of Squares (SOS) techniques for synthesis of control policies. A candidate polynomial with variable coefficients is proposed as the solution to the stochastic optimal control problem. An SOS relaxation is then taken to the partial differential constraints, leading to a hierarchy of semidefinite relaxations with improving sub-optimality gap. The resulting approximate solutions are shown to be guaranteed over- and under-approximations for the optimal value function. It is shown that these results extend to arbitrary parabolic and elliptic PDEs, yielding a novel method for Uncertainty Quantification (UQ) of systems governed by partial differential constraints. Domain decomposition techniques are also made available, allowing for such problems to be solved via parallelization and low-order polynomials.

The optimization-based SOS technique is then contrasted with the Separated Representation (SR) approach from the applied mathematics community. The technique allows for systems of equations to be solved through a low-rank decomposition that results in algorithms that scale linearly with dimensionality. Its application in stochastic optimal control allows for previously uncomputable problems to be solved quickly, scaling to such complex systems as the Quadcopter and VTOL aircraft. This technique may be combined with the SOS approach, yielding not only a numerical technique, but also an analytical one that allows for entirely new classes of systems to be studied and for stability properties to be guaranteed.

The analysis of the linear HJB is completed by the study of its implications in application. It is shown that the HJB and a popular technique in robotics, the use of navigation functions, sit on opposite ends of a spectrum of optimization problems, upon which tradeoffs may be made in problem complexity. Analytical solutions to the HJB in these settings are available in simplified domains, yielding guidance towards optimality for approximation schemes. Finally, the use of HJB equations in temporal multi-task planning problems is investigated. It is demonstrated that such problems are reducible to a sequence of SOC problems linked via boundary conditions. The linearity of the PDE allows us to pre-compute control policy primitives and then compose them, at essentially zero cost, to satisfy a complex temporal logic specification.

The stochastic exit problem for dynamical systems

The problem of "exit against a flow" for dynamical systems subject to small Gaussian white noise excitation is studied. Here the word "flow" refers to the behavior in phase space of the unperturbed system's state variables. "Exit against a flow" occurs if a perturbation causes the phase point to leave a phase space region within which it would normally be confined. In particular, there are two components of the problem of exit against a flow:

i) the mean exit time

ii) the phase-space distribution of exit locations.

When the noise perturbing the dynamical systems is small, the solution of each component of the problem of exit against a flow is, in general, the solution of a singularly perturbed, degenerate elliptic-parabolic boundary value problem.

Singular perturbation techniques are used to express the asymptotic solution in terms of an unknown parameter. The unknown parameter is determined using the solution of the adjoint boundary value problem.

The problem of exit against a flow for several dynamical systems of physical interest is considered, and the mean exit times and distributions of exit positions are calculated. The systems are then simulated numerically, using Monte Carlo techniques, in order to determine the validity of the asymptotic solutions.

The stability of traveling wave solutions of parabolic equations

A method for determining by inspection the stability or instability of any solution u(t,x) = ɸ(x-ct) of any smooth equation of the form u_t = f(u_(xx),u_x,u where ∂/∂a f(a,b,c) > 0 for all arguments a,b,c, is developed. The connection between the mean wavespeed of solutions u(t,x) and their initial conditions u(0,x) is also explored. The mean wavespeed results and some of the stability results are then extended to include equations which contain integrals and also to include some special systems of equations. The results are applied to several physical examples.

Existence, uniqueness, and stability of solutions of a class of nonlinear partial differential equations

In this study we investigate the existence, uniqueness and asymptotic stability of solutions of a class of nonlinear integral equations which are representations for some time dependent non- linear partial differential equations. Sufficient conditions are established which allow one to infer the stability of the nonlinear equations from the stability of the linearized equations. Improved estimates of the domain of stability are obtained using a Liapunov Functional approach. These results are applied to some nonlinear partial differential equations governing the behavior of nonlinear continuous dynamical systems.

Boundary value problems for stochastic differential equations

A theory of two-point boundary value problems analogous to the theory of initial value problems for stochastic ordinary differential equations whose solutions form Markov processes is developed. The theory of initial value problems consists of three main parts: the proof that the solution process is markovian and diffusive; the construction of the Kolmogorov or Fokker-Planck equation of the process; and the proof that the transistion probability density of the process is a unique solution of the Fokker-Planck equation.

It is assumed here that the stochastic differential equation under consideration has, as an initial value problem, a diffusive markovian solution process. When a given boundary value problem for this stochastic equation almost surely has unique solutions, we show that the solution process of the boundary value problem is also a diffusive Markov process. Since a boundary value problem, unlike an initial value problem, has no preferred direction for the parameter set, we find that there are two Fokker-Planck equations, one for each direction. It is shown that the density of the solution process of the boundary value problem is the unique simultaneous solution of this pair of Fokker-Planck equations.

This theory is then applied to the problem of a vibrating string with stochastic density.

Temporal and spacial control of RNA stability in the early embryo of Drosophila melanogaster

Early embryogenesis in metazoa is controlled by maternally synthesized products. Among these products, the mature egg is loaded with transcripts representing approximately two thirds of the genome. A subset of this maternal RNA pool is degraded prior to the transition to zygotic control of development. This transfer of control of development from maternal to zygotic products is referred to as the midblastula transition (or MBT). It is believed that the degradation of maternal transcripts is required to terminate maternal control of development and to allow zygotic control of development to begin. Until now this process of maternal transcript degradation and the subsequent timing of the MBT has been poorly understood. I have demonstrated that in the early embryo there are two independent RNA degradation pathways, either of which is sufficient for transcript elimination. However, only the concerted action of both pathways leads to elimination of transcripts with the correct timing, at the MBT. The first pathway is maternally encoded, is triggered by egg activation, and is targeted to specific classes of mRNAs through cis-acting elements in the 3' untranslated region (UTR}. The second pathway is activated 2 hr after fertilization and functions together with the maternal pathway to ensure that transcripts are degraded by the MBT. In addition, some transcripts fail to degrade at select subcellular locations adding an element of spatial control to RNA degradation. The spatial control of RNA degradation is achieved by protecting, or masking, transcripts from the degradation machinery. The RNA degradation and protection events are regulated by distinct cis-elements in the 3' untranslated region (UTR). These results provide the first systematic dissection of this highly conserved process in development and demonstrate that RNA degradation is a novel mechanism used for both temporal and spatial control of development.

Dynamical stability of nascent neutron stars

This thesis presents a study of the dynamical stability of nascent neutron stars resulting from the accretion induced collapse of rapidly rotating white dwarfs.

Chapter 2 and part of Chapter 3 study the equilibrium models for these neutron stars. They are constructed by assuming that the neutron stars have the same masses, angular momenta, and specific angular momentum distributions as the pre-collapse white dwarfs. If the pre-collapse white dwarf is rapidly rotating, the collapsed object will contain a high density central core of size about 20 km, surrounded by a massive accretion torus extending to hundreds of kilometers from the rotation axis. The ratio of the rotational kinetic energy to gravitational binding energy, β, of these neutron stars is all found to be less than 0.27.

Chapter 3 studies the dynamical stability of these neutron stars by numerically evolving the linearized hydrodynamical equations. A dynamical bar-mode instability is observed when the β of the star is greater than the critical value β_d ≈ 0.25. It is expected that the unstable mode will persist until a substantial amount of angular momentum is carried away by gravitational radiation. The detectability of these sources is studied and it is estimated that LIGO II is unlikely to detect them unless the event rate is greater than 10^-6/year/galaxy.

All the calculations on the structure and stability of the neutron stars in Chapters 2 and 3 are carried out using Newtonian hydrodynamics and gravity. Chapter 4 studies the relativistic effects on the structure of these neutron stars. New techniques are developed and used to construct neutron star models to the first post-Newtonian (1PN) order. The structures of the 1PN models are qualitatively similar to the corresponding Newtonian models, but the values of β are somewhat smaller. The maximum β for these 1PN neutron stars is found to be 0.24, which is 8% smaller than the Newtonian result (0.26). However, relativistic effects will also change the critical value β_d. A detailed post-Newtonian stability analysis has yet to be carried out to study the relativistic effects on the dynamical stability of these neutron stars.

Multiscale model reduction methods for deterministic and stochastic partial differential equations

Partial differential equations (PDEs) with multiscale coefficients are very difficult to solve due to the wide range of scales in the solutions. In the thesis, we propose some efficient numerical methods for both deterministic and stochastic PDEs based on the model reduction technique.

For the deterministic PDEs, the main purpose of our method is to derive an effective equation for the multiscale problem. An essential ingredient is to decompose the harmonic coordinate into a smooth part and a highly oscillatory part of which the magnitude is small. Such a decomposition plays a key role in our construction of the effective equation. We show that the solution to the effective equation is smooth, and could be resolved on a regular coarse mesh grid. Furthermore, we provide error analysis and show that the solution to the effective equation plus a correction term is close to the original multiscale solution.

For the stochastic PDEs, we propose the model reduction based data-driven stochastic method and multilevel Monte Carlo method. In the multiquery, setting and on the assumption that the ratio of the smallest scale and largest scale is not too small, we propose the multiscale data-driven stochastic method. We construct a data-driven stochastic basis and solve the coupled deterministic PDEs to obtain the solutions. For the tougher problems, we propose the multiscale multilevel Monte Carlo method. We apply the multilevel scheme to the effective equations and assemble the stiffness matrices efficiently on each coarse mesh grid. In both methods, the $\KL$ expansion plays an important role in extracting the main parts of some stochastic quantities.

For both the deterministic and stochastic PDEs, numerical results are presented to demonstrate the accuracy and robustness of the methods. We also show the computational time cost reduction in the numerical examples.

Selectivity, activity, and stability of ruthenium-carbene based olefin metathesis initiators

The olefin metathesis reaction has found many applications in polymer synthesis and more recently in organic synthesis. The use of single component late metal olefin metathesis catalysts has expanded the scope of the reaction to many new applications and has allowed for detailed study of the catalytic species.

The metathesis of terminal olefins of different steric bulk, different geometry as well as electronically different para-substituted styrenes was studied with the ruthenium based metathesis initiators, trans-(PCy₃)₂Cl₂Ru=CHR, of different carbene substituents. Increasing olefin bulk was found to slow the rate of reaction and trans internal olefins were found to be slower to react than cis internal olefins. The kinetic product of a11 reactions was found to be the alkylidene, rather than the methylidene, suggesting the intermediacy of a 2,4-metallacycle. The observed effects were used to explain the mechanism of ring opening cross metathesis and acyclic diene metathesis polymerization. No linear electronic effects were observed.

In studying the different carbene ligands, a series of ester-carbene complexes was synthesized. These complexes were found to be highly active for the metathesis of olefinic substrates, including acrylates and trisubstituted olefins. In addition, the estercarbene moiety is thermodynamically high in energy. As a result, these complexes react to ring-open cyclohexene by metathesis to alleviate the thermodynamic strain of the ester-carbene ligand. However, ester-carbene complexes were found to be thermolytically unstable in solution.

Thermolytic decomposition pathways were studied for several ruthenium-carbene based olefin metathesis catalysts. Substituted carbenes were found to decompose through bimolecular pathways while the unsubstituted carbene (the methylidene) was found to decompose unimolecularly. The stability of several derivatives of the bis-phosphine ruthenium based catalysts was studied for its implications to ring-closing metathesis. The reasons for the activity and stability of the different ruthenium-based catalysts is discussed.

The difference in catalyst activity and initiation is discussed for the bis-phosphine based and mixed N-heterocyclic carbene/phosphine based ruthenium olefin metathesis catalysts. The mixed ligand catalysts initiate far slower than the bis-phosphine catalysts but are far more metathesis active. A scheme is proposed to explain the difference in reactivity between the two types of catalysts.

On the Role of Delays in Biological Systems : Analysis and Design

This work quantifies the nature of delays in genetic regulatory networks and their effect on system dynamics. It is known that a time lag can emerge from a sequence of biochemical reactions. Applying this modeling framework to the protein production processes, delay distributions are derived in a stochastic (probability density function) and deterministic setting (impulse function), whilst being shown to be equivalent under different assumptions. The dependence of the distribution properties on rate constants, gene length, and time-varying temperatures is investigated. Overall, the distribution of the delay in the context of protein production processes is shown to be highly dependent on the size of the genes and mRNA strands as well as the reaction rates. Results suggest longer genes have delay distributions with a smaller relative variance, and hence, less uncertainty in the completion times, however, they lead to larger delays. On the other hand large uncertainties may actually play a positive role, as broader distributions can lead to larger stability regions when this formalization of the protein production delays is incorporated into a feedback system.

Furthermore, evidence suggests that delays may play a role as an explicit design into existing controlling mechanisms. Accordingly, the reccurring dual-feedback motif is also investigated with delays incorporated into the feedback channels. The dual-delayed feedback is shown to have stabilizing effects through a control theoretic approach. Lastly, a distributed delay based controller design method is proposed as a potential design tool. In a preliminary study, the dual-delayed feedback system re-emerges as an effective controller design.

General-domain compressible Navier-Stokes solvers exhibiting quasi-unconditional stability and high-order accuracy in space and time

This thesis presents a new class of solvers for the subsonic compressible Navier-Stokes equations in general two- and three-dimensional spatial domains. The proposed methodology incorporates: 1) A novel linear-cost implicit solver based on use of higher-order backward differentiation formulae (BDF) and the alternating direction implicit approach (ADI); 2) A fast explicit solver; 3) Dispersionless spectral spatial discretizations; and 4) A domain decomposition strategy that negotiates the interactions between the implicit and explicit domains. In particular, the implicit methodology is quasi-unconditionally stable (it does not suffer from CFL constraints for adequately resolved flows), and it can deliver orders of time accuracy between two and six in the presence of general boundary conditions. In fact this thesis presents, for the first time in the literature, high-order time-convergence curves for Navier-Stokes solvers based on the ADI strategy---previous ADI solvers for the Navier-Stokes equations have not demonstrated orders of temporal accuracy higher than one. An extended discussion is presented in this thesis which places on a solid theoretical basis the observed quasi-unconditional stability of the methods of orders two through six. The performance of the proposed solvers is favorable. For example, a two-dimensional rough-surface configuration including boundary layer effects at Reynolds number equal to one million and Mach number 0.85 (with a well-resolved boundary layer, run up to a sufficiently long time that single vortices travel the entire spatial extent of the domain, and with spatial mesh sizes near the wall of the order of one hundred-thousandth the length of the domain) was successfully tackled in a relatively short (approximately thirty-hour) single-core run; for such discretizations an explicit solver would require truly prohibitive computing times. As demonstrated via a variety of numerical experiments in two- and three-dimensions, further, the proposed multi-domain parallel implicit-explicit implementations exhibit high-order convergence in space and time, useful stability properties, limited dispersion, and high parallel efficiency.

Continuous stochastic processes

A general review of stochastic processes is given in the introduction; definitions, properties and a rough classification are presented together with the position and scope of the author's work as it fits into the general scheme.

The first section presents a brief summary of the pertinent analytical properties of continuous stochastic processes and their probability-theoretic foundations which are used in the sequel.

The remaining two sections (II and III), comprising the body of the work, are the author's contribution to the theory. It turns out that a very inclusive class of continuous stochastic processes are characterized by a fundamental partial differential equation and its adjoint (the Fokker-Planck equations). The coefficients appearing in those equations assimilate, in a most concise way, all the salient properties of the process, freed from boundary value considerations. The writer’s work consists in characterizing the processes through these coefficients without recourse to solving the partial differential equations.

First, a class of coefficients leading to a unique, continuous process is presented, and several facts are proven to show why this class is restricted. Then, in terms of the coefficients, the unconditional statistics are deduced, these being the mean, variance and covariance. The most general class of coefficients leading to the Gaussian distribution is deduced, and a complete characterization of these processes is presented. By specializing the coefficients, all the known stochastic processes may be readily studied, and some examples of these are presented; viz. the Einstein process, Bachelier process, Ornstein-Uhlenbeck process, etc. The calculations are effectively reduced down to ordinary first order differential equations, and in addition to giving a comprehensive characterization, the derivations are materially simplified over the solution to the original partial differential equations.

In the last section the properties of the integral process are presented. After an expository section on the definition, meaning, and importance of the integral process, a particular example is carried through starting from basic definition. This illustrates the fundamental properties, and an inherent paradox. Next the basic coefficients of the integral process are studied in terms of the original coefficients, and the integral process is uniquely characterized. It is shown that the integral process, with a slight modification, is a continuous Markoff process.

The elementary statistics of the integral process are deduced: means, variances, and covariances, in terms of the original coefficients. It is shown that an integral process is never temporally homogeneous in a non-degenerate process.

Finally, in terms of the original class of admissible coefficients, the statistics of the integral process are explicitly presented, and the integral process of all known continuous processes are specified.

Stability of Hypervelocity Boundary Layers

The early stage of laminar-turbulent transition in a hypervelocity boundary layer is studied using a combination of modal linear stability analysis, transient growth analysis, and direct numerical simulation. Modal stability analysis is used to clarify the behavior of first and second mode instabilities on flat plates and sharp cones for a wide range of high enthalpy flow conditions relevant to experiments in impulse facilities. Vibrational nonequilibrium is included in this analysis, its influence on the stability properties is investigated, and simple models for predicting when it is important are described.

Transient growth analysis is used to determine the optimal initial conditions that lead to the largest possible energy amplification within the flow. Such analysis is performed for both spatially and temporally evolving disturbances. The analysis again targets flows that have large stagnation enthalpy, such as those found in shock tunnels, expansion tubes, and atmospheric flight at high Mach numbers, and clarifies the effects of Mach number and wall temperature on the amplification achieved. Direct comparisons between modal and non-modal growth are made to determine the relative importance of these mechanisms under different flow regimes.

Conventional stability analysis employs the assumption that disturbances evolve with either a fixed frequency (spatial analysis) or a fixed wavenumber (temporal analysis). Direct numerical simulations are employed to relax these assumptions and investigate the downstream propagation of wave packets that are localized in space and time, and hence contain a distribution of frequencies and wavenumbers. Such wave packets are commonly observed in experiments and hence their amplification is highly relevant to boundary layer transition prediction. It is demonstrated that such localized wave packets experience much less growth than is predicted by spatial stability analysis, and therefore it is essential that the bandwidth of localized noise sources that excite the instability be taken into account in making transition estimates. A simple model based on linear stability theory is also developed which yields comparable results with an enormous reduction in computational expense. This enables the amplification of finite-width wave packets to be taken into account in transition prediction.

Stochastic optimal control

H. J. Kushner has obtained the differential equation satisfied by the optimal feedback control law for a stochastic control system in which the plant dynamics and observations are perturbed by independent additive Gaussian white noise processes. However, the differentiation includes the first and second functional derivatives and, except for a restricted set of systems, is too complex to solve with present techniques.

This investigation studies the optimal control law for the open loop system and incorporates it in a sub-optimal feedback control law. This suboptimal control law's performance is at least as good as that of the optimal control function and satisfies a differential equation involving only the first functional derivative. The solution of this equation is equivalent to solving two two-point boundary valued integro-partial differential equations. An approximate solution has advantages over the conventional approximate solution of Kushner's equation.

As a result of this study, well known results of deterministic optimal control are deduced from the analysis of optimal open loop control.

Stability of Electrode-Electrolyte Interfaces during Charging in Lithium Batteries

In this thesis we study the growth of a Li electrode-electrolyte interface in the presence of an elastic prestress. In particular, we focus our interest on Li-air batteries with a solid electrolyte, LIPON, which is a new type of secondary or rechargeable battery. Theoretical studies and experimental evidence show that during the process of charging the battery the replated lithium adds unevenly to the electrode surface. This phenomenon eventually leads to dendrite formation as the battery is charged and discharged numerous times. In order to suppress or alleviate this deleterious effect of dendrite growth, we put forth a study based on a linear stability analysis. Taking into account all the mechanisms of mass transport and interfacial kinetics, we model the evolution of the interface. We find that, in the absence of stress, the stability of a planar interface depends on interfacial diffusion properties and interfacial energy. Specifically, if Herring-Mullins capillarity-driven interfacial diffusion is accounted for, interfaces are unstable against all perturbations of wavenumber larger than a critical value. We find that the effect of an elastic prestress is always to stabilize planar interfacial growth by increasing the critical wavenumber for instability. A parametric study results in quantifying the extent of the prestress stabilization in a manner that can potentially be used in the design of Li-air batteries. Moreover, employing the theory of finite differences we numerically solve the equation that describes the evolution of the surface profile and present visualization results of the surface evolution by time. Lastly, numerical simulations performed in a commercial finite element software validate the theoretical formulation of the interfacial elastic energy change with respect to the planar interface.