Joris Gillis

Search for another author

Author Description

Ask a Question About This Mathematician

All published works (11)

Exact Wavefront Propagation for Globally Optimal One-to-All Path Planning on 2D Cartesian Grids

2024-09-13

Ibrahim Ibrahim , Joris Gillis , Wilm Decré +1 more

This paper introduces an efficient $\mathcal{O}(n)$ compute and memory complexity algorithm for globally optimal path planning on 2D Cartesian grids. Unlike existing marching methods that rely on approximate discretized solutions … This paper introduces an efficient $\mathcal{O}(n)$ compute and memory complexity algorithm for globally optimal path planning on 2D Cartesian grids. Unlike existing marching methods that rely on approximate discretized solutions to the Eikonal equation, our approach achieves exact wavefront propagation by pivoting the analytic distance function based on visibility. The algorithm leverages a dynamic-programming subroutine to efficiently evaluate visibility queries. Through benchmarking against state-of-the-art any-angle path planners, we demonstrate that our method outperforms existing approaches in both speed and accuracy, particularly in cluttered environments. Notably, our method inherently provides globally optimal paths to all grid points, eliminating the need for additional gradient descent steps per path query. The same capability extends to multiple starting positions. We also provide a greedy version of our algorithm as well as open-source C++ implementation of our solver.

Chat View PDF

An Efficient Solution to the 2D Visibility Problem in Cartesian Grid Maps and its Application in Heuristic Path Planning

2024-05-13

Ibrahim Ibrahim , Joris Gillis , Wilm Decré +1 more

Chat View PDF

An Efficient Solution to the 2D Visibility Problem in Cartesian Grid Maps and its Application in Heuristic Path Planning

2024-03-11

Ibrahim Ibrahim , Joris Gillis , Wilm Decré +1 more

This paper introduces a novel, lightweight method to solve the visibility problem for 2D grids. The proposed method evaluates the existence of lines-of-sight from a source point to all other … This paper introduces a novel, lightweight method to solve the visibility problem for 2D grids. The proposed method evaluates the existence of lines-of-sight from a source point to all other grid cells in a single pass with no preprocessing and independently of the number and shape of obstacles. It has a compute and memory complexity of $\mathcal{O}(n)$, where $n = n_{x}\times{} n_{y}$ is the size of the grid, and requires at most ten arithmetic operations per grid cell. In the proposed approach, we use a linear first-order hyperbolic partial differential equation to transport the visibility quantity in all directions. In order to accomplish that, we use an entropy-satisfying upwind scheme that converges to the true visibility polygon as the step size goes to zero. This dynamic-programming approach allows the evaluation of visibility for an entire grid orders of magnitude faster than typical ray-casting algorithms. We provide a practical application of our proposed algorithm by posing the visibility quantity as a heuristic and implementing a deterministic, local-minima-free path planner, setting apart the proposed planner from traditional methods. Lastly, we provide necessary algorithms and an open-source implementation of the proposed methods.

Chat View PDF

IMPACT: A Toolchain for Nonlinear Model Predictive Control Specification, Prototyping, and Deployment

2023-01-01

Alvaro Florez , Alejandro Astudillo , Wilm Decré +2 more

We present IMPACT, a flexible toolchain for nonlinear model predictive control (NMPC) specification with automatic code generation capabilities. The toolchain reduces the engineering complexity of NMPC implementations by providing the … We present IMPACT, a flexible toolchain for nonlinear model predictive control (NMPC) specification with automatic code generation capabilities. The toolchain reduces the engineering complexity of NMPC implementations by providing the user with an easy-to-use application programming interface, and with the flexibility of using multiple state-of-the-art tools and numerical optimization solvers for rapid prototyping of NMPC solutions. IMPACT is written in Python, users can call it from Python and MATLAB, and the generated NMPC solvers can be directly executed from C, Python, MATLAB and Simulink. An application example is presented involving problem specification and deployment on embedded hardware using Simulink, showing the effectiveness and applicability of IMPACT for NMPC-based solutions.

Chat View PDF

IMPACT: A Toolchain for Nonlinear Model Predictive Control Specification, Prototyping, and Deployment

