SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

All published works (240)

A Comparative Study of MINLP and MPVC Formulations for Solving Complex Nonlinear Decision-Making Problems in Aerospace Applications

2025-04-03
Andrea Ghezzi , Armin Nurkanović , Avishai Weiss +2 more
High-level decision-making for dynamical systems often involves performance and safety specifications that are activated or deactivated depending on conditions related to the system state and commands. Such decision-making problems can … High-level decision-making for dynamical systems often involves performance and safety specifications that are activated or deactivated depending on conditions related to the system state and commands. Such decision-making problems can be naturally formulated as optimization problems where these conditional activations are regulated by discrete variables. However, solving these problems can be challenging numerically, even on powerful computing platforms, especially when the dynamics are nonlinear. In this work, we consider decision-making for nonlinear systems where certain constraints, as well as possible terms in the cost function, are activated or deactivated depending on the system state and commands. We show that these problems can be formulated either as mixed-integer nonlinear programs (MINLPs) or as mathematical programs with vanishing constraints (MPVCs), where the former formulation involves discrete decision variables, whereas the latter relies on continuous variables subject to structured nonconvex constraints. We discuss the different solution methods available for both formulations and demonstrate them on optimal trajectory planning problems in various aerospace applications. Finally, we compare the strengths and weaknesses of the MINLP and MPVC approaches through a focused case study on powered descent guidance with divert-feasible regions.
Chat View PDF

A Numerically Efficient Method to Enhance Model Predictive Control Performance with a Reinforcement Learning Policy

2025-04-03
Andrea Ghezzi , Rudolf Reiter , Katrin Baumgärtner +2 more
We propose a novel approach for combining model predictive control (MPC) with reinforcement learning (RL) to reduce online computation while achieving high closed-loop tracking performance and constraint satisfaction. This method, … We propose a novel approach for combining model predictive control (MPC) with reinforcement learning (RL) to reduce online computation while achieving high closed-loop tracking performance and constraint satisfaction. This method, called Policy-Enhanced Partial Tightening (PEPT), approximates the optimal value function through a Riccati recursion around a state-control trajectory obtained by evaluating the RL policy. The result is a convex quadratic terminal cost that can be seamlessly integrated into the MPC formulation. The proposed controller is tested in simulations on a trajectory tracking problem for a quadcopter with nonlinear dynamics and bounded state and control. The results highlight PEPT's effectiveness, outperforming both pure RL policies and several MPC variations. Compared to pure RL, PEPT achieves 1000 times lower constraint violation cost with only twice the feedback time. Against the best MPC-based policy, PEPT reduces constraint violations by 2 to 5 times and runs nearly 3 times faster while maintaining similar tracking performance. The code is open-source at www.github.com/aghezz1/pept.
Chat View PDF

Synthesis of Model Predictive Control and Reinforcement Learning: Survey and Classification

2025-02-04
Rudolf Reiter , Jasper Hoffmann , Dirk Reinhardt +6 more
The fields of MPC and RL consider two successful control techniques for Markov decision processes. Both approaches are derived from similar fundamental principles, and both are widely used in practical … The fields of MPC and RL consider two successful control techniques for Markov decision processes. Both approaches are derived from similar fundamental principles, and both are widely used in practical applications, including robotics, process control, energy systems, and autonomous driving. Despite their similarities, MPC and RL follow distinct paradigms that emerged from diverse communities and different requirements. Various technical discrepancies, particularly the role of an environment model as part of the algorithm, lead to methodologies with nearly complementary advantages. Due to their orthogonal benefits, research interest in combination methods has recently increased significantly, leading to a large and growing set of complex ideas leveraging MPC and RL. This work illuminates the differences, similarities, and fundamentals that allow for different combination algorithms and categorizes existing work accordingly. Particularly, we focus on the versatile actor-critic RL approach as a basis for our categorization and examine how the online optimization approach of MPC can be used to improve the overall closed-loop performance of a policy.
Chat View PDF

Solgenia -- A Test Vessel Toward Energy-Efficient Autonomous Water Taxi Applications

2025-02-03
Hannes Homburger , Stefan Wirtensohn , Patrick Hoher +4 more
Autonomous surface vessels are a promising building block of the future's transport sector and are investigated by research groups worldwide. This paper presents a comprehensive and systematic overview of the … Autonomous surface vessels are a promising building block of the future's transport sector and are investigated by research groups worldwide. This paper presents a comprehensive and systematic overview of the autonomous research vessel Solgenia including the latest investigations and recently presented methods that contributed to the fields of autonomous systems, applied numerical optimization, nonlinear model predictive control, multi-extended-object-tracking, computer vision, and collision avoidance. These are considered to be the main components of autonomous water taxi applications. Autonomous water taxis have the potential to transform the traffic in cities close to the water into a more efficient, sustainable, and flexible future state. Regarding this transformation, the test platform Solgenia offers an opportunity to gain new insights by investigating novel methods in real-world experiments. An established test platform will strongly reduce the effort required for real-world experiments in the future.
Chat View PDF

MPC4RL -- A Software Package for Reinforcement Learning based on Model Predictive Control

2025-01-27
Dirk Reinhardt , Katrin Baumgärnter , Jonathan Frey +2 more
In this paper, we present an early software integrating Reinforcement Learning (RL) with Model Predictive Control (MPC). Our aim is to make recent theoretical contributions from the literature more accessible … In this paper, we present an early software integrating Reinforcement Learning (RL) with Model Predictive Control (MPC). Our aim is to make recent theoretical contributions from the literature more accessible to both the RL and MPC communities. We combine standard software tools developed by the RL community, such as Gymnasium, stable-baselines3, or CleanRL with the acados toolbox, a widely-used software package for efficient MPC algorithms. Our core contribution is MPC4RL, an open-source Python package that supports learning-enhanced MPC schemes for existing acados implementations. The package is designed to be modular, extensible, and user-friendly, facilitating the tuning of MPC algorithms for a broad range of control problems. It is available on GitHub.
Chat View PDF

Implicit Central Difference Approximations of Averaged Dynamics of Highly Oscillatory Systems With Applications to Direct Optimal Control

2025-01-22
Jakob Harzer , Jochem De Schutter , Per Rutquist +1 more
ABSTRACT Trajectory optimization of highly oscillatory systems can require huge computational efforts if the horizon of the problem is much larger than the duration of a single cycle. To alleviate … ABSTRACT Trajectory optimization of highly oscillatory systems can require huge computational efforts if the horizon of the problem is much larger than the duration of a single cycle. To alleviate this effort, stroboscopic averaging methods can be used, which utilize local single‐cycle simulations of the oscillatory dynamics to then approximate the average dynamics of the system and integrate them with integration steps much larger than a single cycle. Targeting especially the field of direct optimal control, where, after discretization, the simulation of the dynamics is often included implicitly in the equality constraints of the nonlinear programming problem, we introduce an implicit central difference scheme for the approximation of the average dynamics. In the introduced implicit central difference methods, we solve a nonlinear system of equations that connects single‐cycle simulations of the oscillatory dynamics in order to approximate the average dynamics from a linear combination of points in state‐space. We derive the accuracy order for this generalized ‐point central difference approximation of the average dynamics and confirm the claims in numerical experiments. Compared to existing explicit approaches, the introduced methods are up to twice as efficient while maintaining the same level of accuracy.

Towards Solutions of Manipulation Tasks via Optimal Control of Projected Dynamical Systems

2025-01-21
Anton Pozharskiy , Armin Nurkanović , Moritz Diehl
We introduce a modeling framework for manipulation planning based on the formulation of the dynamics as a projected dynamical system. This method uses implicit signed distance functions and their gradients … We introduce a modeling framework for manipulation planning based on the formulation of the dynamics as a projected dynamical system. This method uses implicit signed distance functions and their gradients to formulate an equivalent gradient complementarity system. The optimal control problem is then solved via a direct method, discretized using finite-elements with switch detection. An extension to this approach is provided in the form of a friction formulation commonly used in quasi-static models. We show that this approach is able to generate trajectories for problems including multiple pushers, friction, and non-convex objects modeled as unions of convex ellipsoids with reasonable computational effort.
Chat View PDF

Multi‐Phase Optimal Control Problems for Efficient Nonlinear Model Predictive Control With acados

2025-01-16
Jonathan Frey , Katrin Baumgärtner , Gianluca Frison +1 more
ABSTRACT Computationally efficient nonlinear model predictive control (NMPC) relies on elaborate discrete‐time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous‐time problem and online computational burden. … ABSTRACT Computationally efficient nonlinear model predictive control (NMPC) relies on elaborate discrete‐time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous‐time problem and online computational burden. Such formulations, however, are in general not easy to implement within specialized software frameworks tailored to numerical optimal control. This article introduces a new multi‐phase optimal control problem (MOCP) interface for the open‐source software acados allowing to conveniently formulate such problems and generate fast solvers that can be used for NMPC. While multi‐phase OCP formulations occur naturally in many applications, such as, for example, walking robots, this work focuses on MOCP formulations that can be used to efficiently approximate standard continuous‐time OCPs in the context of NMPC. To this end, the article discusses advanced control parametrizations, such as closed‐loop costing and piecewise polynomials with varying degree, as well as partial tightening and formulations that leverage models of different fidelity. An introductory example is presented to showcase the usability of the new interface. Finally, three numerical experiments demonstrate that NMPC controllers based on multi‐phase formulations can efficiently trade off computation time and control performance.
Chat View PDF

An Efficient Mixed-Integer Formulation and an Iterative Method for Optimal Control of Switched Systems Under Dwell Time Constraints

