Time transformed mixed integer optimal control problems with impacts

The solutions of mixed integer optimal control problems (MIOCPs) yield optimized trajectories for dynamical systems with instantly changing dynamical behavior. The instant change is caused by a changing value of the integer valued control function. For example, a changing integer value can cause a car to change the gear, or a mechanical system to close a contact. The direct discretization of a MIOCP leads to a mixed integer nonlinear program (MINLP) and can not be solved with gradient based optimization methods at once. We extend the work by Gerdts [1] and reformulate a MIOCP with integer dependent constraints as an ordinary optimal control problem (OCP). The discretized OCP can be solved using gradient based optimization methods. We show how the integer dependent constraints can be used to model systems with impact and present optimized trajectories of computational examples, namely of a lockable double pendulum and an acyclic telescope walker. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the time transformation of mixed integer optimal control problems using a consistent fixed integer control function

Nonlinear control systems with instantly changing dynamical behavior can be modeled by introducing an additional control function that is integer valued in contrast to a control function that is allowed to have continuous values. The discretization of a mixed integer optimal control problem (MIOCP) leads to a non differentiable optimization problem and the non differentiability is caused by the integer values. The paper is about a time transformation method that is used to transform a MIOCP with integer dependent constraints into an ordinary optimal control problem. Differentiability is achieved by replacing a variable integer control function with a fixed integer control function and a variable time allows to change the sequence of active integer values. In contrast to other contributions, so called control consistent fixed integer control functions are taken into account here. It is shown that these control consistent fixed integer control functions allow a better accuracy in the resulting trajectories, in particular in the computed switching times. The method is verified on analytical and numerical examples.     

整数规划的广义填充函数算法

文[9,10]设计了直接求整数规划问题近似解的填充函数算法,但其所利用的文[2,3]的填充函数均带有参数,需要在算法过程中逐步调节。本文建立整数规划的广义填充函数的定义,说明了文[9,10]所利用的填充函数是整数规划问题的广义填充函数,并构造了一类不带参数的广义填充函数。进而本文设计了整数规划的一类不带参数的广义填充函数算法,数值试验表明算法是有效的。     

Quadratic Control for Stochastic Systems Defined by Evolution Operators and Square Integrable Martingales

The infinite dimensional version of the linear quadratic cost control problem is studied by Curtain and Pritchard [2], Gibson [5] by using Riccati integral equations, instead of differential equations. In the present paper the corresponding stochastic case over a finite horizon is considered. The stochastic perturbations are given by Hilbert valued square integrable martingales and it is shown that the deterministic optimal feedback control is also optimal in the stochastic case. Sufficient conditions are given for the convergence of approximate solutions of optimal control problems.     

Relaxing mixed integer optimal control problems using a time transformation

Mixed integer control systems are used to model dynamical behavior that can change instantly, for example a driving car with different gears. Changing a gear corresponds to an instant change of the differential equation what is achieved in the model by changing the value of the integer control function. The optimal control of a mixed integer control system by a discretize-then-optimize approach leads to a mixed integer optimization problem that is not differentiable with respect to the integer variables, such that gradient based optimization methods can not be applied. In this work, differentiability with respect to all optimization variables is achieved by reformulating the mixed integer optimal control problem (MIOCP). A fixed integer control function and a time transformation are introduced. The combination of both allows to change the sequence of active differential equations by partially deactivating the fixed integer control function. In contrast to other works, here different fixed integer control functions are taken into account. Advantages of so called control consistent (CC) fixed integer control functions are discussed and confirmed on a numerical example. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Small-parameter method for constructing approximate strategies in a class of differential games : PMM vol. 39, n 6, 1975, pp. 1006–1016

We examine a class of problems in which the pay-off is some function of the terminal state of a conflict-controlled system. When the opportunities of one of the players are small in relation with the opportunities of the other, we propose methods for constructing approximate optimal strategies of the players, based on solving the Bellman equation containing a small parameter. We have shown that the players' approximate optimal strategies can be constructed if the solutions of the corresponding optimal control problems are known. The error bounds for the methods are proved and examples are considered. The arguments used rely on the results in [1–6] on the theory of differential games and on [7–11] devoted to optimal control synthesis methods for systems subject to random perturbations of small intensity.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Digital modeling and control of multiple time-delayed distributed power grid

