Further results on the L1 analysis of sampled-data systems via kernel approximation approach

This paper gives two methods for the L₁ analysis of sampled-data systems, by which we mean computing the L_∞-induced norm of sampled-data systems. This is achieved by developing what we call the kernel approximation approach in the setting of sampled-data systems. We first consider the lifting treatment of sampled-data systems and give an operator theoretic representation of their input/output relation. We further apply the fast-lifting technique by which the sampling interval [0, h) is divided into M subintervals with an equal width, and provide methods for computing the L_∞-induced norm. In contrast to a similar approach developed earlier called the input approximation approach, we use an idea of kernel approximation, in which the kernel function of an input operator and the hold function of an output operator are approximated by piecewise constant or piecewise linear functions. Furthermore, it is shown that the approximation errors in the piecewise constant approximation or piecewise linear approximation scheme converge to 0 at the rate of 1/M or 1/M², respectively. In comparison with the existing input approximation approach, in which the input function (rather than the kernel function) of the input operator is approximated by piecewise constant or piecewise linear functions, we show that the kernel approximation approach gives improved computation results. More precisely, even though the convergence rates in the kernel approximation approach remain qualitatively the same as those in the input approximation approach, the newly developed former approach could lead to quantitatively improved approximation errors than the latter approach particularly when the piecewise linear approximation scheme is taken. Finally, a numerical example is given to demonstrate the effectiveness of the kernel approximation approach with this scheme.     

Adaptive fuzzy switched control design for uncertain nonholonomic systems with input nonsmooth constraint

In this paper, a fuzzy adaptive switched control approach is proposed for a class of uncertain nonholonomic chained systems with input nonsmooth constraint. In the control design, an auxiliary dynamic system is designed to address the input nonsmooth constraint, and an adaptive switched control strategy is constructed to overcome the uncontrollability problem associated with x₀(t₀) = 0. By using fuzzy logic systems to tackle unknown nonlinear functions, a fuzzy adaptive control approach is explored based on the adaptive backstepping technique. By constructing the combination approximation technique and using Young's inequality scaling technique, the number of the online learning parameters is reduced to n and the ‘explosion of complexity’ problem is avoid. It is proved that the proposed method can guarantee that all variables of the closed-loop system converge to a small neighbourhood of zero. Two simulation examples are provided to illustrate the effectiveness of the proposed control approach.     

Polynomial approximation of functions of matrices and applications

In solving a mathematical problem numerically, we frequently need to operate on a vector by an operator that can be expressed asf(A), whereA is anN ×N matrix [e.g., exp(A), sin(A), A^–-]. Except for very simple matrices, it is impractical to construct the matrixf (A) explicitly. Usually an approximation to it is used. This paper develops an algorithm based upon a polynomial approximation tof (A). First the problem is reduced to a problem of approximatingf (z) by a polynomial in z, where z belongs to a domainD in the complex plane that includes all the eigenvalues ofA. This approximation problem is treated by interpolatingf (z) in a certain set of points that is known to have some maximal properties. The approximation thus achieved is almost best. Implementing the algorithm to some practical problems is described. Since a solution to a linear systemAx=b isx=A ^–1 b, an iterative solution algorithm can be based upon a polynomial approximation tof (A)=A ^–1. We give special attention to this important problem.     

Improved stability and H∞ performance criteria for linear systems with interval time-varying delays via three terms approximation

This paper investigates the problem of delay dependent stability and H_∞ performance for a class of linear systems with interval time-varying delay. A new model transformation is first proposed by employing a three-terms approximation of delayed state variables, for a better approximation of delayed state. By using scaled small gain theorem and a simple Lyapunov–Krasovskii functional, new stability and H_∞ performance criteria are proposed in terms of linear matrix inequalities, which can be easily solved by using standard numerical packages. Finally, numerical examples are presented to illustrate the effectiveness of the proposed method.     

Approximation of functions by perceptrons: a new approach

We provide a constructive proof of the theorem of function approximation by perceptrons (cf Leshno et al. [1], Hornik [2]) when the activation function ψ isC∞ with all its derivatives non 0 at 0. We deal with uniform approximation on compact sets of continuous functions on ℜ ^d ,d≥1. This approach is elementary and provides some approximation results for the derivatives along with some bounds for the hidden layer.     

Modified fast-sample/fast-hold approximation and γ-independent H ∞-discretisation for general sampled-data systems by fast-lifting