2025-01-09
Ramin Abbasi-Esfeden , Armin Nurkanović , Moritz Diehl +2 more
This paper presents an efficient Mixed-Integer Nonlinear Programming (MINLP) formulation for systems with discrete control inputs under dwell time constraints. By viewing such systems as a switched system, the problem … This paper presents an efficient Mixed-Integer Nonlinear Programming (MINLP) formulation for systems with discrete control inputs under dwell time constraints. By viewing such systems as a switched system, the problem is decomposed into a Sequence Optimization (SO) and a Switching Time Optimization (STO) -- the former providing the sequence of the switched system, and the latter calculating the optimal switching times. By limiting the feasible set of SO to subsequences of a master sequence, this formulation requires a small number of binary variables, independent of the number of time discretization nodes. This enables the proposed formulation to provide solutions efficiently, even for large numbers of time discretization nodes. To provide even faster solutions, an iterative algorithm is introduced to heuristically solve STO and SO. The proposed approaches are then showcased on four different switched systems and results demonstrate the efficiency of the MINLP formulation and the iterative algorithm.
Chat View PDF

LCQPow: a solver for linear complementarity quadratic programs

2024-12-16
Jonas Hall , Armin Nurkanović , Florian Messerer +1 more

MPC4RL - A Software Package for Reinforcement Learning based on Model Predictive Control

2024-12-16
Dirk Reinhardt , Katrin Baumgärtner , Jonathan Frey +2 more
Chat View PDF

Parallelizable Parametric Nonlinear System Identification via tuning of a Moving Horizon State Estimator

2024-12-16
Léo Simpson , Jonas Asprion , Simon Muntwiler +2 more
Chat View PDF

First-Order Sweeping Processes and Extended Projected Dynamical Systems: Equivalence, Time-Discretization and Numerical Optimal Control

2024-12-15
Anton Pozharskiy , Armin Nurkanović , Moritz Diehl
Constrained dynamical systems are systems such that, by some means, the state stays within a given set. Two such systems are the (perturbed) Moreau sweeping process and the recently proposed … Constrained dynamical systems are systems such that, by some means, the state stays within a given set. Two such systems are the (perturbed) Moreau sweeping process and the recently proposed extended Projected Dynamical System (ePDS). We show that under certain conditions solutions to the ePDS correspond to the solutions of a dynamic complementarity system, similar to the one equivalent to ordinary PDS. We then show that the perturbed sweeping process with time varying set can, under similar conditions, be reformulated as an ePDS. In this paper, we leverage these equivalences to develop an accurate discretization method for perturbed first-order Moreau sweeping processes via the finite elements with switch detection method. This allows the efficient optimal control of systems governed by ePDS and perturbed first-order sweeping processes.
Chat View PDF

L4acados: Learning-based models for acados, applied to Gaussian process-based predictive control

2024-11-28
Amon Lahr , Joshua Näf , Kim P. Wabersich +5 more
Incorporating learning-based models, such as Gaussian processes (GPs), into model predictive control (MPC) strategies can significantly improve control performance and online adaptation capabilities for real-world applications. Still, despite recent advances … Incorporating learning-based models, such as Gaussian processes (GPs), into model predictive control (MPC) strategies can significantly improve control performance and online adaptation capabilities for real-world applications. Still, despite recent advances in numerical optimization and real-time GP inference, its widespread application is limited by the lack of an efficient and modular open-source implementation. This work aims at filling this gap by providing an efficient implementation of zero-order Gaussian process-based MPC in acados, as well as L4acados, a general framework for incorporating non-CasADi (learning-based) residual models in acados. By providing the required sensitivities via a user-defined Python module, L4acados enables the implementation of MPC controllers with learning-based residual models in acados, while supporting custom Jacobian approximations, as well as parallelization of sensitivity computations when preparing the quadratic subproblems. The computational efficiency of L4acados is benchmarked against available software using a neural network-based control example. Last, it is used demonstrate the performance of the zero-order GP-MPC method applied to two hardware examples: autonomous miniature racing, as well as motion control of a full-scale autonomous vehicle for an ISO lane change maneuver.
Chat View PDF

Real-Time-Feasible Collision-Free Motion Planning For Ellipsoidal Objects

2024-09-18
Yunfan Gao , Florian Messerer , Niels van Duijkeren +2 more
Online planning of collision-free trajectories is a fundamental task for robotics and self-driving car applications. This paper revisits collision avoidance between ellipsoidal objects using differentiable constraints. Two ellipsoids do not … Online planning of collision-free trajectories is a fundamental task for robotics and self-driving car applications. This paper revisits collision avoidance between ellipsoidal objects using differentiable constraints. Two ellipsoids do not overlap if and only if the endpoint of the vector between the center points of the ellipsoids does not lie in the interior of the Minkowski sum of the ellipsoids. This condition is formulated using a parametric over-approximation of the Minkowski sum, which can be made tight in any given direction. The resulting collision avoidance constraint is included in an optimal control problem (OCP) and evaluated in comparison to the separating-hyperplane approach. Not only do we observe that the Minkowski-sum formulation is computationally more efficient in our experiments, but also that using pre-determined over-approximation parameters based on warm-start trajectories leads to a very limited increase in suboptimality. This gives rise to a novel real-time scheme for collision-free motion planning with model predictive control (MPC). Both the real-time feasibility and the effectiveness of the constraint formulation are demonstrated in challenging real-world experiments.
Chat View PDF

Solving Mathematical Programs with Complementarity Constraints Arising in Nonsmooth Optimal Control

2024-08-27
Armin Nurkanović , Anton Pozharskiy , Moritz Diehl
Abstract This paper examines solution methods for mathematical programs with complementarity constraints (MPCC) obtained from the time-discretization of optimal control problems (OCPs) subject to nonsmooth dynamical systems. The MPCC theory … Abstract This paper examines solution methods for mathematical programs with complementarity constraints (MPCC) obtained from the time-discretization of optimal control problems (OCPs) subject to nonsmooth dynamical systems. The MPCC theory and stationarity concepts are reviewed and summarized. The focus is on relaxation-based methods for MPCCs, which solve a (finite) sequence of more regular nonlinear programs (NLP), where a regularization/homotopy parameter is driven to zero. Such methods perform reasonably well on currently available benchmarks. However, these results do not always generalize to MPCCs obtained from nonsmooth OCPs. To provide a more complete picture, this paper introduces a novel benchmark collection of such problems, which we call . The problem set includes 603 different MPCCs and we split it into a few representative subsets to accelerate the testing. We compare different relaxation-based methods, NLP solvers, homotopy parameter update and relaxation parameter steering strategies. Moreover, we check whether the obtained stationary points allow first-order descent directions, which may be the case for some of the weaker MPCC stationarity concepts. In the best case, the Scholtes’ relaxation (SIAM J. Optim. 11 , 918–936, 2001) with (Math. Program. 106 , 25–57, 2006) as NLP solver manages to solve 73.8% of the problems. This highlights the need for further improvements in algorithms and software for MPCCs.

Multi-Phase Optimal Control Problems for Efficient Nonlinear Model Predictive Control with acados

2024-08-24
Jonathan Frey , Katrin Baumgärtner , Gianluca Frison +1 more
Computationally efficient nonlinear model predictive control relies on elaborate discrete-time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous-time problem and associated computational burden. Such formulations, … Computationally efficient nonlinear model predictive control relies on elaborate discrete-time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous-time problem and associated computational burden. Such formulations, however, are in general not easy to implement within specialized software frameworks tailored to numerical optimal control. This paper introduces a new multi-phase OCP interface for the open-source software acados allowing to conveniently formulate such problems and generate fast solvers that can be used for nonlinear model predictive control (NMPC). While multi-phase OCP (MOCP) formulations occur naturally in many applications, this work focuses on MOCP formulations that can be used to efficiently approximate standard continuous-time OCPs in the context of NMPC. To this end, the paper discusses advanced control parametrizations, such as closed-loop costing and piecewise polynomials with varying degree, as well as partial tightening and formulations that leverage models of different fidelity. An introductory example is presented to showcase the usability of the new interface. Finally, three numerical experiments demonstrate that NMPC controllers based on multi-phase formulations can efficiently trade-off computation time and control performance.
Chat View PDF

Multi-Phase Optimal Control Problems for Efficient Nonlinear Model Predictive Control with acados

2024-08-14
Jonathan Frey , Katrin Baumgärtner , Gianluca Frison +1 more
Computationally efficient nonlinear model predictive control relies on elaborate discrete-time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous-time problem and associated computational burden. Such formulations, … Computationally efficient nonlinear model predictive control relies on elaborate discrete-time optimal control problem (OCP) formulations trading off accuracy with respect to the continuous-time problem and associated computational burden. Such formulations, however, are in general not easy to implement within specialized software frameworks tailored to numerical optimal control. This paper introduces a new multi-phase OCP interface for the open-source software acados allowing to conveniently formulate such problems and generate fast solvers that can be used for nonlinear model predictive control (NMPC). While multi-phase OCP (MOCP) formulations occur naturally in many applications, this work focuses on MOCP formulations that can be used to efficiently approximate standard continuous-time OCPs in the context of NMPC. To this end, the paper discusses advanced control parametrizations, such as closed-loop costing and piecewise polynomials with varying degree, as well as partial tightening and formulations that leverage models of different fidelity. An introductory example is presented to showcase the usability of the new interface. Finally, three numerical experiments demonstrate that NMPC controllers based on multi-phase formulations can efficiently trade-off computation time and control performance.
Chat View PDF

Stochastic Model Predictive Control with Optimal Linear Feedback for Mobile Robots in Dynamic Environments

