Multistable learning dynamics in second-order neural networks with time-varying delays

In this paper, we present new results on multistability and attractivity of second-order networks with unsupervised Hebbian-type learning component and time-varying delays. By using the properties of activation functions, we divide state space into invariant sets and establish new criteria of coexistence of equilibrium points which are exponentially stable. The attained results show that second-order synaptic interactions and learning behaviour have an important effect on the multistable convergence of the networks. Finally, numerical simulations will illustrate multistable learning dynamics of second-order networks.     

Multistability analysis for recurrent neural networks with unsaturating piecewise linear transfer functions

Multistability is a property necessary in neural networks in order to enable certain applications (e.g., decision making), where monostable networks can be computationally restrictive. This article focuses on the analysis of multistability for a class of recurrent neural networks with unsaturating piecewise linear transfer functions. It deals fully with the three basic properties of a multistable network: boundedness, global attractivity, and complete convergence. This article makes the following contributions: conditions based on local inhibition are derived that guarantee boundedness of some multistable networks, conditions are established for global attractivity, bounds on global attractive sets are obtained, complete convergence conditions for the network are developed using novel energy-like functions, and simulation examples are employed to illustrate the theory thus developed.     

一类二维神经网络的动力学研究*

神经网络的多稳定性已经吸引越来越多的科学家的兴趣。由于单稳定的神经网络可能存在计算局限,因此多稳定性神经网络的研究变得尤为必要。本文探讨了一类二维神经网络的可能存在的复杂动力学行为。首先利用反证法,获得了这类神经网络的一个不变集, 以保证从这个集合出发的所有轨迹最终都在这个集合中。然后利用向量场的旋转数理论,通过构建一个封闭曲线证明了这类网络平衡点的存在性。此外,利用反证法,证明了该网络的有界性。最后通过数值模拟,验证了分析所得结果。     

Global exponential stability in Lagrange sense for neutral type recurrent neural networks

In this paper, the global exponential stability in Lagrange sense for continuous neutral type recurrent neural networks (NRNNs) with multiple time delays is studied. Three different types of activation functions are considered, including general bounded and two types of sigmoid activation functions. By constructing appropriate Lyapunov functions, some easily verifiable criteria for the ultimate boundedness and global exponential attractivity of NRNNs are obtained. These results can be applied to monostable and multistable neural networks as well as chaos control and chaos synchronization.     

Double bound method for solving the p-center location problem

We give a review of existing methods for solving the absolute and vertex restricted p-center problems on networks and propose a new integer programming formulation, a tightened version of this formulation and a new method based on successive restrictions of the new formulation. A specialization of the new method with two-element restrictions obtains the optimal p-center solution by solving a series of simple structured integer programs in recognition form. This specialization is called the double bound method. A relaxation of the proposed formulation gives the tightest known lower bound in the literature (obtained earlier by Elloumi et al., [1]). A polynomial time algorithm is presented to compute this bound. New lower and upper bounds are proposed. Problems from the OR-Library [2] and TSPLIB [3] are solved by the proposed algorithms with up to 3038 nodes. Previous computational results were restricted to networks with at most 1817 nodes.     

The strong network orientation problem

This study presents models and heuristics for solving the strong network orientation problem (SNOP), which can model several tactical optimization problems of setting directions in urban networks. The objective is to set an orientation for each edge in an undirected graph such that the resulting digraph is strongly connected and the total travel distance between any pair of nodes is minimized (or maximized). Investigating tactical optimization problems such as SNOP is motivated by several challenges in urban networks due to the growth of population in urban areas, large number of daily trips, increasing price of maintaining urban networks, and the need to reduce air pollution and passive noise. Thus, a new trend is to utilize the urban networks better. In this context, we first use a multicommodity flow formulation to model the minimization problem. The maximization version is modeled by using the dual formulation of the shortest path problem. Then, scalable heuristic strategies for solving SNOP are investigated. For such purpose, we first propose basic components such as constructive heuristics, perturbations and local searches. They are combined into several metaheuristics based on local searches, multi-start and evolutionary schemes, i.e. Multistart Local Search, Iterated Local Search (ILS), Relaxed ILS, Evolutionary Local Search (ELS), Relaxed ELS, and Variable Neighborhood Search. Computational experiments have been performed to analyze the proposed methods in terms of efficiency and quality of solutions, using grid instances and a graph from downtown Clermont-Ferrand in France.     

Robustness of delayed multistable systems with application to droop-controlled inverter-based microgrids

