A Parallel Block Scaled Gradient Method With Decentralized Step‐Size For Block Additive Unconstrained Optimization Problems Of Large Distributed Systems

In this paper, we propose a modified parallel block scaled gradient method for solving block additive unconstrained optimization problems of large distributed systems. Our method makes two major modifications to the typical parallel block scaled gradient method: First, we include a pre‐processing step which reduces the computational time; second, we propose a decentralized Armijo‐type step‐size rule. This rule circumvents the difficulty of determining a step‐size in a distributed computing environment and enables the proposed parallel algorithm to execute in a distributed computer network with a limited amount of data transfer. We have applied our method to the weighted‐least‐square problems of power system state estimation and demonstrated the convergence of our method by testing numerous examples on a PC network. The speedup ratio of the distributed version of our method tends to increase proportionally with the number of subsystems (or computers).     

A graph-theoretical clustering method based on two rounds of minimum spanning trees

Many clustering approaches have been proposed in the literature, but most of them are vulnerable to the different cluster sizes, shapes and densities. In this paper, we present a graph-theoretical clustering method which is robust to the difference. Based on the graph composed of two rounds of minimum spanning trees (MST), the proposed method (2-MSTClus) classifies cluster problems into two groups, i.e. separated cluster problems and touching cluster problems, and identifies the two groups of cluster problems automatically. It contains two clustering algorithms which deal with separated clusters and touching clusters in two phases, respectively. In the first phase, two round minimum spanning trees are employed to construct a graph and detect separated clusters which cover distance separated and density separated clusters. In the second phase, touching clusters, which are subgroups produced in the first phase, can be partitioned by comparing cuts, respectively, on the two round minimum spanning trees. The proposed method is robust to the varied cluster sizes, shapes and densities, and can discover the number of clusters. Experimental results on synthetic and real datasets demonstrate the performance of the proposed method.     

On the controllability of discrete linear systems with output feedback

