An online-implementable differential evolution tuned all-aspect guidance law

This paper proposes a differential evolution based method of improving the performance of conventional guidance laws at high heading errors, without resorting to techniques from optimal control theory, which are complicated and suffer from several limitations. The basic guidance law is augmented with a term that is a polynomial function of the heading error. The values of the coefficients of the polynomial are found by applying the differential evolution algorithm. The results are compared with the basic guidance law, and the all-aspect proportional navigation laws in the literature. A scheme for online implementation of the proposed law for application in practice is also given. (c) 2010 Elsevier Ltd. All rights reserved.

Patterns in permuted binary matrices

Reorganizing a dataset so that its hidden structure can be observed is useful in any data analysis task. For example, detecting a regularity in a dataset helps us to interpret the data, compress the data, and explain the processes behind the data. We study datasets that come in the form of binary matrices (tables with 0s and 1s). Our goal is to develop automatic methods that bring out certain patterns by permuting the rows and columns. We concentrate on the following patterns in binary matrices: consecutive-ones (C1P), simultaneous consecutive-ones (SC1P), nestedness, k-nestedness, and bandedness. These patterns reflect specific types of interplay and variation between the rows and columns, such as continuity and hierarchies. Furthermore, their combinatorial properties are interlinked, which helps us to develop the theory of binary matrices and efficient algorithms. Indeed, we can detect all these patterns in a binary matrix efficiently, that is, in polynomial time in the size of the matrix. Since real-world datasets often contain noise and errors, we rarely witness perfect patterns. Therefore we also need to assess how far an input matrix is from a pattern: we count the number of flips (from 0s to 1s or vice versa) needed to bring out the perfect pattern in the matrix. Unfortunately, for most patterns it is an NP-complete problem to find the minimum distance to a matrix that has the perfect pattern, which means that the existence of a polynomial-time algorithm is unlikely. To find patterns in datasets with noise, we need methods that are noise-tolerant and work in practical time with large datasets. The theory of binary matrices gives rise to robust heuristics that have good performance with synthetic data and discover easily interpretable structures in real-world datasets: dialectical variation in the spoken Finnish language, division of European locations by the hierarchies found in mammal occurrences, and co-occuring groups in network data. In addition to determining the distance from a dataset to a pattern, we need to determine whether the pattern is significant or a mere occurrence of a random chance. To this end, we use significance testing: we deem a dataset significant if it appears exceptional when compared to datasets generated from a certain null hypothesis. After detecting a significant pattern in a dataset, it is up to domain experts to interpret the results in the terms of the application.

A sufficient criterion for Rayleigh-Taylor instability of incompressible viscous three-layer flow

Using normal mode analysis Rayleigh-Taylor instability is investigated for three-layer viscous stratified incompressible steady flow, when the top 3rd and bottom 1st layers extend up to infinity, the middle layer has a small thickness δ. The wave Reynolds number in the middle layer is assumed to be sufficiently small. A dispersion relation (a seventh degree polynomial in wave frequency ω) valid up to the order of the maximal value of all possible Kj (j less-than-or-equals, slant 0, K is the wave number) in each coefficient of the polynomial is obtained. A sufficient condition for instability is found out for the first time, pursuing a medium wavelength analysis. It depends on ratios (α and β) of the coefficients of viscosity, the thickness of the middle layer δ, surface tension ratio T and wave number K. This is a new analytical criterion for Rayleigh-Taylor instability of three-layer fluids. It recovers the results of the corresponding problem for two-layer fluids. Among the results obtained, it is observed that taking the coefficients of viscosity of 2nd and 3rd layers same can inhibit the effect of surface tension completely. For large wave number K, the thickness of the middle layer should be correspondingly small to keep the domain of dependence of the threshold wave number Kc constant for fixed α, β and T.

Invariant norm quantifying nonlinear content of Hamiltonian systems

Given a Hamiltonian system, one can represent it using a symplectic map. This symplectic map is specified by a set of homogeneous polynomials which are uniquely determined by the Hamiltonian. In this paper, we construct an invariant norm in the space of homogeneous polynomials of a given degree. This norm is a function of parameters characterizing the original Hamiltonian system. Such a norm has several potential applications. (C) 2010 Elsevier Inc. All rights reserved.

Curved composite beams—optimum lay-up for buckling by ranking

Instability of laminated curved composite beams made of repeated sublaminate construction is studied using finite element method. In repeated sublaminate construction, a full laminate is obtained by repeating a basic sublaminate which has a smaller number of plies. This paper deals with the determination of optimum lay-up for buckling by ranking of such composite curved beams (which may be solid or sandwich). For this purpose, use is made of a two-noded, 16 degress of freedom curved composite beam finite element. The displacements u, v, w of the element reference axis are expressed in terms of one-dimensional first-order Hermite interpolation polynomials, and line member assumptions are invoked in formulation of the elastic stiffness matrix and geometric stiffness matrix. The nonlinear expressions for the strains, occurring in beams subjected to axial, flexural and torsional loads, are incorporated in a general instability analysis. The computer program developed has been used, after extensive checking for correctness, to obtain optimum orientation scheme of the plies in the sublaminate so as to achieve maximum buckling load for typical curved solid/sandwich composite beams.

Entropy and dynamics of water in hydration layers of a bilayer

