A review of methods for input/output selection <s> Search methods <s> The premise in low-authority control (LAG) is that the actuators have limited authority, and hence cannot significantly shift the eigenvalues of the system. We introduce a near method for low authority controller design, based on convex programming. We formulate the LAC design problem as a nonlinear convex optimization problem, which can then be solved efficiently by interior-point methods. We show that by optimizing the l/sub 1/ norm of the gains, we can arrive at sparse designs, i.e., designs in which only a small number of the control gains are non-zero. Thus, we can also solve actuator/sensor placement or controller architecture design problems. Moreover, it is possible to address the robustness of the LAG, i.e., a closed-loop performance subject to uncertainties or variations in the plant model. Therefore, by combining all these, for example, we can solve the problem of robust actuator/sensor placement and LAC design in one step. <s> BIB001 </s> A review of methods for input/output selection <s> Search methods <s> From the Publisher: ::: In the past three decades local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization. Local search is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in a reasonable time. This area of discrete mathematics is of great practical use and is attracting ever increasing attention. The contributions to this book cover local search and its variants from both a theoretical and practical point of view, each with a chapter written by leading authorities on that particular aspect. This book is an important reference volume and an invaluable source of inspiration for advanced students and researchers in discrete mathematics, computer science, operations research, industrial engineering and management science. <s> BIB002
Most IO selection criteria discussed are evaluated on a per candidate basis, so worst case all IO sets have to be checked. This implies an exhaustive search for a number of combinations that grows exponentially with N S #N W , which is practically intractable and ine$cient. As will appear below, to avoid the combinatorial nature of the problem, in general one has to make a compromise, either in the choice of the selection criterion or in the choice of the search strategy. The computational e!ort can be reduced signi"cantly by realizing that often it is not necessary to check all candidate IO sets to discriminate viable from nonviable IO sets. For many IO selection problem formulations, the following two dual properties hold: (A) eliminating inputs and/or outputs does not improve control and (B) adding inputs and/or outputs does not worsen control. Realizing this, subsets (supersets) of nonviable (viable) IO sets need not be checked, but can directly be termed nonviable (viable). The validity of (A) or (B) depends on the considered system and the IO selection criterion. For instance, the properties may not apply if there are candidate actuators and sensors a!ecting the open-loop dynamics or if the IO selection criterion involves the plant's condition number. Properties (A) or (B) can form the basis of a strategy of going through the candidate IO sets. Such a strategy is discussed by  . It is based on a novel algorithm to generate all maximal-independent or minimal-dependent sets, a standard problem in combinatorial optimization. The problem is still NP-hard, i.e., there is no solution possible in polynomial time, although in practice (for N S #N W not too large) the computing time is polynomial in N S #N W and in the number of IO sets that characterize the complete solution. An example using a -based RP criterion for a problem with N S #N W "28 has shown the algorithm to reduce signi"-cantly, i.e., by a factor 10\, the number of IO sets to be checked, compared to an exhaustive search . The algorithm proposed by De Jager and Toker (1998) generates all minimal dependent sets, i.e., sets that are viable but whose subsets are all nonviable. These IO sets do not contain redundant actuators or sensors. If any device fails, even if the failure is detected and the controller changed accordingly, the performance will be below par. But, (1) redundancy aspects can be built into the selection criterion and (2) combining two disjunct minimal IO sets will protect against single-device failures. The results are therefore also useful for adding fault-tolerance to a system. Contained in the minimal-dependent sets are sets with the smallest number of devices: the minimumdependent sets. By providing all minimal-dependent sets (not only the smallest ones) the designer is given full information about the performance structure. He can use this knowledge to attend to aspects not included in the selection criterion and can limit a further search for an optimal IO set to the minimal-dependent sets. Another approach to avoid exhaustive testing on a candidate-by-candidate basis is by using optimization. The minimal-dependent set algorithm generates all sets that meet a certain constraint using the selection criterion. Adding an optimization criterion to the constraint may yield a unique solution. Several algorithms in combinatorial optimization can be employed BIB002 . BIB001 combine an L norm optimization criterion on the controller coe$cients with other design constraints. For closed-loop pole region constraints, this yields a linear programming problem that can be solved e$ciently. If controller coe$cients tend to be zero, it may be possible that some actuators and sensors are not used. This method combines IO and CC selection. It gives an approximate solution to a combinatorial optimization problem. It is not guaranteed to generate one of the optimum solutions with the lowest number of devices, but it may end up with a solution close to the optimal ones. It has the advantage of being very e$cient, because it is a direct method and uses a simple convex optimization routine.