Robustly complete synthesis of sampled-data control for continuous-time nonlinear systems with reach-and-stay objectives

Formal methods are becoming favorable for control and verification of safety-critical systems because of the rigorous model-based computation. Relying on an over-approximated model of the original system behaviors, formal control synthesis algorithms are not often complete, which means that a controller cannot necessarily be synthesized even if there exists one. The main result of this paper shows that, for continuous-time nonlinear systems, a sample-and-hold control strategy for a reach-and-stay specification can be synthesized whenever such a strategy exists for the same system with its dynamics perturbed by small disturbances. Control synthesis is carried out by a fixed-point algorithm that adaptively partitions the system state space into a finite number of cells. In each iteration, the reachable set from each cell after one sampling time is over-approximated within a precision determined by the bound of the disturbances. To meet such a requirement, we integrate validated high-order Taylor expansion of the system solution over one sampling period into every fixed-point iteration and provide a criterion for choosing the Taylor order and the partition precision. Two nonlinear system examples are given to illustrate the effectiveness of the proposed method.     

Comparison of path-complete Lyapunov functions via template-dependent lifts

This paper investigates, in the context of discrete-time switched systems, the problem of comparison for path-complete stability certificates. We introduce and study abstract operations on path-complete graphs, called lifts, which allow us to recover previous results in a general framework. Moreover, this approach highlights the existing relations between the analytical properties of the chosen set of candidate Lyapunov functions (the template) and the admissibility of certain lifts. This provides a new methodology for the characterization of the ordering relation of path-complete Lyapunov functions criteria, when a particular template is chosen. We apply our results to specific templates, notably the sets of primal and dual copositive norms, providing new stability certificates for positive switched systems. These tools are finally illustrated with the aim of numerical examples.     

Lack of dissipativity is not symplecticness

We show that, when numerically integrating Hamiltonian problems, nondissipative numerical methods do not in general share the advantages possessed by symplectic integrators. Here a numerical method is called nondissipative if, when applied with a small stepsize to the test equationdy/dt = iy, real, has amplification factors of unit modulus. We construct a fourth order, nondissipative, explicit Runge-Kutta-Nyström procedure with small error constants. Numerical experiments show that this scheme does not perform efficiently in the numerical integration of Hamiltonian problems.This research has been supported by project DGICYT PB92-254.     

Finding normal solutions in piecewise linear programming

Letf: ⁿ (–, ] be a convex polyhedral function. We show that if any standard active set method for quadratic programming (QP) findsx(t)= arg min _x ¦x¦²/2+t f(x) for somet> 0, then its final working set defines a simple equality QP subproblem, whose Lagrange multiplier can be used both for testing ift is large enough forx(t) to coincide with the normal minimizer off, and for increasingt otherwise. The QP subproblem may easily be solved via the matrix factorizations used for findingx(t). This opens up the way for efficient implementations. We also give finite methods for computing the whole trajectory {x(t)} _t 0, minimizingf over an ellipsoid, and choosing penalty parameters inL ₁QP methods for strictly convex QP.This research was supported by the State Committee for Scientific Research under Grant 8S50502206.     

Potential reduction method for harmonically convex programming

In this paper, we introduce a potential reduction method for harmonically convex programming. We show that, if the objective function and them constraint functions are allk-harmonically convex in the feasible set, then the number of iterations needed to find an -optimal solution is bounded by a polynomial inm, k, and log(1/). The method requires either the optimal objective value of the problem or an upper bound of the harmonic constantk as a working parameter. Moreover, we discuss the relation between the harmonic convexity condition used in this paper and some other convexity and smoothness conditions used in the literature.The authors like to thank Dr. Hans Nieuwenhuis for carefully reading this paper and the anonymous referees for the worthy suggestions.     

Multistep methods for differential algebraic equations

Multistep methods for the differential/algebraic equations (DAEs) in the form of

Analytical solutions of the lattice Boltzmann BGK model

Analytical solutions of the two-dimensional triangular and square lattice Boltzmann BGK models have been obtained for the plane Poiseuille flow and the plane Couette flow. The analytical solutions are written in terms of the characteristic velocity of the flow, the single relaxation time , and the lattice spacing. The analytic solutions are the exact representation of these two flows without any approximation. Using the analytical solution, it is shown that in Poiseuille flow the bounce-back boundary condition introduces an error of first order in the lattice spacing. The boundary condition used by Kadanoffet al. in lattice gas automata to simulate Poiseuille flow is also considered for the triangular lattice Boltzmann BGK model. An analytical solution is obtained and used to show that the boundary condition introduces an error of second order in the lattice spacing.     

Lattice-BGK approach to simulating granular flows

Many continuum theories for granular flow produce an equation of motion for the fluctuating kinetic energy density (granular temperature) that accounts for the energy lost in inelastic collisions. Apart from the presence of an extra dissipative term, this equation is very similar in form to the usual temperature equation in hydrodynamics. It is shown how a lattice-kinetic model based on the Bhatnagar-Gross-Krook (BGK) equation that was previously derived for a miscible two-component fluid may be modified to model the continuum equations for granular flow. This is done by noting that the variable corresponding to the concentration of one species follows an equation that is essentially analogous to the granular temperature equation. A simulation of an unforced granular fluid using the modified model reproduces the phenomenon of clustering instability, namely the spontaneous agglomeration of particles into dense clusters, which occurs generically in all granular flows. The success of the continuum theory in capturing the gross features of this basic phenomenon is discussed. Some shear flow simulations are also presented.     

Local minima of the trust region problem

We consider the minimization of a quadratic formzVz+2zq subject to the two-norm constraint z=. The problem received considerable attention in the literature, notably due to its applications to a class of trust region methods in nonlinear optimization. While the previous studies were concerned with just the global minimum of the problem, we investigate the existence of all local minima. The problem is approached via the dual Lagrangian, and the necessary and sufficient conditions for the existence of all local minima are derived. We also examine the suitability of the conventional numerical techniques used to solve the problem to a class of single-instruction multiple-data computers known as processor arrays (in our case, AMT DAP 610). Simultaneously, we introduce certain hardware-oriented multisection algorithms, showing their efficiency in the case of small to medium size problems.This research was partially supported by the National Physical Laboratories of England under Contract RTP2/155/127.     

Parallelism across the steps in iterated Runge-Kutta methods for stiff initial value problems

For the parallel integration of stiff initial value problems (IVPs) three main approaches can be distinguished: approaches based on parallelism across the problem, on parallelism across the method and on parallelism across the steps. The first type of parallelism does not require special integration methods can be exploited within any available IVP solver. The methodparallel approach received some attention in the case of Runge-Kutta based methods. For these methods, the required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The step-parallel iteraction process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to solve the four-stage Radau IIA corrector used in our experiments within a few effective iterations per step and to achieve speed-up factors up to 10 with respect to the best sequential codes.The research reported in this paper was partly supported by the Technology Foundation (STW) in the Netherlands.