Distributed nonlinear optimization algorithms for general network problems

There are a number of large networks which occur in many problems dealing with the flow of power, communication signals, water, gas, transportable goods, etc. Both design and planning of these networks involve optimization problems. The first part of this paper introduces the common characteristics of a nonlinear network (the network may be linear, the objective function may be non linear, or both may be nonlinear). The second part develops a mathematical model trying to put together some important constraints based on the abstraction for a general network. The third part deals with solution procedures; it converts the network to a matrix based system of equations, gives the characteristics of the matrix and suggests two solution procedures, one of them being a new one. The fourth part handles spatially distributed networks and evolves a number of decomposition techniques so that we can solve the problem with the help of a distributed computer system. Algorithms for parallel processors and spatially distributed systems have been described.There are a number of common features that pertain to networks. A network consists of a set of nodes and arcs. In addition at every node, there is a possibility of an input (like power, water, message, goods etc) or an output or none. Normally, the network equations describe the flows amoungst nodes through the arcs. These network equations couple variables associated with nodes. Invariably, variables pertaining to arcs are constants; the result required will be flows through the arcs. To solve the normal base problem, we are given input flows at nodes, output flows at nodes and certain physical constraints on other variables at nodes and we should find out the flows through the network (variables at nodes will be referred to as across variables).The optimization problem involves in selecting inputs at nodes so as to optimise an objective function; the objective may be a cost function based on the inputs to be minimised or a loss function or an efficiency function. The above mathematical model can be solved using Lagrange Multiplier technique since the equalities are strong compared to inequalities. The Lagrange multiplier technique divides the solution procedure into two stages per iteration. Stage one calculates the problem variables % and stage two the multipliers lambda. It is shown that the Jacobian matrix used in stage one (for solving a nonlinear system of necessary conditions) occurs in the stage two also.A second solution procedure has also been imbedded into the first one. This is called total residue approach. It changes the equality constraints so that we can get faster convergence of the iterations.Both solution procedures are found to coverge in 3 to 7 iterations for a sample network.The availability of distributed computer systems — both LAN and WAN — suggest the need for algorithms to solve the optimization problems. Two types of algorithms have been proposed — one based on the physics of the network and the other on the property of the Jacobian matrix. Three algorithms have been deviced, one of them for the local area case. These algorithms are called as regional distributed algorithm, hierarchical regional distributed algorithm (both using the physics properties of the network), and locally distributed algorithm (a multiprocessor based approach with a local area network configuration). The approach used was to define an algorithm that is faster and uses minimum communications. These algorithms are found to converge at the same rate as the non distributed (unitary) case.

Relationship Between The Impedance Matrix And The Transfer Matrix With Specific Reference To Symmetrical, Reciprocal And Conservative Systems

Impedance matrix and transfer matrix methods are often used in the analysis of linear dynamical systems. In this paper, general relationships between these matrices are derived. The properties of the impedance matrix and the transfer matrix of symmetrical systems, reciprocal systems and conservative systems are investigated. In the process, the following observations are made: (a) symmetrical systems are not a subset of reciprocal systems, as is often misunderstood; (b) the cascading of reciprocal systems again results in a reciprocal system, whereas cascading of symmetrical systems does not necessarily result in a symmetrical system; (c) the determinant of the transfer matrix, being ±1, is a property of both symmetrical systems and reciprocal systems, but this condition, however, is not sufficient to establish either the reciprocity or the symmetry of the system; (d) the impedance matrix of a conservative system is skew-Hermitian.

Piezoelectrically actuated insect scale flapping wing

An energy method is used in order to derive the non-linear equations of motion of a smart flapping wing. Flapping wing is actuated from the root by a PZT unimorph in the piezofan configuration. Dynamic characteristics of the wing, having the same size as dragonfly Aeshna Multicolor, are analyzed using numerical simulations. It is shown that flapping angle variations of the smart flapping wing are similar to the actual dragonfly wing for a specific feasible voltage. An unsteady aerodynamic model based on modified strip theory is used to obtain the aerodynamic forces. It is found that the smart wing generates sufficient lift to support its own weight and carry a small payload. It is therefore a potential candidate for flapping wing of micro air vehicles.