2023-01-01

Alvaro Florez , Alejandro Astudillo , Wilm Decré +2 more

Chat View PDF

A Feasible Sequential Linear Programming Algorithm with Application to Time-Optimal Path Planning Problems

2022-12-06

David Kiessling , Andrea Zanelli , Armin Nurkanović +5 more

In this paper, we propose a Feasible Sequential Linear Programming (FSLP) algorithm applied to time-optimal control problems (TOCP) obtained through direct multiple shooting discretization. This method is motivated by TOCP … In this paper, we propose a Feasible Sequential Linear Programming (FSLP) algorithm applied to time-optimal control problems (TOCP) obtained through direct multiple shooting discretization. This method is motivated by TOCP with nonlinear constraints which arise in motion planning of mechatronic systems. The algorithm applies a trust-region globalization strategy ensuring global convergence. For fully determined problems our algorithm provides locally quadratic convergence. Moreover, the algorithm keeps all iterates feasible enabling early termination at suboptimal, feasible solutions. This additional feasibility is achieved by an efficient iterative strategy using evaluations of constraints, i.e., zero-order information. Convergence of the feasibility iterations can be enforced by reduction of the trust-region radius. These feasibility iterations maintain feasibility for general Nonlinear Programs (NLP). Therefore, the algorithm is applicable to general NLPs. We demonstrate our algorithm's efficiency and the feasibility update strategy on a TOCP of an overhead crane motion planning simulation case.

Chat View PDF

A Feasible Sequential Linear Programming Algorithm with Application to Time-Optimal Path Planning Problems

2022-01-01

David Kiessling , Andrea Zanelli , Armin Nurkanović +5 more

Chat View PDF

A proximal-point outer approximation algorithm

2020-09-09

Massimo De Mauri , Joris Gillis , Jan Swevers +1 more

Chat View PDF

Real Time Iterations for Mixed-Integer Model Predictive Control

2020-05-01

Massimo De Mauri , Wim Van Roy , Joris Gillis +2 more

The subject matter of the present paper is Model Predictive Control (MPC). MPC is a well known approach to optimal control that tackles a long time-horizon control problem by sequentially … The subject matter of the present paper is Model Predictive Control (MPC). MPC is a well known approach to optimal control that tackles a long time-horizon control problem by sequentially optimizing small portions of it. MPC is generally regarded as a powerful tool for efficiently finding approximate solutions to complex optimal control problems. However, in the context of mixed-integer non-linear optimal control, MPC suffers from the high computational cost of mixed-integer non-linear programming. As a consequence, in real-time applications, the suitability of mixed-integer nonlinear MPC is limited. In this paper we present the Mixed-Integer Real Time Optimal Control (MIRT-OC) algorithm: a novel MPC technique that reduces the cost of each MPC iteration by reusing the information generated during past iterations. MIRT-OC extends the basic ideas behind LP/NLP-Branch&Bound to MPC. In LP/NLP-B&B, a mixed-integer convex optimization problem is tackled as a linear one where new linear constraints are added on the run in order to enforce the original nonlinear constraints on the solution. MIRT-OC in addition to using a LP/NLP-B&B procedure at each MPC iteration, introduces two forward shifting techniques. The first technique transforms the linearizations generated during one MPC iteration into linearizations for the sub-problem to solve in the subsequent MPC iteration. The second one extrapolates from the B&B tree built during the solution of one MPC sub-problem into a partially explored B&B tree for the next MPC sub-problem. Consequently, the non-linear MPC problem is tackled as a single mixed-integer linearly-constrained optimal control problem in which new linearizations are added on the run and, at each given moment, only a portion of the problem is optimized.The collected empirical data shows how the proposed algorithm is capable of providing sizeable computational savings, representing a first step towards a true real-time mixed-integer convex MPC scheme.

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

A positive definiteness preserving discretization method for Lyapunov differential equations

2013-12-01

Joris Gillis , Moritz Diehl

