Search

In an earlier analysis of strong variation algorithms for optimal control problems with endpoint inequality constraints, Mayne and Polak provided conditions under which accumulation points satisfy a condition requiring a certain optimality function, used in the algorithms to generate search directions, to be nonnegative for all controls. The aim of this paper is to clarify the nature of this optimality condition, which we call the first-order minimax condition, and of a related integrated form of the condition, which, also, is implicit in past algorithm convergence analysis. We consider these conditions, separately, when a pathwise state constraint is, and is not, included in the problem formulation. When there are no pathwise state constraints, we show that the integrated first-order minimax condition is equivalent to the minimum principle and that the minimum principle (and equivalent integrated first-order minimax condition) is strictly stronger than the first-order minimax condition. For problems with state constraints, we establish that the integrated first-order minimax condition and the minimum principle are, once again, equivalent. But, in the state constrained context, it is no longer the case that the minimum principle is stronger than the first-order minimax condition, or vice versa. An example confirms the perhaps surprising fact that the first-order minimax condition is a distinct optimality condition that can provide information, for problems with state constraints, in some circumstances when the minimum principle fails to do so.

We propose in this note a method for computing the solution to the infinite horizon continuous-time constrained linear quadratic regulator. The method is based on two main ingredients: a multigrid method for placing a finite number of time intervals, and a piece-wise linear parameterization of the input within the intervals. The input values at the decision-time points and slopes within the time intervals are computed via quadratic programs (QPs). The grids are gradually refined to efficiently improve the accuracy of the solution, and the required matrices and vectors for all QPs are computed offline and stored to improve the online efficiency. Two examples are presented to show the main characteristics of the proposed method.

© 2015, The Author(s).This note addresses the tracking problem for model predictive control. It presents simple procedures for both linear and nonlinear constrained model predictive control when the desired equilibrium state is any point in a specified set. The resultant region of attraction is the union of the regions of attraction for each equilibrium state in the specified set and is therefore larger than that obtained when conventional model predictive control is employed.

This note provides results on approximating the minimal robust positively invariant (mRPI) set (also known as the 0-reachable set) of an asymptotically stable discrete-time linear time-invariant system. It is assumed that the disturbance is bounded, persistent and acts additively on the state and that the constraints on the disturbance are polyhedral. Results are given that allow for the computation of a robust positively invariant, outer approximation of the mRPI set. Conditions are also given that allow one to a priori specify the accuracy of this approximation.

This paper makes two contributionss firstly, it provides a characterization of the solution of the optimal control problem for piecewise affine discrete-time systems with a quadratic cost function (the generally preferred option) and, secondly, provides a simple method (reverse transformation) for solving this and the previously solved e∞ problem. The characterization is useful for on-line implementation.

Many design objectives may be formulated as semi-infinite constraints. Examples in control design, for example, include hard constraints on time and frequency responses and robustness constraints. A useful algorithm for solving such inequalities is the outer approximations algorithm. One version of an outer approximations algorithm for solving an infinite set of inequalitiesϕ(x, y) ≤0 for allyeY proceeds by solving, at iterationi of the master algorithm, a finite set of inequalities (ϕ(x, y) ≤0 for allyeYi) to yieldxi and then updatingYi toYi+1=Y i ∪ {yi} whereyie arg max {ϕ(xi,y)¦ye Y}. Since global optimization is computationally extremely expensive, it is desirable to reduce the number of such optimizations. We present, in this paper, a modified version of the outer approximations algorithm which achieves this objective.

This paper introduces two new techniques for the analysis and construction of semi-infinite optimization algorithms. The first is a very simple technique for establishing the superlinear rate of convergence of semi-infinite optimization algorithms. The second technique enables specification of discretization rules that preserve the superlinear convergence of conceptual superlinearly converging semi-infinite optimization algorithms.Natural extensions of Newton’s method to semi-infinite optimization are used as a vehicle for presenting the techniques. In particular, it is shown that both local and global versions of the conceptual extension of Newton’s method converge Q-superlinearly, with rate at least ${3 / 2}$, and that their implementations, based on the discretization rules, retain this rate of convergence.

