Polynomial Constraints for Robustness Analysis of Nonlinear SystemsNeelay Junnarkar, Peter Seiler, Murat Arcak
This paper presents a framework for abstracting uncertain or non-polynomial components of dynamical systems using polynomial constraints. This enables the application of polynomial-based analysis tools, such as sum-of-squares programming, to a broader class of non-polynomial systems. A numerical method for constructing these constraints is proposed. The relationship between polynomial constraints and existing integral quadratic constraints (IQCs) is investigated, providing transformations of IQCs into polynomial constraints. The effectiveness of polynomial constraints in characterizing nonlinearities is validated via numerical examples to compute inner estimates of the region of attraction for two systems.
7.2OCDec 27, 2021
SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLABAntonis 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.
1.2SYMar 21, 2020
Direct Synthesis of Iterative Algorithms With Bounds on Achievable Worst-Case Convergence RateLaurent Lessard, Peter Seiler
Iterative first-order methods such as gradient descent and its variants are widely used for solving optimization and machine learning problems. There has been recent interest in analytic or numerically efficient methods for computing worst-case performance bounds for such algorithms, for example over the class of strongly convex loss functions. A popular approach is to assume the algorithm has a fixed size (fixed dimension, or memory) and that its structure is parameterized by one or two hyperparameters, for example a learning rate and a momentum parameter. Then, a Lyapunov function is sought to certify robust stability and subsequent optimization can be performed to find optimal hyperparameter tunings. In the present work, we instead fix the constraints that characterize the loss function and apply techniques from robust control synthesis to directly search over algorithms. This approach yields stronger results than those previously available, since the bounds produced hold over algorithms with an arbitrary, but finite, amount of memory rather than just holding for algorithms with a prescribed structure.
1.2SYOct 27, 2018
Reduced-order Aggregate Dynamical Model for Wind FarmsSanjana Vijayshankar, Victor Purba, Peter J. Seiler et al.
This paper presents an aggregate reduced-order model for a wind farm composed of identical parallel-connected Type-3 wind turbines. The model for individual turbines includes mechanical dynamics (arising from the turbine and doubly fed induction generator) and electrical dynamics (arising from the rotor-side and grid-side converters and associated filters). The proposed aggregate wind-farm model is structure preserving, in the sense that the parameters of the model are derived by scaling corresponding ones from the individual turbines. The aggregate model hence maps to an equivalent--albeit fictitious--wind turbine that captures the dynamics corresponding to the entire wind farm. The reduced-order model has obvious computational advantages, but more importantly, the presented analysis rigorously formalizes parametric scalings for aggregate wind-turbine models that have been applied with limited justification in prior works. Exhaustive numerical simulations validate the accuracy and computational benefits of the proposed reduced-order model.
1.2SYAug 28, 2014
Computation of lower bounds for the induced L2 norm of LPV systemsTamas Peni, Peter J. Seiler
Determining the induced L2 norm of a linear, parameter-varying (LPV) system is an integral part of many analysis and robust control design procedures. Most prior work has focused on efficiently computing upper bounds for the induced L2 norm. The conditions for upper bounds are typically based on scaled small-gain theorems with dynamic multipliers or dissipation inequalities with parameter dependent Lyapunov functions. This paper presents a complementary algorithm to compute lower bounds for the induced L2 norm. The proposed approach computes a lower bound on the gain by restricting the parameter trajectory to be a periodic signal. This restriction enables the use of recent results for exact calculation of the L2 norm for a periodic linear time varying system. The proposed lower bound algorithm has two benefits. First, the lower bound complements standard upper bound techniques. Specifically, a small gap between the bounds indicates that further computation, e.g. upper bounds with more complex Lyapunov functions, is unnecessary. Second, the lower bound algorithm returns a bad parameter trajectory for the LPV system that can be further analyzed to provide insight into the system performance.
7.3SYMar 16
Time-Transformation-Based Analysis of Systems with Periodic Delay via Perturbative ExpansionJungbae 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.
6.5OCMar 16
Parameterization of Seed Functions for Equivalent Representations of Time-Varying Delay SystemsSengiyumva 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.
9.2LGJul 9, 2024
A Complete Set of Quadratic Constraints for Repeated ReLU and GeneralizationsSahel Vahedi Noori, Bin Hu, Geir Dullerud et al.
This paper derives a complete set of quadratic constraints (QCs) for the repeated ReLU. The complete set of QCs is described by a collection of matrix copositivity conditions. We also show that only two functions satisfy all QCs in our complete set: the repeated ReLU and flipped ReLU. Thus our complete set of QCs bounds the repeated ReLU as tight as possible up to the sign invariance inherent in quadratic forms. We derive a similar complete set of incremental QCs for repeated ReLU, which can potentially lead to less conservative Lipschitz bounds for ReLU networks than the standard LipSDP approach. The basic constructions are also used to derive the complete sets of QCs for other piecewise linear activation functions such as leaky ReLU, MaxMin, and HouseHolder. Finally, we illustrate the use of the complete set of QCs to assess stability and performance for recurrent neural networks with ReLU activation functions. We rely on a standard copositivity relaxation to formulate the stability/performance condition as a semidefinite program. Simple examples are provided to illustrate that the complete sets of QCs and incremental QCs can yield less conservative bounds than existing sets.
10.3SYMar 17
Integral Quadratic Constraints for Repeated ReLUSahel Vahedi Noori, Bin Hu, Geir Dullerud et al.
This paper presents a new dynamic integral quadratic constraint (IQC) for the repeated Rectified Linear Unit (ReLU). These dynamic IQCs can be used to analyze stability and induced $\ell_2$-gain performance of discrete-time, recurrent neural networks (RNNs) with ReLU activation functions. These analysis conditions can be incorporated into learning-based controller synthesis methods, which currently rely on static IQCs. We show that our proposed dynamic IQCs for repeated ReLU form a superset of the dynamic IQCs for repeated, slope-restricted nonlinearities. We also prove that the $\ell_2$-gain bounds are nonincreasing with respect to the horizon used in the dynamic IQC filter. A numerical example using a simple (academic) RNN shows that our proposed IQCs lead to less conservative bounds than existing IQCs.
9.2SYMar 25
A Model Predictive Control Approach to Dual-Axis Agrivoltaic Panel TrackingAnna Stuhlmacher, Panupong Srisuthankul, Johanna L. Mathieu et al.
Agrivoltaic systems--photovoltaic (PV) panels installed above agricultural land--have emerged as a promising dual-use solution to address competing land demands for food and energy production. In this paper, we propose a model predictive control (MPC) approach to dual-axis agrivoltaic panel tracking control that dynamically adjusts panel positions in real time to maximize power production and crop yield given solar irradiance and ambient temperature measurements. We apply convex relaxations and shading factor approximations to reformulate the MPC optimization problem as a convex second-order cone program that determines the PV panel position adjustments away from the sun-tracking trajectory. Through case studies, we demonstrate our approach, exploring the Pareto front between i) an approach that maximizes power production without considering crop needs and ii) crop yield with no agrivoltaics. We also conduct a case study exploring the impact of forecast error on MPC performance. We find that dynamically adjusting agrivoltaic panel position helps us actively manage the trade-offs between power production and crop yield, and that active panel control enables the agrivoltaic system to achieve land equivalent ratio values of up to 1.897.
7.0SYMar 17
Robust Time-Varying Control Barrier Functions with Sector-Bounded NonlinearitiesFelix Biertümpfel, Jungbae Chun, and Peter Seiler
This paper presents a novel approach for ensuring safe operation of systems subject to input nonlinearities and time-varying safety constraints. We extend the time-varying barrier function framework to address time-varying safety constraints and explicitly account for control-dependent nonlinearities at the plant input. Guaranteed bounds on the input-output behavior of these nonlinearities are provided through pointwise-in-time quadratic constraints. The result is a class of robust time-varying control barrier functions that define a safety filter. This filter ensures robust safety for all admissible nonlinearities while minimally modifying the command generated by a baseline controller. We derive a second-order cone program (SOCP) to compute this safety filter online and provide feasibility conditions for ball-constrained inputs. The proposed approach is demonstrated on a spacecraft docking maneuver.
6.8SYMar 16
Transformers As Generalizable Optimal ControllersTurki Bin Mohaya, Maitham F. AL-Sunni, John M. Dolan et al.
We study whether optimal state-feedback laws for a family of heterogeneous Multiple-Input, Multiple-Output (MIMO) Linear Time-Invariant (LTI) systems can be captured by a single learned controller. We train one transformer policy on LQR-generated trajectories from systems with different state and input dimensions, using a shared representation with standardization, padding, dimension encoding, and masked loss. The policy maps recent state history to control actions without requiring plant matrices at inference time. Across a broad set of systems, it achieves empirically small sub-optimality relative to Linear Quadratic Regulator (LQR), remains stabilizing under moderate parameter perturbations, and benefits from lightweight fine-tuning on unseen systems. These results support transformer policies as practical approximators of near-optimal feedback laws over structured linear-system families.
2.3SYSep 13, 2024
Stability Margins of Neural Network ControllersNeelay Junnarkar, Murat Arcak, Peter Seiler
We present a method to train neural network controllers with guaranteed stability margins. The method is applicable to linear time-invariant plants interconnected with uncertainties and nonlinearities that are described by integral quadratic constraints. The type of stability margin we consider is the disk margin. Our training method alternates between a training step to maximize reward and a stability margin-enforcing step. In the stability margin enforcing-step, we solve a semidefinite program to project the controller into the set of controllers for which we can certify the desired disk margin.
26.9OCApr 4, 2024
Capabilities of Large Language Models in Control Engineering: A Benchmark Study on GPT-4, Claude 3 Opus, and Gemini 1.0 UltraDarioush Kevian, Usman Syed, Xingang Guo et al.
In this paper, we explore the capabilities of state-of-the-art large language models (LLMs) such as GPT-4, Claude 3 Opus, and Gemini 1.0 Ultra in solving undergraduate-level control problems. Controls provides an interesting case study for LLM reasoning due to its combination of mathematical theory and engineering design. We introduce ControlBench, a benchmark dataset tailored to reflect the breadth, depth, and complexity of classical control design. We use this dataset to study and evaluate the problem-solving abilities of these LLMs in the context of control engineering. We present evaluations conducted by a panel of human experts, providing insights into the accuracy, reasoning, and explanatory prowess of LLMs in control engineering. Our analysis reveals the strengths and limitations of each LLM in the context of classical control, and our results imply that Claude 3 Opus has become the state-of-the-art LLM for solving undergraduate control problems. Our study serves as an initial step towards the broader goal of employing artificial general intelligence in control engineering.
ControlAgent: Automating Control System Design via Novel Integration of LLM Agents and Domain ExpertiseXingang Guo, Darioush Keivan, Usman Syed et al.
Control system design is a crucial aspect of modern engineering with far-reaching applications across diverse sectors including aerospace, automotive systems, power grids, and robotics. Despite advances made by Large Language Models (LLMs) in various domains, their application in control system design remains limited due to the complexity and specificity of control theory. To bridge this gap, we introduce ControlAgent, a new paradigm that automates control system design via novel integration of LLM agents and control-oriented domain expertise. ControlAgent encodes expert control knowledge and emulates human iterative design processes by gradually tuning controller parameters to meet user-specified requirements for stability, performance, and robustness. ControlAgent integrates multiple collaborative LLM agents, including a central agent responsible for task distribution and task-specific agents dedicated to detailed controller design for various types of systems and requirements. ControlAgent also employs a Python computation agent that performs complex calculations and controller evaluations based on standard design information provided by task-specified LLM agents. Combined with a history and feedback module, the task-specific LLM agents iteratively refine controller parameters based on real-time feedback from prior designs. Overall, ControlAgent mimics the design processes used by (human) practicing engineers, but removes all the human efforts and can be run in a fully automated way to give end-to-end solutions for control system design with user-specified requirements. To validate ControlAgent's effectiveness, we develop ControlEval, an evaluation dataset that comprises 500 control tasks with various specific design goals. The effectiveness of ControlAgent is demonstrated via extensive comparative evaluations between LLM-based and traditional human-involved toolbox-based baselines.
5.1SYMay 8, 2024
Stability and Performance Analysis of Discrete-Time ReLU Recurrent Neural NetworksSahel Vahedi Noori, Bin Hu, Geir Dullerud et al.
This paper presents sufficient conditions for the stability and $\ell_2$-gain performance of recurrent neural networks (RNNs) with ReLU activation functions. These conditions are derived by combining Lyapunov/dissipativity theory with Quadratic Constraints (QCs) satisfied by repeated ReLUs. We write a general class of QCs for repeated RELUs using known properties for the scalar ReLU. Our stability and performance condition uses these QCs along with a "lifted" representation for the ReLU RNN. We show that the positive homogeneity property satisfied by a scalar ReLU does not expand the class of QCs for the repeated ReLU. We present examples to demonstrate the stability / performance condition and study the effect of the lifting horizon.
Synthesizing Neural Network Controllers with Closed-Loop Dissipativity GuaranteesNeelay Junnarkar, Murat Arcak, Peter Seiler
In this paper, a method is presented to synthesize neural network controllers such that the feedback system of plant and controller is dissipative, certifying performance requirements such as L2 gain bounds. The class of plants considered is that of linear time-invariant (LTI) systems interconnected with an uncertainty, including nonlinearities treated as an uncertainty for convenience of analysis. The uncertainty of the plant and the nonlinearities of the neural network are both described using integral quadratic constraints (IQCs). First, a dissipativity condition is derived for uncertain LTI systems. Second, this condition is used to construct a linear matrix inequality (LMI) which can be used to synthesize neural network controllers. Finally, this convex condition is used in a projection-based training method to synthesize neural network controllers with dissipativity guarantees. Numerical examples on an inverted pendulum and a flexible rod on a cart are provided to demonstrate the effectiveness of this approach.
3.2OCFeb 18, 2024
Model-Free $μ$-Synthesis: A Nonsmooth Optimization PerspectiveDarioush Keivan, Xingang Guo, Peter Seiler et al.
In this paper, we revisit model-free policy search on an important robust control benchmark, namely $μ$-synthesis. In the general output-feedback setting, there do not exist convex formulations for this problem, and hence global optimality guarantees are not expected. Apkarian (2011) presented a nonconvex nonsmooth policy optimization approach for this problem, and achieved state-of-the-art design results via using subgradient-based policy search algorithms which generate update directions in a model-based manner. Despite the lack of convexity and global optimality guarantees, these subgradient-based policy search methods have led to impressive numerical results in practice. Built upon such a policy optimization persepctive, our paper extends these subgradient-based search methods to a model-free setting. Specifically, we examine the effectiveness of two model-free policy optimization strategies: the model-free non-derivative sampling method and the zeroth-order policy search with uniform smoothing. We performed an extensive numerical study to demonstrate that both methods consistently replicate the design outcomes achieved by their model-based counterparts. Additionally, we provide some theoretical justifications showing that convergence guarantees to stationary points can be established for our model-free $μ$-synthesis under some assumptions related to the coerciveness of the cost function. Overall, our results demonstrate that derivative-free policy optimization offers a competitive and viable approach for solving general output-feedback $μ$-synthesis problems in the model-free setting.
Synthesis of Stabilizing Recurrent Equilibrium Network ControllersNeelay Junnarkar, He Yin, Fangda Gu et al.
We propose a parameterization of a nonlinear dynamic controller based on the recurrent equilibrium network, a generalization of the recurrent neural network. We derive constraints on the parameterization under which the controller guarantees exponential stability of a partially observed dynamical system with sector bounded nonlinearities. Finally, we present a method to synthesize this controller using projected policy gradient methods to maximize a reward function with arbitrary structure. The projection step involves the solution of convex optimization problems. We demonstrate the proposed method with simulated examples of controlling nonlinear plants, including plants modeled with neural networks.
2.2OCJan 3, 2022
Revisiting PGD Attacks for Stability Analysis of Large-Scale Nonlinear Systems and Perception-Based ControlAaron Havens, Darioush Keivan, Peter Seiler et al.
Many existing region-of-attraction (ROA) analysis tools find difficulty in addressing feedback systems with large-scale neural network (NN) policies and/or high-dimensional sensing modalities such as cameras. In this paper, we tailor the projected gradient descent (PGD) attack method developed in the adversarial learning community as a general-purpose ROA analysis tool for large-scale nonlinear systems and end-to-end perception-based control. We show that the ROA analysis can be approximated as a constrained maximization problem whose goal is to find the worst-case initial condition which shifts the terminal state the most. Then we present two PGD-based iterative methods which can be used to solve the resultant constrained maximization problem. Our analysis is not based on Lyapunov theory, and hence requires minimum information of the problem structures. In the model-based setting, we show that the PGD updates can be efficiently performed using back-propagation. In the model-free setting (which is more relevant to ROA analysis of perception-based control), we propose a finite-difference PGD estimate which is general and only requires a black-box simulator for generating the trajectories of the closed-loop system given any initial state. We demonstrate the scalability and generality of our analysis tool on several numerical examples with large-scale NN policies and high-dimensional image observations. We believe that our proposed analysis serves as a meaningful initial step toward further understanding of closed-loop stability of large-scale nonlinear systems and perception-based control.
5.5LGNov 30, 2021
Model-Free $μ$ Synthesis via Adversarial Reinforcement LearningDarioush Keivan, Aaron Havens, Peter Seiler et al.
Motivated by the recent empirical success of policy-based reinforcement learning (RL), there has been a research trend studying the performance of policy-based RL methods on standard control benchmark problems. In this paper, we examine the effectiveness of policy-based RL methods on an important robust control problem, namely $μ$ synthesis. We build a connection between robust adversarial RL and $μ$ synthesis, and develop a model-free version of the well-known $DK$-iteration for solving state-feedback $μ$ synthesis with static $D$-scaling. In the proposed algorithm, the $K$ step mimics the classical central path algorithm via incorporating a recently-developed double-loop adversarial RL method as a subroutine, and the $D$ step is based on model-free finite difference approximation. Extensive numerical study is also presented to demonstrate the utility of our proposed model-free algorithm. Our study sheds new light on the connections between adversarial RL and robust control.
Robustness against Adversarial Attacks in Neural Networks using Incremental DissipativityBernardo Aquino, Arash Rahnama, Peter Seiler et al.
Adversarial examples can easily degrade the classification performance in neural networks. Empirical methods for promoting robustness to such examples have been proposed, but often lack both analytical insights and formal guarantees. Recently, some robustness certificates have appeared in the literature based on system theoretic notions. This work proposes an incremental dissipativity-based robustness certificate for neural networks in the form of a linear matrix inequality for each layer. We also propose an equivalent spectral norm bound for this certificate which is scalable to neural networks with multiple layers. We demonstrate the improved performance against adversarial attacks on a feed-forward neural network trained on MNIST and an Alexnet trained using CIFAR-10.
Recurrent Neural Network Controllers Synthesis with Stability Guarantees for Partially Observed SystemsFangda Gu, He Yin, Laurent El Ghaoui et al.
Neural network controllers have become popular in control tasks thanks to their flexibility and expressivity. Stability is a crucial property for safety-critical dynamical systems, while stabilization of partially observed systems, in many cases, requires controllers to retain and process long-term memories of the past. We consider the important class of recurrent neural networks (RNN) as dynamic controllers for nonlinear uncertain partially-observed systems, and derive convex stability conditions based on integral quadratic constraints, S-lemma and sequential convexification. To ensure stability during the learning and control process, we propose a projected policy gradient method that iteratively enforces the stability conditions in the reparametrized space taking advantage of mild additional information on system dynamics. Numerical experiments show that our method learns stabilizing controllers while using fewer samples and achieving higher final performance compared with policy gradient.
14.0LGJan 26, 2020
Tractable Reinforcement Learning of Signal Temporal Logic ObjectivesHarish Venkataraman, Derya Aksaray, Peter Seiler
Signal temporal logic (STL) is an expressive language to specify time-bound real-world robotic tasks and safety specifications. Recently, there has been an interest in learning optimal policies to satisfy STL specifications via reinforcement learning (RL). Learning to satisfy STL specifications often needs a sufficient length of state history to compute reward and the next action. The need for history results in exponential state-space growth for the learning problem. Thus the learning problem becomes computationally intractable for most real-world applications. In this paper, we propose a compact means to capture state history in a new augmented state-space representation. An approximation to the objective (maximizing probability of satisfaction) is proposed and solved for in the new augmented state-space. We show the performance bound of the approximate solution and compare it with the solution of an existing technique via simulations.
1.2SYApr 7, 2019
Recovering Robustness in Model-Free Reinforcement learningHarish K. Venkataraman, Peter J. Seiler
Reinforcement learning (RL) is used to directly design a control policy using data collected from the system. This paper considers the robustness of controllers trained via model-free RL. The discussion focuses on the standard model-based linear quadratic Gaussian (LQG) problem as a special instance of RL. A simple example, originally formulated for LQG problems, is used to demonstrate that RL with partial observations can lead to poor robustness margins. It is proposed to recover robustness by introducing random perturbations at the system input during the RL training. The perturbation magnitude can be used to trade off performance for robustness. Two simple examples are presented to demonstrate the proposed method for enhancing robustness during RL training.
1.2SYSep 30, 2018
Finite Horizon Backward Reachability Analysis and Control Synthesis for Uncertain Nonlinear SystemsHe Yin, Andrew Packard, Murat Arcak et al.
We present a method for synthesizing controllers to steer trajectories from an initial set to a target set on a finite time horizon. The proposed control synthesis problem is decomposed into two steps. The first step under-approximates the backward reachable set (BRS) from the target set, using level sets of storage functions. The storage function is constructed with an iterative algorithm to maximize the volume of the under-approximated BRS. The second step obtains a control law by solving a pointwise min-norm optimization problem using the pre-computed storage function. A closed-form solution of this min-norm optimization can be computed through the KKT conditions. This control synthesis framework is then extended to uncertain nonlinear systems with parametric uncertainties and L_2 disturbances. The computation algorithm for all cases is derived using sum-of-squares (SOS) programming and the S-procedure. The proposed method is applied to several robotics and aircraft examples.
25.3OCNov 3, 2017
Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite ProgramsBin Hu, Peter Seiler, Laurent Lessard
We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy, and robustness to gradient inaccuracy. We also provide feasible points for this LMI and obtain theoretical formulas that quantify the convergence properties of biased SGD under various assumptions on the loss functions.
7.6MLJun 25, 2017
A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic ConstraintsBin Hu, Peter Seiler, Anders Rantzer
We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods including SAGA, Finito, and stochastic dual coordinate ascent (SDCA). First, we show an intrinsic connection between stochastic optimization methods and dynamic jump systems, and propose a general jump system model for stochastic optimization methods. Our proposed model recovers SAGA, SDCA, Finito, and SAG as special cases. Then we combine jump system theory with several simple quadratic inequalities to derive sufficient conditions for convergence rate certifications of the proposed jump system model under various assumptions (with or without individual convexity, etc). The derived conditions are linear matrix inequalities (LMIs) whose sizes roughly scale with the size of the training set. We make use of the symmetry in the stochastic optimization methods and reduce these LMIs to some equivalent small LMIs whose sizes are at most 3 by 3. We solve these small LMIs to provide analytical proofs of new convergence rates for SAGA, Finito and SDCA (with or without individual convexity). We also explain why our proposed LMI fails in analyzing SAG. We reveal a key difference between SAG and other methods, and briefly discuss how to extend our LMI analysis for SAG. An advantage of our approach is that the proposed analysis can be automated for a large class of stochastic methods under various assumptions (with or without individual convexity, etc).
1.2SYApr 9, 2015
An Overview of Integral Quadratic Constraints for Delayed Nonlinear and Parameter-Varying SystemsHarald Pfifer, Peter Seiler
A general framework is presented for analyzing the stability and performance of nonlinear and linear parameter varying (LPV) time delayed systems. First, the input/output behavior of the time delay operator is bounded in the frequency domain by integral quadratic constraints (IQCs). A constant delay is a linear, time-invariant system and this leads to a simple, intuitive interpretation for these frequency domain constraints. This simple interpretation is used to derive new IQCs for both constant and varying delays. Second, the performance of nonlinear and LPV delayed systems is bounded using dissipation inequalities that incorporate IQCs. This step makes use of recent results that show, under mild technical conditions, that an IQC has an equivalent representation as a finite-horizon time-domain constraint. Numerical examples are provided to demonstrate the effectiveness of the method for both class of systems.