Improved deterministic algorithms for weighted matching and packing problems

Based on the method of (n,k)-universal sets, we present a deterministic parameterized algorithm for the weighted rd-matching problem with time complexity O^∗(4^{(r−1)k+o(k)}), improving the previous best upper bound O^∗(4^rk+o(k)). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O^∗(16^k+o(k)), improving the previous best result O^∗(21.26^k). For the weighted r-set packing problem, we present a deterministic parameterized algorithm with time complexity O^∗(2^{(2r−1)k+o(k)}), improving the previous best result O^∗(2^2rk+o(k)). The algorithm, when applied to the unweighted 3-set packing problem, has running time O^∗(32^k+o(k)), improving the previous best result O^∗(43.62^k+o(k)). Moreover, for the weighted r-set packing and weighted rd-matching problems, we give a kernel of size O(k^r), which is the first kernelization algorithm for the problems on weighted versions.     

Modelling series of studies with a common structure

Consider the situation where the Structuration des Tableaux à Trois Indices de la Statistique (STATIS) methodology is applied to a series of studies, each study being represented by data and weight matrices. Relations between studies may be captured by the Hilbert-Schmidt product of these matrices. Specifically, the eigenvalues and eigenvectors of the Hilbert-Schmidt matrix S may be used to obtain a geometrical representation of the studies. The studies in a series may further be considered to have a common structure whenever their corresponding points lie along the first axis. The matrix S can be expressed as the sum of a rank 1 matrix λuu^T with an error matrix E. Therefore, the components of the vector are sufficient to locate the points associated to the studies. Former models for S where vec(E) are mathematically tractable and yet do not take into account the symmetry of the matrix S. Thus a new symmetric model is proposed as well as the corresponding tests for a common structure. It is further shown how to assess the goodness of fit of such models. An application to the human immunodeficiency virus (HIV) infection is used for assessing the proposed model.     

Hierarchical trajectory refinement for a class of nonlinear systems

Trajectory generation for nonlinear control systems is an important and difficult problem. In this paper, we provide a constructive method for hierarchical trajectory refinement. The approach is based on the recent notion of φ-related control systems. Given a control affine system satisfying certain assumptions, we construct a φ-related control system of smaller dimension. Trajectories designed for the smaller, abstracted system are guaranteed, by construction, to be feasible for the original system. Constructive procedures are provided for refining trajectories from the coarser to the more detailed system.     

Dissipative analysis and control of state-space symmetric systems

The paper addresses the problem of analysis and static output feedback control synthesis for strict quadratic dissipativity of linear time-invariant systems with state-space symmetry. As a particular case of dissipative systems, we consider the mixed H_∞ and positive real performance criterion and we develop an explicit expression for calculating the H_∞ norm of these systems. Subsequently, an explicit parametrization of the static output feedback control gains that solve the mixed H_∞ and positive real performance problem is obtained. Numerical examples demonstrate the use and computational advantages of the proposed explicit solutions.     

Filter design for LPV systems using quadratically parameter-dependent Lyapunov functions

This paper considers design problems of robust gain-scheduled H_∞ and H₂ filters for linear parameter-varying (LPV) systems whose state-space matrices are represented as parametrically affine matrices, using quadratically parameter-dependent Lyapunov functions, and proposes methods of filter design via parametrically affine linear matrix inequalities (LMIs). For robust filters, our design methods theoretically encompass those that use constant Lyapunov functions. Several numerical examples are included that demonstrate the effectiveness of gain-scheduled and robust filters using our proposed methods compared with robust filters using existing methods.     

Optimal control of a deterministic multiclass queuing system for which several queues can be served simultaneously

We consider the optimal control problem of emptying a deterministic single server multiclass queuing system without arrivals. We assume that the server is able to serve several queues simultaneously, each at its own rate, independent of the number of queues being served.We show that the optimal sequence of modes is ordered by the rate of cost decrease. However, queues are not necessarily emptied. We propose a dynamic programming approach for solving the problem, which reduces the multi-parametric QP (mpQP) to a series of problems that can be solved readily.     

Verification of reactive systems via instantiation of Parameterised Boolean Equation Systems