2024-07-19
Yunfan Gao , Florian Messerer , Niels van Duijkeren +1 more
Robot navigation around humans can be a challenging problem since human movements are hard to predict. Stochastic model predictive control (MPC) can account for such uncertainties and approximately bound the … Robot navigation around humans can be a challenging problem since human movements are hard to predict. Stochastic model predictive control (MPC) can account for such uncertainties and approximately bound the probability of a collision to take place. In this paper, to counteract the rapidly growing human motion uncertainty over time, we incorporate state feedback in the stochastic MPC. This allows the robot to more closely track reference trajectories. To this end the feedback policy is left as a degree of freedom in the optimal control problem. The stochastic MPC with feedback is validated in simulation experiments and is compared against nominal MPC and stochastic MPC without feedback. The added computation time can be limited by reducing the number of additional variables for the feedback law with a small compromise in control performance.
Chat View PDF

Progressive Smoothing for Motion Planning in Real-Time NMPC

2024-06-25
Rudolf Reiter , Katrin Baumgärtner , Rien Quirynen +1 more
Chat View PDF

Efficient Zero-Order Robust Optimization for Real-Time Model Predictive Control with acados

2024-06-25
Jonathan Frey , Yunfan Gao , Florian Messerer +3 more
Chat View PDF

Finite Elements with Switch Detection for numerical optimal control of nonsmooth dynamical systems with set-valued heaviside step functions

2024-06-08
Armin Nurkanović , Anton Pozharskiy , Jonathan Frey +1 more
Chat View PDF

AC4MPC: Actor-Critic Reinforcement Learning for Nonlinear Model Predictive Control

2024-06-06
Rudolf Reiter , Andrea Ghezzi , Katrin Baumgärtner +3 more
\Ac{MPC} and \ac{RL} are two powerful control strategies with, arguably, complementary advantages. In this work, we show how actor-critic \ac{RL} techniques can be leveraged to improve the performance of \ac{MPC}. … \Ac{MPC} and \ac{RL} are two powerful control strategies with, arguably, complementary advantages. In this work, we show how actor-critic \ac{RL} techniques can be leveraged to improve the performance of \ac{MPC}. The \ac{RL} critic is used as an approximation of the optimal value function, and an actor roll-out provides an initial guess for primal variables of the \ac{MPC}. A parallel control architecture is proposed where each \ac{MPC} instance is solved twice for different initial guesses. Besides the actor roll-out initialization, a shifted initialization from the previous solution is used. Thereafter, the actor and the critic are again used to approximately evaluate the infinite horizon cost of these trajectories. The control actions from the lowest-cost trajectory are applied to the system at each time step. We establish that the proposed algorithm is guaranteed to outperform the original \ac{RL} policy plus an error term that depends on the accuracy of the critic and decays with the horizon length of the \ac{MPC} formulation. Moreover, we do not require globally optimal solutions for these guarantees to hold. The approach is demonstrated on an illustrative toy example and an \ac{AD} overtaking scenario.
Chat View PDF

Gauss–Newton Runge–Kutta integration for efficient discretization of optimal control problems with long horizons and least-squares costs

2024-06-01
Jonathan Frey , Katrin Baumgärtner , Moritz Diehl
This work proposes an efficient treatment of continuous-time optimal control problems with long horizons and nonlinear least-squares costs. In particular, we present the Gauss–Newton Runge–Kutta (GNRK) integrator which provides a … This work proposes an efficient treatment of continuous-time optimal control problems with long horizons and nonlinear least-squares costs. In particular, we present the Gauss–Newton Runge–Kutta (GNRK) integrator which provides a high-order cost integration. Crucially, the Hessian of the cost terms required within an SQP-type algorithm is approximated with a Gauss–Newton Hessian. Moreover, L2 penalty formulations for constraints are shown to be particularly effective for optimization with GNRK. An efficient implementation of GNRK is provided in the open-source software framework acados. We demonstrate the effectiveness of the proposed approach and its implementation on an illustrative example showing a reduction of relative suboptimality by a factor greater than 10 while increasing the runtime by only 10%.
Chat View PDF

Finite Elements with Switch Detection for direct optimal control of nonsmooth systems

2024-05-24
Armin Nurkanović , Mario Sperl , Sebastian Albrecht +1 more
Abstract This paper introduces Finite Elements with Switch Detection (FESD), a numerical discretization method for nonsmooth differential equations. We consider the Filippov convexification of these systems and a transformation into … Abstract This paper introduces Finite Elements with Switch Detection (FESD), a numerical discretization method for nonsmooth differential equations. We consider the Filippov convexification of these systems and a transformation into dynamic complementarity systems introduced by Stewart (Numer Math 58(1):299–328, 1990). FESD is based on solving nonlinear complementarity problems and can automatically detect nonsmooth events in time. If standard time-stepping Runge–Kutta (RK) methods are naively applied to a nonsmooth ODE, the accuracy is at best of order one. In FESD, we let the integrator step size be a degree of freedom. Additional complementarity conditions, which we call cross complementarities , enable exact switch detection, hence FESD can recover the high order accuracy that the RK methods enjoy for smooth ODE. Additional conditions called step equilibration allow the step size to change only when switches occur and thus avoid spurious degrees of freedom. Convergence results for the FESD method are derived, local uniqueness of the solution and convergence of numerical sensitivities are proven. The efficacy of FESD is demonstrated in several simulation and optimal control examples. In an optimal control problem benchmark with FESD, we achieve up to five orders of magnitude more accurate solutions than a standard time-stepping approach for the same computational time.
Chat View PDF

A Long-Short-Term Mixed-Integer Formulation for Highway Lane Change Planning

2024-05-05
Rudolf Reiter , Armin Nurkanović , Daniele Bernadini +2 more
This work considers the problem of optimal lane changing in a structured multi-agent road environment. A novel motion planning algorithm that can capture long-horizon dependencies as well as short-horizon dynamics … This work considers the problem of optimal lane changing in a structured multi-agent road environment. A novel motion planning algorithm that can capture long-horizon dependencies as well as short-horizon dynamics is presented. Pivotal to our approach is a geometric approximation of the long-horizon combinatorial transition problem which we formulate in the continuous time-space domain. Moreover, a discrete-time formulation of a short-horizon optimal motion planning problem is formulated and combined with the long-horizon planner. Both individual problems, as well as their combination, are formulated as MIQP and solved in real-time by using state-of-the-art solvers. We show how the presented algorithm outperforms two other state-of-the-art motion planning algorithms in closed-loop performance and computation time in lane changing problems. Evaluations are performed using the traffic simulator SUMO, a custom low-level tracking model predictive controller, and high-fidelity vehicle models and scenarios, provided by the CommonRoad environment.
Chat View PDF

Approximate propagation of normal distributions for stochastic optimal control of nonsmooth systems

2024-04-25
Florian Messerer , Katrin Baumgärtner , Armin Nurkanović +1 more
We present a method for the approximate propagation of mean and covariance of a probability distribution through ordinary differential equations (ODE) with discontinuous right-hand side. For piecewise affine systems, a … We present a method for the approximate propagation of mean and covariance of a probability distribution through ordinary differential equations (ODE) with discontinuous right-hand side. For piecewise affine systems, a normalization of the propagated probability distribution at every time step allows us to analytically compute the expectation integrals of the mean and covariance dynamics while explicitly taking into account the discontinuity. This leads to a natural smoothing of the discontinuity such that for relevant levels of uncertainty the resulting ODE can be integrated directly with standard schemes and it is neither necessary to prespecify the switching sequence nor to use a switch detection method. We then show how this result can be employed in the more general case of piecewise smooth functions based on a structure preserving linearization scheme. The resulting dynamics can be straightforwardly used within standard formulations of stochastic optimal control problems with chance constraints.
Chat View PDF

A Sequential Benders-based Mixed-Integer Quadratic Programming Algorithm

2024-04-17
Andrea Ghezzi , Wim Van Roy , Sebastian Säger +1 more
For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality … For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact. The aim of the presented sequential mixed-integer quadratic programming (MIQP) algorithm for mixed-integer nonlinear problems (MINLPs) is to extend the SQP/SCP methodology to MINLPs and leverage the availability of efficient MIQP solvers. The algorithm employs a three-step method in each iterate: First, the MINLP is linearized at a given iterate. Second, an MIQP with its feasible set restricted to a specific region around the current linearization point is formulated and solved. Third, the integer variables obtained from the MIQP solution are fixed, and only an NLP in the continuous variables is solved. The outcome of the third step is compared to previous iterates, and the best iterate so far is used as a linearization point in the next iterate. Crucially, the objective values and derivatives from all previous iterates are used to formulate the polyhedral region in the second step. The linear inequalities that define the region build on concepts from generalized Benders' decomposition for MINLPs. Although the presented MINLP algorithm is a heuristic method without any global optimality guarantee, it converges to the exact integer solution when applied to convex MINLP with a linear outer structure. The conducted numerical experiments demonstrate that the proposed algorithm is competitive with other open-source solvers for MINLP. Finally, we solve two mixed-integer optimal control problems (MIOCPs) transcribed into MINLPs via direct methods, showing that the presented algorithm can effectively deal with nonlinear equality constraints, a major hurdle for generic MINLP solvers.
Chat View PDF

Finite Elements with Switch Detection for Numerical Optimal Control of Projected Dynamical Systems

2024-04-08
Anton Pozharskiy , Armin Nurkanović , Moritz Diehl
The Finite Elements with Switch Detection (FESD) method is a highly accurate direct transcription method for optimal control of several classes of nonsmooth dynamical systems. This paper extends the FESD … The Finite Elements with Switch Detection (FESD) method is a highly accurate direct transcription method for optimal control of several classes of nonsmooth dynamical systems. This paper extends the FESD method to Projected Dynamical Systems (PDS) and first-order sweeping processes with time-independent sets. This method discretizes an equivalent dynamic complementarity system and exploits the particular structure of the discontinuities present in these systems. In the FESD method, allowing integration step sizes to be degrees of freedom, and introducing additional complementarity constraints, enables the exact detection of nonsmooth events. In contrast to the standard fixed-step Runge-Kutta methods, this approach allows for the recovery of full-order integration accuracy and the correct computation of numerical sensitivities. Numerical examples illustrate the effectiveness of the proposed method in an optimal control context. This method and the examples are included in the open-source software package nosnoc.
Chat View PDF