This article is concerned with the fast-lifting approach to H _∞ analysis and design of sampled-data systems, and extends our preceding study on modified fast-sample/fast-hold (FSFH) approximation, in which the direct feedthrough matrix D ₁₁ from the disturbance w to the controlled output z was assumed to be zero. More precisely, this article removes this assumption and shows that a γ-independent H _∞ discretisation is still possible in a nontrivial fashion by applying what we call quasi-finite-rank approximation of an infinite-rank operator and then the loop-shifting technique. As in the case of D ₁₁ = 0, the modified FSFH approach retains the feature that both the upper and lower bounds of the H _∞-norm or the frequency response gain can be computed, where the gap between the upper and lower bounds can be bounded with the approximation parameter N and is independent of the discrete-time controller. This feature is significant in applying the new method especially to control system design, and this study indeed has a very close relationship to the recent progress in the study of control system analysis/design via noncausal linear periodically time-varying scaling. The significance of a key lemma pertinent to the fast-lifting approach is suggested in connection with such a relationship, and also with its application to time-delay systems.     

Input–output method to fault detection for discrete-time fuzzy networked systems with time-varying delay and multiple packet losses

The fault detection (FD) problem for discrete-time fuzzy networked systems with time-varying delay and multiple packet losses is investigated in this paper. The communication links between the plant and the FD filter (FDF) are assumed to be imperfect, and the missing probability is governed by an individual random variable satisfying a certain probabilistic distribution over the interval [0 1]. The discrete-time delayed fuzzy networked system is first transformed into the form of interconnect ion of two subsystems by applying an input–output method and a two-term approximation approach, which are employed to approximate the time-varying delay. Our attention is focused on the design of fuzzy FDF (FFDF) such that, for all data missing conditions, the overall FD dynamics are input–output stable in mean square and preserves a guaranteed performance. Sufficient conditions are first established via H_∞ performance analysis for the existence of the desired FFDF; meanwhile, the corresponding solvability conditions for the desired FFDF gains are characterised in terms of the feasibility of a convex optimisation problem. Moreover, we show that the obtained criteria based on the input–output approach can also be established by applying the direct Lyapunov method to the original time-delay systems. Finally, simulation examples are provided to demonstrate the effectiveness of the proposed approaches.     

An approximation algorithm for minimum-cost vertex-connectivity problems

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuer _ij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer _ij vertex-disjoint paths between verticesi andj must be found. In the case for whichr _ij ∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr _ij =k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where . No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems. This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while the author was visiting MIT. This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while the author was a graduate student at MIT and in part while a postdoc at Cornell.     

Fixed‐Structure ℋ∞ Controller Design for Systems with Polytopic Uncertainty: An LMI Solution

This note provides a new method for fixed‐structure H_∞ controller design for discrete‐time single input single output (SISO) systems with polytopic uncertainty. New conditions are derived based on the concept of robust strict positive realness (SPRness) of an uncertain polynomial with respect to a parameter‐dependent polynomial. The quality of this approximation depends on this SPR‐maker. A procedure is proposed for choosing the parameter‐dependent SPR‐maker that guarantees the improvement of the performance for the designed controller in comparison with the traditional approaches employed fixed SPR‐makers. The proposed conditions are given in terms of solutions to a set of linear matrix inequalities. The effectiveness of the proposed approach is demonstrated by comparing with the existing results.     

Structured H∞‐control of infinite‐dimensional systems

We develop a novel frequency‐based H_∞‐control method for a large class of infinite‐dimensional linear time‐invariant systems in transfer function form. A major benefit of our approach is that reduction or identification techniques are not needed, which avoids typical distortions. Our method allows to exploit both state‐space or transfer function models and input/output frequency response data when only such are available. We aim for the design of practically useful H_∞‐controllers of any convenient structure and size. We use a nonsmooth trust‐region bundle method to compute arbitrarily structured locally optimal H_∞‐controllers for a frequency‐sampled approximation of the underlying infinite‐dimensional H_∞‐problem in such a way that (i) exponential stability in closed loop is guaranteed and that (ii) the optimal H_∞‐value of the approximation differs from the true infinite‐dimensional value only by a prior user‐specified tolerance. We demonstrate the versatility and practicality of our method on a variety of infinite‐dimensional H_∞‐synthesis problems, including distributed and boundary control of partial differential equations, control of dead‐time and delay systems, and using a rich testing set.     

Finite Computation of the ℓ1 Estimator from Huber’s M-Estimator in Linear Regression

We review and extend previous work on the approximation of the linear ₁ estimator by the Huber M-estimator based on the algorithms proposed by Clark and Osborne [7], and Madsen and Nielsen [12]. Although the Madsen-Nielsen algorithm is a promising one, it is guaranteed to terminate finitely under certain assumptions. We describe a variant of the Madsen-Nielsen algorithm to compute the ₁ estimator from the Huber M-estimator in a finite number of steps without any restrictive steps nor assumptions. Summary computational results are given.     