Verification problems for finite- and infinite-state processes, like model checking and equivalence checking, can effectively be encoded in Parameterised Boolean Equation Systems (PBESs). Solving the PBES then solves the encoded problem. The decidability of solving a PBES depends on the data sorts that occur in the PBES. We describe a pragmatic methodology for solving PBESs, viz., by attempting to instantiate them to the sub-fragment of Boolean Equation Systems (BESs). Unlike solving PBESs, solving BESs is a decidable problem. Based on instantiation, verification using PBESs can effectively be done fully automatically in most practical cases. We demonstrate this by solving several complex verification problems using a prototype implementation of our instantiation technique. In addition, practical issues concerning this implementation are addressed. Furthermore, we illustrate the effectiveness of instantiation as a transformation on PBESs when solving verification problems involving systems of infinite size.     

Design of linear time-invariant controllers for multirate systems

In this paper we discuss a frequency domain approach to model multirate single-input single-output (SISO) systems which facilitates design of linear time-invariant (LTI) controllers operating at the fast rate. To illustrate the approach we consider a dual-rate system with slow output measurements and fast control actions. We obtain necessary and sufficient conditions for the existence of stabilizing linear time-invariant (LTI) controllers for which model matching is also achieved at the fast rate with a desired single-rate system. Moreover, a solution to the problem of parameterizing the set of such LTI controllers is also given.     

A model reference approach to safe controller changes in iterative identification and control

A controller change from a current controller which stabilises the plant to a new controller, designed on the basis of an approximate model of the plant and with guaranteed bounds on the stability properties of the true closed loop, is called a safe controller change. In this paper, we present a model reference approach to the determination of safe controller changes on the basis of approximate closed loop models of the plant and robust stability results in the ν-gap.     

Guaranteed robustness bounds for matched-disturbance nonlinear systems

This paper considers input affine nonlinear systems with matched disturbances and shows how to compute an a priori upper bound of the H_∞ attenuation level achieved by the optimal L₂ controller and the suboptimal H_∞ central controller. The case where the disturbance contains a constant term is also discussed. These bounds are shown to depend only on the function mapping the control input to the performance variable. This result is used to derive a robust control design for a special, but practically important, class of non-input affine nonlinear systems consisting of the series connection of a nonlinear state and input dependent map and of a nonlinear input affine dynamical system. Approximate inversion of the nonlinear static map leads to a robust control problem which fits into the framework. The effectiveness of the theoretical results is shown by its use for the robust control design of a diesel engine test bench.     

Exponential stability of singular systems with multiple time-varying delays

This paper deals with the class of continuous-time singular linear systems with multiple time-varying delays in a range. The global exponential stability problem of this class of systems is addressed. Delay-range-dependent sufficient conditions such that the system is regular, impulse-free and α-stable are developed in the linear matrix inequality (LMI) setting. Moreover, an estimate of the convergence rate of such stable systems is presented. A numerical example is employed to show the usefulness of the proposed results.     

New bounded real lemma for discrete-time singular systems

In this paper, the problem of bounded real lemma for discrete-time singular system with strict matrix inequalities is investigated. It is proved that the bounded real lemma for discrete singular system can be described by a strict matrix inequality. The results lead to more tractable and reliable computation when applying them to design control systems.     

Stability properties of reset systems

Stability properties for a class of reset systems, such as systems containing a Clegg integrator, are investigated. We present Lyapunov based results for verifying L₂ and exponential stability of reset systems. Our results generalize the available results in the literature and can be easily modified to cover L_p stability for arbitrary p∈[1,∞]. Several examples illustrate that introducing resets in a linear system may reduce the L₂ gain if the reset controller parameters are carefully tuned.     

Application of a fault detection filter to structural health monitoring

A model-based fault detection filter is developed for structural health monitoring of a simply supported beam. The structural damage represented in the plant model is shown to decompose into a known fault direction vector maintaining a fixed direction, dependent on the damage location, and an arbitrary fault magnitude representing the extent of the damage. According to detection filter theory, if damage occurs, under certain circumstances the fault will be uniquely detected and identified through an associated invariance in the direction imposed on the fault detection filter residuals. The spectral algorithm used to design the detection filter is based on a left eigenstructure assignment approach which accommodates system sensitivities that are revealed as ill-conditioned matrices formed from the eigenvectors in the construction of the detection filter gains. The detection filter is applied to data from an aluminum simply supported beam with four piezoelectric sensors and one piezoelectric actuator. By exciting the structure at the first natural frequency, damage in the form of a 5 mm saw cut made to one side of the beam is detected and localized.     

