We present an extension of the CasADi numerical optimization framework that allows arbitrary order NLP sensitivities to be calculated automatically and efficiently. The approach, which can be used together with …
We present an extension of the CasADi numerical optimization framework that allows arbitrary order NLP sensitivities to be calculated automatically and efficiently. The approach, which can be used together with any NLP solver available in CasADi, is based on a sparse QR factorization and an implementation of a primal-dual active set method. The whole toolchain is freely available as open-source software and allows generation of thread-safe, self-contained C code with small memory footprint. We illustrate the toolchain using three examples; a sparse QP, an optimal control problem and a parameter estimation problem.
We present a new “lifting” approach for the solution of nonlinear optimization problems (NLPs) that have objective and constraint functions with intermediate variables. Introducing these as additional degrees of freedom …
We present a new “lifting” approach for the solution of nonlinear optimization problems (NLPs) that have objective and constraint functions with intermediate variables. Introducing these as additional degrees of freedom into the original problem, combined with adding suitable new constraints to ensure equivalence of the problems, we propose to solve this augmented system instead of the original system by a Newton-type method. This often offers advantages in terms of convergence rates and region of attraction. The main contribution of this article is an efficient algorithmic trick to generate the quantities needed for a Newton-type method on the augmented (“lifted”) system with (a) almost no additional computational cost per iteration compared to a nonlifted Newton method, and (b) with negligible programming burden. We derive lifted schemes for Newton's method, as well as for constrained Gauss–Newton and adjoint based sequential quadratic programming (SQP) methods, and show equivalence of the new efficiently lifted approaches with “full-space” lifted Newton iterations. We establish conditions on the intermediate functions that imply faster local quadratic convergence for lifted versus nonlifted Newton iterations, a phenomenon often observed in practice but not yet explained theoretically. Finally, we compare numerically the behavior of the lifted approach with the nonlifted approach on several test problems, including a large scale example with 27 million intermediate variables. The algorithms and examples are available as open-source code in the C++ package LiftOpt.
Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality …
Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom).
Receding horizon control requires the solution of an optimization problem at every sampling instant. We present efficient interior point methods tailored to convex multistage problems, a problem class which most …
Receding horizon control requires the solution of an optimization problem at every sampling instant. We present efficient interior point methods tailored to convex multistage problems, a problem class which most relevant MPC problems with linear dynamics can be cast in, and specify important algorithmic details required for a high speed implementation with superior numerical stability. In particular, the presented approach allows for quadratic constraints, which is not supported by existing fast MPC solvers. A categorization of widely used MPC problem formulations into classes of different complexity is given, and we show how the computational burden of certain quadratic or linear constraints can be decreased by a low rank matrix forward substitution scheme. Implementation details are provided that are crucial to obtain high speed solvers.We present extensive numerical studies for the proposed methods and compare our solver to three well-known solver packages, outperforming the fastest of these by a factor 2-5 in speed and 3-70 in code size. Moreover, our solver is shown to be very efficient for large problem sizes and for quadratically constrained QPs, extending the set of systems amenable to advanced MPC formulations on low-cost embedded hardware.
Abstract A near-optimal feedback control law for a distributed parameter system with a quadratic performance index is obtained by the method of trajectory approximation. The system equation is reduced to …
Abstract A near-optimal feedback control law for a distributed parameter system with a quadratic performance index is obtained by the method of trajectory approximation. The system equation is reduced to an approximate system of ordinary differential equations by the Galerkin—Kantorovich method, and then Pontryagin's maximum principle is applied to show that the feedback control law is linear and can be obtained as the solution of a matrix Riccati equation. Numerical computations performed using Chebyshev polynomials as the Galerkin weighting functions on the equation for a heat exchanger with wall flux forcing indicate that four thermocouples are enough to attain virtual optimality.
The object-oriented software package OOQP for solving convex quadratic programming problems (QP) is described. The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely …
The object-oriented software package OOQP for solving convex quadratic programming problems (QP) is described. The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely independent of the problem structure. Users may exploit problem structure by supplying linear algebra, problem data, and variable classes that are customized to their particular applications. The OOQP distribution contains default implementations that solve several important QP problem types, including general sparse and dense QPs, bound-constrained QPs, and QPs arising from support vector machines and Huber regression. The implementations supplied with the OOQP distribution are based on such well known linear algebra packages as MA27/57, LAPACK, and PETSc. OOQP demonstrates the usefulness of object-oriented design in optimization software development, and establishes standards that can be followed in the design of software packages for other classes of optimization problems. A number of the classes in OOQP may also be reusable directly in other codes.
Time-optimal path following for robots considers the problem of moving along a predetermined Cartesian geometric path in minimum time. In practice this path need not be followed exactly, but within …
Time-optimal path following for robots considers the problem of moving along a predetermined Cartesian geometric path in minimum time. In practice this path need not be followed exactly, but within a certain tolerance; so that the motion may be executed faster. In this paper, we define this deviation as a tube around the given geometric path. This transforms the path following problem into a tube following problem. However, unlike the former, the latter is not convex.We propose a problem formulation that can still be solved efficiently, as illustrated by some numerical examples.
SUNDIALS is a suite of advanced computational codes for solving large-scale problems that can be modeled as a system of nonlinear algebraic equations, or as initial-value problems in ordinary differential …
SUNDIALS is a suite of advanced computational codes for solving large-scale problems that can be modeled as a system of nonlinear algebraic equations, or as initial-value problems in ordinary differential or differential-algebraic equations. The basic versions of these codes are called KINSOL, CVODE, and IDA, respectively. The codes are written in ANSI standard C and are suitable for either serial or parallel machine environments. Common and notable features of these codes include inexact Newton-Krylov methods for solving large-scale nonlinear systems; linear multistep methods for time-dependent problems; a highly modular structure to allow incorporation of different preconditioning and/or linear solver methods; and clear interfaces allowing for users to provide their own data structures underneath the solvers. We describe the current capabilities of the codes, along with some of the algorithms and heuristics used to achieve efficiency and robustness. We also describe how the codes stem from previous and widely used Fortran 77 solvers, and how the codes have been augmented with forward and adjoint methods for carrying out first-order sensitivity analysis with respect to model parameters or initial conditions.
Representations of the SO(3) rotation group are crucial for airborne and aerospace applications. Euler angles is a popular representation in many applications, but yield models having singular dynamics. This issue …
Representations of the SO(3) rotation group are crucial for airborne and aerospace applications. Euler angles is a popular representation in many applications, but yield models having singular dynamics. This issue is addressed via non-singular representations, operating in dimensions higher than 3. Unit quaternions and the Direction Cosine Matrix are the best known non-singular representations, and favoured in challenging aeronautic and aerospace applications. All nonsingular representations yield invariants in the model dynamics, i.e. a set of nonlinear algebraic conditions that must be fulfilled by the model initial conditions, and that remain fulfilled over time. However, due to numerical integration errors, these conditions tend to become violated when using standard integrators, making the model inconsistent with the physical reality. This issue poses some challenges when non-singular representations are deployed in optimal control. In this paper, we propose a simple technique to address the issue for classical integration schemes, establish formally its properties, and illustrate it on the optimal control of a satellite.
Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. …
Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
This work is devoted to demonstration of the analysis on optimizing the output power harvested from vibration energy harvester.
This work is devoted to demonstration of the analysis on optimizing the output power harvested from vibration energy harvester.
This paper is about a real-time model predictive control (MPC) algorithm for a particular class of model based controllers, whose objective consists of a nominal tracking objective and an additional …
This paper is about a real-time model predictive control (MPC) algorithm for a particular class of model based controllers, whose objective consists of a nominal tracking objective and an additional learning objective. Here, the construction of the learning term is based on economic optimal experiment design criteria. It is added to the MPC objective in order to excite the system from time-to-time on purpose in order to improve the accuracy of the state and parameter estimates in the presence of incomplete or noise affected measurements. A particular focus of this paper is on so-called self-reflective model predictive control schemes, which have the property that the additional learning term can be interpreted as the expected loss of optimality of the controller in the presence of random measurement errors. The main contribution of this paper is a formulation-tailored algorithm, which exploits the particular structure of self-reflective MPC problems in order to speed-up the online computation. It is shown that, in contrast to generic state-of-the-art optimal control problem solvers, the proposed algorithm can solve the self-reflective optimization problems with reasonable additional computational effort and in real-time. The advantages of the proposed real-time scheme are illustrated by applying the algorithm to a nonlinear process control problem in the presence of measurement errors and process noise.
Direct optimal control methods first discretize a continuous-time Optimal Control Problem (OCP) and then solve the resulting Nonlinear Program (NLP). Sequential Quadratic Programming (SQP) is a popular family of algorithms …
Direct optimal control methods first discretize a continuous-time Optimal Control Problem (OCP) and then solve the resulting Nonlinear Program (NLP). Sequential Quadratic Programming (SQP) is a popular family of algorithms to solve this finite dimensional optimization problem. In the specific case of a least squares cost, the Generalized Gauss-Newton (GGN) method is a popular approach which works very well under some assumptions. This paper proposes a Sequential Convex Quadratic Programming (SCQP) scheme which exploits additional convexities in the NLP in order to generalize the GGN algorithm, possibly extend its applicability and improve its local convergence. These properties are studied in detail for the proposed SCQP algorithm, which will be compared to the classical GGN method using a numerical case study of the optimal control of an inverted pendulum.
Airborne wind energy systems are capable of extracting energy from higher wind speeds at higher altitudes. The configuration considered in this paper is based on a tethered kite flown in …
Airborne wind energy systems are capable of extracting energy from higher wind speeds at higher altitudes. The configuration considered in this paper is based on a tethered kite flown in a pumping orbit. This pumping cycle generates energy by winching out at high tether forces and driving a generator while flying figures-of-eight, or lemniscates, as crosswind pattern. Then, the tether is reeled in while keeping the kite at a neutral position, thus leaving a net amount of generated energy. In order to achieve an economic operation, optimization of pumping cycles is of great interest. In this paper, first the principles of airborne wind energy will be briefly revisited. The first contribution is a singularity-free model for the tethered kite dynamics in quaternion representation, where the model is derived from first principles. The second contribution is an optimal control formulation and numerical results for complete pumping cycles. Based on the developed model, the setup of the optimal control problem (OCP) is described in detail along with its numerical solution based on the direct multiple shooting method in the CasADi optimization environment. Optimization results for a pumping cycle consisting of six lemniscates show that the approach is capable to find an optimal orbit in a few minutes of computation time. For this optimal orbit, the power output is increased by a factor of two compared to a sophisticated initial guess for the considered test scenario.
Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, …
Graph coloring has been employed since the 1980s to efficiently compute sparse Jacobian and Hessian matrices using either finite differences or automatic differentiation. Several coloring problems occur in this context, depending on whether the matrix is a Jacobian or a Hessian, and on the specifics of the computational techniques employed. We consider eight variant vertex coloring problems here. This article begins with a gentle introduction to the problem of computing a sparse Jacobian, followed by an overview of the historical development of the research area. Then we present a unifying framework for the graph models of the variant matrix estimation problems. The framework is based upon the viewpoint that a partition of a matrix into structurally orthogonal groups of columns corresponds to distance-2 coloring an appropriate graph representation. The unified framework helps integrate earlier work and leads to fresh insights; enables the design of more efficient algorithms for many problems; leads to new algorithms for others; and eases the task of building graph models for new problems. We report computational results on two of the coloring problems to support our claims. Most of the methods for these problems treat a column or a row of a matrix as an atomic entity, and partition the columns or rows (or both). A brief review of methods that do not fit these criteria is provided. We also discuss results in discrete mathematics and theoretical computer science that intersect with the topics considered here.