Noise and outlier removal from jet engine health signals using weighted FIR median hybrid filters

The removal of noise and outliers from measurement signals is a major problem in jet engine health monitoring. Topical measurement signals found in most jet engines include low rotor speed, high rotor speed. fuel flow and exhaust gas temperature. Deviations in these measurements from a baseline 'good' engine are often called measurement deltas and the health signals used for fault detection, isolation, trending and data mining. Linear filters such as the FIR moving average filter and IIR exponential average filter are used in the industry to remove noise and outliers from the jet engine measurement deltas. However, the use of linear filters can lead to loss of critical features in the signal that can contain information about maintenance and repair events that could be used by fault isolation algorithms to determine engine condition or by data mining algorithms to learn valuable patterns in the data, Non-linear filters such as the median and weighted median hybrid filters offer the opportunity to remove noise and gross outliers from signals while preserving features. In this study. a comparison of traditional linear filters popular in the jet engine industry is made with the median filter and the subfilter weighted FIR median hybrid (SWFMH) filter. Results using simulated data with implanted faults shows that the SWFMH filter results in a noise reduction of over 60 per cent compared to only 20 per cent for FIR filters and 30 per cent for IIR filters. Preprocessing jet engine health signals using the SWFMH filter would greatly improve the accuracy of diagnostic systems. (C) 2002 Published by Elsevier Science Ltd.

Persistent passive hopping and juggling is possible even with plastic collisions

We describe simple one-dimensional models of passive (no energy input, no control), generally dissipative, vertical hopping and one-ball juggling. The central observation is that internal passive system motions can conspire to eliminate collisions in these systems. For hopping, two point masses are connected by a spring and the lower mass has inelastic collisions with the ground. For juggling, a lower point-mass hand is connected by a spring to the ground and an upper point-mass ball is caught with an inelastic collision and then re-thrown into gravitational free flight. The two systems have identical dynamics. Despite inelastic collisions between non-zero masses, these systems have special symmetric energy-conserving periodic motions where the collision is at zero relative velocity. Additionally, these special periodic motions have a non-zero sized, one-sided region of attraction on the higher-energy side. For either very large or very small mass ratios, the one-sided region of attraction is large. These results persist for mildly non-linear springs and non-constant gravity. Although non-collisional damping destroys the periodic motions, small energy injection makes the periodic motions stable, with a two-sided region of attraction. The existence of such special energy conserving solutions for hopping and juggling points to possibly useful strategies for both animals and robots. The lossless motions are demonstrated with a table-top experiment.

Fault-Tolerant Average Execution Time Optimization for General Purpose Multi-Processor System-on Chips

Fault-tolerance is due to the semiconductor technology development important, not only for safety-critical systems but also for general-purpose (non-safety critical) systems. However, instead of guaranteeing that deadlines always are met, it is for general-purpose systems important to minimize the average execution time (AET) while ensuring fault-tolerance. For a given job and a soft (transient) error probability, we define mathematical formulas for AET that includes bus communication overhead for both voting (active replication) and rollback-recovery with checkpointing (RRC). And, for a given multi-processor system-on-chip (MPSoC), we define integer linear programming (ILP) models that minimize AET including bus communication overhead when: (1) selecting the number of checkpoints when using RRC, (2) finding the number of processors and job-to-processor assignment when using voting, and (3) defining fault-tolerance scheme (voting or RRC) per job and defining its usage for each job. Experiments demonstrate significant savings in AET.

Bounds on Defect Level and Fault Coverage in Linear Analog Circuit Testing