Periodic Lyapunov differential equations can be used to formulate robust optimal periodic control problems for nonlinear systems. Typically, the added Lyapunov states are discretized in the same manner as the … Periodic Lyapunov differential equations can be used to formulate robust optimal periodic control problems for nonlinear systems. Typically, the added Lyapunov states are discretized in the same manner as the original states. This straightforward technique fails to guarantee conservation of positive-semidefiniteness of the Lyapunov matrix under discretization. This paper describes a discretization method, coined PDPLD, that does come with such a guarantee. The applicability is demonstrated at hand of a tutorial example, and is specifically suited for direct collocation methods.

Chat View PDF

Common Coauthors

Coauthor	Papers Together
Jan Swevers	9
Wilm Decré	5
Moritz Diehl	4
Goele Pipeleers	4
Melanie N. Zeilinger	2
Andrea Zanelli	2
Alejandro Astudillo	2
Armin Nurkanović	2
Massimo De Mauri	2
Ibrahim Ibrahim	2
David Kiessling	2
Alvaro Florez	2
Wim Van Roy	1
James B. Rawlings	1
Ibrahim Ibrahim	1
Greg Horn	1
Joel A.E. Andersson	1

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

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

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

1984-07-01

H.G. Bock , K.J. Plitt

OpEn: Code Generation for Embedded Nonconvex Optimization

2020-01-01

Pantelis Sopasakis , Emil Fresk , Panagiotis Patrinos

We present Optimization Engine (OpEn): an open-source code generation framework for real-time embedded nonconvex optimization, which implements a novel numerical method. OpEn combines the proximal averaged Newton-type method for optimal … We present Optimization Engine (OpEn): an open-source code generation framework for real-time embedded nonconvex optimization, which implements a novel numerical method. OpEn combines the proximal averaged Newton-type method for optimal control (PANOC) with the penalty and augmented Lagrangian methods to compute approximate stationary points of nonconvex problems. The proposed method involves very simple algebraic operations such as vector products, has a low memory footprint and exhibits very good convergence properties that allow the solution of nonconvex problems on embedded devices. OpEn's core solver is written is Rust — a modern, high-performance, memory-safe and thread-safe systems programming language — while users can call it from Python, MATLAB, C, C++, ROS or over a TCP socket.

Chat View PDF

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

A software framework for embedded nonlinear model predictive control using a gradient-based augmented Lagrangian approach (GRAMPC)

2019-01-18

Tobias Englert , Andreas Völz , Felix Mesmer +2 more

A nonlinear MPC framework is presented that is suitable for dynamical systems with sampling times in the (sub)millisecond range and that allows for an efficient implementation on embedded hardware. The … A nonlinear MPC framework is presented that is suitable for dynamical systems with sampling times in the (sub)millisecond range and that allows for an efficient implementation on embedded hardware. The algorithm is based on an augmented Lagrangian formulation with a tailored gradient method for the inner minimization problem. The algorithm is implemented in the software framework GRAMPC and is a fundamental revision of an earlier version. Detailed performance results are presented for a test set of benchmark problems and in comparison to other nonlinear MPC packages. In addition, runtime results and memory requirements for GRAMPC on ECU level demonstrate its applicability on embedded hardware.

Chat View PDF

Sensitivity Analysis for Nonlinear Programming in CasADi

2018-01-01

Joel A.E. Andersson , James B. Rawlings

We present an extension of the CasADi numerical optimization framework that allows arbitrary order NLP sensitivities to be calculated automatically and efficiently. The approach, which can be used together with … We present an extension of the CasADi numerical optimization framework that allows arbitrary order NLP sensitivities to be calculated automatically and efficiently. The approach, which can be used together with any NLP solver available in CasADi, is based on a sparse QR factorization and an implementation of a primal-dual active set method. The whole toolchain is freely available as open-source software and allows generation of thread-safe, self-contained C code with small memory footprint. We illustrate the toolchain using three examples; a sparse QP, an optimal control problem and a parameter estimation problem.

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.

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).

Solution of dynamic optimization problems by successive quadratic programming and orthogonal collocation

1984-01-01

Lorenz T. Biegler

Proximity search for 0-1 mixed-integer convex programming

2014-11-03

Matteo Fischetti , Michele Monaci

Computing a visibility polygon using few variables

