Resource-optimal control of linear systems

A numerical method for minimizing the resource consumption for linear dynamical systems is proposed. It is based on forming a finite-time control that steers the linear system from an arbitrary initial state to the desired terminal state in a given fixed time; this control gives an approximate solution of the problem. It is shown that the structure of the finite-time control makes it possible to determine the structure of the resource-optimal control. A method for determining an initial approximation is described, and an iterative algorithm for calculating the optimal control is proposed. A system of linear algebraic equations relating the deviations of the initial conditions in the adjoint system to the deviations of the phase coordinates from the prescribed terminal state at the terminal point in time is obtained. A computational algorithm is described. The radius of local convergence is found and the quadratic rate of convergence is established. It is proved that the computational procedure and the sequence of controls converge to the resource-optimal control.     

A transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

Convergence of a feasible directions algorithm for a distributed optimal control problem of parabolic type with terminal inequality constraints

In this paper, we consider a class of optimal control problems with control and terminal inequality constraints, where the system dynamics is governed by a linear second-order parabolic partial differential equation with first boundary condition. A feasible direction algorithm for solving this class of optimal control problems has already been obtained in the literature. The aim of this paper is to improve the convergence result by using a topology arising in the study of relaxed controls.     

A relaxation method for solving systems with infinitely many linear inequalities

The problem of finding a feasible solution to a linear inequality system arises in numerous contexts. We consider solving linear semi-infinite inequality systems via an extension of the relaxation method for finite linear inequality systems. The difficulties are discussed and a convergence result is derived under fairly general assumptions on a large class of linear semi-infinite inequality systems.     

Approximate solution of the linear quadratic control problem

In this paper the Legendre polynomials method is applied in order to find the approximate solution of the linear quadratic optimal control problem with imposed inequality constraints. The computational procedure based on the obtained results, is presented     

Optimal control computation for linear time-lag systems with linear terminal constraints

A computational scheme using the technique of control parameterization is developed for solving a class of optimal control problems involving linear hereditary systems with bounded control region and linear terminal constraints. Several examples have been solved to illustrate the efficiency of the technique.The authors wish to thank Dr. B. D. Craven for pointing out an error in an earlier version of this paper.From January 1985, Associate Professor, Department of Industrial and Systems Engineering, National University of Singapore, Kent Ridge, Singapore.     

A new result on finite-time control of singular linear time-delay systems

In this paper, problem of robust finite-time stability and control is first time discussed for singular linear time-delay systems subject to disturbance. By developing delay singular value decomposition approach combining with linear matrix inequality (LMI) technique, new sufficient conditions for the existence of such controllers are proposed in terms of the solvability to a set of LMIs. Finally, a numerical example is given to illustrate the effectiveness of the proposed method.     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

A unified framework for linear control problems with state-variable inequality constraints

This paper briefly reviews the literature on necessary optimality conditions for optimal control problems with state-variable inequality constraints. Then, it attempts to unify the treatment of linear optimal control problems with state-variable inequality constraints in the framework of continuous linear programming. The duality theory in this framework makes it possible to relate the adjoint variables arising in different formulations of a problem; these relationships are illustrated by the use of a simple example. This framework also allows more general problems and admits a simplex-like algorithm to solve these problems.This research was partially supported by Grant No. A4619 from the National Research Council of Canada to the first author. The first author also acknowledges the support provided by the Brookhaven National Laboratory, where he conducted his research.     

Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games

We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study.     

A feasible directions algorithm for time-lag optimal control problems with control and terminal inequality constraints

A computational algorithm for a class of time-lag optimal control problems involving control and terminal inequality constraints is presented. The convergence properties of the algorithm is also investigated. To test the algorithm, an example is solved.This work was partially supported by the Australian Research Grant Committee.     

Uniform saturation in linear inequality systems

Redundant constraints in linear inequality systems can be characterized as those inequalities that can be removed from an arbitrary linear optimization problem posed on its solution set without modifying its value and its optimal set. A constraint is saturated in a given linear optimization problem when it is binding at the optimal set. Saturation is a property related with the preservation of the value and the optimal set under the elimination of the given constraint, phenomena which can be seen as weaker forms of excess information in linear optimization problems. We say that an inequality of a given linear inequality system is uniformly saturated when it is saturated for any solvable linear optimization problem posed on its solution set. This paper characterizes the uniform saturated inequalities and other related classes of inequalities. This work was supported by the MCYT of Spain and FEDER of UE, Grant BFM2002-04114-C02-01.     