Parallelizable Parametric Nonlinear System Identification via tuning of a Moving Horizon State Estimator

2024-03-26
Léo Simpson , Jonas Asprion , Simon Muntwiler +2 more
This paper introduces a novel optimization-based approach for parametric nonlinear system identification. Building upon the prediction error method framework, traditionally used for linear system identification, we extend its capabilities to … This paper introduces a novel optimization-based approach for parametric nonlinear system identification. Building upon the prediction error method framework, traditionally used for linear system identification, we extend its capabilities to nonlinear systems. The predictions are computed using a moving horizon state estimator with a constant arrival cost. Eventually, both the system parameters and the arrival cost are estimated by minimizing the sum of the squared prediction errors. Since the predictions are induced by the state estimator, the method can be viewed as the tuning of a state estimator, based on its predictive capacities. The present extension of the prediction error method not only enhances performance for nonlinear systems but also enables learning from multiple trajectories with unknown initial states, broadening its applicability in practical scenarios. Additionally, the novel formulation leaves room for the design of efficient and parallelizable optimization algorithms, since each output prediction only depends on a fixed window of past actions and measurements. In the special case of linear time-invariant systems, we show an important property of the proposed method which suggests asymptotic consistency under reasonable assumptions. Numerical examples illustrate the effectiveness and practicality of the approach, and one of the examples also highlights the necessity for the arrival cost.
Chat View PDF

High Accuracy Numerical Optimal Control for Rigid Bodies with Patch Contacts through Equivalent Contact Points -- Extended Version

2024-03-20
Christian Dietz , Armin Nurkanović , Sebastian Albrecht +1 more
This paper extends the Finite Elements with Switch Detection and Jumps (FESD-J) [1] method to problems of rigid body dynamics involving patch contacts. The FESD-J method is a high accuracy … This paper extends the Finite Elements with Switch Detection and Jumps (FESD-J) [1] method to problems of rigid body dynamics involving patch contacts. The FESD-J method is a high accuracy discretization scheme suitable for use in direct optimal control of nonsmooth mechanical systems. It detects dynamic switches exactly in time and, thereby, maintains the integration order of the underlying Runge- Kutta (RK) method. This is in contrast to commonly used time-stepping methods which only achieve first-order accuracy. Considering rigid bodies with possible patch contacts results in nondifferentiable signed distance functions (SDF), which introduces additional nonsmoothness into the dynamical system. In this work, we utilize so-called equivalent contact points (ECP), which parameterize force and impulse distributions on contact patches by evaluation at single points. We embed a nondifferentiable SDF into a complementarity Lagrangian system (CLS) and show that the determined ECP are well-defined. We then extend the FESD-J discretization to the considered CLS such that its integration accuracy is maintained. The functionality of the method is illustrated for both a simulation and an optimal control example.
Chat View PDF

Fast Generation of Feasible Trajectories in Direct Optimal Control

2024-03-15
David Kiessling , Katrin Baumgärtner , Jonathan Frey +3 more
This paper examines the question of finding feasible points to discrete-time optimal control problems. The optimization problem of finding a feasible trajectory is transcribed to an unconstrained optimal control problem. … This paper examines the question of finding feasible points to discrete-time optimal control problems. The optimization problem of finding a feasible trajectory is transcribed to an unconstrained optimal control problem. An efficient algorithm, called FP-DDP, is proposed that solves the resulting problem using Differential Dynamic Programming preserving feasibility with respect to the system dynamics in every iteration. Notably, FP-DDP admits global and rapid local convergence properties induced by a combination of a Levenberg-Marquardt method and an Armijo-type line search. The efficiency of FP-DDP is demonstrated against established methods such as Direct Multiple Shooting, Direct Single Shooting, and state-of-the-art solvers.
Chat View PDF

Advanced-Step Real-time Iterations with Four Levels -- New Error Bounds and Fast Implementation in acados

2024-03-11
Jonathan Frey , Armin Nurkanović , Moritz Diehl
The Real-Time Iteration (RTI) is an online nonlinear model predictive control algorithm that performs a single Sequential Quadratic Programming (SQP) per sampling time. The algorithm is split into a preparation … The Real-Time Iteration (RTI) is an online nonlinear model predictive control algorithm that performs a single Sequential Quadratic Programming (SQP) per sampling time. The algorithm is split into a preparation and a feedback phase, where the latter one performs as little computations as possible solving a single prepared quadratic program. To further improve the accuracy of this method, the Advanced-Step RTI (AS-RTI) performs additional Multi-Level Iterations (MLI) in the preparation phase, such as inexact or zero-order SQP iterations on a problem with a predicted state estimate. This paper extends and streamlines the existing local convergence analysis of AS-RTI, such as analyzing MLI of level A and B for the first time, and significantly simplifying the proofs for levels C and D. Moreover, this paper provides an efficient open-source implementation in acados, making it widely accessible to practitioners.
Chat View PDF

Fourth-order suboptimality of nominal model predictive control in the presence of uncertainty

2024-03-07
Florian Messerer , Katrin Baumgärtner , Sergio Lucia +1 more
We investigate the suboptimality resulting from the application of nominal model predictive control (MPC) to a nonlinear discrete time stochastic system. The suboptimality is defined with respect to the corresponding … We investigate the suboptimality resulting from the application of nominal model predictive control (MPC) to a nonlinear discrete time stochastic system. The suboptimality is defined with respect to the corresponding stochastic optimal control problem (OCP) that minimizes the expected cost of the closed loop system. In this context, nominal MPC corresponds to a form of certainty-equivalent control (CEC). We prove that, in a smooth and unconstrained setting, the suboptimality growth is of fourth order with respect to the level of uncertainty, a parameter which we can think of as a standard deviation. This implies that the suboptimality does not grow very quickly as the level of uncertainty is increased, providing further insight into the practical success of nominal MPC. Similarly, the difference between the optimal and suboptimal control inputs is of second order. We illustrate the result on a simple numerical example, which we also use to show how the proven relationship may cease to hold in the presence of state constraints.
Chat View PDF

Progressive Smoothing for Motion Planning in Real-Time NMPC

2024-03-04
Rudolf Reiter , Katrin Baumgärtner , Rien Quirynen +1 more
Nonlinear model predictive control (NMPC) is a popular strategy for solving motion planning problems, including obstacle avoidance constraints, in autonomous driving applications. Non-smooth obstacle shapes, such as rectangles, introduce additional … Nonlinear model predictive control (NMPC) is a popular strategy for solving motion planning problems, including obstacle avoidance constraints, in autonomous driving applications. Non-smooth obstacle shapes, such as rectangles, introduce additional local minima in the underlying optimization problem. Smooth over-approximations, e.g., ellipsoidal shapes, limit the performance due to their conservativeness. We propose to vary the smoothness and the related over-approximation by a homotopy. Instead of varying the smoothness in consecutive sequential quadratic programming iterations, we use formulations that decrease the smooth over-approximation from the end towards the beginning of the prediction horizon. Thus, the real-time iterations algorithm is applicable to the proposed NMPC formulation. Different formulations are compared in simulation experiments and shown to successfully improve performance indicators without increasing the computation time.
Chat View PDF

Decentralized real-time iterations for distributed nonlinear model predictive control

2024-01-26
Gösta Stomberg , Alexander Engelmann , Moritz Diehl +1 more
This article presents a Real-Time Iteration (RTI) scheme for distributed Nonlinear Model Predictive Control (NMPC). The scheme transfers the well-known RTI approach, a key enabler for many industrial real-time NMPC … This article presents a Real-Time Iteration (RTI) scheme for distributed Nonlinear Model Predictive Control (NMPC). The scheme transfers the well-known RTI approach, a key enabler for many industrial real-time NMPC implementations, to the setting of cooperative distributed control. At each sampling instant, one outer iteration of a bi-level decentralized Sequential Quadratic Programming (dSQP) method is applied to a centralized optimal control croblem. This ensures that real-time requirements are met and it facilitates cooperation between subsystems. Combining novel dSQP convergence results with RTI stability guarantees, we prove local exponential stability under standard assumptions on the MPC design with and without terminal constraints. The proposed scheme only requires neighbor-to-neighbor communication and avoids a central coordinator. A numerical example with coupled inverted pendulums demonstrates the efficacy of the approach.
Chat View PDF

Fast System Level Synthesis: Robust Model Predictive Control using Riccati Recursions

2024-01-01
Antoine P. Leeman , Johannes Köhler , Florian Messerer +3 more
System Level Synthesis (SLS) enables improved robust MPC formulations by allowing for joint optimization of the nominal trajectory and controller. This paper introduces a tailored algorithm for solving the corresponding … System Level Synthesis (SLS) enables improved robust MPC formulations by allowing for joint optimization of the nominal trajectory and controller. This paper introduces a tailored algorithm for solving the corresponding disturbance feedback optimization problem. The proposed algorithm builds on a recently proposed joint optimization scheme and iterates between optimizing the controller and the nominal trajectory while converging q-linearly to an optimal solution. We show that the controller optimization can be solved through Riccati recursions leading to a horizon-length, state, and input scalability of $\mathcal{O}(N^2 ( n_x^3 + n_u ^3 ) )$ for each iterate. On a numerical example, the proposed algorithm exhibits computational speedups of order $10$ to $10^3$ compared to general-purpose commercial solvers.
Chat View PDF

A Long-Short-Term Mixed-Integer Formulation for Highway Lane Change Planning