Distributed power grid (DPG) control systems are so highly interconnected that the effects of local disturbances as well as transmission time delays can be amplified as they propagate through a complex network of transmission lines. These effects deteriorate control performance and could possibly destabilize the overall system. In this paper, a new approximated discretization method and digital design for DPG control systems with multiple state, input and output delays as well as a generalized bilinear transformation method are presented. Based on a procedure for the generation of impulse response data, the multiple fractional/integer time-delayed continuous-time system is transformed to a discrete-time model with multiple integer time delays. To implement the digital modeling, the singular value decomposition (SVD) of a Hankel matrix together with an energy loss level is employed to obtain an extended discrete-time state space model. Then, the extended discrete-time state space model of the DPG control system is reformulated as an integer time-delayed discrete-time system by computing its observable canonical form. The proposed method can closely approximate the step response of the original continuous time-delayed DPG control system by choosing various energy loss levels. For completeness, an optimal digital controller design for the DPG control system and a generalized bilinear transformation method with a tunable parameter are also provided, which can re-transform the integer time-delayed discrete-time model to its continuous-time model. Illustrative examples are given to demonstrate the effectiveness of the developed method.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Applications of numerical optimal control to nonlinear hybrid systems

This paper develops a technique for numerically solving hybrid optimal control problems. The theoretical foundation of the approach is a recently developed methodology by S.C. Bengea and R.A. DeCarlo [Optimal control of switching systems, Automatica. A Journal of IFAC 41 (1) (2005) 11–27] for solving switched optimal control problems through embedding. The methodology is extended to incorporate hybrid behavior stemming from autonomous (uncontrolled) switches that results in plant equations with piecewise smooth vector fields. We demonstrate that when the system has no memory, the embedding technique can be used to reduce the hybrid optimal control problem for such systems to the traditional one. In particular, we show that the solution methodology does not require mixed integer programming (MIP) methods, but rather can utilize traditional nonlinear programming techniques such as sequential quadratic programming (SQP). By dramatically reducing the computational complexity over existing approaches, the proposed techniques make optimal control highly appealing for hybrid systems. This appeal is concretely demonstrated in an exhaustive application to a unicycle model that contains both autonomous and controlled switches; optimal and model predictive control solutions are given for two types of models using both a minimum energy and minimum time performance index. Controller performance is evaluated in the presence of a step frictional disturbance and parameter uncertainties which demonstrates the robustness of the controllers.     

On the Optimal Stabilisation for a set of Programmed Motions of the Bilinear Control System

During recent years there has been considerable interest in using bilinear systems [1, 2] as mathematical models to represent the dynamic behavior of a wide class of engineering, biological and economic systems. Moreover, there are some methods [3] which may approximate nonlinear control systems by bilinear systems. For the first time Zubov has proposed a method of stabilization control synthesis for a set of programmed motions in linear systems [4]. In papers [5, 6] this method has been developed and used to solve the same problem for bilinear systems. In the present paper the following problems are considered. First, synthesis of nonlinear control as feedback under which the bilinear control system has a given set of programmed and asymptotic stable motions. Because this control is not unique, the second problem concerns optimal stabilization. In this paper a method for the design of nonlinear optimal control is suggested. This control is constructed in the form of a convergent series. The theorem on the sufficient conditions to solve this problem is represented.     

Approximate solution of nonlinear problems of optimal control of oscillatory processes using the method of canonical separation of motions : PMM vol.40, n 6, 1976, pp. 1024–1033

An asymptotic method of solving certain problems of optimal control of motion of the standard type systems with rotating phase is developed. It is assumed that the controls enter only the small perturbing terms, and that the fixed time interval over which the process is being considered is long enough to ensure that the slow variables change essentially. Assuming also that the system and the controls satisfy the necessary requirements of smoothness, the method of canonical averaging [1] is used to construct a scheme for deriving a simplified boundary value problem of the maximum principle. The structure of the set of solutions of the boundary value problem is investigated and a scheme for choosing the optimal solution with the given degree of accuracy in the small parameter is worked out. The validity of the approximate method of solving the boundary value problem is proved. The method suggested in [2] for constructing a solution in the first approximation for similar problems of optimal control is developed.     

Total dual integrality and integer polyhedra

A linear system Ax ? b (A, b rational) is said to be totally dual integral (TDI) if for any integer objective function c such that max {cx: Ax ? b} exists, there is an integer optimum dual solution. We show that if P is a polytope all of whose vertices are integer valued, then it is the solution set of a TDI system Ax ? b where b is integer valued. This was shown by Edmonds and Giles [4] to be a sufficient condition for a polytope to have integer vertices.     

