Compactness and convergence rates in the combinatorial integral approximation decomposition

The combinatorial integral approximation decomposition splits the optimization of a discrete-valued control into two steps: solving a continuous relaxation of the discrete control problem, and computing a discrete-valued approximation of the relaxed control. Different algorithms exist for the second step to construct piecewise constant discrete-valued approximants that are defined on given decompositions of the domain. It is known that the resulting discrete controls can be constructed such that they converge to a relaxed control in the \(\hbox {weak}^*\) topology of \(L^\infty \) if the grid constant of this decomposition is driven to zero. We exploit this insight to formulate a general approximation result for optimization problems, which feature discrete and distributed optimization variables, and which are governed by a compact control-to-state operator. We analyze the topology induced by the grid refinements and prove convergence rates of the control vectors for two problem classes. We use a reconstruction problem from signal processing to demonstrate both the applicability of the method outside the scope of differential equations, the predominant case in the literature, and the effectiveness of the approach.

     

Combinatorial integral approximation

We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms cplex on a numerical case study and hence further improves efficiency of our novel method.     

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.     

Mixed-integer optimal control problems with switching costs: a shortest path approach

Mathematical Programming - We investigate an extension of Mixed-Integer Optimal Control Problems by adding switching costs, which enables the penalization of chattering and extends current modeling...     

TACO: a toolkit for AMPL control optimization

We describe a set of extensions to the AMPL modeling language to conveniently model mixed-integer optimal control problems for ODE or DAE dynamic processes. These extensions are realized as AMPL user functions and suffixes and do not require intrusive changes to the AMPL language standard or implementation itself. We describe and provide TACO, a Toolkit for AMPL Control Optimization that reads AMPL stub.nl files and detects the structure of the optimal control problem. This toolkit is designed to facilitate the coupling of existing optimal control software packages to AMPL. We discuss requirements, capabilities, and the current implementation. Using the example of the multiple shooting code for optimal control MUSCOD-II, a direct and simultaneous method for DAE-constrained optimal control, we demonstrate how the problem information provided by the TACO toolkit is interfaced to the solver. In addition, we show how the MS-MINTOC algorithm for mixed-integer optimal control can be used to efficiently solve mixed-integer optimal control problems modeled in AMPL. We use the AMPL extensions to model three control problem examples and we discuss how those extensions affect the representation of optimal control problems. Solutions to these problems are obtained by using MUSCOD-II and MS-MINTOC inside the AMPL environment. A collection of further AMPL control models is provided on the web site http://mintoc.de. MUSCOD-II and MS-MINTOC have been made available on the NEOS Server for Optimization, using the TACO toolkit to enable input of AMPL models.     

Structure-exploiting polynomial chaos for uncertain optimal control problems with sparse derivative generation

We present advances in structure-exploiting non-intrusive polynomial chaos methods for the numerical solution of nonlinear optimal control problems with parametric uncertainties. In particular, we make use of the special structure induced by the spectral projection to reuse model derivatives and exploit sparsity information leading to a fast automatic sensitivity generation. This greatly reduces the computational effort of Newton-type methods for the solution of the resulting high-dimensional surrogate problem. The results are complemented by a complexity comparison and a numerical case study. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A factorization with update procedures for a KKT matrix arising in direct optimal control

Quadratic programs obtained for optimal control problems of dynamic or discrete-time processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fill-in. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.