2024-01-01
Rudolf Reiter , Armin Nurkanović , Daniele Bernardini +2 more
This work considers the problem of optimal lane changing in a structured multi-agent road environment. A novel motion planning algorithm that can capture long-horizon dependencies as well as short-horizon dynamics … This work considers the problem of optimal lane changing in a structured multi-agent road environment. A novel motion planning algorithm that can capture long-horizon dependencies as well as short-horizon dynamics is presented. Pivotal to our approach is a geometric approximation of the long-horizon combinatorial transition problem which we formulate in the continuous time-space domain. Moreover, a discrete-time formulation of a short-horizon optimal motion planning problem is formulated and combined with the long-horizon planner. Both individual problems, as well as their combination, are formulated as mixed-integer quadratic programs (MIQPs) and solved in real-time by using state-of-the-art solvers. We show how the presented algorithm outperforms two other state-of-the-art motion planning algorithms in closed-loop performance and computation time in lane changing problems. Evaluations are performed using the traffic simulator <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SUMO</monospace> , a custom low-level tracking model predictive controller, and high-fidelity vehicle models and scenarios, provided by the <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CommonRoad</monospace> environment.
Chat View PDF

Equivariant Deep Learning of Mixed-Integer Optimal Control Solutions for Vehicle Decision Making and Motion Planning

2024-01-01
Rudolf Reiter , Rien Quirynen , Moritz Diehl +1 more
Mixed-integer quadratic programs (MIQPs) are a versatile way of formulating vehicle decision making and motion planning problems, where the prediction model is a hybrid dynamical system that involves both discrete … Mixed-integer quadratic programs (MIQPs) are a versatile way of formulating vehicle decision making and motion planning problems, where the prediction model is a hybrid dynamical system that involves both discrete and continuous decision variables. However, even the most advanced MIQP solvers can hardly account for the challenging requirements of automotive embedded platforms. Thus, we use machine learning to simplify and hence speed up optimization. Our work builds on recent ideas for solving MIQPs in real-time by training a neural network to predict the optimal values of integer variables and solving the remaining problem by online quadratic programming. Specifically, we propose a recurrent permutation equivariant deep set that is particularly suited for imitating MIQPs that involve many obstacles, which is often the major source of computational burden in motion planning problems. Our framework comprises also a feasibility projector that corrects infeasible predictions of integer variables and considerably increases the likelihood of computing a collision-free trajectory. We evaluate the performance, safety and real-time feasibility of decision-making for autonomous driving using the proposed approach on realistic multi-lane traffic scenarios with interactive agents in SUMO simulations.
Chat View PDF

Fast Generation of Feasible Trajectories in Direct Optimal Control

2024-01-01
David Kiessling , Katrin Baumgärtner , Jonathan Frey +3 more
This paper examines the question of finding feasible points to discrete-time optimal control problems. The optimization problem of finding a feasible trajectory is transcribed to an unconstrained optimal control problem. … This paper examines the question of finding feasible points to discrete-time optimal control problems. The optimization problem of finding a feasible trajectory is transcribed to an unconstrained optimal control problem. An efficient algorithm, called FP-DDP, is proposed that solves the resulting problem using Differential Dynamic Programming preserving feasibility with respect to the system dynamics in every iteration. Notably, FP-DDP admits global and rapid local convergence properties induced by a combination of a Levenberg-Marquardt method and an Armijo-type line search. An efficient implementation of FP-DDP within acados is compared to established methods such as Direct Multiple Shooting, Direct Single Shooting, and state-of-the-art solvers.
Chat View PDF

FESD-J: Finite Elements with Switch Detection for numerical optimal control of rigid bodies with impacts and Coulomb friction

2023-12-28
Armin Nurkanović , Jonathan Frey , Anton Pozharskiy +1 more
Chat View PDF

An Efficient Method for the Joint Estimation of System Parameters and Noise Covariances for Linear Time-Variant Systems

2023-12-13
Léo Simpson , Andrea Ghezzi , Jonas Asprion +1 more
We present an optimization-based method for the joint estimation of system parameters and noise covariances of linear time-variant systems. Given measured data, this method maximizes the likelihood of the parameters. … We present an optimization-based method for the joint estimation of system parameters and noise covariances of linear time-variant systems. Given measured data, this method maximizes the likelihood of the parameters. We solve the optimization problem of interest via a novel structure-exploiting solver. We present the advantages of the proposed approach over commonly used methods in the framework of Moving Horizon Estimation. Finally, we show the performance of the method through numerical simulations on a realistic example of a thermal system. In this example, the method can successfully estimate the model parameters in a short computational time.
Chat View PDF

Finite Elements with Switch Detection for Direct Optimal Control of Nonsmooth Systems with Set-Valued Step Functions

2023-12-13
Armin Nurkanović , Jonathan Frey , Anton Pozharskiy +1 more
This paper extends the Finite Elements with Switch Detection (FESD) method [19] to optimal control problems with nonsmooth systems involving set-valued step functions. Logical relations and common nonsmooth functions within … This paper extends the Finite Elements with Switch Detection (FESD) method [19] to optimal control problems with nonsmooth systems involving set-valued step functions. Logical relations and common nonsmooth functions within a dynamical system can be expressed using linear and nonlinear expressions involving step functions. A prominent subclass of these systems are Filippov systems. The set-valued step function can be expressed by the solution map of a linear program, and using its KKT conditions allows one to transform the initial system into an equivalent dynamic complementarity system (DCS). Standard Runge-Kutta (RK) methods applied to DCS have only first-order accuracy. The FESD discretization makes the step sizes degrees of freedom and adds further constraints that ensure exact switch detection to recover the high-accuracy properties that RK methods have for smooth ODEs. We use the novel FESD method for the direct transcription of optimal control problems. All methods and examples in this paper are implemented in the open-source software package NOSNOC.
Chat View PDF

Imitation Learning from Nonlinear MPC via the Exact Q-Loss and its Gauss-Newton Approximation

2023-12-13
Andrea Ghezzi , Jasper Hoffman , Jonathan Frey +2 more
This work presents a novel loss function for learning nonlinear Model Predictive Control policies via Imitation Learning. Standard approaches to Imitation Learning neglect information about the expert and generally adopt … This work presents a novel loss function for learning nonlinear Model Predictive Control policies via Imitation Learning. Standard approaches to Imitation Learning neglect information about the expert and generally adopt a loss function based on the distance between expert and learned controls. In this work, we present a loss based on the Q-function directly embedding the performance objectives and constraint satisfaction of the associated Optimal Control Problem (OCP). However, training a Neural Network with the Q-loss requires solving the associated OCP for each new sample. To alleviate the computational burden, we derive a second Q-loss based on the Gauss-Newton approximation of the OCP resulting in a faster training time. We validate our losses against Behavioral Cloning, the standard approach to Imitation Learning, on the control of a nonlinear system with constraints. The final results show that the Q-function-based losses significantly reduce the amount of constraint violations while achieving comparable or better closed-loop costs.
Chat View PDF

Active Learning of Discrete-Time Dynamics for Uncertainty-Aware Model Predictive Control

2023-12-05
Alessandro Saviolo , Jonathan Frey , Abhishek Rathod +2 more
Model-based control requires an accurate model of the system dynamics for precisely and safely controlling the robot in complex and dynamic environments. Moreover, in presence of variations in the operating … Model-based control requires an accurate model of the system dynamics for precisely and safely controlling the robot in complex and dynamic environments. Moreover, in presence of variations in the operating conditions, the model should be continuously refined to compensate for dynamics changes. In this article, we present a self-supervised learning approach that actively models the dynamics of nonlinear robotic systems. We combine <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">offline</i> learning from past experience and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">online</i> learning from current robot interaction with the unknown environment. These two ingredients enable a highly sample-efficient and adaptive learning process, capable of accurately inferring model dynamics in real-time even in operating regimes that greatly differ from the training distribution. Moreover, we design an uncertainty-aware model predictive controller that is heuristically conditioned to the aleatoric (data) uncertainty of the learned dynamics. This controller <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">actively</i> chooses the optimal control actions that i) optimize the control performance, and ii) improve the efficiency of online learning sample collection. We demonstrate the effectiveness of our method through a series of challenging real-world experiments using a quadrotor system. Our approach showcases high resilience and generalization capabilities by consistently adapting to unseen flight conditions, while it significantly outperforms classical and adaptive control baselines. <xref ref-type="fn" rid="fn1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sup>1</sup></xref> <fn id="fn1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><label><sup>1</sup></label> Video: <uri>https://youtu.be/QmEhSTcWob4</uri> </fn>
Chat View PDF

The time-freezing reformulation for numerical optimal control of complementarity Lagrangian systems with state jumps

2023-09-28
Armin Nurkanović , Sebastian Albrecht , Bernard Brogliato +1 more
Chat View PDF

Vertical Airborne Wind Energy Farms with High Power Density per Ground Area based on Multi-Aircraft Systems

2023-06-22
Jochem De Schutter , Jakob Harzer , Moritz Diehl
Chat View PDF

Frenet-Cartesian model representations for automotive obstacle avoidance within nonlinear MPC

2023-06-15
Rudolf Reiter , Armin Nurkanović , Jonathan Frey +1 more
Chat View PDF

An implicit and explicit dual model predictive control formulation for a steel recycling process

2023-06-15
Andrea Ghezzi , Florian Messerer , Jacopo Balocco +2 more
Chat View PDF

Direct Collocation for Numerical Optimal Control of Second-Order ODE