Transfer function coefficients (TFC) are widely used to test linear analog circuits for parametric and catastrophic faults. This paper presents closed form expressions for an upper bound on the defect level (DL) and a lower bound on fault coverage (FC) achievable in TFC based test method. The computed bounds have been tested and validated on several benchmark circuits. Further, application of these bounds to scalable RC ladder networks reveal a number of interesting characteristics. The approach adopted here is general and can be extended to find bounds of DL and FC of other parametric test methods for linear and non-linear circuits.

Modeling of active fiber composite for delamination sensing

In order to demonstrate the feasibility of Active Fiber Composites (AFC) as sensors for detecting damage, a pretwisted strip made of AFC with symmetric free-edge delamination is considered in this paper. The strain developed on the top/bottom of the strip is measured to detect and assess delamination. Variational Asymptotic Method (VAM) is used in the development of a non-classical non-linear cross sectional model of the strip. The original three dimensional (3D) problem is simplified by the decomposition into two simpler problems: a two-dimensional (2D) problem, which provides in a compact form the cross-sectional properties using VAM, and a non-linear one-dimensional (1D) problem along the length of the beam. This procedure gives the non-linear stiffnesses, which are very sensitive to damage, at any given cross-section of the strip. The developed model is used to study a special case of cantilevered laminated strip with antisymmetric layup, loaded only by an axial force at the tip. The charge generated in the AFC lamina is derived in closed form in terms of the 1D strain measures. It is observed that delamination length and location have a definite influence on the charge developed in the AFC lamina. Also, sensor voltage output distribution along the length of the beam is obtained using evenly distributed electrode strip. These data could in turn be used to detect the presence of damage.

Scheduling a Burn-In Oven with Non-Agreeable Release Times and Due Dates

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modelled as batch processing machines. Most of the studies assume that ready times and due dates of jobs are agreeable (i.e., ri < rj implies di ≤ dj). In many real world applications, the agreeable property assumption does not hold. Therefore, in this paper, scheduling of a single burn-in oven with non-agreeable release times and due dates along with non-identical job sizes as well as non-identical processing of time problem is formulated as a Non-Linear (0-1) Integer Programming optimisation problem. The objective measure of the problem is minimising the maximum completion time (makespan) of all jobs. Due to computational intractability, we have proposed four variants of a two-phase greedy heuristic algorithm. Computational experiments indicate that two out of four proposed algorithms have excellent average performance and also capable of solving any large-scale real life problems with a relatively low computational effort on a Pentium IV computer.

Pickup and delivery problem using metaheuristics techniques

Dial-a-ride problem (DARP) is an optimization problem which deals with the minimization of the cost of the provided service where the customers are provided a door-to-door service based on their requests. This optimization model presented in earlier studies, is considered in this study. Due to the non-linear nature of the objective function the traditional optimization methods are plagued with the problem of converging to a local minima. To overcome this pitfall we use metaheuristics namely Simulated Annealing (SA), Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Artificial Immune System (AIS). From the results obtained, we conclude that Artificial Immune System method effectively tackles this optimization problem by providing us with optimal solutions. Crown Copyright (C) 2011 Published by Elsevier Ltd. All rights reserved.

An Accurate Model for EESM and its Application to Analysis of CQI Feedback Schemes and Scheduling in LTE

The Effective Exponential SNR Mapping (EESM) is an indispensable tool for analyzing and simulating next generation orthogonal frequency division multiplexing (OFDM) based wireless systems. It converts the different gains of multiple subchannels, over which a codeword is transmitted, into a single effective flat-fading gain with the same codeword error rate. It facilitates link adaptation by helping each user to compute an accurate channel quality indicator (CQI), which is fed back to the base station to enable downlink rate adaptation and scheduling. However, the highly non-linear nature of EESM makes a performance analysis of adaptation and scheduling difficult; even the probability distribution of EESM is not known in closed-form. This paper shows that EESM can be accurately modeled as a lognormal random variable when the subchannel gains are Rayleigh distributed. The model is also valid when the subchannel gains are correlated in frequency or space. With some simplifying assumptions, the paper then develops a novel analysis of the performance of LTE's two CQI feedback schemes that use EESM to generate CQI. The comprehensive model and analysis quantify the joint effect of several critical components such as scheduler, multiple antenna mode, CQI feedback scheme, and EESM-based feedback averaging on the overall system throughput.

