Pole placement by performance criterion modification

A procedure is presented that modifies the state weighting matrix Q and introduces a degree of relative stability into the original performance criterion to shape the resulting optimal dynamics by positioning the closed-loop eigenvalues along the real axis of the optimal system in the linear-quadratic regulator problem. It is based on the results of the algebraic Riccati equation (ARE) which establish the invariance of certain eigenspaces of the associated Hamiltonian matrix with respect to certain perturbations of Q and the degree of relative stability     

Direct state-space solution to the discrete-timeH∞ one-block problem

A general state-space representation is used to allow a complete formulation of the H_∞ optimization problem without any invertibility condition on the system matrix, unlike existing solutions. A straightforward approach is used to solve the one-block H_∞ optimization problem. The parameterization of all solutions to the discrete-time H_∞ suboptimal one-block problem is first given in transfer function form in terms of a set of functions in H _∞ that satisfy a norm bound. The parameterization of all solutions is also given as a linear fractional representation     

A parametrization of stabilizing controllers for multiratesampled-data systems

All linear multirate controllers for a given multirate sampled-data system plant are parameterized in terms of a single parameter Q(z) that is allowed to be any stable transfer matrix provided that certain causality conditions are met. The result parallels a well-known parameterization result for single-rate sampled-data plants. The parameterization suggests architectures for multirate controllers     

Simultaneous stabilization of single-input single-output discretetime systems

The problem of finding one compensator which simultaneously stabilizes a family of single-input-single-output (SISO) discrete-time plants is considered. The family of plants is described by the transfer functions {Pz, q): q∈Q}, which are generated via a z-transformation. A number of assumptions describing the set of allowable plants are then given. These assumptions include some regularity conditions on the plants and a minimum-phase requirement. The satisfaction of these assumptions guarantees the existence of a strictly proper stable compensator C(z) for simultaneous stabilization. An iterative computation method is provided for control design     

A new realization theory

A realization theory that is based on the Kalman system theory and motivated by the Fuhrmann realization theory is presented. In the Fuhrmann realization theory, the realization state-space is defined by a natural polynomial module K_Q, which is related to a nonsingular polynomial matrix Q. The module K_Q is formed of all f where Q^-1f is strictly proper. In the realization theory proposed, the realization state-space is defined by a different module M_Q, which is formed of properly truncated, strictly proper formal power series of Q^-1f. The realization theory can be used to prove the dual-realization scheme induced by the Fuhrmann realization theory     

A VLSI constant geometry architecture for the fast Hartley andFourier transforms

An application-specific architecture for the parallel calculation of the decimation in time and radix 2 fast Hartley (FHT) and Fourier (FFT) transforms is presented. A real sequence with N=2ⁿ data items is considered as input. The system calculates the FHT and the FFT in n and n+1 stages. respectively. The modular and regular parallel architecture is based on a constant geometry algorithm using butterflies of four data items and the perfect unshuffle permutation. With this permutation, the mapping of the algorithm in VLSI technology is simplified and the communications among processors are minimized. Organization of the processor memory based on first-in, first-out (FIFO) queues facilitates a systolic data flow and permits the implementation in a direct way of the complex data movements and address sequences of the transforms. This is accomplished by means of simple multiplexing operations, using hardwired control. The total calculation time is (Nlog₂N)/4Q cycles for the FHT and N(1+log₂N)/4Q cycles for the FFT, where Q is the number of processors ( Q= 2^q, Q⩽N/4)     

On the convexity of H∞ Riccati solutionsand its applications

The authors consider the two-Riccati-equation solution to a standard H^∞ control problem, which can be used to characterize all possible stabilizing optimal or suboptimal H^∞ controllers if the optimal H^∞ norm (or γ), an upper bound of a suboptimal H^∞ norm is given. Some eigen properties of these H^∞ Riccati solutions are revealed. The most prominent one is that the spectral radius of the product of these two Riccati solutions is a continuous, nonincreasing, convex function of γ on the domain of interest. Based on these properties, a quadratically convergent algorithm is developed to compute the optimal H^∞ norm     

Decomposition of 2-D linear systems into 1-D systems in thefrequency domain

A method is presented for the decomposition of the frequency domain of 2-D linear systems into two equivalent 1-D systems having dynamics in different directions and connected by a feedback system. It is shown that under some assumptions the decomposition problem can be reduced to finding a realizable solution to the matrix polynomial equation X(z₁)P(z₂ )+Q(z₁)Y(z₂ )=D(z₁, z₂). A procedure for finding a realizable solution X(z₁ ), Y(z₂) to the equation is given     

Minimization of the L∞-induced norm forsampled-data systems

It is shown that given any degree of accuracy, there exists a standard discrete-time l¹ problem that can be determined a priori whose solution yields a controller that is almost optimal in terms of the hybrid L^∞-induced norm. This is accomplished by first converting the hybrid system into an equivalent infinite-dimensional discrete-time system using the lifting technique in continuous time, and then approximating the infinite-dimensional parts of the system which model the intersample dynamics. A thorough analysis of the approximation procedure is presented, and it is shown that it is convergent at the rate of 1/n . Explicit bounds that are independent of the controller are obtained to characterize the approximation. It is also shown that the geometry of the induced norm for the sampled-data problem is different from that of the standard l¹ norm, and hence there might not exist a linear isometry that maps the sampled-data problem exactly to a standard discrete-time problem     

Making reuse cost-effective

