A parametrization of piecewise linear Lyapunov functions via linear programming

In this paper, we present a parametrization of piecewise linear (PWL) Lyapunov functions. To this end, we consider the class of all continuous PWL functions defined over a simplicial partition. We take advantage of a recently developed high level canonical PWL (HL CPWL) representation, which expresses the PWL function in a compact and closed form. Once the parametrization problem is properly stated, we focus on its application to the stabiilty analysis of dynamic systems. We consider uncertain non-linear systems and extend the sector condition obtained by Ohta et al. In addition, we propose a method of selecting an optimal candidate. One of the main advantages of this approach is that the parametrization and choice of the Lyapunov candidate, as well as the stability analysis, result in linear programming problems.     

Fitting optimal piecewise linear functions using genetic algorithms

Constructing a model for data in R² is a common problem in many scientific fields, including pattern recognition, computer vision, and applied mathematics. Often little is known about the process which generated the data or its statistical properties. For example, in fitting a piecewise linear model, the number of pieces, as well as the knot locations, may be unknown. Hence, the method used to build the statistical model should have few assumptions, yet, still provide a model that is optimal in some sense. Such methods can be designed through the use of genetic algorithms. We examine the use of genetic algorithms to fit piecewise linear functions to data in R². The number of pieces, the location of the knots, and the underlying distribution of the data are assumed to be unknown. We discuss existing methods which attempt to solve this problem and introduce a new method which employs genetic algorithms to optimize the number and location of the pieces. Experimental results are presented which demonstrate the performance of our method and compare it to the performance of several existing methods, We conclude that our method represents a valuable tool for fitting both robust and nonrobust piecewise linear functions     

Inverse Laplace transform by piecewise linear polynomial functions

A new approximation method with piecewise linear polynomial functions based on the application of the operational matrix for integration is presented. It is shown that this approximation is more satisfactory than the block-pulse approximation. Two illustrative examples are given.     

Operational matrices of piecewise linear polynomial functions with application to linear time-varying systems

Application of the piecewise linear polynomial functions expansion is extended to linear time-varying systems. With the treatment of the product of two time functions, two types of operational matrix are developed. By applying these operational matrices, the dynamic equations are transformed into a set of algebraic equations. A recursive algorithm is derived and the system equations can be solved with very low dimensional matrix inversions. This represents a considerable saving of computer memory capacity and computing time.     

Numerical approach for solving linear Fredholm integro-differential equation with piecewise intervals by Bernoulli polynomials

In this paper a numerical method is given for the solution of linear Fredholm integro-differential equation (FIDE) with piecewise intervals under the mixed conditions using the Bernoulli polynomials. The aim of this article is to present an efficient numerical procedure for solving linear FIDE with piecewise intervals. This method transforms linear FIDE with piecewise intervals and the given conditions into matrix equation which corresponds to a system of linear algebraic equation. Finally, some experiments and their numerical solutions are given. The results reveal that this method is reliable and efficient.     

Pattern classification by concurrently determined piecewise linear and convex discriminant functions

This paper develops a new methodology for pattern classification by concurrently determined k piecewise linear and convex discriminant functions. Toward the end, we design a new l₁-norm distance metric for measuring misclassification errors and use it to develop a mixed 0–1 integer and linear program (MILP) for the k piecewise linear and convex separation of data. The proposed model is meritorious in that it considers the synergy as well as the individual role of the k hyperplanes in constructing a decision surface and exploits the advances in theory and algorithms and the advent of powerful softwares for MILP for its solution. With artificially created data, we illustrate pros and cons of pattern classification by the proposed methodology. With six benchmark classification datasets, we demonstrate that the proposed approach is effective and competitive with well-established learning methods. In summary, the classifiers constructed by the proposed approach obtain the best prediction rates on three of the six datasets and the second best records for two of the remaining three datasets.     

Minimum energy control of time delay systems via piecewise linear polynomial functions

