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)     

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 efficiency of optimal grid synthesis in optimal control problems with fixed terminal time

In the paper, we consider nonlinear optimal control problems with the Bolza functional and with fixed terminal time. We suggest a construction of optimal grid synthesis. For each initial state of the control system, we obtain an estimate for the difference between the optimal result and the value of the functional on the trajectory generated by the suggested grid positional control. The considered feedback control constructions and the estimates of their efficiency are based on a backward dynamic programming procedure. We also use necessary and sufficient optimality conditions in terms of characteristics of the Bellman equation and the sub-differential of the minimax viscosity solution of this equation in the Cauchy problem specified for the fixed terminal time. The results are illustrated by the numerical solution of a nonlinear optimal control problem.     

On the mixed integer signomial programming problems

This paper proposes an approximate method to solve the mixed integer signomial programming problem, for which the objective function and the constraints may contain product terms with exponents and decision variables, which could be continuous or integral. A linear programming relaxation is derived for the problem based on piecewise linearization techniques, which first convert a signomial term into the sum of absolute terms; these absolute terms are then linearized by linearization strategies. In addition, a novel approach is included for solving integer and undefined problems in the logarithmic piecewise technique, which leads to more usefulness of the proposed method. The proposed method could reach a solution as close as possible to the global optimum.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

Discrete mechanics and mixed integer optimal control of dynamical systems

Mixed integer optimal control problems are a generalization of ordinary optimal control problems that include additional integer valued control functions. The integer control functions are used to switch instantaneously from one system to another. We use a time transformation (similar as in [1]) to get rid of the integer valued functions. This allows to apply gradient based optimization methods to approximate the mixed integer optimal control problem. The time transformation from [1] is adapted such that problems with distinct state domains for each system can be solved and it is combined with the direct discretization method DMOC [2,3] (Discrete Mechanics and Optimal Control) to approximate trajectories of the underlying optimal control problems. Our approach is illustrated with the help of a first example, the hybrid mass oscillator. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the use of consistent approximations in the solution of semi-infinite optimization and optimal control problems

The purpose of this study is to broaden the scope of projective transformation methods in mathematical programming, both in terms of theory and algorithms. We start by generalizing the concept of the analytic center of a polyhedral system of constraints to the w-center of a polyhedral system, which stands for weighted center, where there is a positive weight on the logarithmic barrier term for each inequality constraint defining the polyhedronX. We prove basic results regarding contained and containing ellipsoids centered at the w-center of the systemX. We next shift attention to projective transformations, and we exhibit an elementary projective transformation that transforms the polyhedronX to another polyhedronZ, and that transforms the current interior point to the w-center of the transformed polyhedronZ. We work throughout with a polyhedral system of the most general form, namely both inequality and equality costraints.This theory is then applied to the problem of finding the w-center of a polyhedral systemX. We present a projective transformation algorithm, which is an extension of Karmarkar's algorithm, for finding the w-center of the systemX. At each iteration, the algorithm exhibits either a fixed constant objective function improvement, or converges superlinearly to the optimal solution. The algorithm produces upper bounds on the optimal value at each iteration. The direction chosen at each iteration is shown to be a positively scaled Newton direction. This broadens a result of Bayer and Lagarias regarding the connection between projective transformation methods and Newton's method. Furthermore, the algorithm specializes to Vaidya's algorithm when used with a line-search, and so shows that Vaidya's algorithm is superlinearly convergent as well. Finally, we show how the algorithm can be used to construct well-scaled containing and contained ellipsoids at near-optimal solutions to the w-center problem.This paper is a revision of the two papers Projective transformations for interior point methods, part I: Basic theory and linear programming, O.R. working paper 179-88 and Projective transformations for interior point methods, part II: Analysis of an algorithm for finding the weighted center of a polyhedral system, O.R. working paper 180-88, M.I.T.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

On the value function for optimal control problems with infinite horizon

We consider optimal control problems of infinite horizon type, whose control laws are given by L¹_loc‐functions and whose objective function has the meaning of a discounted utility. Our main objective is the verification of the fact that the value function is a viscosity solution of the Hamilton‐Jacobi‐Bellman (HJB) equation in this framework. The usual final condition for the HJB‐equation in the finite horizon case (V (T, x) = 0 or V (T, x) = g(x)) has to be substituted by a decay condition at the infinity. Following the dynamic programming approach, we obtain Bellman's optimality principle and the dynamic programming equation (see (3)). We also prove a regularity result (local Lipschitz continuity) for the value function.     

On the global solution of multi-parametric mixed integer linear programming problems

This paper deals with the global solution of the general multi-parametric mixed integer linear programming problem with uncertainty in the entries of the constraint matrix, the right-hand side vector, and in the coefficients of the objective function. To derive the piecewise affine globally optimal solution, the steps of a multi-parametric branch-and-bound procedure are outlined, where McCormick-type relaxations of bilinear terms are employed to construct suitable multi-parametric under- and overestimating problems. The alternative of embedding novel piecewise affine relaxations of bilinear terms in the proposed algorithmic procedure is also discussed.     

On a class of nonsmooth optimal control problems