2023-06-13
Léo Simpson , Armin Nurkanović , Moritz Diehl
Mechanical systems are usually modeled by second-order Ordinary Differential Equations (ODE) which take the form $\ddot{q}=f(t,\ q,\ \dot{q})$. While simulation methods tailored to these equations have been studied, using them … Mechanical systems are usually modeled by second-order Ordinary Differential Equations (ODE) which take the form $\ddot{q}=f(t,\ q,\ \dot{q})$. While simulation methods tailored to these equations have been studied, using them in direct optimal control methods is rare. Indeed, the standard approach is to perform a state augmentation, adding the velocities to the state. The main drawback of this approach is that the number of decision variables is doubled, which could harm the performance of the resulting optimization problem. In this paper, we present an approach tailored to second-order ODE. We compare it with the standard one, both on theoretical aspects and in a numerical example. Notably, we show that the tailored formulation is likely to improve the performance of a direct collocation method, for solving optimal control problems with second-order ODE of the more restrictive form $\ddot{q}=f(t,\ q)$.
Chat View PDF

Common Coauthors

Coauthor Papers Together
Armin Nurkanović 40
Jonathan Frey 34
Andrea Zanelli 28
Florian Messerer 26
Rien Quirynen 23
Katrin Baumgärtner 23
Gianluca Frison 22
Quoc Tran Dinh 19
Boris Houska 19
Sébastien Gros 16
Rudolf Reiter 11
Andrea Ghezzi 11
Carlo Savorgnan 11
Anton Pozharskiy 11
Sebastian Albrecht 11
Tommaso Sartor 9
Adrian Bürger 9
Ion Necoara 9
Niels van Duijkeren 8
Attila Kozma 7
Dimitris Kouzoupis 7
Sebastian Säger 7
Léo Simpson 7
Wim Michiels 7
Tran Dinh Quoc 7
Jan Swevers 7
Hans Georg Bock 6
Bernhard Schölkopf 6
Melanie N. Zeilinger 6
Yunfan Gao 6
Jochem De Schutter 6
Vyacheslav Kungurtsev 5
Tobias Schoels 5
Robin Verschueren 5
Mario Zanon 5
Joschka Boedecker 5
Jakob Harzer 4
Jia‐Jie Zhu 4
Jonas Asprion 4
Rudolf Reiter 4
Joris Gillis 4
David Kiessling 4
Quoc Tran-Dinh 4
Angelika Altmann‐Dieses 4
Alberto Bemporad 4
Amon Lahr 4
Jasper Hoffmann 4
Kai O. Arras 4
Milan Vukov 3
Janick V. Frasch 3

Commonly Cited References

On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming

2005-04-28
Andreas Wächter , Lorenz T. Biegler

A Multiple Shooting Algorithm for Direct Solution of Optimal Control Problems *

1984-07-01
H.G. Bock , K.J. Plitt

CasADi: a software framework for nonlinear optimization and optimal control

2018-07-11
Joel A.E. Andersson , Joris Gillis , Greg Horn +2 more
Chat View PDF

qpOASES: a parametric active-set algorithm for quadratic programming

2014-04-29
Hans Joachim Ferreau , Christian Kirches , Andreas Potschka +2 more

HPIPM: a high-performance quadratic programming framework for model predictive control

2020-01-01
Gianluca Frison , Moritz Diehl
This paper introduces HPIPM, a high-performance framework for quadratic programming (QP), designed to provide building blocks to efficiently and reliably solve model predictive control problems. HPIPM currently supports three QP … This paper introduces HPIPM, a high-performance framework for quadratic programming (QP), designed to provide building blocks to efficiently and reliably solve model predictive control problems. HPIPM currently supports three QP types, and provides interior point method (IPM) solvers as well (partial) condensing routines. In particular, the IPM for optimal control QPs is intended to supersede the HPMPC solver, and it largely improves robustness while keeping the focus on speed. Numerical experiments show that HPIPM reliably solves challenging QPs, and that it outperforms other state-of-the-art solvers in speed.
Chat View PDF

Convex Optimization

2004-03-01
Stephen Boyd , Lieven Vandenberghe
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.

BLASFEO

2018-07-31
Gianluca Frison , Dimitris Kouzoupis , Tommaso Sartor +2 more
BLASFEO is a dense linear algebra library providing high-performance implementations of BLAS- and LAPACK-like routines for use in embedded optimization. A key difference with respect to existing high-performance implementations of … BLASFEO is a dense linear algebra library providing high-performance implementations of BLAS- and LAPACK-like routines for use in embedded optimization. A key difference with respect to existing high-performance implementations of BLAS is that the computational performance is optimized for small to medium scale matrices, i.e., for sizes up to a few hundred. BLASFEO comes with three different implementations: a high-performance implementation aiming at providing the highest performance for matrices fitting in cache, a reference implementation providing portability and embeddability and optimized for very small matrices, and a wrapper to standard BLAS and LAPACK providing high-performance on large matrices. The three implementations of BLASFEO together provide high-performance dense linear algebra routines for matrices ranging from very small to large. Compared to both open-source and proprietary highly-tuned BLAS libraries, for matrices of size up to about one hundred the high-performance implementation of BLASFEO is about 20-30% faster than the corresponding level 3 BLAS routines and 2-3 times faster than the corresponding LAPACK routines.
Chat View PDF

Efficient interior point methods for multistage problems arising in receding horizon control

2012-12-01
Alexander Domahidi , Aldo U. Zgraggen , Melanie N. Zeilinger +2 more
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.
Chat View PDF

Autogenerating microsecond solvers for nonlinear MPC: A tutorial using ACADO integrators

2014-11-26
Rien Quirynen , Milan Vukov , Mario Zanon +1 more
Summary Nonlinear model predictive control (NMPC) allows one to explicitly treat nonlinear dynamics and constraints. To apply NMPC in real time on embedded hardware, online algorithms as well as efficient … Summary Nonlinear model predictive control (NMPC) allows one to explicitly treat nonlinear dynamics and constraints. To apply NMPC in real time on embedded hardware, online algorithms as well as efficient code implementations are crucial. A tutorial‐style approach is adopted in this article to present such algorithmic ideas and to show how they can efficiently be implemented based on the ACADO Toolkit from MATLAB (MathWorks, Natick, MA, USA). Using its code generation tool, one can export tailored Runge–Kutta methods—explicit and implicit ones—with efficient propagation of their sensitivities. The article summarizes recent research results on autogenerated integrators for NMPC and shows how they allow to formulate and solve practically relevant problems in only a few tens of microseconds. Several common NMPC formulations can be treated by these methods, including those with stiff ordinary differential equations, fully implicit differential algebraic equations, linear input and output models, and continuous output independent of the integration grid. One of the new algorithmic contributions is an efficient implementation of infinite horizon closed‐loop costing. As a guiding example, a full swing‐up of an inverted pendulum is considered. Copyright © 2014 John Wiley &amp; Sons, Ltd.

An online active set strategy to overcome the limitations of explicit MPC

2007-07-09
Hans Joachim Ferreau , H. G. Bock , Martin Diehl
Abstract Nearly all algorithms for linear model predictive control (MPC) either rely on the solution of convex quadratic programs (QPs) in real time, or on an explicit precalculation of this … Abstract Nearly all algorithms for linear model predictive control (MPC) either rely on the solution of convex quadratic programs (QPs) in real time, or on an explicit precalculation of this solution for all possible problem instances. In this paper, we present an online active set strategy for the fast solution of parametric QPs arising in MPC. This strategy exploits solution information of the previous QP under the assumption that the active set does not change much from one QP to the next. Furthermore, we present a modification where the CPU time is limited in order to make it suitable for strict real‐time applications. Its performance is demonstrated with a challenging test example comprising 240 variables and 1191 inequalities, which depends on 57 parameters and is prohibitive for explicit MPC approaches. In this example, our strategy allows CPU times of well below 100 ms per QP and was about one order of magnitude faster than a standard active set QP solver. Copyright © 2007 John Wiley &amp; Sons, Ltd.

acados—a modular open-source framework for fast embedded optimal control

2021-10-09
Robin Verschueren , Gianluca Frison , Dimitris Kouzoupis +7 more
Chat View PDF

The Lifted Newton Method and Its Application in Optimization

2010-01-01
Jan Albersmeyer , Moritz Diehl
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.

Optimal control of systems with discontinuous differential equations

2009-09-24
David E. Stewart , Mihai Anitescu

Efficient Numerical Methods for Nonlinear MPC and Moving Horizon Estimation

2009-01-01
Moritz Diehl , Hans Joachim Ferreau , Niels Haverbeke
This overview paper reviews numerical methods for solution of optimal control problems in real-time, as they arise in nonlinear model predictive control (NMPC) as well as in moving horizon estimation … This overview paper reviews numerical methods for solution of optimal control problems in real-time, as they arise in nonlinear model predictive control (NMPC) as well as in moving horizon estimation (MHE). In the first part, we review numerical optimal control solution methods, focussing exclusively on a discrete time setting. We discuss several algorithmic ”building blocks” that can be combined to a multitude of algorithms. We start by discussing the sequential and simultaneous approaches, the first leading to smaller, the second to more structured optimization problems. The two big families of Newton type optimization methods, Sequential Quadratic Programming (SQP) and Interior Point (IP) methods, are presented, and we discuss how to exploit the optimal control structure in the solution of the linear-quadratic subproblems, where the two major alternatives are “condensing” and band structure exploiting approaches. The second part of the paper discusses how the algorithms can be adapted to the real-time challenge of NMPC and MHE. We recall an important sensitivity result from parametric optimization, and show that a tangential solution predictor for online data can easily be generated in Newton type algorithms. We point out one important difference between SQP and IP methods: while both methods are able to generate the tangential predictor for fixed active sets, the SQP predictor even works across active set changes. We then classify many proposed real-time optimization approaches from the literature into the developed categories.
Chat View PDF

A parallel quadratic programming method for dynamic optimization problems

2015-04-30
Janick V. Frasch , Sebastian Säger , Moritz Diehl

A continuation/GMRES method for fast computation of nonlinear receding horizon control

2004-01-02
Toshiyuki Ohtsuka

Strongly Regular Generalized Equations