Until reuse is better understood, significant reductions in the cost of building large systems will not be possible. This assertion is based primarily on the belief that the defining characteristic of good reuse is not the reuse of software per se, but the reuse of human problem solving. Analytical approaches for making good reuse investments are suggested in terms of increasing a quality-of-investment measure, Q, which is simply the ratio of reuse benefits to reuse investments. The first strategy for increasing Q is to increase the level of consumer reuse. The second technique for increasing Q is to reduce the average cost of reusing work products by making them easy and inexpensive to reuse. The third strategy is to reduce investment costs. Reuse strategies, and reuse and parameterizations, are discussed     

Trace bounds on the covariances of continuous-time systems withmultiplicative noise

Matrix equations such as AP+PA^T+FPF^T+Ω=0 and AQ+QA^T+-QVQ+FPF^T +Ω=0, which arise in the estimation problem of systems with both additive and multiplicative noise, are treated. Trace bounds on the steady-state and error covariances P and Q are established, under complete and incomplete noise information. An example illustrates the usefulness of these bounds in determining the size of the estimation error     

A Schur method for balanced-truncation model reduction

It is shown that a not-necessarily-balanced state-space realization of the Moore reduced model can be computed directly without balancing via projections defined in terms of arbitrary bases for the left and right eigenspaces associated with the large eigenvalues of the product PQ of the reachability and controllability Grammians. Two specific methods for computing these bases are proposed, one based on the ordered Schur decomposition of PQ and the other based on the Cholesky factors of P and Q. The algorithms perform reliably even for nonminimal models     

A linear programming approach for the weighted graph matchingproblem

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods     

Simultaneous controller design for linear time-invariant systems

The use of generalized sampled-data hold functions (GSHF) in the problem of simultaneous controller design for linear time-invariant plants is discussed. This problem can be stated as follows: given plants P₁, P₂, . . ., P_N , find a controller C which achieves not only simultaneous stability, but also simultaneous optimal performance in the N given systems. By this, it is meant that C must optimize an overall cost function reflecting the closed-loop performance of each plant when it is regulated by C. The problem is solved in three aspects: simultaneous stabilization, simultaneous optimal quadratic performance, and simultaneous pole assignment in combination with simultaneous intersampling performance     

Model reduction via balanced realizations: an extension andfrequency weighting techniques

Two model-reduction methods for discrete systems related to balanced realizations are described. The first is a technique which utilizes the least controllable and observable subsystem in deriving a balanced discrete reduced-order model. For this technique as L ^∞ norm bound on the reduction error is given. The second method is a frequency-weighting technique for discrete- and continuous-time systems where the input-normal or output-normal realizations are modified to include a simple frequency weighting. For this technique, L^∞ norm bounds on the weighted reduction errors are obtained     

Mixed H2/H∞ control:a convex optimization approach

The problem of finding an internally stabilizing controller that minimizes a mixed H₂/H_∞ performance measure subject to an inequality constraint on the H_∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H₂/H_∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n×n and n ×q, where n and q are, respectively, the state and input dimensions) real matrices. Using the central H_∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant     

Optimal dynamic scheduling in Jackson networks

A Jackson-like network that supports J types of interactive traffic (e.g., interactive messages) as well as I types of noninteractive traffic (e.g., file transfers, facsimile) is considered. The service-time distributions and the internal routing are homogeneous for all traffic types but can be node (queue) dependent. The problem is to find a scheduling control that minimizes a weighted sum of the average end-to-end delay for the interactive types and at the same time ensures that the average end-to-end delays for the interactive types will be below given design constraints. Conservation laws are first established and shown to yield the base of a polymatroid. The optimal control problem is then transformed into a linear program with the feasible region being the polymatroid base truncated by delay constraints. An optimal control is identified that partitions the traffic types into I+r (0⩽r⩽J) ordered groups and applies a strict priority rule among the groups. An algorithm is developed that does the grouping and solves the optimization problem. A decentralized implementation of the optimal control is also discussed     

A novel discrete relaxation architecture

The discrete relaxation algorithm (DRA) is a computational technique that enforces arc consistency (AC) in a constraint satisfaction problem (CSP). The original sequential AC-1 algorithm suffers from O(n³m³) time complexity, and even the optimal sequential AC-4 algorithm is O (n²m²) for an n-object and m-label DRA problem. Sample problem runs show that these algorithms are all too slow to meet the need for any useful, real-time CSP applications. A parallel DRA5 algorithm that reaches a lower bound of O(nm) (where the number of processors is polynomial in the problem size) is given. A fine-grained, massively parallel hardware computer architecture has been designed for the DRA5 algorithm. For practical problems, many orders of magnitude of efficiency improvement can be reached on such a hardware architecture     

The minimal dimension of stable faces required to guaranteestability of a matrix polytope: D-stability

The problem of determining whether a polytope P of n ×n matrices is D-stable-i.e. whether each point in P has all its eigenvalues in a given nonempty, open, convex, conjugate-symmetric subset D of the complex plane-is discussed. An approach which checks the D-stability of certain faces of P is used. In particular, for each D and n the smallest integer m such that D-stability of every m-dimensional face guarantees D-stability of P is determined. It is shown that, without further information describing the particular structure of a polytope, either (2n-4)-dimensional or (2n-2)-dimensional faces need to be checked for D-stability, depending on the structure of D. Thus more work needs to be done before a computationally tractable algorithm for checking D-stability can be devised