Matthew M. Peet

Antonis Papachristodoulou, James Anderson, Giorgio Valmorbida et al.

The release of SOSTOOLS v4.00 comes as we approach the 20th anniversary of the original release of SOSTOOLS v1.00 back in April, 2002. SOSTOOLS was originally envisioned as a flexible tool for parsing and solving polynomial optimization problems, using the SOS tightening of polynomial positivity constraints, and capable of adapting to the ever-evolving fauna of applications of SOS. There are now a variety of SOS programming parsers beyond SOSTOOLS, including YALMIP, Gloptipoly, SumOfSquares, and others. We hope SOSTOOLS remains the most intuitive, robust and adaptable toolbox for SOS programming. Recent progress in Semidefinite programming has opened up new possibilities for solving large Sum of Squares programming problems, and we hope the next decade will be one where SOS methods will find wide application in different areas. In SOSTOOLS v4.00, we implement a parsing approach that reduces the computational and memory requirements of the parser below that of the SDP solver itself. We have re-developed the internal structure of our polynomial decision variables. Specifically, polynomial and SOS variable declarations made using sossosvar, sospolyvar, sosmatrixvar, etc now return a new polynomial structure, dpvar. This new polynomial structure, is documented in the enclosed dpvar guide, and isolates the scalar SDP decision variables in the SOS program from the independent variables used to construct the SOS program. As a result, the complexity of the parser scales almost linearly in the number of decision variables. As a result of these changes, almost all users will notice a significant increase in speed, with large-scaleproblems experiencing the most dramatic speedups. Parsing time is now always less than 10% of time spent in the SDP solver. Finally, SOSTOOLS now provides support for the MOSEK solver interface as well as the SeDuMi, SDPT3, CSDP, SDPNAL, SDPNAL+, and SDPA solvers.

Declan S. Jagt, Matthew M. Peet

Physical processes evolving in both time and space are often modeled using Partial Differential Equations (PDEs). Recently, it has been shown how stability analysis and control of coupled PDEs in a single spatial variable can be more conveniently performed using an equivalent Partial Integral Equation (PIE) representation. The construction of this PIE representation is based on an analytic expression for the inverse of the spatial differential operator, $\partial_s^{d}$, on the domain defined by boundary conditions. In this paper, we show how this univariate representation may be extended inductively to multiple spatial variables by representing the domain as the intersection of lifted univariate domains. Specifically, we show that if each univariate domain is well-posed, then there exists a readily verified consistency condition which is necessary and sufficient for existence of an inverse to the multivariate spatial differential operator, $D^α=\partial_{s_1}^{α_1}\cdots\partial_{s_N}^{α_N}$, on the PDE domain. Furthermore, we show that this inverse is an element of a $*$-algebra of Partial Integral (PI) operators defined by polynomial semi-separable kernels. Based on this operator algebra, we show that the evolution of any suitably well-posed linear multivariate PDE may be described by a PIE, parameterized by elements of the PI algebra. A convex computational test for PDE stability is then proposed using a positive matrix parameterization of positive PI operators, and software (PIETOOLS) is provided which automates the process of representation and stability analysis of such PDEs. This software is used to analyze stability of 2D heat, wave, and plate equations, obtaining accurate bounds on the rate of decay.

Guoying Miao, Matthew M. Peet, Keqin Gu

This article presents the inverse of the kernel operator associated with the complete quadratic Lyapunov-Krasovskii functional for coupled differential-functional equations when the kernel operator is separable. Similar to the case of time-delay systems of retarded type, the inverse operator is instrumental in control synthesis. Unlike the power series expansion approach used in the previous literature, a direct algebraic method is used here. It is shown that the domain of definition of the infinitesimal generator is an invariant subspace of the inverse operator if it is an invariant subspace of the kernel operator. The process of control synthesis using the inverse operator is described, and a numerical example is presented using the sum-of-square formulation.

Matthew M. Peet