We compute the entropy and transport properties of water in the hydration layer of dipalmitoylphosphatidylcholine bilayer by using a recently developed theoretical scheme two-phase thermodynamic model, termed as 2PT method; S.-T. Lin et al., J. Chem. Phys. 119, 11792 (2003)] based on the translational and rotational velocity autocorrelation functions and their power spectra. The weights of translational and rotational power spectra shift from higher to lower frequency as one goes from the bilayer interface to the bulk. Water molecules near the bilayer head groups have substantially lower entropy (48.36 J/mol/K) than water molecules in the intermediate region (51.36 J/mol/K), which have again lower entropy than the molecules (60.52 J/mol/K) in bulk. Thus, the entropic contribution to the free energy change (T Delta S) of transferring an interface water molecule to the bulk is 3.65 kJ/mol and of transferring intermediate water to the bulk is 2.75 kJ/mol at 300 K, which is to be compared with 6.03 kJ/mol for melting of ice at 273 K. The translational diffusion of water in the vicinity of the head groups is found to be in a subdiffusive regime and the rotational diffusion constant increases going away from the interface. This behavior is supported by the slower reorientational relaxation of the dipole vector and OH bond vector of interfacial water. The ratio of reorientational relaxation time for Legendre polynomials of order 1 and 2 is approximately 2 for interface, intermediate, and bulk water, indicating the presence of jump dynamics in these water molecules. (C) 2010 American Institute of Physics. doi:10.1063/1.3494115]

Optimisation problems in wireless sensor networks

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating–dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating–dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs – these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating–dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

A field-consistent and variationally correct representation of transverse shear strains in the nine-noded plate element

We present a biquadratic Lagrangian plate bending element with consistent fields for the constrained transverse shear strain functions. A technique involving expansion of the strain interpolations in terms of Legendre polynomials is used to redistribute the kinematically derived shear strain fields so that the field-consistent forms (i.e. avoiding locking) are also variationally correct (i.e. do not violate the variational norms). Also, a rational method of isoparametric Jacobian transformation is incorporated so that the constrained covariant shear strain fields are always consistent in whatever general quadrilateral form the element may take. Finally the element is compared with another formulation which was recently published. The element is subjected to several robust bench mark tests and is found to pass all the tests efficiently.

A homotopy approach for stabilizing single-input systems with control structure constraints

A linear state feedback gain vector used in the control of a single input dynamical system may be constrained because of the way feedback is realized. Some examples of feedback realizations which impose constraints on the gain vector are: static output feedback, constant gain feedback for several operating points of a system, and two-controller feedback. We consider a general class of problems of stabilization of single input dynamical systems with such structural constraints and give a numerical method to solve them. Each of these problems is cast into a problem of solving a system of equalities and inequalities. In this formulation, the coefficients of the quadratic and linear factors of the closed-loop characteristic polynomial are the variables. To solve the system of equalities and inequalities, a continuous realization of the gradient projection method and a barrier method are used under the homotopy framework. Our method is illustrated with an example for each class of control structure constraint.

An Algebraic Implicitization and Specialization of Minimum KL-Divergence Models

In this paper we study representation of KL-divergence minimization, in the cases where integer sufficient statistics exists, using tools from polynomial algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. In particular, we also study the case of Kullback-Csiszar iteration scheme. We present implicit descriptions of these models and show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner bases method to compute an implicit representation of minimum KL-divergence models.

Time-Dependent Dynamics of a Planar Galaxy Model

Time-dependent models of collisionless stellar systems with harmonic potentials allowing for an essentially exact analytic description have recently been described. These include oscillating spheres and spheroids. This paper extends the analysis to time-dependent elliptic discs. Although restricted to two space dimensions, the systems are richer in that their parameters form a 10-dimensional phase space (in contrast to six for the earlier models). Apart from total energy and angular momentum, two additional conserved quantities emerge naturally. These can be chosen as the areas of extremal sections of the ellipsoidal region of phase space occupied by the system (their product gives the conserved volume). The present paper describes the construction of these models. An application to a tidal encounter is given which allows one to go beyond the impulse approximation and demonstrates the effects of rotation of the perturbed system on energy and angular-momentum transfer. The angular-momentum transfer is shown to scale inversely as the cube of the encounter velocity for an initial configuration of the perturbed galaxy with zero quadrupole moment.

A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science," pp. 514-519), which states that circled plus P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci.47, 85-93).

A note on resolving infeasibility in linear programs by constraint relaxation

We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.

Minimizing total completion time on a batch processing machine with job families

We consider the problem of minimizing the total completion time on a single batch processing machine. The set of jobs to be scheduled can be partitioned into a number of families, where all jobs in the same family have the same processing time. The machine can process at most B jobs simultaneously as a batch, and the processing time of a batch is equal to the processing time of the longest job in the batch. We analyze that properties of an optimal schedule and develop a dynamic programming algorithm of polynomial time complexity when the number of job families is fixed. The research is motivated by the problem of scheduling burn-in ovens in the semiconductor industry

Some new results regarding spikes and a heuristic for spike construction

his paper addresses the problem of minimizing the number of columns with superdiagonal nonzeroes (viz., spiked columns) in a square, nonsingular linear system of equations which is to be solved by Gaussian elimination. The exact focus is on a class of min-spike heuristics in which the rows and columns of the coefficient matrix are first permuted to block lower-triangular form. Subsequently, the number of spiked columns in each irreducible block and their heights above the diagonal are minimized heuristically. We show that ifevery column in an irreducible block has exactly two nonzeroes, i.e., is a doubleton, then there is exactly one spiked column. Further, if there is at least one non-doubleton column, there isalways an optimal permutation of rows and columns under whichnone of the doubleton columns are spiked. An analysis of a few benchmark linear programs suggests that singleton and doubleton columns can abound in practice. Hence, it appears that the results of this paper can be practically useful. In the rest of the paper, we develop a polynomial-time min-spike heuristic based on the above results and on a graph-theoretic interpretation of doubleton columns.