Simultaneous stabilization of a set of nonlinear port-controlled Hamiltonian systems

This paper investigates simultaneous stabilization of a set of nonlinear port-controlled Hamiltonian (PCH) systems and proposes a number of results on the design of simultaneous stabilization controllers for the PCH systems. Firstly, the case of two PCH systems is studied. Using the dissipative Hamiltonian structural properties, the two systems are combined to generate an augmented PCH system, with which some results on the control design are then obtained. For the case that there exist parametric uncertainties in the two systems’ Hamiltonian structures, an adaptive simultaneous stabilization controller is proposed. When there are external disturbances and parametric uncertainties in the two systems, two simultaneous stabilization controllers are designed for the systems: one is a robust controller and the other is a robust adaptive one. Secondly, the case of more than two PCH systems is investigated, and a new result is proposed for the simultaneous stabilization of the systems. Finally, two illustrative examples are studied by using the results proposed in this paper. Simulations show that the simultaneous stabilization controllers obtained in this paper work very well.     

Gain-scheduling control of LFT systems using parameter-dependent Lyapunov functions

In this paper, we propose a new control design approach for linear fractional transformation (LFT) systems using parameter-dependent Lyapunov functions. Instead of assuming parameter dependency in LFT fashion, we consider general parameter-dependent controllers to achieve better closed-loop performance. Using full-block multipliers, new LPV synthesis conditions have been derived in terms of finite number of linear matrix inequalities (LMIs). Both continuous- and discrete-time cases are discussed. A ship steering example has been used to demonstrate advantages and benefits of the proposed approach.     

Simultaneous LQ control of a set of LTI systems using constrained generalized sampled-data hold functions

In this paper, sampled-data control of a set of continuous-time LTI systems is considered. It is assumed that a predefined guaranteed continuous-time quadratic cost function, which is, in fact, the sum of the performance indices for all systems, is given. The main objective here is to design a decentralized periodic output feedback controller with a prespecified form, e.g., polynomial, piecewise constant, exponential, etc., which minimizes the above mentioned guaranteed cost function. This problem is first formulated as a set of matrix inequalities, and then by using a well-known technique, it is reformulated as a LMI problem. The set of linear matrix inequalities obtained provides necessary and sufficient conditions for the existence of a decentralized optimal simultaneous stabilizing controller with the prespecified form (rather than a general form). Moreover, an algorithm is presented to solve the resultant LMI problem. Finally, the efficiency of the proposed method is demonstrated in two numerical examples.     

On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.     

Approximate dynamic programming-based approaches for input-output data-driven control of nonlinear processes

We propose two approximate dynamic programming (ADP)-based strategies for control of nonlinear processes using input-output data. In the first strategy, which we term ‘J-learning,’ one builds an empirical nonlinear model using closed-loop test data and performs dynamic programming with it to derive an improved control policy. In the second strategy, called ‘Q-learning,’ one tries to learn an improved control policy in a model-less manner. Compared to the conventional model predictive control approach, the new approach offers some practical advantages in using nonlinear empirical models for process control. Besides the potential reduction in the on-line computational burden, it offers a convenient way to control the degree of model extrapolation in the calculation of optimal control moves. One major difficulty associated with using an empirical model within the multi-step predictive control setting is that the model can be excessively extrapolated into regions of the state space where identification data were scarce or nonexistent, leading to performances far worse than predicted by the model. Within the proposed ADP-based strategies, this problem is handled by imposing a penalty term designed on the basis of local data distribution. A CSTR example is provided to illustrate the proposed approaches.     

A distributed controller approach for delay-independent stability of networked control systems

This article introduces a novel distributed controller approach for networked control systems (NCS) to achieve finite gain L₂ stability independent of constant time delay. The proposed approach represents a generalization of the well-known scattering transformation which applies for passive systems only. The main results of this article are (a) a sufficient stability condition for general multi-input-multi-output (MIMO) input-feedforward-output-feedback-passive (IF-OFP) nonlinear systems and (b) a necessary and sufficient stability condition for linear time-invariant (LTI) single-input-single-output (SISO) systems. The performance advantages of the proposed approach are reduced sensitivity to time delay and improved steady state error compared to alternative known delay-independent small gain type approaches. Simulations validate the proposed approach.