Real-μ bounds based on fixed shapes in the Nyquist plane: Parabolas, hyperbolas, cissoids, nephroids, and octomorphs

In this paper we introduce new bounds for the real structured singular value. The approach is based on absolute stability criteria with plant-dependent multipliers that exclude the Nyquist plot from fixed plane curve shapes containing the critical point − + _jO. Unlike half-plane and circle-based bounds the critical feature of the fixed curve bounds is their ability to differentiate between the real and imaginary components of the uncertainty. Since the plant-dependent multipliers have the same functional form at all frequencies, the resulting graphical interpretation of the absolute stability criteria are frequency independent in contrast to the frequency-dependent off-axis circles that arise in standard real-μ bounds.     

Real-μ bounds based on fixed shapes in the Nyquist plane: Parabolas, hyperbolas, cissoids, nephroids, and octomorphs

In this paper we introduce new bounds for the real structured singular value. The approach is based on absolute stability criteria with plant-dependent multipliers that exclude the Nyquist plot from fixed plane curve shapes containing the critical point − + _jO. Unlike half-plane and circle-based bounds the critical feature of the fixed curve bounds is their ability to differentiate between the real and imaginary components of the uncertainty. Since the plant-dependent multipliers have the same functional form at all frequencies, the resulting graphical interpretation of the absolute stability criteria are frequency independent in contrast to the frequency-dependent off-axis circles that arise in standard real-μ bounds.     

Small-μ theorems with frequency-dependent uncertainty bounds

We present conditions, some necessary and some sufficient, valid under weak assumptions, for robust stability and uniform robust stability of uncertain linear time-invariant systems with linear time-invariant uncertainties that are block-diagonal, with known frequency-dependent norm bounds on the diagonal, blocks. Small-μ theorems with frequency-independent uncertainty bounds are recovered as special cases. This research was in part supported by NSF’s Engineering Research Center No. NSFD-CDR-88-03012, and in part by the Office of Naval Research under Contract No. N00014-97-1-0640.     

GENERATION OF EXACT QFT BOUNDS FOR PLANTS WITH AFFINELY DEPENDENT UNCERTAINTIES

This paper presents an efficient method for the generation of exact QFT bounds for robust sensitivity reduction and gain‐phase margin specifications for plants with affinely dependent uncertainties. It is shown that, for a plant with m affinely dependent uncertainties, the exact QFT bounds for robust sensitivity reduction and gain‐phase margin specifications at a given frequency and controller phase can be computed by solving m^2m‐1 bivariate polynomial inequalities corresponding to the edges of the parameter domain box. Moreover, the solution set for each bivariate polynomial inequality can be computed by solving for the real roots of one fourth‐order and six second‐order polynomials. This avoids the unfavorable trade‐off between the computational burden and the accuracy of QFT bounds that has arisen in the application of many existing QFT bound generation algorithms. Numerical examples are given to illustrate the proposed method and its computational superiority.     

On the stability of a linear time-varying system

A single-loop linear system with a time-invariant stable blockGin the direct path and a time-varying gain in the feedback path is analyzed for asymptotic stability in the Popov framework by way of admitting noncausal "multipliers" in the stability criterion. It is shown that an auto-correlation bound, analogous to O'Shea's cross-correlation bounds [1], results in a constraint on dk/dt more restrictive than that of Gruber and Willems [2].     

Treewidth computations II. Lower bounds

For several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs.     

Dynamic matrix rank

We consider maintaining information about the rank of a matrix under changes of the entries. For n×n matrices, we show an upper bound of O(n^1.575) arithmetic operations and a lower bound of Ω(n) arithmetic operations per element change. The upper bound is valid when changing up to O(n^0.575) entries in a single column of the matrix. We also give an algorithm that maintains the rank using O(n²) arithmetic operations per rank one update. These bounds appear to be the first nontrivial bounds for the problem. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. The upper bound for element updates uses fast rectangular matrix multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

Robust, reduced-order, nonstrictly proper state estimation via the optimal projection equations with Petersen—Hollot bounds

