Composite quadratic Lyapunov functions for constrained control systems

A Lyapunov function based on a set of quadratic functions is introduced in this paper. We call this Lyapunov function a composite quadratic function. Some important properties of this Lyapunov function are revealed. We show that this function is continuously differentiable and its level set is the convex hull of a set of ellipsoids. These results are used to study the set invariance properties of continuous-time linear systems with input and state constraints. We show that, for a system under a given saturated linear feedback, the convex hull of a set of invariant ellipsoids is also invariant. If each ellipsoid in a set can be made invariant with a bounded control of the saturating actuators, then their convex hull can also be made invariant by the same actuators. For a set of ellipsoids, each invariant under a separate saturated linear feedback, we also present a method for constructing a nonlinear continuous feedback law which makes their convex hull invariant.     

Average-preserving symmetries and energy equipartition in linear Hamiltonian systems

This paper analyzes energy equipartition in linear Hamiltonian systems in a deterministic setting. We consider the group of phase space symmetries of a stable linear Hamiltonian system, and characterize the subgroup of symmetries whose elements preserve the time averages of quadratic functions along the trajectories of the system. As a corollary, we show that if the system has simple eigenvalues, then every symmetry preserves averages of quadratic functions. As an application of our results to linear undamped lumped-parameter systems, we provide a novel proof of the virial theorem, which states that the total energy is equipartitioned on the average between the kinetic energy and the potential energy. We also show that under the assumption of distinct natural frequencies, the time-averaged energies of two identical substructures of a linear undamped structure are equal. Examples are provided to illustrate the results.     

Quadratic boosting

This paper presents a strategy to improve the AdaBoost algorithm with a quadratic combination of base classifiers. We observe that learning this combination is necessary to get better performance and is possible by constructing an intermediate learner operating on the combined linear and quadratic terms. This is not trivial, as the parameters of the base classifiers are not under direct control, obstructing the application of direct optimization. We propose a new method realizing iterative optimization indirectly. First we train a classifier by randomizing the labels of training examples. Subsequently, the input learner is called repeatedly with a systematic update of the labels of the training examples in each round. We show that the quadratic boosting algorithm converges under the condition that the given base learner minimizes the empirical error. We also give an upper bound on the VC-dimension of the new classifier. Our experimental results on 23 standard problems show that quadratic boosting compares favorably with AdaBoost on large data sets at the cost of training speed. The classification time of the two algorithms, however, is equivalent.     

Stochastic linear control over a communication channel

We examine linear stochastic control systems when there is a communication channel connecting the sensor to the controller. The problem consists of designing the channel encoder and decoder as well as the controller to satisfy some given control objectives. In particular, we examine the role communication has on the classical linear quadratic Gaussian problem. We give conditions under which the classical separation property between estimation and control holds and the certainty equivalent control law is optimal. We then present the sequential rate distortion framework. We present bounds on the achievable performance and show the inherent tradeoffs between control and communication costs. In particular, we show that optimal quadratic cost decomposes into two terms: A full knowledge cost and a sequential rate distortion cost.     

Scale-space properties of quadratic feature detectors

We consider the scale-space properties of quadratic feature detectors and, in particular, investigate whether, like linear detectors, they permit a scale selection scheme with the “causality property”, which guarantees that features are never created as the scale is coarsened. We concentrate on the design of one dimensional detectors with two constituent filters, with the scale selection implemented as convolution and a scaling function. We consider two special cases of interest: the constituent filter pairs related by the Hilbert transform, and by the first spatial derivative. We show that, under reasonable assumptions, Hilbert-pair quadratic detectors cannot have the causality property. In the case of derivative-pair detectors, we describe a family of scaling functions related to fractional derivatives of the Gaussian that are necessary and sufficient for causality. In addition, we report experiments that show the effects of these properties in practice. We thus demonstrate that at least one class of quadratic feature detectors has the same desirable scaling property as the more familiar detectors based on linear filtering     

Support vector machine classification with noisy data: a second order cone programming approach

In this paper, we investigate the stability of linear and quadratic programming support vector machines (SVMs) with bounded noise in the input data using a robust optimisation model. For a linear discriminant function, this model is expressed as a second order cone optimisation problem. Using the concept of the kernel function, we generalise for nonlinear discriminant functions. Intuitively, it looks quite clear that large margin classifiers are robust in terms of bounded input noise. However, there is no theoretical analysis investigating this behaviour. We show that the SVM solution is stable under bounded perturbations of the data both in the linear programming and quadratic programming. Computational results are also presented for toy and real-world data.     

Solving equations via the trust region and its application to a class of stochastic linear complementarity problems

Equations with box constraints are applied in many fields, for example the complementarity problem. After studying the existing methods, we find that quadratic convergence of majority algorithms is based on the solvability of the equations. But whether the equations are solvable is previously unknown. So, it is necessary to design an algorithm which has fast quadratic convergence. The quadratic convergence does not depend on the solvability of the equations. In this paper, we propose a new method for solving equations. The global and local quadratic convergence of the proposed algorithm are established under some suitable assumptions. We apply the proposed algorithm to a class of stochastic linear complementarity problems. Numerical results show that our method is valid.     

