Asymptotic methods in the theory of optimal control

The paper gives a survey of some works devoted to methods of the small parameter for the solution of optimal control problems. It is well known that these problems are difficult both for analytical and numerical approaches. Exact analytical solutions exist only for specific classes of optimal control problems. A numerical solution is possible for optimal program (open-loop) controls, but it becomes very difficult for obtaining synthesis if the order of the system is high. Therefore, approximate methods based on the small parameter techniques seem to be useful. By means of these methods, one can find approximate optimal control (both program and synthesis) for a number of optimal control problems which arise in applications. The paper presents some approaches and results in this direction obtained in the Computing Center and the Institute for Problems of Mechanics of the USSR Academy of Sciences in the past 10-15 years.     

Asymptotic methods in the optimal control of distributed systems

A short review of the various problems which arise in connection with the use of asymptotic methods in the optimal control of distributed systems is presented. We consider the cases when the asymptotic analysis comes from the state equation, or from the cost function, or both and also when the state equation is defined in perturbed domains.     

Pseudospectral methods for solving infinite-horizon optimal control problems

An important aspect of numerically approximating the solution of an infinite-horizon optimal control problem is the manner in which the horizon is treated. Generally, an infinite-horizon optimal control problem is approximated with a finite-horizon problem. In such cases, regardless of the finite duration of the approximation, the final time lies an infinite duration from the actual horizon at t=+∞. In this paper we describe two new direct pseudospectral methods using Legendre–Gauss (LG) and Legendre–Gauss–Radau (LGR) collocation for solving infinite-horizon optimal control problems numerically. A smooth, strictly monotonic transformation is used to map the infinite time domain t∈[0,∞) onto a half-open interval τ∈[−1,1). The resulting problem on the finite interval is transcribed to a nonlinear programming problem using collocation. The proposed methods yield approximations to the state and the costate on the entire horizon, including approximations at t=+∞. These pseudospectral methods can be written equivalently in either a differential or an implicit integral form. In numerical experiments, the discrete solution exhibits exponential convergence as a function of the number of collocation points. It is shown that the map ?:[−1,+1)→[0,+∞) can be tuned to improve the quality of the discrete approximation.     

Gradient refinement methods for optimal impulse control problems

An optimal control problem is considered for a system described by a differential equation with measures; a certain constraint is imposed on the total variation of controlmeasure. Involving the method of discontinuous time reparameterization, an interpretation is performed for the procedures of weak control variation in an auxiliary reduced problem, and new refinement methods are developed for impulsive processes. An example is provided.     

Semi-smooth Newton methods for state-constrained optimal control problems

A regularized optimality system for state-constrained optimal control problems is introduced and semi-smooth Newton methods for its solution are analyzed. Convergence of the regularized problems is proved. Numerical tests confirm the theoretical results and demonstrate the efficiency of the proposed methodology.     

One-shot methods in function space for PDE-constrained optimal control problems

We state and analyse one-shot methods in function space for the optimal control of nonlinear partial differential equations (PDEs) that can be formulated in terms of a fixed-point operator. A general convergence theorem is proved by generalizing the previously obtained results in finite dimensions. As application examples we consider two nonlinear elliptic model problems: the stationary solid fuel ignition model and the stationary viscous Burgers equation. For these problems we present a more detailed convergence analysis of the method. The resulting algorithms are computationally implemented in combination with an adaptive mesh refinement strategy, which leads to an improvement in the performance of the one-shot approach.     

Logic-based solution methods for optimal control of hybrid systems

Combinatorial optimization over continuous and integer variables is a useful tool for solving complex optimal control problems of hybrid dynamical systems formulated in discrete-time. Current approaches are based on mixed-integer linear (or quadratic) programming (MIP), which provides the solution after solving a sequence of relaxed linear (or quadratic) programs. MIP formulations require the translation of the discrete/logic part of the hybrid problem into mixed-integer inequalities. Although this operation can be done automatically, most of the original symbolic structure of the problem (e.g., transition functions of finite state machines, logic constraints, symbolic variables, etc.) is lost during the conversion, with a consequent loss of computational performance. In this paper, we attempt to overcome such a difficulty by combining numerical techniques for solving convex programming problems with symbolic techniques for solving constraint satisfaction problems (CSP). The resulting "hybrid" solver proposed here takes advantage of CSP solvers for dealing with satisfiability of logic constraints very efficiently. We propose a suitable model of the hybrid dynamics and a class of optimal control problems that embrace both symbolic and continuous variables/functions, and that are tailored to the use of the new hybrid solver. The superiority in terms of computational performance with respect to commercial MIP solvers is shown on a centralized supply chain management problem with uncertain forecast demand.     

Numerical methods of optimal control of the HIV-infection dynamics

The problem of optimal control of a dynamic model of HIV-infection development in humans is solved. This work illustrates the possibilities of applying numerical methods for optimization of the treatment process.     