1980-02-01
Stephen M. Robinson
This paper considers generalized equations, which are convenient tools for formulating problems in complementarity and in mathematical programming, as well as variational inequalities. We introduce a regularity condition for such … This paper considers generalized equations, which are convenient tools for formulating problems in complementarity and in mathematical programming, as well as variational inequalities. We introduce a regularity condition for such problems and, with its help, prove existence, uniqueness and Lipschitz continuity of solutions to generalized equations with parametric data. Applications to nonlinear programming and to other areas are discussed, and for important classes of such applications the regularity condition given here is shown to be in a certain sense the weakest possible condition under which the stated properties will hold.

Benchmarking optimization software with performance profiles

2002-01-01
Elizabeth D. Dolan , Jorge J. Morè
Chat View PDF

An adjoint-based SQP algorithm with quasi-Newton Jacobian updates for inequality constrained optimization

2009-08-14
Moritz Diehl , Andrea Walther , Hans Georg Bock +1 more
We present a sequential quadratic programming (SQP) type algorithm, based on quasi-Newton approximations of Hessian and Jacobian matrices, which is suitable for the solution of general nonlinear programming problems involving … We present a sequential quadratic programming (SQP) type algorithm, based on quasi-Newton approximations of Hessian and Jacobian matrices, which is suitable for the solution of general nonlinear programming problems involving equality and inequality constraints. In contrast to most existing SQP methods, no evaluation of the exact constraint Jacobian matrix needs to be performed. Instead, in each SQP iteration only one evaluation of the constraint residuals and two evaluations of the gradient of the Lagrangian function are necessary, the latter of which can efficiently be performed by the reverse mode of automatic differentiation. Factorizations of the Hessian and of the constraint Jacobian are approximated by the recently proposed STR1 update procedure. Inequality constraints are treated by solving within each SQP iteration a quadratic program (QP), the dimension of which equals the number of degrees of freedom. A recently proposed gradient modification in these QPs takes account of Jacobian inexactness in the active set determination. Superlinear convergence of the procedure is shown under mild conditions. The convergence behaviour of the algorithm is analysed using several problems from the Hock–Schittkowski test library. Furthermore, we present numerical results for an optimization problem based on a small periodic adsorption process, where the Jacobian of the equality constraints is dense.

Application of a Smoothing Technique to Decomposition in Convex Optimization

2008-12-01
Ion Necoara , Johan A. K. Suykens
Dual decomposition is a powerful technique for deriving decomposition schemes for convex optimization problems with separable structure. Although the augmented Lagrangian is computationally more stable than the ordinary Lagrangian, the … Dual decomposition is a powerful technique for deriving decomposition schemes for convex optimization problems with separable structure. Although the augmented Lagrangian is computationally more stable than the ordinary Lagrangian, the ldquoprox-termrdquo destroys the separability of the given problem. In this technical note we use another approach to obtain a smooth Lagrangian, based on a smoothing technique developed by Nesterov, which preserves separability of the problem. With this approach we derive a new decomposition method, called ldquoproximal center algorithm,rdquo which from the viewpoint of efficiency estimates improves the bounds on the number of iterations of the classical dual gradient scheme by an order of magnitude.
Chat View PDF

SUNDIALS

2005-09-01
A.C. Hindmarsh , Peter N. Brown , Keith Eric Grant +4 more
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.

Object-oriented software for quadratic programming

2003-03-01
E. Michael Gertz , Stephen J. Wright
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.
Chat View PDF

NOSNOC: A Software Package for Numerical Optimal Control of Nonsmooth Systems

2022-01-01
Armin Nurkanović , Moritz Diehl
This letter introduces the NOnSmooth Numerical Optimal Control (NOSNOC) open-source software package. It is a modular MATLAB tool based on CasADi and IPOPT for numerically solving Optimal Control Problems (OCP) … This letter introduces the NOnSmooth Numerical Optimal Control (NOSNOC) open-source software package. It is a modular MATLAB tool based on CasADi and IPOPT for numerically solving Optimal Control Problems (OCP) with piecewise smooth systems (PSS). The tool supports: 1) automatic reformulation of systems with state jumps into PSS (via the time-freezing reformulation [Nurkanovi\'c et al., 2021]) and of PSS into computationally more convenient forms, 2) automatic discretization of the OCP via, e.g., the recently introduced Finite Elements with Switch Detection [Nurkanovi\'c et al., 2022] which enables high accuracy optimal control and simulation of PSS, 3) solution methods for the resulting discrete-time OCP. The nonsmooth discrete-time OCP are solved with techniques of continuous optimization in a homotopy procedure, without the use of integer variables. This enables the treatment of a broad class of nonsmooth systems in a unified way. Two tutorial examples are given. A benchmark shows that NOSNOC provides both faster and more accurate solutions than conventional approaches, including mixed-integer formulations.
Chat View PDF

Controlling the level of sparsity in MPC

2015-01-09
Daniel Axehill
Chat View PDF

Limits of MPCC Formulations in Direct Optimal Control with Nonsmooth Differential Equations

2020-05-01
Armin Nurkanović , Sebastian Albrecht , Moritz Diehl
In this work we discuss the limits of direct methods for Optimal Control Problems (OCPs) for some classes of nonsmooth dynamic systems. We highlight the equivalence between Filippov systems and … In this work we discuss the limits of direct methods for Optimal Control Problems (OCPs) for some classes of nonsmooth dynamic systems. We highlight the equivalence between Filippov systems and a subclass of Differential Complementarity Systems (DCSs). Direct methods for optimal control with DCSs yield Mathematical Programs with Complementarity Constraints (MPCC), which are often solved with relaxation or smoothing methods. Due to the equivalence, results from the first class transfer to the DCSs. Therefore, to get the right numerical sensitivities one has to have a step-size of h = o(σ), where σ is the relaxation or smoothing parameter in the MPCC. A possible consequence of wrong numerical sensitivities is the appearance of spurious local solutions of the discretized OCP. We demonstrate and highlight the limits of MPCC approaches in direct optimal control on a simple counterexample.

An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization. Part 1: theoretical aspects

2003-01-30
Daniel B. Leineweber , Irene Bauer , Hans Georg Bock +1 more

Exploiting convexity in direct Optimal Control: a sequential convex quadratic programming method

2016-12-01
Robin Verschueren , Niels van Duijkeren , Rien Quirynen +1 more
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.
Chat View PDF

A Time-Freezing Approach for Numerical Optimal Control of Nonsmooth Differential Equations With State Jumps

2020-06-18
Armin Nurkanović , Tommaso Sartor , Sebastian Albrecht +1 more
We present a novel reformulation of nonsmooth differential equations with state jumps enabling their easier simulation and use in optimal control problems without the need for integer variables. The main … We present a novel reformulation of nonsmooth differential equations with state jumps enabling their easier simulation and use in optimal control problems without the need for integer variables. The main idea is to introduce an auxiliary differential equation to mimic the state jump map. Thereby, a clock state is introduced which does not evolve during the runtime of the auxiliary system. The pieces of the trajectory that correspond to the parts when the clock state was evolving recover the solution of the original system with jumps. Our reformulation results in nonsmooth ordinary differential equations where the discontinuity is in the first time derivative of the trajectory, rather than in the trajectory itself. This class of systems is easier to handle both theoretically and numerically. The reformulation is suitable for partially elastic mechanical impact problems. We provide numerical examples demonstrating the ease of use of this reformulation in both simulation and optimal control. In the optimal control example, we solve a sequence of nonlinear programming problems (NLPs) in a homotopy penalization approach and recover a time-optimal trajectory with state jumps.
Chat View PDF

SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization

2005-01-01
Philip E. Gill , Walter Murray , Michael A. Saunders
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).

An approximation technique for robust nonlinear optimization

2005-12-30
Moritz Diehl , Hans Georg Bock , Ekaterina Kostina
Chat View PDF

Survey of sequential convex programming and generalized Gauss-Newton methods

2021-08-01
Florian Messerer , Katrin Baumgärtner , Moritz Diehl
We provide an overview of a class of iterative convex approximation methods for nonlinear optimization problems with convex-over-nonlinear substructure. These problems are characterized by outer convexities on the one hand, … We provide an overview of a class of iterative convex approximation methods for nonlinear optimization problems with convex-over-nonlinear substructure. These problems are characterized by outer convexities on the one hand, and nonlinear, generally nonconvex, but differentiable functions on the other hand. All methods from this class use only first order derivatives of the nonlinear functions and sequentially solve convex optimization problems. All of them are different generalizations of the classical Gauss-Newton (GN) method. We focus on the smooth constrained case and on three methods to address it: Sequential Convex Programming (SCP), Sequential Convex Quadratic Programming (SCQP), and Sequential Quadratically Constrained Quadratic Programming (SQCQP). While the first two methods were previously known, the last is newly proposed and investigated in this paper. We show under mild assumptions that SCP, SCQP and SQCQP have exactly the same local linear convergence – or divergence – rate. We then discuss the special case in which the solution is fully determined by the active constraints, and show that for this case the KKT conditions are sufficient for local optimality and that SCP, SCQP and SQCQP even converge quadratically. In the context of parameter estimation with symmetric convex loss functions, the possible divergence of the methods can in fact be an advantage that helps them to avoid some undesirable local minima: generalizing existing results, we show that the presented methods converge to a local minimum if and only if this local minimum is stable against a mirroring operation applied to the measurement data of the estimation problem. All results are illustrated by numerical experiments on a tutorial example.
Chat View PDF

Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties

2006-08-01
Mihai Anitescu , Paul Tseng , Stephen J. Wright
Chat View PDF

MPEC strategies for optimization of a class of hybrid dynamic systems

2009-06-25
B.T. Baumrucker , Lorenz T. Biegler

Nominal stability of real-time iteration scheme for nonlinear model predictive control

2005-05-01
Moritz Diehl , Rolf Findeisen , H.G. Bock +2 more
A Newton-type method is investigated for online optimisation in nonlinear model predictive control, the so-called real-time iteration scheme. Only one Newton-type iteration is performed per sampling instant in this scheme, … A Newton-type method is investigated for online optimisation in nonlinear model predictive control, the so-called real-time iteration scheme. Only one Newton-type iteration is performed per sampling instant in this scheme, and control of the system and the solution of the optimal control problem are performed in parallel. In the resulting combined dynamics of system and optimiser, the actual feedback control in each step is based on the current solution estimate, and the solution estimates are at each sampling instant refined and transferred to the next optimisation problem by a specially designed transition. This approach yields an efficient online optimisation algorithm that has already been successfully tested in several applications. Due to the close dovetailing of system and optimiser dynamics, however, stability of the closed-loop system is not implied by standard nonlinear model predictive control results. A proof of nominal stability of the scheme is given which builds on concepts from both NMPC stability theory and convergence analysis of Newton-type methods. The principal result is that, under some reasonable assumptions, the combined system–optimiser dynamics can be guaranteed to converge towards the origin from significantly disturbed system–optimiser states.
Chat View PDF

Continuous Control Set Nonlinear Model Predictive Control of Reluctance Synchronous Machines

2021-02-22
Andrea Zanelli , Julian Kullick , Hisham Eldeeb +3 more
In this article, we describe the design and implementation of a current controller for a reluctance synchronous machine (RSM) based on continuous control set nonlinear model predictive control (NMPC). A … In this article, we describe the design and implementation of a current controller for a reluctance synchronous machine (RSM) based on continuous control set nonlinear model predictive control (NMPC). A computationally efficient gray box model of the flux linkage map, the Gaussian-linear-arctangent (GLA) model, is proposed and employed in a tracking formulation, which is implemented using the high-performance framework for NMPC <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">acados</monospace> . The resulting controller is validated in simulation and deployed on a <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dSPACE real-time</monospace> system connected to a physical RSM. Experimental results are presented where the proposed implementation can reach sampling times in the range typical for electrical drives and can achieve large improvements in terms of control performance with respect to state-of-the-art classical control strategies.
Chat View PDF

A proximal-based decomposition method for convex minimization problems

1994-03-01
Gong Chen , Marc Teboulle

Application of Interior-Point Methods to Model Predictive Control

1998-12-01
C. V. Rao , Stephen J. Wright , James B. Rawlings
Chat View PDF

Sequential Quadratic Programming

1995-01-01
Paul T. Boggs , Jon W. Tolle
Since its popularization in the late 1970s, Sequential Quadratic Programming (SQP) has arguably become the most successful method for solving nonlinearly constrained optimization problems. As with most optimization methods, SQP … Since its popularization in the late 1970s, Sequential Quadratic Programming (SQP) has arguably become the most successful method for solving nonlinearly constrained optimization problems. As with most optimization methods, SQP is not a single algorithm, but rather a conceptual method from which numerous specific algorithms have evolved. Backed by a solid theoretical and computational foundation, both commercial and public-domain SQP algorithms have been developed and used to solve a remarkably large set of important practical problems. Recently large-scale versions have been devised and tested with promising results.

Smooth minimization of non-smooth functions

2004-12-29
Yu. Nesterov
Chat View PDF

Interior-Point Lagrangian Decomposition Method for Separable Convex Optimization

2009-05-29
Ion Necoara , Johan A. K. Suykens
Chat View PDF

A high accuracy method for solving ODEs with discontinuous right-hand side

1990-12-01
David E. Stewart

Combining Convex–Concave Decompositions and Linearization Approaches for Solving BMIs, With Application to Static Output Feedback

2011-12-05
Quoc Tran Dinh , Suat Gümüşsoy , Wim Michiels +1 more
A novel optimization method is proposed to minimize a convex function subject to bilinear matrix inequality (BMI) constraints. The key idea is to decompose the bilinear mapping as a difference … A novel optimization method is proposed to minimize a convex function subject to bilinear matrix inequality (BMI) constraints. The key idea is to decompose the bilinear mapping as a difference between two positive semidefinite convex mappings. At each iteration of the algorithm the concave part is linearized, leading to a convex subproblem. Applications to various output feedback controller synthesis problems are presented. In these applications, the subproblem in each iteration step can be turned into a convex optimization problem with linear matrix inequality (LMI) constraints. The performance of the algorithm has been benchmarked on the data from the <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\rm COMPl}_{\rm e}{\rm ib}$</tex></formula> library.
Chat View PDF