Motivated by the problem of phase-locking in droop-controlled inverter-based microgrids with delays, the recently developed theory of input-to-state stability (ISS) for multistable systems is extended to the case of multistable systems with delayed dynamics. Sufficient conditions for ISS of delayed systems are presented using Lyapunov–Razumikhin functions. It is shown that ISS multistable systems are robust with respect to delays in a feedback. The derived theory is applied to two examples. First, the ISS property is established for the model of a nonlinear pendulum and delay-dependent robustness conditions are derived. Second, it is shown that, under certain assumptions, the problem of phase-locking analysis in droop-controlled inverter-based microgrids with delays can be reduced to the stability investigation of the nonlinear pendulum. For this case, corresponding delay-dependent conditions for asymptotic phase-locking are given.     

A Lagrangean Approach to Network Design Problems

Network design is a very important issue in the area of telecommunications and computer networks, where there is a large need for construction of new networks. This is due to technological development (fiber optics for telecommunication) and new ways of usage (Internet for computer networks). Optimal design of such networks requires formulation and solution of new optimization models. In this paper, we formulate several fixed charge network design models, capacitated or uncapacitated, directed or undirected, possibly with staircase costs, and survivability requirements. We propose a common solution approach for all these problems, based on Lagrangean relaxation, subgradient optimization and primal heuristics, which together form a Lagrangean heuristic. The Lagrangean heuristic can be incorporated into a branch-and-bound framework, if the exact optimal solution must be found. The approach has been tested on problems of various structures and sizes, and computational results are presented.     

Dynamical stability conditions for recurrent neural networks with unsaturating piecewise linear transfer functions

We establish two conditions that ensure the nondivergence of additive recurrent networks with unsaturating piecewise linear transfer functions, also called linear threshold or semilinear transfer functions. As Hahnloser, Sarpeshkar, Mahowald, Douglas, and Seung (2000) showed, networks of this type can be efficiently built in silicon and exhibit the coexistence of digital selection and analog amplification in a single circuit. To obtain this behavior, the network must be multistable and nondivergent, and our conditions allow determining the regimes where this can be achieved with maximal recurrent amplification. The first condition can be applied to nonsymmetric networks and has a simple interpretation of requiring that the strength of local inhibition match the sum over excitatory weights converging onto a neuron. The second condition is restricted to symmetric networks, but can also take into account the stabilizing effect of nonlocal inhibitory interactions. We demonstrate the application of the conditions on a simple example and the orientation-selectivity model of Ben-Yishai, Lev Bar-Or, and Sompolinsky (1995). We show that the conditions can be used to identify in their model regions of maximal orientation-selective amplification and symmetry breaking.     

Flows in dynamic networks with aggregate arc capacities

Dynamic networks are characterized by transit times on edges. Dynamic flow problems consider transshipment problems in dynamic networks. We introduce a new version of dynamic flow problems, called bridge problem. The bridge problem has practical importance and raises interesting theoretical issues. We show that the bridge problem is NP-complete. Traditional static flow techniques for solving dynamic flow problems do not extend to the new problem. We give a linear programming formulation for the bridge problem which is based on the time-expanded network of the original dynamic network.     

Core-Edge design of storage area networks—A Single-edge formulation with problem-specific cuts

Optimization and heuristic methods for the design of medium to large storage area networks (SANs) are in the early stages of development, but are required if large clustered storage systems are to become a viable alternative to expensive monolithic storage. We present here a new mixed-integer formulation for optimal design of a storage area network. Our formulation models the Single-edge Core-Edge topology. Using a testbed of medium to large problems, we compare the solution times for our new formulation to the current benchmark in the literature—our formulation solves in significantly less time with an off-the-shelf optimization software package. We also generate problem-specific cuts to further reduce the solution time for our formulation. An algorithm, which includes an integer programming subproblem, is described for generating some of these cuts. For all test problems, the cuts yield a further reduction in the solution time.     

Gamma deployment problem in grids: hardness and new integer linear programming formulation

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.     

Decision models for designing and planning private communication networks

We consider the recently developed reconfigurable digital data networks consisting of T1/T3 circuits and Digital Crossconnect Systems (DCSs). A DCS is a device to patch base channels electronically from one T1/T3 circuit to another with a negligible queuing delay at the connecting node. We present new decision models for the design and circuit leasing policies of such digital backbone networks. Our model takes advantage of the special capabilities of the DCS technology and is likely to result in remarkable economic gains for the private network users. The formulation and analyses presented here simultaneously address the following problems: physical link and capacity selection, logical network configuration and channel assignment, and traffic routing on the logical network. The problem formulation results in a large-scale non-linear mixed integer program, and we propose an efficient solution methodology employing Lagrangean relaxation and subgradient optimization. Several numerical results illustrate the utility of our approach for these complex problems. We show that the economies of scale built into the tariff structure of these digital networks can be successfully exploited, and that the inherent flexibility of DCSs leads to logical networks that are dramatically different from their underlying physical topologies.     

A rapid learning and dynamic stepwise updating algorithm for flatneural networks and the application to time-series prediction