Towards formal verification of analog mixed signal designs using SPICE circuit simulation traces

An extension to a formal verification approach of hybrid systems is proposed to verify analog and mixed signal (AMS) designs. AMS designs can be formally modeled as hybrid systems and therefore lend themselves to the formal analysis and verification techniques applied to hybrid systems. The proposed approach employs simulation traces obtained from an actual design implementation of AMS circuit blocks (for example, in the form of SPICE netlists) to carry out formal analysis and verification. This enables the same platform used for formally validating an abstract model of an AMS design, to be also used for validating its different refinements and design implementation; thereby, providing a simple route to formal verification at different levels of implementation. The feasibility of the proposed approach is demonstrated with a case study based on a tunnel diode oscillator. Since the device characteristic of a tunnel diode is highly non-linear with a negative resistance region, dynamic behavior of circuits in which it is employed as an element is difficult to model, analyze and verify within a general hybrid system formal verification tool. In the case study presented the formal model and the proposed computational techniques have been incorporated into CheckMate, a formal verification tool based on MATLAB and Simulink-Stateflow Framework from MathWorks.

Comparison of one cycle control of charge and current for bi-directional boost rectifiers

Classical control and one cycle control of current are popular methods used to modulate pulses in active rectifiers for ac-dc power conversion. One cycle control has lower control complexity and can be implemented using linear analog circuits when compared with the classical approach. However, it also suffers from problems such as instability and offsets in current that is severe at light load conditions. A control strategy for bidirectional boost rectifiers based on one cycle control of charge is proposed for that overcomes these limitations. The integral of sensed current, which represents charge, is compared with a non-linear carrier, which is modified for ac-dc power conversion. This generates the gating signals for the switching devices. The modifications required for the control law governing one cycle control of charge is derived in the paper. Detailed simulation studies are carried out to compare one cycle control of current with the proposed method for ac-dc power conversion, which are validated on a laboratory hardware prototype.

Epoch extraction based on integrated linear prediction residual using plosion index

Epoch is defined as the instant of significant excitation within a pitch period of voiced speech. Epoch extraction continues to attract the interest of researchers because of its significance in speech analysis. Existing high performance epoch extraction algorithms require either dynamic programming techniques or a priori information of the average pitch period. An algorithm without such requirements is proposed based on integrated linear prediction residual (ILPR) which resembles the voice source signal. Half wave rectified and negated ILPR (or Hilbert transform of ILPR) is used as the pre-processed signal. A new non-linear temporal measure named the plosion index (PI) has been proposed for detecting `transients' in speech signal. An extension of PI, called the dynamic plosion index (DPI) is applied on pre-processed signal to estimate the epochs. The proposed DPI algorithm is validated using six large databases which provide simultaneous EGG recordings. Creaky and singing voice samples are also analyzed. The algorithm has been tested for its robustness in the presence of additive white and babble noise and on simulated telephone quality speech. The performance of the DPI algorithm is found to be comparable or better than five state-of-the-art techniques for the experiments considered.

Sliding mode control based terminal impact angle constrained guidance laws using dual sliding surfaces

In this paper, sliding mode control theory based guidance laws to intercept non-maneuvering targets at a desired impact angle are presented. The desired impact angle, defined in terms of a desired line-of-sight (LOS) angle, is achieved by selecting the missile's lateral acceleration (latax) to enforce sliding mode on a sliding surface based on this LOS angle. As will be shown, this guidance law does not ensure interception for all states of the missile and the target during the engagement. Hence, to satisfy the requirement of interception at the desired impact angle, a second sliding surface is designed and a switching logic, based on the conditions necessary for interception, is presented that allows the latax to switch between enforcing sliding mode on one of these surfaces so that the target can be intercepted at the desired impact angle. The guidance laws are designed using non-linear engagement dynamics.