Abstract We present a method for computing the solution to the infinite horizon continuous-time constrained linear quadratic regulator (CLQR). The method relies on two main features: a multi-grid method for placing a finite number of time intervals, and a piece-wise linear parameterization of the input within the intervals. The input values at the grid points and slopes within the time intervals are computed via quadratic programs (QPs). The grids are gradually refined to efficiently improve the accuracy of the solution, and the required matrices and vectors for all QPs are computed offline and stored to improve the online efficiency.We present two examples, a single-input single-output unstable system and a three-input three-output stable system, to show the main characteristics of the proposed computation method.

Algorithms for solving the problem of minimizing the maximum of a finite number of functions are proposed and analyzed. Quadratic approximations to the functions are employed in the determination of a search direction. Global convergence is proven and it is shown that a quadratic rate of convergence is obtained.

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by solving a quadratic programming subproblem, which always has an optimal solution, and uses an exact penalty function to compute the steplength along this direction through an Armijo-type scheme. The special structure of the quadratic subproblem is exploited to construct a new and simple method for updating the penalty parameter. This method may increase or reduce the value of the penalty parameter depending on some easily performed tests. A new method for updating the Hessian of the Lagrangian is presented, and a Q-superlinear rate of convergence is established.

This paper provides a new and efficient method for the computation of an arbitrarily close outer robust positively invariant (RPI) approximation to the minimal robust positively invariant (mRPI) set for linear difference inclusions. It is assumed that the linear difference inclusion is absolutely asymptotically stable (AAS) in the absence of an additive state disturbance, which is the case for parametrically uncertain or switching linear discrete-time systems controlled by a stabilizing linear state feedback controller.

The problem of state estimation for piecewise affine, discrete time systems with bounded disturbances is considered. It is shown that the state lies in a closed uncertainty set that is determined by the available observations and that evolves in time. The uncertainty set is characterised and a recursive algorithm for its computation is presented. Recursive algorithms are proposed for filtering prediction and smoothing problems.

The authors describe a method of centers based on barrier functions for solving optimal control problems with continuum inequality constraints on the state and control. The method decomposes the original problem into a sequence of easily solved optimal control problems with control constraints only. The method requires only approximate solution of the problems. Two versions of a phase I-phase II method-of-centers-type algorithm are presented. Although, at first glance, the algorithms appear to have potential for failure owing to ill conditioning, preliminary computational results show that this is not so and in fact, that the algorithms are highly effective. >

The problem of minimizing a nondifferential functionx →f(x) (subject, possibly, to nondifferential constraints) is considered. Conventional algorithms are employed for minimizing a differential approximationf∈ off (subject to differentiable approximations ofg). The parameter ɛ is adaptively reduced in such a way as to ensure convergence to points satisfying necessary conditions of optimality for the original problem.

A new method for estimating the parameters of an ARMA process is presented. The method consists of three linear least-squares estimations. In the first an autoregressive model is fitted to the observation sequence, yielding an estimate of the values of the driving white noise sequence. Linear least squares is then used to fit an ARMA model to the observation and estimated white noise sequences. This model is used to filter the observation and estimated white noise sequences. Finally an ARMA model is fitted to the filtered sequences. It is shown that the resultant estimator is 'p-consistent' (the asymptotic bias tends to zero as the degree p of the autoregressive model tends to infinity) and is 'p-efficient' (the asymptotic efficiency approaches the theoretical maximum as p tends to infinity).

This paper presents eight algorithms for solving optimal control problems with general constraints on the control and inequality constraints on the terminal state. These algorithms are of the differential dynamic programming type and bear a strong kinship to nonlinear programming algorithms of the feasible direction type.

This paper presents an implementable algorithm of the outer approximations type for solving nonlinear programming problems with functional inequality constraints. The algorithm was motivated by engineering design problems in circuit tolerancing, multivariable control, and shock-resistant structures.

This paper describes a modified Newton algorithm for solving a finite system of inequalities in a finite number of iterations.