2014-04-24

Luis Barba , Matias Korman , Stefan Langerman +1 more

Chat View PDF

Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations

1988-11-01

Stanley Osher , James A. Sethian

Chat View PDF

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.

A Third Order Accurate Fast Marching Method for the Eikonal Equation in Two Dimensions

2011-01-01

Shahnawaz Ahmed , Stanley Bak , Joyce R. McLaughlin +1 more

In this paper, we develop a third order accurate fast marching method for the solution of the eikonal equation in two dimensions. There have been two obstacles to extending the … In this paper, we develop a third order accurate fast marching method for the solution of the eikonal equation in two dimensions. There have been two obstacles to extending the fast marching method to higher orders of accuracy. The first obstacle is that using one-sided difference schemes is unstable for orders of accuracy higher than two. The second obstacle is that the points in the difference stencil are not available when the gradient is closely aligned with the grid. We overcome these obstacles by using a two-dimensional (2D) finite difference approximation to improve stability, and by locally rotating the grid 45 degrees (i.e., using derivatives along the diagonals) to ensure all the points needed in the difference stencil are available. We show that in smooth regions the full difference stencil is used for a suitably small enough grid size and that the difference scheme satisfies the von Neumann stability condition for the linearized eikonal equation. Our method reverts to first order accuracy near caustics without developing oscillations by using a simple switching scheme. The efficiency and high order of the method are demonstrated on a number of 2D test problems.

Sensitivity and stability analysis for nonlinear programming

1990-12-01

Anthony V. Fiacco , Yo Ishizuka

A generalized front marching algorithm for the solution of the eikonal equation

2003-06-09

Paul Covello , Garry Rodrigue

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

Simultaneous optimization and solution methods for batch reactor control profiles

1989-01-01

J.E. Cuthrell , Lorenz T. Biegler

The use of orthogonal polynomials in the near-optimal control of distributed systems by trajectory approximation†

1970-12-01

L. L. Lynn , R.L. Zahradnik

Abstract A near-optimal feedback control law for a distributed parameter system with a quadratic performance index is obtained by the method of trajectory approximation. The system equation is reduced to … Abstract A near-optimal feedback control law for a distributed parameter system with a quadratic performance index is obtained by the method of trajectory approximation. The system equation is reduced to an approximate system of ordinary differential equations by the Galerkin—Kantorovich method, and then Pontryagin's maximum principle is applied to show that the feedback control law is linear and can be obtained as the solution of a matrix Riccati equation. Numerical computations performed using Chebyshev polynomials as the Galerkin weighting functions on the equation for a heat exchanger with wall flux forcing indicate that four thermocouples are enough to attain virtual optimality.

RENS

2013-10-31

Timo Berthold

A fast sweeping method for Eikonal equations

2004-05-21

Hongkai Zhao