A fast learning algorithm is proposed to find an optimal weights of the flat neural networks (especially, the functional-link network). Although the flat networks are used for nonlinear function approximation, they can be formulated as linear systems. Thus, the weights of the networks can be solved easily using a linear least-square method. This formulation makes it easier to update the weights instantly for both a new added pattern and a new added enhancement node. A dynamic stepwise updating algorithm is proposed to update the weights of the system on-the-fly. The model is tested on several time-series data including an infrared laser data set, a chaotic time-series, a monthly flour price data set, and a nonlinear system identification problem. The simulation results are compared to existing models in which more complex architectures and more costly training are needed. The results indicate that the proposed model is very attractive to real-time processes.     

多速率无线网状网中低延迟广播研究

多速率广播是多速率无线网状网的特有问题。常用的基于最小连通支配集的广播树构造算法不能有效降低多速率无线网状网的全网广播延迟。提出了一种分布式多速率广播树构造算法。该算法与现有算法的不同之处在于生成广播节点的同时还根据其局部拓扑信息选择合适的广播速率。与现有算法相比,该算法显著降低了全网广播延迟。     

A new self-routing multicast network

In this paper, we propose a design for a new self-routing multicast network which can realize arbitrary multicast assignments between its inputs and outputs without any blocking. The network design uses a recursive decomposition approach and is based on the binary radix sorting concept. All functional components of the network are reverse banyan networks. Specifically, the new multicast network is recursively constructed by cascading a binary splitting network and two half-size multicast networks. The binary splitting network, in turn, consists of two recursively constructed reverse banyan networks. The first reverse banyan network serves as a scatter network and the second reverse banyan network serves as a quasisorting network. The advantage of this approach is to provide a way to self-route multicast assignments through the network and a possibility to reuse part of network to reduce the network cost. The new multicast network we design is compared favorably with the previously proposed multicast networks. It uses O(n log² n) logic gates, and has O(log² n) depth and O(log² n) routing time where the unit of time is a gate delay. By reusing part of the network, the feedback implementation of the network can further reduce the network cost to O(n log n)     

Avoiding local minima in the potential field method using input-to-state stability

Supported by a novel field definition and recent control theory results, a new method to avoid local minima is proposed. It is formally shown that the system has an attracting equilibrium at the target point, repelling equilibriums in the obstacle centers and saddle points on the borders. Those unstable equilibriums are avoided capitalizing on the established Input-to-State Stability (ISS) property of this multistable system. The proposed modification of the PF method is shown to be effective by simulation for a two variable integrator and then applied to a unicycle-like wheeled mobile robots which is subject to additive input disturbances.     

A co-tree flows formulation for steady state in water distribution networks

This article describes a co-tree flows formulation for steady state simulation in water distribution networks, which reduces the original governing system of equations into a smaller set, expressed in terms of the co-tree chord flows. The formulation is derived from graph theory and matrix partitioning. The reduction in the size of the set of equations does not require any new conditions on the initial solution estimate, unlike the loop flow correction method. The proposed formulation is numerically equivalent to the link flow method. However, it requires, about 5% for the Jacobian memory storage requirements of the link flow method, thereby also drastically reducing the time of execution for solving the resulting nonlinear system, as well. Furthermore, the Jacobian matrix of the new method is symmetrical, which can reduce the memory storage by half. Thus, even for large distribution systems, there is no need for sparse matrix solvers, which trade off the storage memory with time of execution in order to manage the data requirements.     

On the discrete-time dynamics of the basic Hebbian neural network node

In this paper, the dynamical behavior of the basic node used for constructing Hebbian artificial neural networks (NNs) is analyzed. Hebbian NNs are employed in communications and signal processing applications, among others. They have been traditionally studied on a continuous-time formulation whose validity is justified via some analytical procedures that presume, among other hypotheses, a specific asymptotic behavior of the learning gain. The main contribution of this paper is the study of a deterministic discrete-time (DDT) formulation that characterizes the average evolution of the node, preserving the discrete-time form of the original network and gathering a more realistic behavior of the learning gain. The new deterministic discrete-time model provides some unstability results (critical for the case of large similar variance signals) which are drastically different to the ones known for the continuous-time formulation. Simulation examples support the presented results, illustrating the practical limitations of the basic Hebbian model.     

Exact geometry considerations in buckling analysis of trusses

This paper is concerned with the exact geometrical formulation for truss buckling. Based on the assumptions of large member rotations but small strains, a generalized formulation is presented for the nonlinear analysis of trusses in their deformed state. Conditions for instability are included and the snap-through load is accurately predicted for various examples by using the Newton-Raphson approach. The formulation is used to study the response of cable networks to external loads. Under uniformly distributed loads the networks behaved linearly with very small nodal displacements. In other loading cases, where the load distribution is unsymmetrical and the total load applied is smaller than the uniform loading, very large displacements occurred with significant nonlinearities.