A state-estimation design problem involving parametric plant uncertainties is considered. An error bound suggested by recent work of Petersen and Hollot is utilized for guaranteeing robust estimation. Necessary conditions which generalize the optimal projection equations for reduced-order state estimation are used to characterize the estimator which minimizes the error bound. The design equations thus effectively serve as sufficient conditions for synthesizing robust estimators. An additional feature is the presence of a static estimation gain in conjunction with the dynamic (Kalman) estimator, i. e., a nonstrictly proper estimator.     

/spl Lscr//sub /spl infin//-multipliers for robust performance analysis

Linear systems subject to nonlinear time-varying sector-bounded uncertainties are considered. Robust performance is measured in terms of the worst-case ratio between the /spl Lscr//sub /spl infin//-norms of the output and input signals. A new class of multipliers is introduced and characterized. The characterization can be used to compute an upper bound for robust performance, which tightens the bound obtained by the scaled small gain theorem. While the standard Popov multipliers and their extensions have been developed within the /spl Lscr//sub 2/ framework, our multipliers are adapted to /spl Lscr//sub /spl infin//.     

Lower bounds on precedence-constrained scheduling for parallel processors

We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark.We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.     

A note on monotone complexity and the rank of matrices

We shall give simpler proofs of some lower bounds on monotone computations. We describe a simple condition on combinatorial structures, such that the rank of the matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be constructed from self-avoiding families. As a corollary, we obtain an upper bound on the size of self-avoiding families, which solves a problem posed by Babai and Gál [Combinatorica 19 (3) (1999) 301-319].     

The complexity of updating snapshot objects

This paper proves Ω(m) lower bounds on the step complexity of UPDATE operations for space-optimal wait-free implementations of an m-component snapshot object from historyless objects. These lower bounds follow from lower bounds for a new, more general class of implementations from base objects of any type. This work extends a similar lower bound by Israeli and Shirazi for implementations of m-component single-writer snapshot objects from single-writer registers.     

Robust pole location with experimental validation for three-phase grid-connected converters

This paper provides design and experimental validation of robust current controllers for three-phase grid-connected converters. The main objectives here are: (i) to show that a simple polytopic model can be used for designing robust controllers for predominately inductive grids; (ii) to help in the choice of the control design parameter, based on a trade-off between an upper bound of the transient settling times and the control gain sizes. Linear matrix inequality based conditions are used to design the robust control gains with lower numerical complexity than similar conditions on literature. It is shown that small values the radius of pole location lead to better bounds for the transient responses, at the price of higher control gains. Good tracking of references for the grid currents is also illustrated in practice, allowing the closed-loop system to inject active and reactive power into the grid. Simulation and experimental results prove that the system connected to the grid can provide three-phase currents complying with requirements of an important international standard.     

Performance bounds for nonlinear systems with a nonlinear ℒ2-gain property

Nonlinear ?₂-gain is a finite gain concept that generalises the notion of conventional (linear) finite ?₂-gain to admit the application of ?₂-gain analysis tools of a broader class of nonlinear systems. The computation of tight comparison function bounds for this nonlinear ?₂-gain property is important in applications such as small gain design. This article presents an approximation framework for these comparison function bounds through the formulation and solution of an optimal control problem. Key to the solution of this problem is the lifting of an ?₂-norm input constraint, which is facilitated via the introduction of an energy saturation operator. This admits the solution of the optimal control problem of interest via dynamic programming and associated numerical methods, leading to the computation of the proposed bounds. Two examples are presented to demonstrate this approach.     

Upper bounds for reversible circuits based on Young subgroups

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%.     

线性状态空间模型的稳定鲁棒性改善

本文讨论线性定常系统的稳定鲁棒性问题。文中给出了线性定常系统的稳定鲁棒性范围的新改善界限。在结构扰动情况下,本文给出的稳定鲁棒性界限比引文[1]中的相应结果更好。用数值计算方法容易得到这一动扰界限。文中给出的两个例子证实了本文结果的优点。     

Exponential lower bounds for the pigeonhole principle

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an (loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.     

Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem

We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.