Optimal controller synthesis is a bilinear problem and hence difficult to solve in a computationally efficient manner. We are able to resolve this bilinearity for systems with delay by first convexifying the problem in infinite-dimensions - formulating the $H_\infty$ optimal state-feedback controller synthesis problem for distributed-parameter systems as a Linear Operator Inequality - a form of convex optimization with operator variables. Next, we use positive matrices to parameterize positive `complete quadratic' operators - allowing the controller synthesis problem to be solved using Semidefinite Programming (SDP). We then use the solution to this SDP to calculate the feedback gains and provide effective methods for real-time implementation. Finally, we use several test cases to verify that the resulting controllers are \textit{optimal} to several decimal places as measured by the minimal achievable closed-loop $H_\infty$ norm, and as compared against controllers designed using high-order Padé approximations.

Brendon K. Colbert, Joslyn L. Mangal, Aleksandr Talitckii et al.

The immune response is a dynamic process by which the body determines whether an antigen is self or nonself. The state of this dynamic process is defined by the relative balance and population of inflammatory and regulatory actors which comprise this decision making process. The goal of immunotherapy as applied to, e.g. Rheumatoid Arthritis (RA), then, is to bias the immune state in favor of the regulatory actors - thereby shutting down autoimmune pathways in the response. While there are several known approaches to immunotherapy, the effectiveness of the therapy will depend on how this intervention alters the evolution of this state. Unfortunately, this process is determined not only by the dynamics of the process, but the state of the system at the time of intervention - a state which is difficult if not impossible to determine prior to application of the therapy. To identify such states we consider a mouse model of RA (Collagen-Induced Arthritis (CIA)) immunotherapy; collect high dimensional data on T cell markers and populations of mice after treatment with a recently developed immunotherapy for CIA; and use feature selection algorithms in order to select a lower dimensional subset of this data which can be used to predict both the full set of T cell markers and populations, along with the efficacy of immunotherapy treatment.

Matthew M. Peet

In this paper, we present a framework for Stability Analysis of Systems of Coupled Linear Partial-Differential Equations. The class of PDE systems considered in this paper includes parabolic, elliptic and hyperbolic systems with Dirichelet, Neuman and mixed boundary conditions. The results in this paper apply to systems with a single spatial variable and assume existence and continuity of solutions except in such cases when existence and continuity can be inferred from existence of a Lyapunov function. Our approach is based on a new concept of state for PDE systems which allows us to express the derivative of the Lyapunov function as a Linear Operator Inequality directly on $L_2$ and allows for any type of suitably well-posed boundary conditions. This approach obviates the need for integration by parts, spacing functions or similar mathematical encumbrances. The resulting algorithms are implemented in Matlab, tested on several motivating examples, and the codes have been posted online. Numerical testing indicates the approach has little or no conservatism for a large class of systems.

Aleksandr Talitckii, Brendon K. Colbert, Matthew M. Peet

The accuracy and complexity of machine learning algorithms based on kernel optimization are determined by the set of kernels over which they are able to optimize. An ideal set of kernels should: admit a linear parameterization (for tractability); be dense in the set of all kernels (for robustness); be universal (for accuracy). Recently, a framework was proposed for using positive matrices to parameterize a class of positive semi-separable kernels. Although this class can be shown to meet all three criteria, previous algorithms for optimization of such kernels were limited to classification and furthermore relied on computationally complex Semidefinite Programming (SDP) algorithms. In this paper, we pose the problem of learning semiseparable kernels as a minimax optimization problem and propose a SVD-QCQP primal-dual algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches. Furthermore, we provide an efficient implementation of this algorithm for both classification and regression -- an implementation which enables us to solve problems with 100 features and up to 30,000 datums. Finally, when applied to benchmark data, the algorithm demonstrates the potential for significant improvement in accuracy over typical (but non-convex) approaches such as Neural Nets and Random Forest with similar or better computation time.

Evgeny Meyer, Matthew M. Peet

In this paper, we present an algorithm for stability analysis of systems described by coupled linear Partial Differential Equations (PDEs) with constant coefficients and mixed boundary conditions. Our approach uses positive matrices to parameterize functionals which are positive or negative on certain function spaces. Applying this parameterization to construct Lyapunov functionals with negative derivative allows us to express stability conditions as a set of LMI constraints which can be constructed using SOSTOOLS and tested using standard SDP solvers such as SeDuMi. The results are tested using a simple numerical example and compared results obtained from simulation using a standard form of discretization.

Evgeny Meyer, Matthew M. Peet

In this paper, we present a methodology for stability analysis of a general class of systems defined by coupled Partial Differential Equations (PDEs) with spatially dependent coefficients and a general class of boundary conditions. This class includes PDEs of the parabolic, elliptic and hyperbolic type as well as coupled systems without boundary feedback. Our approach uses positive matrices to parameterize a new class of SOS Lyapunov functionals and combines these with a parametrization of projection operators which allow us to enforce positivity and negativity on subspaces of L_2. The result allows us to express Lyapunov stability conditions as a set of Linear Matrix Inequality (LMI) constraints which can be constructed using SOSTOOLS and tested using Semi-Definite Programming (SDP) solvers such as SeDuMi or Mosek. The methodology is tested using several simple numerical examples and compared with results obtained from simulation using a standard form of numerical discretization.

Declan S. Jagt, Matthew M. Peet

Ensuring that a PDE model is well-posed is a necessary precursor to any form of analysis, control, or numerical simulation. Although the Lumer-Phillips theorem provides necessary and sufficient conditions for well-posedness of dissipative PDEs, these conditions must hold only on the domain of the PDE -- a proper subspace of $L_{2}$ -- which can make them difficult to verify in practice. In this paper, we show how the Lumer-Phillips conditions for PDEs can be tested more conveniently using the equivalent Partial Integral Equation (PIE) representation. This representation introduces a fundamental state in the Hilbert space $L_{2}$ and provides a bijection between this state space and the PDE domain. Using this bijection, we reformulate the Lumer-Phillips conditions as operator inequalities on $L_{2}$. We show how these inequalities can be tested using convex optimization methods, establishing a least upper bound on the exponential growth rate of solutions. We demonstrate the effectiveness of the proposed approach by verifying well-posedness for several classical examples of parabolic and hyperbolic PDEs.

Jungbae Chun, Sengiyumva Kisole, Matthew M. Peet et al.

It is difficult to analyze the stability of systems with time-varying delays. One approach is to construct a time-transformation that converts the system into a form with a constant delay but with a time-varying scalar appearing in the system matrices. The stability of this transformed system can then be analyzed using methods to bound the effect of the time-varying scalar. One issue is that this transformation is non-unique and requires the solution of an Abel equation. A specific time-transformation typically must be computed numerically. We address this issue by computing an explicit, although approximate, time-transformation for systems where the delay has a constant plus small periodic term. We use a perturbative expansion to construct our explicit solutions. We provide a simple numerical example to illustrate the approach. We also demonstrate the use of this time-transformation to analyze stability of the system with this class of periodic delays.

Sengiyumva Kisole, Jungbae Chun, Peter Seiler et al.

Abel's classic transformation shows that any well-posed system with time-varying delay is equivalent to a parameter-varying system with fixed delay. The existence of such a parameter-varying constant delay representation then simplifies the problems of stability analysis and optimal control. Unfortunately, the method for construction of such transformations has been ad-hoc -- requiring an iterative time-stepping approach to constructing the transformation beginning with a seed function subject to boundary-value constraints. Moreover, a poor choice of seed function often results in a constant delay representation with large time-variations in system parameters -- obviating the benefits of such a representation. In this paper, we show how the set of all feasible seed functions can be parameterized using a basis for $L_2$. This parameterization is then used to search for seed functions for which the corresponding time-transformation results in smaller parameter variation. The parameterization of admissible seed functions is illustrated with numerical examples that contrast how well-chosen and poorly chosen seed functions affect the boundedness of a time transformation.

Brendon K. Colbert, Matthew M. Peet

The accuracy and complexity of machine learning algorithms based on kernel optimization are limited by the set of kernels over which they are able to optimize. An ideal set of kernels should: admit a linear parameterization (for tractability); be dense in the set of all kernels (for robustness); be universal (for accuracy). The recently proposed Tesselated Kernels (TKs) is currently the only known class which meets all three criteria. However, previous algorithms for optimizing TKs were limited to classification and relied on Semidefinite Programming (SDP) - limiting them to relatively small datasets. By contrast, the 2-step algorithm proposed here scales to 10,000 data points and extends to the regression problem. Furthermore, when applied to benchmark data, the algorithm demonstrates significant improvement in performance over Neural Nets and SimpleMKL with similar computation time.

Brendon K. Colbert, Matthew M. Peet

The accuracy and complexity of kernel learning algorithms is determined by the set of kernels over which it is able to optimize. An ideal set of kernels should: admit a linear parameterization (tractability); be dense in the set of all kernels (accuracy); and every member should be universal so that the hypothesis space is infinite-dimensional (scalability). Currently, there is no class of kernel that meets all three criteria - e.g. Gaussians are not tractable or accurate; polynomials are not scalable. We propose a new class that meet all three criteria - the Tessellated Kernel (TK) class. Specifically, the TK class: admits a linear parameterization using positive matrices; is dense in all kernels; and every element in the class is universal. This implies that the use of TK kernels for learning the kernel can obviate the need for selecting candidate kernels in algorithms such as SimpleMKL and parameters such as the bandwidth. Numerical testing on soft margin Support Vector Machine (SVM) problems show that algorithms using TK kernels outperform other kernel learning algorithms and neural networks. Furthermore, our results show that when the ratio of the number of training data to features is high, the improvement of TK over MKL increases significantly.

Aditya Gahlawat, Matthew M. Peet

We present an optimization-based framework for analysis and control of linear parabolic partial differential equations (PDEs) with spatially varying coefficients without discretization or numerical approximation. For controller synthesis, we consider both full-state feedback and point observation (output feedback). The input occurs at the boundary (point actuation). We use positive matrices to parameterize positive Lyapunov functions and polynomials to parameterize controller and observer gains. We use duality and an invertible state-variable transformation to convexify the controller synthesis problem. Finally, we combine our synthesis condition with the Luenberger observer framework to express the output feedback controller synthesis problem as a set of LMI/SDP constraints. We perform an extensive set of numerical experiments to demonstrate accuracy of the conditions and to prove necessity of the Lyapunov structures chosen. We provide numerical and analytical comparisons with alternative approaches to control including Sturm Liouville theory and backstepping. Finally we use numerical tests to show that the method retains its accuracy for alternative boundary conditions.

Aditya Gahlawat, Matthew M. Peet

In this paper we use SOS and SDP to design output feedback controllers for a class of one-dimensional parabolic partial differential equations with point measurements and point actuation. Our approach is based on the use of SOS to search for positive quadratic Lyapunov functions, controllers and observers. These Lyapunov functions, controllers and observers are parameterized by linear operators which are defined by SOS polynomials. The main result of the paper is the development of an improved class of observer-based controllers and evidence which indicates that when the system is controllable and observable, these methods will find a observer-based controller for sufficiently high polynomial degree (similar to well-known results from backstepping).

Matthew M. Peet

This thesis addresses the question of stability of systems defined by differential equations which contain nonlinearity and delay. In particular, we analyze the stability of a well-known delayed nonlinear implementation of a certain Internet congestion control protocol. We also describe a generalized methodology for proving stability of time-delay systems through the use of semidefinite programming. In Chapters 4 and 5, we consider an Internet congestion control protocol based on the decentralized gradient projection algorithm. For a certain class of utility function, this algorithm was shown to be globally convergent for some sufficiently small value of a gain parameter. Later work gave an explicit bound on this gain for a linearized version of the system. This thesis proves that this bound also implies stability of the original system. In Chapter 7, we describe a general methodology for proving stability of linear time-delay systems by computing solutions to an operator-theoretic version of the Lyapunov inequality via semidefinite programming. The result is stated in terms of a nested sequence of sufficient conditions which are of increasing accuracy. This approach is generalized to the case of parametric uncertainty by considering parameter-dependent Lyapunov functionals. Numerical examples are given to demonstrate convergence of the algorithm. In Chapter 8, this approach is generalized to nonlinear time-delay systems through the use of non-quadratic Lyapunov functionals.