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.

A multi-scale approach to shaping carbon nanotube structures for hollow microneedles

The concept of a carbon nanotube microneedle array is explored in this thesis from multiple perspectives including microneedle fabrication, physical aspects of transdermal delivery, and in vivo transdermal drug delivery experiments. Starting with standard techniques in carbon nanotube (CNT) fabrication, including catalyst patterning and chemical vapor deposition, vertically-aligned carbon nanotubes are utilized as a scaffold to define the shape of the hollow microneedle. Passive, scalable techniques based on capillary action and unique photolithographic methods are utilized to produce a CNT-polymer composite microneedle. Specific examples of CNT-polyimide and CNT-epoxy microneedles are investigated. Further analysis of the transport properties of polymer resins reveals general requirements for applying arbitrary polymers to the fabrication process.

The bottom-up fabrication approach embodied by vertically-aligned carbon nanotubes allows for more direct construction of complex high-aspect ratio features than standard top-down fabrication approaches, making microneedles an ideal application for CNTs. However, current vertically-aligned CNT fabrication techniques only allow for the production of extruded geometries with a constant cross-sectional area, such as cylinders. To rectify this limitation, isotropic oxygen etching is introduced as a novel fabrication technique to create true 3D CNT geometry. Oxygen etching is utilized to create a conical geometry from a cylindrical CNT structure as well as create complex shape transformations in other CNT geometries.

CNT-polymer composite microneedles are anchored onto a common polymer base less than 50 µm thick, which allows for the microneedles to be incorporated into multiple drug delivery platforms, including modified hypodermic syringes and silicone skin patches. Cylindrical microneedles are fabricated with 100 µm outer diameter and height of 200-250 µm with a central cavity, or lumen, diameter of 30 µm to facilitate liquid drug flow. In vitro delivery experiments in swine skin demonstrate the ability of the microneedles to successfully penetrate the skin and deliver aqueous solutions.

An in vivo study was performed to assess the ability of the CNT-polymer microneedles to deliver drugs transdermally. CNT-polymer microneedles are attached to a hand actuated silicone skin patch that holds a liquid reservoir of drugs. Fentanyl, a potent analgesic, was administered to New Zealand White Rabbits through 3 routes of delivery: topical patch, CNT-polymer microneedles, and subcutaneous hypodermic injection. Results demonstrate that the CNT-polymer microneedles have a similar onset of action as the topical patch. CNT-polymer microneedles were also vetted as a painless delivery approach compared to hypodermic injection. Comparative analysis with contemporary microneedle designs demonstrates that the delivery achieved through CNT-polymer microneedles is akin to current hollow microneedle architectures. The inherent advantage of applying a bottom-up fabrication approach alongside similar delivery performance to contemporary microneedle designs demonstrates that the CNT-polymer composite microneedle is a viable architecture in the emerging field of painless transdermal delivery.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.