In the paper the Zangwill-Pietrzykowski penalties are used for the augmentation of state-space and terminal state inequality constraints in an optimal control problem with a nonsmooth cost of a special structure having a straightforward practical application. Directional derivatives of the augmented cost are derived. In such a way bundle methods for nonsmooth minimization may be utilized.     

On a class of inverse optimal control problems

Four distinct, though closely related, inverse optimal control problems are considered. Given a closed, convex setU in a real Hilbert spaceX and an elementu ₀ inU, it is desired to find all functionals of the form (u,Ru) such that (i)R is a self-adjoint positive operator and (u,Ru) is minimized over the setU at the pointu ₀, (ii)R is self-adjoint, positive definite and (u,Ru) is minimized overU atu ₀, (iv)R is self-adjoint, positive definite and (u,Ru) is uniquely minimized overU atu ₀. The interrelationships among the sets of solutions of these problems are pointed out. Necessary and sufficient conditions which explicitly characterize the solutions to each of these problems are derived. The question of existence of a solution (namely, Given a particular setU and a particular elementu ₀, under what conditions does there exist an operatorR having certain required properties?) is discussed. The results derived are illustrated by an example.     

On the existence of optimal solutions to integer and mixed-integer programming problems

The purpose of this paper is to present sufficient conditions for the existence of optimal solutions to integer and mixed-integer programming problems in the absence of upper bounds on the integer variables. It is shown that (in addition to feasibility and boundedness of the objective function) (1) in the pure integer case a sufficient condition is that all of the constraints (other than non-negativity and integrality of the variables) beequalities, and (2) that in the mixed-integer caserationality of the constraint coefficients is sufficient. Some computational implications of these results are also given.     

A decomposition approach for optimal control problems with integer innerpoint state constraints

A large class of optimal control problems for hybrid dynamic systems can be formulated as mixed‐integer optimal control problems (MIOCPs). A decomposition approach is suggested to solve a special subclass of MIOCPs with mixed integer inner point state constraints. It is the intrinsic combinatorial complexity of the discrete variables in addition to the high nonlinearity of the continuous optimal control problem that forms the challenges in the theoretical and numerical solution of MIOCPs. During the solution procedure the problem is decomposed at the inner time points into a multiphase problem with mixed integer boundary constraints and phase transitions at unknown switching points. Due to a discretization of the state space at the switching points the problem can be decoupled into a family of continuous optimal control problems (OCPs) and a problem similar to the asymmetric group traveling salesman problem (AGTSP). The OCPs are transcribed by direct collocation to large‐scale nonlinear programming problems, which are solved efficiently by an advanced SQP method. The results are used as weights for the edges of the graph of the corresponding TSP‐like problem, which is solved by a Branch‐and‐Cut‐and‐Price (BCP) algorithm. The proposed approach is applied to a hybrid optimal control benchmark problem for a motorized traveling salesman. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

State constrained optimal control problems with time delays

In a recent, related, paper, necessary conditions in the form of a Maximum Principle were derived for optimal control problems with time delays in both state and control variables. Different versions of the necessary conditions covered fixed end-time problems and, under additional hypotheses, free end-time problems. These conditions improved on previous conditions in the following respects. They provided the first fully non-smooth Pontryagin Maximum Principle for problems involving delays in both state and control variables, only special cases of which were previously available. They provide a strong version of the Weierstrass condition for general problems with possibly non-commensurate control delays, whereas the earlier literature does so only under structural assumptions about the dynamic constraint. They also provided a new ‘two-sided’ generalized transversality condition, associated with the optimal end-time. This paper provides an extension of the Pontryagin Maximum Principle of the earlier paper for time delay systems, to allow for the presence of a unilateral state constraint. The new results fully recover the necessary conditions of the earlier paper when the state constraint is absent, and therefore retain all their advantages but in a setting of greater generality.     

On sensitivity in optimal control problems

Two types of interpretations of multipliers in both static and dynamic optimization problems are described. It is snown that the Lagrange multipliers encountered in mathematical programming problems and the auxiliary functions arising in Pontryagintype optimal control problems sometimes have highly analogous interpretations as rates of change of the optimal attainable value of an objective function, or in some cases as bounds on average rates of change.     

A consistent direct transcription method for optimal control problems in multibody dynamics

The present work deals with optimal control problems governed by differential-algebraic equations (DAEs). In particular, the control effort, which is necessary for moving a multibody system from one configuration to another, will be minimized. The orientation of the rigid bodies will be described using directors, which facilitates the integration of the equations of motion with an energy-momentum consistent time-stepping scheme [1]. This type of structure-preserving integrators offer outstanding numerical stability and robustness properties in comparison to the often applied generalized coordinates formulation. In the context of optimal control, other kinds of consistent integrators have been applied previously in [2] and [3]. We will test the different formulations with two numerical examples, a 3-link manipulator and a satellite. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the order of singular optimal control problems

In singular optimal control problems, the functional form of the optimal control function is usually determined by solving the algebraic equation which results by successively differentiating the switching function until the control appears explicitly. This process defines the order of the singular problem. Order-related results are developed for singular linear-quadratic problems and for a bilinear example which gives new insights into the relationship between singular problem order and singular are order.Dedicated to R. BellmanThis work was supported by the National Science Foundation under Grant No. ENG-77-16660.