A discrete time linear systemx_{t+1}= Ax_{t} + Bu_{t'}y = Cx_{t'}, with output feedbacku_{t} = G_{t}y_{t'}, call be regarded as a nonlinear system with "control" Gt. Weak sufficient conditions are given for the existence of a finite sequence of gains for which every initial state can be driven to the origin. For a one input, one output system, the question of what terminal states can be reached from a given initial state is resolved. It is shown that an important ingredient for these problems is the semigroup of integers generated by the set{k:cA^{k-1}b neq 0, 1 leq k leq k leq 3n}(for a single input, single output system of dimensionn). It is also natural to use a pair of "canonical forms," in the guise of polynomials, to represent states. One is useful for input considerations and the other for output considerations. For output feedback problems one must further distinguish between two polynomials which are equivalent in the sense that they represent the same state. This is due to the fact that some polynomials are ill-conditioned in that they would have us use a nonzero input when the output vanishes.     

An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs

In this paper, a graph problem on connected, weighted, undirected graphs, called the searchlight guarding problem, is considered. Assume that there is a fugitive who moves along the edges of the graph at a random speed. The task involves placing a set of searchlights at vertices to search the edges of the graph and to spot the fugitive. Suppose that placing a searchlight at some vertex incurs some building cost. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total cost of the vertices in S is minimized. If there is more than one set of searchlights, each with a minimum building cost, then identify the set with the minimum search time, that is, where the time slots needed to spot the fugitive is the minimum. As is well established, the problem is NP-hard on weighted bipartite graphs but is linear-time solvable on weighted trees. In this paper, the design of a linear-time optimal algorithm for the searchlight guarding problem on weighted interval graphs is presented. It entails two phases. In the first phase, a set of searchlights with minimum guarding cost is identified and the search directions of all edges are assigned. To achieve this task, a new problem, called the edge-direction assignment problem, is first defined and the problem on weighted complete-split graphs is solved by the greedy strategy. Based on this computational result, the problem of finding the set of searchlights with minimum guarding cost and assigning the search directions of all edges is solved by the dynamic programming strategy. Then, in the second phase, the search time slots of each edge are determined on the basis of the results of the first phase and on some properties of interval graphs.     

Combine crossing matching scores with conventional matching scores for bimodal biometrics and face and palmprint recognition experiments

In this paper, we define for the first time the crossing matching score of two biometrics traits and combine it with the conventional matching scores to perform personal authentication. The proposed method is very suitable for the bimodal biometrics systems with two similar biometrics traits such as the system with visible light and infrared face images and the system with palm images captured at two bands. The proposed method first runs for the first and biometrics traits, respectively. For each of these two biometrics traits, the proposed method calculates the matching scores between the testing sample and each training sample. The matching scores generated from the first and second traits are referred to as the first and second matching scores, respectively. Second, the proposed method calculates the crossing matching scores, i.e. the matching scores between the testing sample of the second biometrics trait and the training samples of the first biometrics trait. Finally, we use a weighted fusion scheme to combine the first, second and crossing matching scores for personal authentication.     

l^{1}-optimal feedback controllers for MIMO discrete-time systems

The problem considered in this paper is the design of a closed-loop system consisting of a MIMO discrete-time plant and compensator in such a way that the system is internally stable and optimally tracks all persistent bounded inputs. The solution consists of two parts: first the calculation of the minimum value of the performance index (a weighted transfer function), which is done by solving a linear programming problem; and second, construction of the optimal transfer function by solving a set of linear equations. It is shown that, in general, the discrete-time problem will have a rational solution and thus appears to be of considerable practical significance.     

Energy Aware Routing Algorithm in Manet Using Linear Programming

Mobile ad hoc networks (MANET) are wireless network without infrastructure and suffering from low power battery. Therefore the main objective in finding a route for traffic transfer from a given source to a given destination is to minimize the node energy consumption. This paper solves the problem of finding a route satisfying the main objective of minimum energy consumption and other QoS requirements such as minimum delay and maximum packet delivery ratio by using linear programming technique. Two cases are considered: 1. The traffic amount of a given request is transmitted into single path, and 2. The traffic amount of a request can be distributed into parallel paths. A preprocessing step is done first for network topology design. This step leads to formulate the first case as integer linear programming problem and the second case as linear programming and not mixed integer linear programming. The two obtained solutions are evaluated in terms of three criteria: energy consumption, execution time, and packet delivery ratio using an experimental study. The results show that the solution of second case is much better than the first case in terms of energy consumption and execution time. Packet delivery ratio in the second case is 100% while in the first case is only 76%.     

Multisensor optimal information fusion input white noise deconvolution estimators

The unified multisensor optimal information fusion criterion weighted by matrices is rederived in the linear minimum variance sense, where the assumption of normal distribution is avoided. Based on this fusion criterion, the optimal information fusion input white noise deconvolution estimators are presented for discrete time-varying linear stochastic control system with multiple sensors and correlated noises, which can be applied to seismic data processing in oil exploration. A three-layer fusion structure with fault tolerant property and reliability is given. The first fusion layer and the second fusion layer both have netted parallel structures to determine the first-step prediction error cross-covariance for the state and the estimation error cross-covariance for the input white noise between any two sensors at each time step, respectively. The third fusion layer is the fusion center to determine the optimal matrix weights and obtain the optimal fusion input white noise estimators. The simulation results for Bernoulli-Gaussian input white noise deconvolution estimators show the effectiveness.     

Binaural Localization Based on Weighted Wiener Gain Improved by Incremental Source Attenuation

This paper addresses the problem of direction-of-arrival (DOA) estimation both in azimuthal and elevation angle from binaural sound that is processed with a head-related transfer function (HRTF). Previously, we proposed a weighted Wiener gain (WWG) method for two-dimensional DOA estimation with two-directional microphones. However, for signals processed with HRTFs, peaks in the spatial spectra of WWG indicating true sources can mingle with spurious peaks. To resolve this situation, we propose to apply incremental source attenuation (ISA) in combination with WWG. In fact, ISA reduces spectral components originating from specified sound sources and thereby improves the localization accuracy of the next targeted source in the proposed incremental estimation procedure. We conduct computer simulations using directional microphones and four HRTF sets corresponding to four individuals. The proposed method is compared to two DOA estimation methods that are equivalent to two generalized cross-correlation functions and two high-resolution methods of multiple signal classification (MUSIC) and minimum variance method. For comparison purposes, we introduce binary coherence detection (BCD) to high-resolution methods for emphasizing valid spectral components for localization in multiple source conditions. Evaluation results demonstrate that, although MUSIC with BCD yield comparable performance to that of WWG in conditions where single speech source exists, WWG with ISA surpasses the other methods in conditions including two or three speech sources.     

An interior point cutting plane heuristic for mixed integer programming

We explore the use of interior point methods in finding feasible solutions to mixed integer programming. As integer solutions are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior of the feasible set. The algorithm searches along two line segments that connect the weighted analytic center and two extreme points of the linear programming relaxation. Candidate points are rounded and tested for feasibility. Cuts aimed to improve the objective function and restore feasibility are then added to displace the weighted analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along the two line segments are rounded gradually to find integer feasible solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated and a new weighted analytic center is found. Upon failing to find a feasible integer solution, a second phase is started where cuts related to the violated feasibility constraints are added. As a last resort, the algorithm solves a minimum distance problem in a third phase. The heuristic is tested on a set of problems from MIPLIB and CORAL. The algorithm finds good quality feasible solutions in the first two phases and never requires the third phase.     

A globally optimal minimax solution for spectral overbounding andfactorization

In this paper, an algorithm is introduced to find a minimum phase transfer function of specified order whose magnitude “tightly” overbounds a specified real-valued nonparametric function of frequency. This method has direct application to transforming nonparametric uncertainty bounds (available from system identification experiments and/or plant modeling) into parametric representations required for modern robust control design software (i.e., a minimum-phase transfer function multiplied by a norm-bounded perturbation)     

Testing from a stochastic timed system with a fault model

In this paper we present a method for testing a system against a non-deterministic stochastic finite state machine. As usual, we assume that the functional behaviour of the system under test (SUT) is deterministic but we allow the timing to be non-deterministic. We extend the state counting method of deriving tests, adapting it to the presence of temporal requirements represented by means of random variables. The notion of conformance is introduced using an implementation relation considering temporal aspects and the limitations imposed by a black-box framework. We propose a new group of implementation relations and an algorithm for generating a test suite that determines the conformance of a deterministic SUT with respect to a non-deterministic specification. We show how previous work on testing from stochastic systems can be encoded into the framework presented in this paper as an instantiation of our parameterized implementation relation. In this setting, we use a notion of conformance up to a given confidence level.     

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

Minimum Dominating Sets of Intervals on Lines

We study the problem of computing minimum dominating sets of n intervals on lines in three cases: (1) the lines intersect at a single point, (2) all lines except one are parallel, and (3) one line with t weighted points on it and the minimum dominating set must maximize the sum of the weights of the points covered. We propose polynomial-time algorithms for the first two problems, which are special cases of the minimum dominating set problem for path graphs which is known to be NP-hard. The third problem requires identifying the structure of minimum dominating sets of intervals on a line so as to be able to select one that maximizes the weight sum of the weighted points covered. Assuming that presorting has been performed, the first problem has an O(n) -time solution, while the second and the third problems are solved by dynamic programming algorithms, requiring O(n log n) and O(n + t) time, respectively. Received April 13, 1995; revised July 27, 1996.     

Weighted dynamic time warping for time series classification

Dynamic time warping (DTW), which finds the minimum path by providing non-linear alignments between two time series, has been widely used as a distance measure for time series classification and clustering. However, DTW does not account for the relative importance regarding the phase difference between a reference point and a testing point. This may lead to misclassification especially in applications where the shape similarity between two sequences is a major consideration for an accurate recognition. Therefore, we propose a novel distance measure, called a weighted DTW (WDTW), which is a penalty-based DTW. Our approach penalizes points with higher phase difference between a reference point and a testing point in order to prevent minimum distance distortion caused by outliers. The rationale underlying the proposed distance measure is demonstrated with some illustrative examples. A new weight function, called the modified logistic weight function (MLWF), is also proposed to systematically assign weights as a function of the phase difference between a reference point and a testing point. By applying different weights to adjacent points, the proposed algorithm can enhance the detection of similarity between two time series. We show that some popular distance measures such as DTW and Euclidean distance are special cases of our proposed WDTW measure. We extend the proposed idea to other variants of DTW such as derivative dynamic time warping (DDTW) and propose the weighted version of DDTW. We have compared the performances of our proposed procedures with other popular approaches using public data sets available through the UCR Time Series Data Mining Archive for both time series classification and clustering problems. The experimental results indicate that the proposed approaches can achieve improved accuracy for time series classification and clustering problems.     

Multi-sensor information fusion white noise filter weighted by scalars based on Kalman predictor

A unified multi-sensor optimal information fusion criterion weighted by scalars is presented in the linear minimum variance sense. The criterion considers the correlation among local estimation errors, only requires the computation of scalar weights, and avoids the computation of matrix weights so that the computational burden can obviously be reduced. Based on this fusion criterion and Kalman predictor, an optimal information fusion filter for the input white noise, which can be applied to seismic data processing in oil exploration, is given for discrete time-varying linear stochastic control systems measured by multiple sensors with correlated noises. It has a two-layer fusion structure. The first fusion layer has a netted parallel structure to determine the first-step prediction error cross-covariance for the state and the filtering error cross-covariance for the input white noise between any two sensors at each time step. The second fusion layer is the fusion center to determine the optimal scalar weights and obtain the optimal fusion filter for the input white noise. Two simulation examples for Bernoulli-Gaussian white noise filter show the effectiveness.     

Two-step procedure for time-suboptimal control

A two-step procedure for stable time-suboptimal control is proposed. The procedure involves the use of two feedback gain matrices. The first matrix is determined to transfer the system from a given state to the vicinity of the desired state in minimum time. Then a switch is made to a second feedback gain matrix obtained from shifting of eigenvalues For maximum stability. The viability of the proposed procedure is demonstrated with a linear six-p!ate gas absorber and a non-linear two-stage CSTR system.     

Exhaustive property oriented model-based testing with symbolic finite state machines

We advocate a fusion of property-oriented testing (POT) and model-based testing (MBT). The existence of a symbolic finite state machine (SFSM) model fulfilling the properties of interest is exploited for property-directed test data generation and to create a test oracle. A new test generation strategy is presented for verifying that the system under test (SUT) satisfies the same LTL safety conditions over a given set of atomic propositions as the model. We prove that this strategy is exhaustive in the sense that any SUT violating at least one of these formulae will fail at least one test case of the generated suite. It is shown that the existence of a model allows for significantly smaller exhaustive test suites as would be necessary for POT without reference models. As a corollary, the main theorem also generalises a known result about SFSM-based conformance testing for language equivalence. Our approach fits well to industrial development processes for (potentially safety-critical) cyber-physical systems, where both models and properties representing system requirements are elaborated for development, verification, and validation.     

Transfer function representation of cyclic consensus systems

This paper presents explicit forms of transfer functions for a class of cyclic consensus systems with different kinds of network topologies; directed, undirected and different numbers of reference agents. Each agent of consensus systems is assumed to satisfy a scalar integrator dynamics which is driven by a common consensus protocol and an independent exogenous input. It is shown that every single-input single-output (SISO) transfer function between the exogenous input of one agent and the state of another generally different agent, is always minimum phase. In addition, the poles and zeros, system degrees and relative degrees of those SISO transfer functions are specified. These results are interpreted in relation to the controllability and closed loop performance of a networked system with one leader agent. Furthermore, our transfer function representations are applied to an investigation of stability margins for a closed loop cyclic consensus system.     

A formal method to real-time protocol interoperability testing

Interoperability testing is an important technique to ensure the quality of implementations of network communication protocol. In the next generation Internet protocol, real-time applications should be supported effectively. However, time constraints were not considered in the related studies of protocol interoperability testing, so existing interoperability testing methods are difficult to be applied in real-time protocol interoperability testing. In this paper, a formal method to real-time protocol interoperability testing is proposed. Firstly, a formal model CMpTIOA （communicating multi-port timed input output automata） is defined to specify the system under test （SUT） in real-time protocol interoperability testing; based on this model, timed interoperability relation is then defined. In order to check this relation, a test generation method is presented to generate a parameterized test behavior tree from SUT model; a mechanism of executability pre-determination is also integrated in the test generation method to alleviate state space explosion problem to some extent. The proposed theory and method are then applied in interoperability testing of IPv6 neighbor discovery protocol to show the feasibility of this method.