In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind … In this paper a fast sweeping method for computing the numerical solution of Eikonal equations on a rectangular grid is presented. The method is an iterative method which uses upwind difference for discretization and uses Gauss-Seidel iterations with alternating sweeping ordering to solve the discretized system. The crucial idea is that each sweeping ordering follows a family of characteristics of the corresponding Eikonal equation in a certain direction simultaneously. The method has an optimal complexity of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> grid points and is extremely simple to implement in any number of dimensions. Monotonicity and stability properties of the fast sweeping algorithm are proven. Convergence and error estimates of the algorithm for computing the distance function is studied in detail. It is shown that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n"> <mml:semantics> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">2^{n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> Gauss-Seidel iterations is enough for the distance function in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> dimensions. An estimation of the number of iterations for general Eikonal equations is also studied. Numerical examples are used to verify the analysis.

Solving mixed integer nonlinear programs by outer approximation

1994-08-01

R. Fletcher , Sven Leyffer

An LP/NLP based branch and bound algorithm for convex MINLP optimization problems

1992-10-01

Ignacio Quesada , Ignacio E. Grossmann

An outer-approximation algorithm for a class of mixed-integer nonlinear programs

1986-10-01

Marco A. Durán , Ignacio E. Grossmann

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.

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

An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs

2013-03-15

Hassan Hijazi , Pierre Bonami , Adam Ouorou

A common structure in convex mixed-integer nonlinear programs (MINLPs) is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first … A common structure in convex mixed-integer nonlinear programs (MINLPs) is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. As a side result, we exhibit a simple example where a classical implementation of the outer approximation would take an exponential number of iterations, whereas it is easily solved with our modifications. These methods have been implemented in the open source solver Bonmin and are available for download from the Computational Infrastructure for Operations Research project website. We test the effectiveness of the approach on three real-world applications and on a larger set of models from an MINLP benchmark library. Finally, we show how the techniques can be extended to perspective formulations of several problems. The proposed tools lead to an important reduction in computing time on most tested instances.

Chat View PDF

The Periodic Lyapunov Equation

1988-10-01

Paolo Bolzern , Patrizio Colaneri

This paper presents an overview of the periodic Lyapunov equation, both in discrete time and in continuous time. Together with some selected results that have recently appeared in the literature, … This paper presents an overview of the periodic Lyapunov equation, both in discrete time and in continuous time. Together with some selected results that have recently appeared in the literature, the paper provides necessary and sufficient conditions for the existence and uniqueness of periodic solutions.

The Numerical Treatment of Differential Equations

1960-01-01

Lothar Collatz

A Feasible Trust-Region Sequential Quadratic Programming Algorithm

2004-01-01

Stephen J. Wright , Matthew J. Tenny

An algorithm for smooth nonlinear constrained optimization problems is described, in which a sequence of feasible iterates is generated by solving a trust-region sequential quadratic programming (SQP) subproblem at each … An algorithm for smooth nonlinear constrained optimization problems is described, in which a sequence of feasible iterates is generated by solving a trust-region sequential quadratic programming (SQP) subproblem at each iteration and by perturbing the resulting step to retain feasibility of each iterate. By retaining feasibility, the algorithm avoids several complications of other trust-region SQP approaches: the objective function can be used as a merit function, and the SQP subproblems are feasible for all choices of the trust-region radius. Global convergence properties are analyzed under various assumptions on the approximate Hessian. Under additional assumptions, superlinear convergence to points satisfying second-order sufficient conditions is proved.

Chat View PDF

Time-optimal tube following for robotic manipulators

2014-03-01

Frederik Debrouwere , Wannes Van Loock , Goele Pipeleers +1 more

Time-optimal path following for robots considers the problem of moving along a predetermined Cartesian geometric path in minimum time. In practice this path need not be followed exactly, but within … Time-optimal path following for robots considers the problem of moving along a predetermined Cartesian geometric path in minimum time. In practice this path need not be followed exactly, but within a certain tolerance; so that the motion may be executed faster. In this paper, we define this deviation as a tube around the given geometric path. This transforms the path following problem into a tube following problem. However, unlike the former, the latter is not convex.We propose a problem formulation that can still be solved efficiently, as illustrated by some numerical examples.

Chat View PDF

A Feasibility Pump for mixed integer nonlinear programs

2008-03-17

Pierre Bonami , Gérard Cornuéjols , Andrea Lodi +1 more

Chat View PDF

A Nonlinear Programming Technique for the Optimization of Continuous Processing Systems

1961-07-01

R. E. Griffith , Richard A. D. Stewart

A description is given of a method for solving some nonlinear programming problems. The mathematics of this method are quite simple and are easy to apply to electronic computation. A … A description is given of a method for solving some nonlinear programming problems. The mathematics of this method are quite simple and are easy to apply to electronic computation. A numerical example, a model construction example, and a description of a particular existing computer system are included in order to clarify the mode of operation of the method.

Baumgarte stabilisation over the SO(3) rotation group for control

2015-12-01

Sébastien Gros , Mario Zanon , Moritz Diehl

Representations of the SO(3) rotation group are crucial for airborne and aerospace applications. Euler angles is a popular representation in many applications, but yield models having singular dynamics. This issue … Representations of the SO(3) rotation group are crucial for airborne and aerospace applications. Euler angles is a popular representation in many applications, but yield models having singular dynamics. This issue is addressed via non-singular representations, operating in dimensions higher than 3. Unit quaternions and the Direction Cosine Matrix are the best known non-singular representations, and favoured in challenging aeronautic and aerospace applications. All nonsingular representations yield invariants in the model dynamics, i.e. a set of nonlinear algebraic conditions that must be fulfilled by the model initial conditions, and that remain fulfilled over time. However, due to numerical integration errors, these conditions tend to become violated when using standard integrators, making the model inconsistent with the physical reality. This issue poses some challenges when non-singular representations are deployed in optimal control. In this paper, we propose a simple technique to address the issue for classical integration schemes, establish formally its properties, and illustrate it on the optimal control of a satellite.

Convex Optimization

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.

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

2016-02-29

Dennis Janka , Christian Kirches , Sebastian Säger +1 more

Synthesis of optimal controls and numerical optimization for the vibration-based energy harvesters

2016-01-01

Thuy T. T. Le , Binh Duc Truong , Felix Jost +3 more

This work is devoted to demonstration of the analysis on optimizing the output power harvested from vibration energy harvester. This work is devoted to demonstration of the analysis on optimizing the output power harvested from vibration energy harvester.

Chat View PDF

Real-time Algorithm for Self-Reflective Model Predictive Control

2016-01-01

Xuhui Feng , Boris Houska

This paper is about a real-time model predictive control (MPC) algorithm for a particular class of model based controllers, whose objective consists of a nominal tracking objective and an additional … This paper is about a real-time model predictive control (MPC) algorithm for a particular class of model based controllers, whose objective consists of a nominal tracking objective and an additional learning objective. Here, the construction of the learning term is based on economic optimal experiment design criteria. It is added to the MPC objective in order to excite the system from time-to-time on purpose in order to improve the accuracy of the state and parameter estimates in the presence of incomplete or noise affected measurements. A particular focus of this paper is on so-called self-reflective model predictive control schemes, which have the property that the additional learning term can be interpreted as the expected loss of optimality of the controller in the presence of random measurement errors. The main contribution of this paper is a formulation-tailored algorithm, which exploits the particular structure of self-reflective MPC problems in order to speed-up the online computation. It is shown that, in contrast to generic state-of-the-art optimal control problem solvers, the proposed algorithm can solve the self-reflective optimization problems with reasonable additional computational effort and in real-time. The advantages of the proposed real-time scheme are illustrated by applying the algorithm to a nonlinear process control problem in the presence of measurement errors and process noise.

Chat View PDF

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

Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

2017-01-01

Björn Geißler , Antonio Morsi , Lars Schewe +1 more

Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only a few works considering their theoretical properties. We … Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only a few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems.

Chat View PDF

A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems

2018-06-27

Jan Kronqvist , David E. Bernal , Andreas Lundell +1 more

A review and comparison of solvers for convex MINLP

2018-12-03

Jan Kronqvist , David E. Bernal , Andreas Lundell +1 more

In this paper, we present a review of deterministic software for solving convex MINLP problems as well as a comprehensive comparison of a large selection of commonly available solvers. As … In this paper, we present a review of deterministic software for solving convex MINLP problems as well as a comprehensive comparison of a large selection of commonly available solvers. As a test set, we have used all MINLP instances classified as convex in the problem library MINLPLib, resulting in a test set of 335 convex MINLP instances. A summary of the most common methods for solving convex MINLP problems is given to better highlight the differences between the solvers. To show how the solvers perform on problems with different properties, we have divided the test set into subsets based on the continuous relaxation gap, the degree of nonlinearity, and the relative number of discrete variables. The results also provide guidelines on how well suited a specific solver or method is for particular types of MINLP problems.

Chat View PDF

Using regularization and second order information in outer approximation for convex MINLP

2018-12-18

Jan Kronqvist , David E. Bernal , Ignacio E. Grossmann

Improving the performance of DICOPT in convex MINLP problems using a feasibility pump

2019-08-12

David E. Bernal , Stefan Vigerske , Francisco Trespalacios +1 more

The solver DICOPT is based on the outer-approximation algorithm used for solving mixed-integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, … The solver DICOPT is based on the outer-approximation algorithm used for solving mixed-integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, it has been observed that DICOPT has difficulties solving instances in which some of the nonlinear constraints are so restrictive that nonlinear subproblems generated by the algorithm are infeasible. This problem is addressed in this paper with a feasibility pump algorithm, which modifies the objective function in order to efficiently find feasible solutions. It has been implemented as a preprocessing algorithm, which is used to initialize both the incumbent and the mixed-integer linear relaxation of the outer-approximation algorithm. Computational comparisons with previous versions of DICOPT on a set of convex MINLPs demonstrate the effectiveness of the proposed algorithm in terms of solution quality and solution time.

Chat View PDF

Parameter-free resolution of the superposition of stochastic signals

2016-11-03

Teresa Scholz , Frank Raischel , Vítor V. Lopes +4 more

Chat View PDF

MATMPC - A MATLAB Based Toolbox for Real-time Nonlinear Model Predictive Control

2019-06-01

Yutao Chen , Mattia Bruschetta , Enrico Picotti +1 more

In this paper we introduce MATMPC, an open source software built in MATLAB for nonlinear model predictive control (NMPC). It is designed to facilitate modelling, controller design and simulation for … In this paper we introduce MATMPC, an open source software built in MATLAB for nonlinear model predictive control (NMPC). It is designed to facilitate modelling, controller design and simulation for a wide class of NMPC applications. MATMPC has a number of algorithmic modules, including automatic differentiation, direct multiple shooting, condensing, linear quadratic program (QP) solver and globalization. It also supports a unique Curvature-like Measure of Nonlinearity (CMoN) MPC algorithm. MATMPC has been designed to provide state-of-the-art performance while making the prototyping easy, also with limited programming knowledge. This is achieved by writing each module directly in MATLAB API for C. As a result, MATMPC modules can be compiled into MEX functions with performance comparable to plain C/C++ solvers. MATMPC has been successfully used in operating systems including WINDOWS, LINUX AND OS X. Selected examples are shown to highlight the effectiveness of MATMPC.

Chat View PDF

The Numerical Treatment of Differential Equations

1961-10-01

Richard C. Roberts , Lothar Collatz , Peter Williams

Shortest Paths Among Obstacles in the Plane Revisited

2021-01-01

Haitao Wang

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been … Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. The algorithm is time-optimal because Ω(n log n) is a lower bound. It has been an open problem for over two decades whether the space can be reduced to O(n). In this paper, we settle it by solving the problem in O(n log n) time and O(n) space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point s in O(n log n) time and O(n) space, such that given any query point t, the length of a shortest path from s to t can be computed in O(log n) time and a shortest path can be produced in additional time linear in the number of edges of the path.

Chat View PDF

A quaternion‐based model for optimal control of an airborne wind energy system

2016-09-05

Michael Erhard , Greg Horn , Moritz Diehl

Airborne wind energy systems are capable of extracting energy from higher wind speeds at higher altitudes. The configuration considered in this paper is based on a tethered kite flown in … Airborne wind energy systems are capable of extracting energy from higher wind speeds at higher altitudes. The configuration considered in this paper is based on a tethered kite flown in a pumping orbit. This pumping cycle generates energy by winching out at high tether forces and driving a generator while flying figures-of-eight, or lemniscates, as crosswind pattern. Then, the tether is reeled in while keeping the kite at a neutral position, thus leaving a net amount of generated energy. In order to achieve an economic operation, optimization of pumping cycles is of great interest. In this paper, first the principles of airborne wind energy will be briefly revisited. The first contribution is a singularity-free model for the tethered kite dynamics in quaternion representation, where the model is derived from first principles. The second contribution is an optimal control formulation and numerical results for complete pumping cycles. Based on the developed model, the setup of the optimal control problem (OCP) is described in detail along with its numerical solution based on the direct multiple shooting method in the CasADi optimization environment. Optimization results for a pumping cycle consisting of six lemniscates show that the approach is capable to find an optimal orbit in a few minutes of computation time. For this optimal orbit, the power output is increased by a factor of two compared to a sophisticated initial guess for the considered test scenario.

Chat View PDF