Stability of Merton's portfolio optimization problem for Lévy models

Merton's classical portfolio optimization problem for an investor, who can trade in a risk-free bond and a stock, can be extended to the case where the driving noise of the logreturns is a pure jump process instead of a Brownian motion. Benth et al. [4,5] solved the problem and found the optimal control implicitly given by an integral equation in the hyperbolic absolute risk aversion (HARA) utility case. There are several ways to approximate a Levy process with infinite activity by neglecting the small jumps or approximating them with a Brownian motion, as discussed in Asmussen and Rosinski [1]. In this setting, we study stability of the corresponding optimal investment problems. The optimal controls are solutions of integral equations, for which we study convergence. We are able to characterize the rate of convergence in terms of the variance of the small jumps. Additionally, we prove convergence of the corresponding wealth processes and indirect utilities (value functions).     

Trajectories, first return limiting notions and rings of H-connected and iteratively H-connected functions

In the paper the existing results concerning a special kind of trajectories and the theory of first return continuous functions connected with them are used to examine some algebraic properties of classes of functions. To that end we define a new class of functions (denoted Conn*) contained between the families (widely described in literature) of Darboux Baire 1 functions (DB₁) and connectivity functions (Conn). The solutions to our problems are based, among other, on the suitable construction of the ring, which turned out to be in some senses an “optimal construction”. These considerations concern mainly real functions defined on [0, 1] but in the last chapter we also extend them to the case of real valued iteratively H-connected functions defined on topological spaces.     

On the approximate synthesis of the optimal control of stochastic quasilinear systems with aftereffect : PMM vol. 42, no. 6, 1978, pp. 978–988

Control problems for quasilinear deterministic systems without time lag were analyzed in [1, 2]. In the present paper the control of quasilinear stochastic systems, whose theory has been presented in [3–6], is studied. The approximate synthesis of the control of stochastic systems with aftereffect is of importance since the construction of their exact optimal control is successful only in exceptional cases [7, 8]. In the paper an approximate optimal control synthesis algorithm is proposed and a method for obtaining error bounds, different from ones previously obtained [9, 10], is developed.     

A computer realization of control-with-guide procedures

Positional differential games of pursuit with target for-conflict-control systems, non-linear with respect to the phase vector, are considered. The problems investigated are approximate construction of the set of positional absorption and construction of control procedures guaranteeing guidance to the target. Issues relating to the development of algorithms for the approximate construction of the positional absorption set and control-with-guide procedures [1–4] are also examined. As an example to illustrate the possibilities of the algorithms considered, a pursuit game of the Homicidal Chauffeur type [5] is considered, with approximate computation of positional absorption sets in the problem of pursuit over a fixed time interval for several parameter sets. Motions of a conflict-control system that generate a control-with-guide procedure are computed for several specific initial values of the phase vector and several choices of the evader's control.     

Two row mixed-integer cuts via lifting

Recently Andersen et al. [1], Borozan and Cornuéjols [6] and Cornuéjols and Margot [9] have characterized the extreme valid inequalities of a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible non-negative integer variables (giving the two row mixed-integer infinite-group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We show that there exists a unique lifting function that yields extreme inequalities when starting from a maximal lattice-free triangle with multiple integer points in the relative interior of one of its sides, or a maximal lattice-free triangle with integral vertices and one integer point in the relative interior of each side. In the other cases (maximal lattice-free triangles with one integer point in the relative interior of each side and non-integral vertices, and maximal lattice-free quadrilaterals), non-unique lifting functions may yield distinct extreme inequalities. For the latter family of triangles, we present sufficient conditions to yield an extreme inequality for the two row mixed-integer infinite-group problem.     

Constructing Robust Feedback Laws by Set Oriented Numerical Methods

In [8, 6] a numerical method for the construction of optimally stabilizing feedback laws was proposed. The method is based on a set oriented discretization of phase space in combination with graph theoretic algorithms for the computation of shortest paths in directed weighted graphs. The resulting approximate optimal value function is piecewise constant, yielding an approximate optimal feedback which might not be robust with respect to perturbations of the system. In this contribution we extend the approach to the case of perturbed control systems. Based on the concept of a multivalued game we show how to derive a directed weighted hypergraph from the original system and generalize the corresponding shortest path algorithm. The resulting optimal value function yields a robustly stabilizing approximate optimal feedback law. This note is an abbreviated version of [5]. For the proofs of the statements here we refer to the full paper. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)