Embedding adaptive JLQG into LQ martingale control with acompletely observable stochastic control matrix

With jump linear quadratic Gaussian (JLQG) control, one refers to the control under a quadratic performance criterion of a linear Gaussian system, the coefficients of which are completely observable, while they are jumping according to a finite-state Markov process. With adaptive JLQG, one refers to the more complicated situation that the finite-state process is only partially observable. Although many practically applicable results have been developed, JLQG and adaptive JLQG control are lagging behind those for linear quadratic Gaussian (LQG) and adaptive LQG. The aim of this paper is to help improve the situation by introducing an exact transformation which embeds adaptive JLQG control into LQM (linear quadratic Martingale) control with a completely observable stochastic control matrix. By LQM control, the authors mean the control of a martingale driven linear system under a quadratic performance criterion. With the LQM transformation, the adaptive JLQG control can be studied within the framework of robust or minimax control without the need for the usual approach of averaging or approximating the adaptive JLQG dynamics. To show the effectiveness of the authors' transformation, it is used to characterize the open-loop-optimal feedback (OLOF) policy for adaptive JLQG control     

Lagrangian duality between constrained estimation and control

We show that the Lagrangian dual of a constrained linear estimation problem is a particular nonlinear optimal control problem. The result has an elegant symmetry, which is revealed when the constrained estimation problem is expressed as an equivalent nonlinear optimisation problem. The results extend and enhance known connections between the linear quadratic regulator and linear quadratic state estimation problems.     

On the analysis and interpretation of inhomogeneous quadratic forms as receptive fields

In this letter, we introduce some mathematical and numerical tools to analyze and interpret inhomogeneous quadratic forms. The resulting characterization is in some aspects similar to that given by experimental studies of cortical cells, making it particularly suitable for application to second-order approximations and theoretical models of physiological receptive fields. We first discuss two ways of analyzing a quadratic form by visualizing the coefficients of its quadratic and linear term directly and by considering the eigenvectors of its quadratic term. We then present an algorithm to compute the optimal excitatory and inhibitory stimuli--those that maximize and minimize the considered quadratic form, respectively, given a fixed energy constraint. The analysis of the optimal stimuli is completed by considering their invariances, which are the transformations to which the quadratic form is most insensitive, and by introducing a test to determine which of these are statistically significant. Next we propose a way to measure the relative contribution of the quadratic and linear term to the total output of the quadratic form. Furthermore, we derive simpler versions of the above techniques in the special case of a quadratic form without linear term. In the final part of the letter, we show that for each quadratic form, it is possible to build an equivalent two-layer neural network, which is compatible with (but more general than) related networks used in some recent articles and with the energy model of complex cells. We show that the neural network is unique only up to an arbitrary orthogonal transformation of the excitatory and inhibitory subunits in the first layer.     

Robust dissipative control for linear systems with dissipative uncertainty and nonlinear perturbation

This paper focuses on the problem of dissipative control for linear systems which are subjected to dissipative uncertainty and matched nonlinear perturbation. Specifically, quadratic dissipative uncertainty is considered, which contains norm-bounded uncertainty, positive real uncertainty and uncertainty satisfying integral quadratic constraints (IQCs) as special cases. We develop a linear matrix inequality (LMI) approach for designing a robust nonlinear state feedback controller such that the closed-loop system is quadratic dissipative for all admissible uncertainties. Furthermore, under some condition on the dissipative uncertainty, we show that the controller also guarantees the asymptotic stability of the closed-loop system. As special cases, robust H_∞ control and robust passive control problems for systems with nonlinear perturbation and norm-bounded uncertainty (respectively, generalized positive real uncertainty) are solved using the LMI approach.     

Robust stability and stabilization of discrete-time non-linear systems: The LMI approach

The purpose of this paper is to convert the problem of robust stability of a discrete-time system under non-linear perturbation to a constrained convex optimization problem involving linear matrix inequalities (LMI). The nominal system is linear and time-invariant, while the perturbation is an uncertain non-linear time-varying function which satisfies a quadratic constraint. We show how the proposed LMI framework can be used to select a quadratic Lyapunov function which allows for the least restrictive non-linear constraints. When the nominal system is unstable the framework can be used to design a linear state feedback which stabilizes the system with the same maximal results regarding the class of non-linear perturbations. Of particular interest in this context is our ability to use the LMI formulation for stabilization of interconnected systems composed of linear subsystems with uncertain non-linear and time-varying coupling. By assuming stabilizability of the subsystems we can produce local control laws under decentralized information structure constraints dictated by the subsystems. Again, the stabilizing feedback laws produce a closed-loop system that is maximally robust with respect to the size of the uncertain interconnection terms.     

On the complexity of division and set joins in the relational algebra