This paper presents two demonstrably convergent, first-order, differential dynamic programming algorithms for the solution of optimal control problems with constraints on the control, but without constraints on the trajectory or the terminal state. The second of these algorithms can be used on more difficult problems than the first one, but it is correspondingly more complex.

This paper presents a secant method, based on R. B. Wilson's formula for the solution of optimization problems with inequality constraints. Global convergence properties are ensured by grafting the secant method onto a phase I - phase II feasible directions method, using a rate of convergence test for crossover control.

The control literature either presents sufficient conditions for global optimality (for example, the Hamilton-Jacobi-Bellman theorem) or, if concerned with local optimality, restricts attention to comparison controls which are local in theL ∞-sense. In this paper, use is made of an exact expression for the change in cost due to a change in control, a natural extension of a result due to Weierstrass, to obtain sufficient conditions for a control to be a strong minimum (in the sense that comparison controls are merely required to be close in theL 1-sense).

We present an algorithm for solving singular value inequalities over a continuum of frequencies. The algorithm is in two parts: a master algorithm which constructs an infinite sequence of finite sets of inequalities, and a nondifferentiable optimization subalgorithm which solves these finite sets of inequalities.

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.

This paper presents three general schemes for extending differentiable optimization algorithms to nondifferentiable problems. It is shown that the Armijo gradient method, phase-I–phase-II methods of feasible directions and exact penalty function methods have conceptual analogs for problems with locally Lipschitz functions and implementable analogs for problems with semismooth functions. The exact penalty method has required the development of a new optimality condition.

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL ∞ accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.

This paper presents a new method for the estimation of the parameters of a mixed autoregressive-moving average (ARMA) system of known order. Since this is a nonlinear estimation problem, existing algorithms, unless they sacrifice efficiency as in instrumental variable methods, require an infinite number of iterations with consequent high computation cost and possible convergence to a local maximum of the likelihood function. The method presented in this paper requires the solution of a few (e.g. three) linear estimation problems: the first yields an autoregressive model, the second yields an ARMA model which is used to prefilter the data, and the third and (possible) subsequent iterations yield improved estimates of the ARMA system. The method is closer in spirit to the classical generalized least squares method (which yield a sequence of unbiassed estimates) than Clarke’s algorithm. The identification procedure yields an estimate which is consistent and asymptotically efficient.

An efficient algorithm for solving a finite system of inequalities in a finite number of iterations is described and analyzed.