Two-level primal–dual proximal decomposition technique to solve large scale optimization problems

2004-02-04
Abdelouahed Hamdi

A Global Algorithm for Nonlinear Semidefinite Programming

2004-01-01
Rafaël Correa , Héctor Ramírez
In this paper we propose a global algorithm for solving nonlinear semidefinite programming problems. This algorithm, inspired by the classic SQP (sequentially quadratic programming) method, modifies the S-SDP (sequentially semidefinite … In this paper we propose a global algorithm for solving nonlinear semidefinite programming problems. This algorithm, inspired by the classic SQP (sequentially quadratic programming) method, modifies the S-SDP (sequentially semidefinite programming) local method by using a nondifferentiable merit function combined with a line search strategy.
Chat View PDF

Local Convergence of Sequential Convex Programming for Nonconvex Optimization

2010-01-01
Quoc Tran Dinh , Moritz Diehl

Some properties of regularization and penalization schemes for MPECs

2004-08-17
Daniel Ralph , Stephen J. Wright
Some properties of regularized and penalized nonlinear programming formulations of mathematical programs with equilibrium constraints (MPECs) are described. The focus is on the properties of these formulations near a local … Some properties of regularized and penalized nonlinear programming formulations of mathematical programs with equilibrium constraints (MPECs) are described. The focus is on the properties of these formulations near a local solution of the MPEC at which strong stationarity and a second-order sufficient condition are satisfied. In the regularized formulations, the complementarity condition is replaced by a constraint involving a positive parameter that can be decreased to zero. In the penalized formulation, the complementarity constraint appears as a penalty term in the objective. The existence and uniqueness of solutions for these formulations are investigated, and estimates are obtained for the distance of these solutions to the MPEC solution under various assumptions.
Chat View PDF

On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization

1995-08-01
Andrzej Ruszczyński
A decomposition method for large-scale convex optimization problems with block-angular structure and many linking constraints is analysed. The method is based on a separable approximation of the augmented Lagrangian function. … A decomposition method for large-scale convex optimization problems with block-angular structure and many linking constraints is analysed. The method is based on a separable approximation of the augmented Lagrangian function. Weak global convergence of the method is proved and speed of convergence analysed. It is shown that convergence properties of the method are heavily dependent on sparsity of the linking constraints. Application to large-scale linear programming and stochastic programming is discussed.

Adjoint-Based Predictor-Corrector Sequential Convex Programming for Parametric Nonlinear Optimization

2012-01-01
Quoc Tran Dinh , Carlo Savorgnan , Moritz Diehl
This paper proposes an algorithmic framework for solving parametric optimization problems which we call adjoint-based predictor-corrector sequential convex programming. After presenting the algorithm, we prove a contraction estimate that guarantees … This paper proposes an algorithmic framework for solving parametric optimization problems which we call adjoint-based predictor-corrector sequential convex programming. After presenting the algorithm, we prove a contraction estimate that guarantees the tracking performance of the algorithm. Two variants of this algorithm are investigated. The first can be used to treat online parametric nonlinear programming problems when the exact Jacobian matrix is available, while the second variant is used to solve nonlinear programming problems. The local convergence of these variants is proved. An application to a large-scale benchmark problem that originates from nonlinear model predictive control of a hydro power plant is implemented to examine the performance of the algorithms.
Chat View PDF

An Inexact Perturbed Path-Following Method for Lagrangian Decomposition in Large-Scale Separable Convex Optimization

2013-01-01
Quoc Tran Dinh , Ion Necoara , Carlo Savorgnan +1 more
This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, … This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, we propose solving the primal subproblems inexactly up to a given accuracy. This leads to an inexactness of the gradient vector and the Hessian matrix of the smoothed dual function. Then an inexact perturbed algorithm is applied to minimize the smoothed dual function. The algorithm consists of two phases, and both make use of the inexact derivative information of the smoothed dual problem. The convergence of the algorithm is analyzed, and the worst-case complexity is estimated. As a special case, an exact path-following decomposition algorithm is obtained and its worst-case complexity is given. Implementation details are discussed, and preliminary numerical results are reported.
Chat View PDF

Convergence Properties of a Regularization Scheme for Mathematical Programs with Complementarity Constraints

2001-01-01
Stefan Scholtes
We study the convergence behavior of a sequence of stationary points of a parametric NLP which regularizes a mathematical program with equilibrium constraints (MPEC) in the form of complementarity conditions. … We study the convergence behavior of a sequence of stationary points of a parametric NLP which regularizes a mathematical program with equilibrium constraints (MPEC) in the form of complementarity conditions. Accumulation points are feasible points of the MPEC; they are C-stationary if the MPEC linear independence constraint qualification holds; they are M-stationary if, in addition, an approaching subsequence satisfies second order necessary conditions, and they are B-stationary if, in addition, an upper level strict complementarity condition holds. These results complement recent results of Fukushima and Pang [Convergence of a smoothing continuation method for mathematical programs with equilibrium constraints, in Ill-posed Variational Problems and Regularization Techniques, Springer-Verlag, New York, 1999]. We further show that every local minimizer of the MPEC which satisfies the linear independence, upper level strict complementarity, and a second order optimality condition can be embedded into a locally unique piecewise smooth curve of local minimizers of the parametric NLP.