We show that any expression of the relational division operator in the relational algebra with union, difference, projection, selection, constant-tagging, and joins, must produce intermediate results of quadratic size. To prove this result, we show a dichotomy theorem about intermediate sizes of relational algebra expressions (they are either all linear, or at least one is quadratic), and we link linear relational algebra expressions to expressions using only semijoins instead of joins.     

Stabilization of linear systems with limited information

We show that the coarsest, or least dense, quantizer that quadratically stabilizes a single input linear discrete time invariant system is logarithmic, and can be computed by solving a special linear quadratic regulator problem. We provide a closed form for the optimal logarithmic base exclusively in terms of the unstable eigenvalues of the system. We show how to design quantized state-feedback controllers, and quantized state estimators. This leads to the design of hybrid output feedback controllers. The theory is then extended to sampling and quantization of continuous time linear systems sampled at constant time intervals. We generalize the definition of density of quantization to the density of sampling and quantization in a natural way, and search for the coarsest sampling and quantization scheme that ensures stability. Finally, by relaxing the definition of quadratic stability, we show how to construct logarithmic quantizers with only finite number of quantization levels and still achieve practical stability of the closed-loop system     

Finite horizon quadratic optimal control and a separation principle for Markovian jump linear systems

In this note, we consider the finite-horizon quadratic optimal control problem of discrete-time Markovian jump linear systems driven by a wide sense white noise sequence. We assume that the output variable and the jump parameters are available to the controller. It is desired to design a dynamic Markovian jump controller such that the closed-loop system minimizes the quadratic functional cost of the system over a finite horizon period of time. As in the case with no jumps, we show that an optimal controller can be obtained from two coupled Riccati difference equations, one associated to the optimal control problem when the state variable is available, and the other one associated to the optimal filtering problem. This is a principle of separation for the finite horizon quadratic optimal control problem for discrete-time Markovian jump linear systems. When there is only one mode of operation our results coincide with the traditional separation principle for the linear quadratic Gaussian control of discrete-time linear systems.     

Diagonal Riccati stability and positive time-delay systems

We consider a class of algebraic Riccati equations arising in the study of positive linear time-delay systems. We show that this class admits diagonal positive definite solutions. This implies that exponentially stable positive linear time-delay systems possess Lyapunpov-Krasovskii functionals of a simple quadratic form. We also show that for this class of equations, the existence of positive-definite solutions is equivalent to a simple spectral condition on the coefficient matrices.     

Affine Controller Parameterization for Decentralized Control Over Banach Spaces

We cast the problem of optimal decentralized control as one of minimizing a closed-loop norm subject to a subspace constraint on the controller. In this note, we consider continuous linear operators on Banach spaces, and show that a simple property called quadratic invariance is necessary and sufficient for the constraint set to be preserved under feedback, and thus allows optimal synthesis to be recast as a convex optimization problem. These results hold for any norm and any Banach space.     

An efficient sequential linear quadratic algorithm for solving nonlinear optimal control problems

We develop a numerically efficient algorithm for computing controls for nonlinear systems that minimize a quadratic performance measure. We formulate the optimal control problem in discrete-time, but many continuous-time problems can be also solved after discretization. Our approach is similar to sequential quadratic programming for finite-dimensional optimization problems in that we solve the nonlinear optimal control problem using sequence of linear quadratic subproblems. Each subproblem is solved efficiently using the Riccati difference equation. We show that each iteration produces a descent direction for the performance measure, and that the sequence of controls converges to a solution that satisfies the well-known necessary conditions for the optimal control.     

A result on output feedback linear quadratic control

In this note we consider the static output feedback linear quadratic control problem. We present both necessary and sufficient conditions under which this problem has a solution in case the involved cost depends only on the output and control variables.This result is used to present both necessary and sufficient conditions under which the corresponding linear quadratic differential game has a Nash equilibrium in case the players use static output feedback control.Another consequence of this result is that the conditions also provide sufficient conditions for the static output stabilizability problem. Of course, in case these conditions are not met this does not mean that the system is not stabilizable via static output feedback.     

An optimal control approach to robust tracking of linear systems

In our early work, we show that one way to solve a robust control problem of an uncertain system is to translate the robust control problem into an optimal control problem. If the system is linear, then the optimal control problem becomes a linear quadratic regulator (LQR) problem, which can be solved by solving an algebraic Riccati equation. In this article, we extend the optimal control approach to robust tracking of linear systems. We assume that the control objective is not simply to drive the state to zero but rather to track a non-zero reference signal. We assume that the reference signal to be tracked is a polynomial function of time. We first investigated the tracking problem under the conditions that all state variables are available for feedback and show that the robust tracking problem can be solved by solving an algebraic Riccati equation. Because the state feedback is not always available in practice, we also investigated the output feedback. We show that if we place the poles of the observer sufficiently left of the imaginary axis, the robust tracking problem can be solved. As in the case of the state feedback, the observer and feedback can be obtained by solving two algebraic Riccati equations.