An iterative algorithm for a least squares solution of a matrix equation

In this article, we propose an iterative algorithm to compute the minimum norm least-squares solution of AXB+CYD=E, based on a matrix form of the algorithm LSQR for solving the least squares problem. We then apply this algorithm to compute the minimum norm least-squares centrosymmetric solution of min _X ‖AXB?E‖ _F . Numerical results are provided to verify the efficiency of the proposed method.     

All-to-All Optical Routing in Chordal Rings of Degree 4

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I _A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I _A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I _A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks. Received July 22, 1998; revised October 14, 1999.     

Two-level stabilized finite element method for the transient Navier–Stokes equations

In this article, a two-level stabilized finite element method based on two local Gauss integrations for the two-dimensional transient Navier–Stokes equations is analysed. This new stabilized method presents attractive features such as being parameter-free, or being defined for nonedge-based data structures. Some new a priori bounds for the stabilized finite element solution are derived. The two-level stabilized method involves solving one small Navier–Stokes problem on a coarse mesh with mesh size 0<H<1, and a large linear Stokes problem on a fine mesh with mesh size 0<h?H. A H ¹-optimal velocity approximation and a L ²-optimal pressure approximation are obtained. If we choose h=O(H ²), the two-level method gives the same order of approximation as the standard stabilized finite element method.     

H∞ model reduction for negative imaginary systems

This paper is concerned with the H_∞ model reduction for negative imaginary (NI) systems. For a given linear time-invariant system that is stable and NI, our goal is to find a stable reduced-order NI system satisfying a pre-specified H_∞ approximation error bound. Sufficient conditions in terms of matrix inequalities are derived for the existence and construction of an H_∞ reduced-order NI system. Iterative algorithms are provided to solve the matrix inequalities and to minimise the H_∞ approximation error. Finally, a numerical example is used to demonstrate the effectiveness of the proposed model reduction method.     

Robust mixed H2/H∞ delayed state feedback control of uncertain neutral systems with time‐varying delays

This paper considers the problem of robust mixed H₂/H_∞ delayed state feedback control for a class of uncertain neutral systems with time‐varying discrete and distributed delays. Based on the Lyapunov–Krasovskii functional theory, new required sufficient conditions are established in terms of delay‐range‐dependent linear matrix inequalities for the stability and stabilization of the considered system using some free matrices. The desired robust mixed H₂/H_∞ delayed state feedback control is derived based on a convex optimization method such that the resulting closed‐loop system is asymptotically stable and satisfies H₂ performance with a guaranteed cost and a prescribed level of H_∞ performance, simultaneously. Finally, a numerical example is given to illustrate the effectiveness of our approach. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

H∞ model reduction for discrete-time singular systems

This paper investigates the problem of H_∞ model reduction for linear discrete-time singular systems. Without decomposing the original system matrices, necessary and sufficient conditions for the solvability of this problem are obtained in terms of linear matrix inequalities (LMIs) and a coupling non-convex rank constraint set. When these conditions are feasible, an explicit parametrization of the desired reduced-order models is given. Particularly, a simple LMI condition without rank constraint is derived for the zeroth-order H_∞ approximation problem. Finally, an illustrative example is provided to demonstrate the applicability of the proposed approach.     

A Fourth Order Hermitian Box-Scheme with Fast Solver for the Poisson Problem in a Square

A new fourth order box-scheme for the Poisson problem in a square with Dirichlet boundary conditions is introduced, extending the approach in Croisille (Computing 78:329–353, 2006). The design is based on a “hermitian box” approach, combining the approximation of the gradient by the fourth order hermitian derivative, with a conservative discrete formulation on boxes of length 2h. The goal is twofold: first to show that fourth order accuracy is obtained both for the unknown and the gradient; second, to describe a fast direct algorithm, based on the Sherman-Morrison formula and the Fast Sine Transform. Several numerical results in a square are given, indicating an asymptotic O(N ²log ₂(N)) computing complexity.     

One for the Price of Two: a Unified Approach for Approximating Covering Problems

We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Forest, and related problems. The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar (at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e., approximation cost) ≤ twice the optimum cost. Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems and others. We further extend the Bafna et al. extension of the Local-Ratio theorem. Our extension eventually yields a short generic r -approximation algorithm which can generate most known approximation algorithms for most covering problems. Another extension of the Local-Ratio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover gives an expected performance ratio ≤ 2 . Received September 17, 1997; revised March 5, 1998.