This paper proposes algorithms for minimizing a continuously differentiable functionf(x):ℝn→ℝ subject to the constraint thatx does not lie in specified bounded subsets of ℝn. Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form\(\psi (x) \triangleq \min \{ g^j (x)|j \in J\} \leqslant 0\). The function ψ is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of ψ at points where the set {j|gj(x)=ψ(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.

Many design algorithms can be formulated as determining a set of parameters to satisfy conventional and infinite dimensional constraints. An algorithm, with quadratic rate of convergence, for solving such inequalities, is presented.

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.

A method for obtaining optimal estimates of the states of a linear system given a record of observations is derived. The method uses Kalman's filtering theory to obtain an estimate using 'past' observations, and optimal control theory to obtain an estimate using 'future' observations, and shows how the two estimates can be combined to give a solution to the smoothing or interpolation problem. The method also yields the variance of the estimate. The method is illustrated by means of a numerical example.

A linear system with gnusian inputs can be specified by its state transition equations. Assuming that the coefficients of the state transition matrix are initially unknown, a procedure, which gives a continuously up-dated estimate of these coefficients, is outlined. The procedure is extended to give an optimal estimate when the coefficients are random processes. Full knowledge of the state of the system as time proceeds is required. The puper shows how the result can be used to obtain an optimal estimate of the coefficients of the state transition and control matrices of a linear control system with gaussian inputs, provided that full knowledge of the value of the control signal is also available.

Using Bayes' theorem the conditional mean of the posterior probability density function is estimated via Monte Carlo techniques. Multi-stage, non-linear filtering requires the solution of high dimensional integrals. The new feature of the approach presented is that a combination of analytical and numerical methods yields a variance reduction which can also be interpreted as an accuracy improvement of approximate non-linear filter equations. Theorems are derived to prove zero sampling variance for the linear Gaussian case and experimental results indicate that the proposed estimators are feasible in non-linear situations.

A pseudo Newton-Raphson algorithm for function minimization is presented. As in all such algorithms, an estimate of the inverse Hessian is calculated. In this case, the estimate is of the formXZX T , whereZ is a diagonal matrix; and this feature permits the use of the simple procedures to maintain the positive definiteness ofZ, and hence of the restriction ofXZX T to the range ofX. The algorithm is shown to have finite convergence for quadratic functions and asymptotic convergence for a fairly general class of functions. Some numerical results are presented, and the extension of the algorithm to deal with linear equality and inequality constraints is briefly discussed.

A second-order method of successively improving a control sequence for a non-linear discrete-time system is derived. One step convergence is obtained for linear systems with quadratic performance functions. Although the results are of interest in their own right, a second-order method for continuous-time systems is obtained by formally allowing the sampling interval to approach zero. The equations so obtained differ slightly, because of the method of derivation, from results already obtained using the calculus of variations approach. The difference, which is an advantage of the method described in this paper, is that one vector differential equation less has to be integrated. The approach used in the derivation is motivated by dynamic programming and facilitates the application of gradient methods to stochastic problems which will be the subject of a future paper.

Control design is naturally formulated as an optimization problem in which the constraints may be conventional, non-differentiable (e. g. constraints on singular values for robustness or eigenvalues for stability) or infinite-dimensional (e. g. time domain constraints on step responses or frequency domain constraints for performance) and the design variables may be finite dimensional (e. g. parameters of a controller) or infinite dimensional (e. g. a non-linear control law). This paper concentrates on the latter type of problem, a typical problem being the simultaneous determination of a Lyapunov function and non-linear control law to stabilize a non-linear system. An outer approximation algorithm is presented and shown to produce converging subsequences. The algorithm is illustrated by its application to a simple non-linear control problem.

Exact penalty functions have been employed in two distinct ways in the mathematical programming literature. In the first (Conn (1973), Conn and Pietrzykowski (1977)) a constrained optimization problem P is replaced by the unconstrained problem Pc of minimizing an exact penalty function X(x,c), where c ~ R denotes the penalty parameter. If c is sufficiently large (but finite) a local solution of P is also a c solution of P. In this class of algorithms the search direction is chosen to be a descent direction for the exact penalty function; the non-differentiability of this function must be taken into account.

It is shown that a number of seemingly unrelated nondiflerentiable optimization algorithms are special cases of two simple algorithm models: one for constrained and one for unconstrained optimization. In both of these models, the direction finding procedures use parametrized families of maps which are locally uniformly u.s.c. with respect to the generalized gradients of the functions defining the problem. The selection of the parameter is determined by a rule which is analogous to the one used in methods of feasible directions.

A new method for estimating the parameters of an ARMA system is considered. The method involves three linear least squares estimations: in the first an autoregressive model is fitted to the output sequence, yielding an estimate of the "white noise" input sequence; in the second an ARMA model is fitted to the output and estimated input sequences (Durbin's estimator); in the third an ARMA model is fitted to filtered versions of the output and estimated input sequences, the filter being obtained from Durbin's estimator. The consistency of the resultant estimator is established and some comments on its efficiency are made.

A recursive version of a three stage linear estimation scheme for ARMA processes has recently been proposed and tested. In the first stage an autoregressive model is fitted. In the second stage an ARMA model is fitted using the residuals obtained in the first stage. The data (output, input and residuals) are then filtered using the model obtained from the second stage and an improved ARMA model is fitted to the filtered data. In this note the almost sure convergence of the algorithm is established using a relatively simple procedure.

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ℝ n can be expressed as minimizing max{g(x, y)|y ∈X}, whereg is a support function forf[f(x) ≥g(x, y), for ally ∈X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.