The piecewise linear polynomial function approach to the minimum energy control of linear systems with time delay, is presented in this paper. The concepts of a delay shift matrix and an operational matrix for integration are employed in solving the related state and costate equations containing terms with advanced and delayed arguments. An attractive feature of the present method is its ultimate simplicity and convenience. The differential equations with delay and advance terms are converted into a set of linear algebraic equations using a recurrence algorithm. An example demonstrates the accuracy of the method.     

Multistability of discrete-time recurrent neural networks with unsaturating piecewise linear activation functions

This paper studies the multistability of a class of discrete-time recurrent neural networks with unsaturating piecewise linear activation functions. It addresses the nondivergence, global attractivity, and complete stability of the networks. Using the local inhibition, conditions for nondivergence are derived, which not only guarantee nondivergence, but also allow for the existence of multiequilibrium points. Under these nondivergence conditions, global attractive compact sets are obtained. Complete stability is studied via constructing novel energy functions and using the well-known Cauchy Convergence Principle. Examples and simulation results are used to illustrate the theory.     

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.     

确定型格值有限自动机的最小化

给出了确定型格值有限自动机的定义,并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFA M=Q,Σ,δ,q₀,σ的实质是求取Q/R_k。由此以可到达状态为基础引入了等价关系R_k、S_k与商集Q/S_k,证明了R_k=R_k-1∩S_k,由此得到Q/R_k的等价类为Q/R_k-1中等价类与Q/S_k中等价类的非空交集全体。引入了H_k,并证明了可由H_k求取Q/S_k,从而得到仅利用集合运算便可求取Q/R_k的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。     

Global analysis of piecewise linear systems using impact maps and surface Lyapunov functions

This paper presents an entirely new constructive global analysis methodology for a class of hybrid systems known as piecewise linear systems (PLS). This methodology infers global properties of PLS solely by studying the behavior at switching surfaces associated with PLS. The main idea is to analyze impact maps, i.e., maps from one switching surface to the next switching surface. Such maps are known to be "unfriendly" maps in the sense that they are highly nonlinear, multivalued, and not continuous. We found, however, that an impact map induced by an linear time-invariant flow between two switching surfaces can be represented as a linear transformation analytically parametrized by a scalar function of the state. This representation of impact maps allows the search for surface Lyapunov functions (SuLF) to be done by simply solving a semidefinite program, allowing global asymptotic stability, robustness, and performance of limit cycles and equilibrium points of PLS to be efficiently checked. This new analysis methodology has been applied to relay feedback, on/off and saturation systems, where it has shown to be very successful in globally analyzing a large number of examples. In fact, it is still an open problem whether there exists an example with a globally stable limit cycle or equilibrium point that cannot be successfully analyzed with this new methodology. Examples analyzed include systems of relative degree larger than one and of high dimension, for which no other analysis methodology could be applied. This success in globally analyzing certain classes of PLS has shown the power of this new methodology, and suggests its potential toward the analysis of larger and more complex PLS.     

Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions

We consider a cumulative scheduling problem where a task duration and resource consumption are not fixed. The consumption profile of the task, which can vary continuously over time, is a decision variable of the problem to be determined and a task is completed as soon as the integration over its time window of a non-decreasing and continuous processing rate function of the consumption profile has reached a predefined amount of energy. The goal is to find a feasible schedule, which is an NP-hard problem. For the case where functions are concave and piecewise linear, we present two propagation algorithms. The first one is the adaptation to concave functions of the variant of the energetic reasoning previously established for linear functions. Furthermore, a full characterization of the relevant intervals for time-window adjustments is provided. The second algorithm combines a flow-based checker with time-bound adjustments derived from the time-table disjunctive reasoning for the cumulative constraint. Complementarity of the algorithms is assessed via their integration in a hybrid branch-and-bound and computational experiments on small-size instances.     

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.     

A class of C 2piecewise quintic polynomials

A new class of C ² piecewise quintic interpolatory polynomials is defined. It is shown that this new class contains a number of interpolatory functions which present practical advantages, when compared with the conventional cubic spline.