Parametric optimization and optimal control using algebraic geometry methods

We present two algebraic methods to solve the parametric optimization problem that arises in non-linear model predictive control. We consider constrained discrete-time polynomial systems and the corresponding constrained finite-time optimal control problem. The first method is based on cylindrical algebraic decomposition. The second uses Gröbner bases and the eigenvalue method for solving systems of polynomial equations. Both methods aim at moving most of the computational burden associated with the optimization problem off-line, by pre-computing certain algebraic objects. Then, an on-line algorithm uses this pre-computed information to obtain the solution of the original optimization problem in real time fast and efficiently. Introductory material is provided as appropriate and the algorithms are accompanied by illustrative examples.     

Nested multigrid methods for time-periodic,parabolic optimal control problems

We present a nested multigrid method to optimize time-periodic, parabolic, partial differential equations (PDE). We consider a quadratic tracking objective with a linear parabolic PDE constraint. The first order optimality conditions, given by a coupled system of boundary value problems can be rewritten as an Fredholm integral equation of the second kind, which is solved by a multigrid of the second kind. The evaluation of the integral operator consists of solving sequentially a boundary value problem for respectively the state and the adjoints. Both problems are solved efficiently by a time-periodic space-time multigrid method.     

Discrete optimization by optimal control methods I. Separable problems

Two general solution schemes are designed for separable discrete optimization problems. Approximations from below and from above to the optimal value of the quality criterion are determined. These schemes are based on a unified theoretical base—sufficient conditions for the global optimal known in optimal control theory. Known and new methods for defining a resolving function, which is essential for applying these conditions, are described.     

Computing interval-valued reliability measures: application of optimal control methods

The paper describes an approach to deriving interval-valued reliability measures given partial statistical information on the occurrence of failures. We apply methods of optimal control theory, in particular, Pontryagin’s principle of maximum to solve the non-linear optimisation problem and derive the probabilistic interval-valued quantities of interest. It is proven that the optimisation problem can be translated into another problem statement that can be solved on the class of piecewise continuous probability density functions (pdfs). This class often consists of piecewise exponential pdfs which appear as soon as among the constraints there are bounds on a failure rate of a component under consideration. Finding the number of switching points of the piecewise continuous pdfs and their values becomes the focus of the approach described in the paper. Examples are provided.     

Weighted multi-model control

A multi-model control which combines the basic controls of the different models, according to the quality of representation of each model, is proposed. A real-time application of this technique to a non-linear thermal process is carried out and the results are given compared to the results of the same application of the other technique where one model only is selected, under the same conditions. This comparison shows the advantages of the combined control signal.     

Lie algebraic methods in optimal control of stochastic systems with exponential-of-integral cost

The purpose of this paper is to formulate and study the optimal control of partially observed stochastic systems with exponential-of-integral-sample cost, known as risk-sensitive problems, using Lie algebraic tools. This leads to the introduction of the sufficient statistic algebra, , through which one can determine á priori the maximum order of the controller. When , the construction of the control laws is addressed through extensions of the Wei–Norman method, as in nonlinear filtering problems. Aside from specific known finite-dimensional examples which are studied in order to delineate the application of the Lie algebraic tools, new classes of finite-dimensional controllers are identified as well. In addition, relations with minimax dynamic games are explored to best assess the importance and generality of the finite-dimensional control systems.     

Weighted hypertree decompositions and optimal query plans

Hypertree width is a measure of the degree of cyclicity of hypergraphs. A number of relevant problems from different areas, e.g., the evaluation of conjunctive queries in database theory or the constraint satisfaction in AI, are tractable when their underlying hypergraphs have bounded hypertree width. However, in practical contexts like the evaluation of database queries, we have more information besides the structure of queries. For instance, we know the number of tuples in relations, the selectivity of attributes and so on. In fact, all commercial query-optimizers are based on quantitative methods and do not care on structural properties.In this paper, in order to combine structural decomposition methods with quantitative approaches, the notion of weighted hypertree decomposition is defined. Weighted hypertree decompositions are equipped with cost functions, that can be used for modeling many situations where there is further information on the given problem, besides its hypergraph representation. The complexity of computing hypertree decompositions having the smallest weights, called minimal hypertree decompositions, is analyzed. It is shown that in many cases tractability is lost if weights are added. However, it is proven that, under some—not very severe—restrictions on the allowed cost functions and on the target hypertrees, optimal weighted hypertree decompositions can be computed in polynomial time. For some easier hypertree weighting functions, this problem is also highly parallelizable. Then, a cost function modeling query evaluation costs is provided, and it is shown how to exploit weighted hypertree decompositions for determining (logical) query plans for answering conjunctive queries. Finally, some preliminary results of an experimental comparison of this query optimization technique with the query optimizer of a commercial DBMS are presented.