General criteria for redundant and nonredundant linear inequalities

A system of linear inequalities subject to nonnegativity restrictions is considered. General criteria which are necessary and sufficient for a linear inequality to be redundant are derived. This general characterization provides a basis for unifying some of the existing techniques. After taking into consideration the existence of redundant linear inequalities, general necessary and sufficient criteria for a linear inequality to be nonredundant are also obtained. An example is given to illustrate the application of these new criteria.The author wishes to thank the referee for his comments.     

A primal conical linear programming algorithm

This paper completes the treatment of the conical approach to linear programming, introducing a conical primal algorithm of linear programming. After some recalls and improvements of a previous paper dealing with such an approach, the algorithm is defined. A first convergence result is then proved, which, along with a series of lemmata, allows to prove that the algorithm terminates in a finite number of steps     

Network synchronization under distributed delayed impulsive control: Average delayed impulsive weight approach

This paper mainly investigates synchronization of complex dynamical networks (CDNs) with both system delay and coupled delay through distributed delayed impulsive control. Instead of constraining the impulsive weight and impulsive delay one by one, a new concept of average delayed impulsive weight is proposed to obtain more relaxed conditions. Subsequently, based on the impulsive control topology, Lyapunov theory and linear matrix inequality (LMI) design, certain flexible criteria of global exponential synchronization (GES) are given and the corresponding convergence rate is estimated. It is interesting to see that the CDNs can still achieve synchronization under comprehensive conditions though impulsive weights work negatively. Namely, the delays in impulsive control are able to promote synchronization potentially. Finally, simulations are given to show that the distributed delayed impulsive control can not only speeds up the convergence rate for synchronized networks, but also facilitates synchronization for desynchronized networks. In addition, the obtained results can be applied to unmanned craft systems.     

Stable barrier-projection and barrier-Newton methods in linear programming

The present paper is devoted to the application of the space transformation techniques for solving linear programming problems. By using a surjective mapping the original constrained optimization problem is transformed to a problem in a new space with only equality constraints. For the numerical solution of the latter problem the stable version of the gradient-projection and Newton's methods are used. After an inverse transformation to the original space a family of numerical methods for solving optimization problems with equality and inequality constraints is obtained. The proposed algorithms are based on the numerical integration of the systems of ordinary differential equations. These algorithms do not require feasibility of the starting and current points, but they preserve feasibility. As a result of a space transformation the vector fields of differential equations are changed and additional terms are introduced which serve as a barrier preventing the trajectories from leaving the feasible set. A proof of a convergence is given.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.Research was supported by the grant N93-012-450 from Russian Scientific Fund.     

Generalization of Murty's direct algorithm to linear and convex quadratic programming

Murty's algorithm for the linear complementarity problem is generalized to solve the optimality conditions for linear and convex quadratic programming problems with both equality and inequality constraints. An implementation is suggested which provides both efficiency and tight error control. Numerical experiments as well as field tests in various applications show favorable results.The author thanks K. G. Murty for his encouragement and helpful comments.     

Characterization and computation of control invariant sets for linear impulsive control systems

Impulsive control systems are suitable to describe and control a venue of real-life problems, going from disease treatment to aerospace guidance. The main characteristic of such systems is that they evolve freely in-between impulsive actions, which makes it difficult to guarantee its permanence in a given state-space region. In this work, we develop a method for characterizing and computing approximations to the maximal control invariant sets for linear impulsive control systems, which can be explicitly used to formulate a set-based model predictive controller. We approach this task using a tractable and non-conservative characterization of the admissible state sets, namely the states whose free response remains within given constraints, emerging from a spectrahedron representation of such sets for systems with rational eigenvalues. The so-obtained impulsive control invariant set is then explicitly used as a terminal set of a predictive controller, which guarantees the feasibly asymptotic convergence to a target set containing the invariant set. Necessary conditions under which an arbitrary target set contains an impulsive control invariant set (and moreover, an impulsive control equilibrium set) are also provided, while the controller performance are tested by means of two simulation examples.     

A constraint generation algorithm for large scale linear programs using multiple-points separation

In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that uses several points to generate violated constraints. The complexity of this separation procedure and of some related problems is studied. Also, preliminary computational results about the advantages of using multiple-points separation procedures over traditional separation procedures are given for random linear programs and survivable network design. They illustrate that, for some specific families of linear programs, multiple-points separation can be computationally effective.