Nonlinear optimal control problems are often addressed by direct methods. These typically result in large structured nonlinear programs (NLP) with convex objective and convex inequality constraints, but also with many nonlinear equality constraints whose derivatives are expensive to evaluate. For continuous decision spaces, sequential quadratic programming (SQP) and more generally, sequential convex programming (SCP) algorithms are often used to solve the resulting NLP. They linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact, such as (conic) inequality constraints or convex objective terms (such as for example least squares terms in the Constrained Gauss-Newton method). Aim of the presented Sequential Mixed Integer Quadratic Programming (MIQP) Algorithm for mixed integer optimal control problems is to confer the SQP/SCP methodology to Mixed Integer Nonlinear Programs (MINLP) and to leverage the availability of efficient MIQP solvers. Each iterate is based on three steps: First, the MINLP is linearized at a given iterate (“linearization point”). Second, an MIQP with its feasible set restricted to a specific trust region around the current linearization point is formulated and solved. Third, the integer variables obtained from the MIQP solution are fixed and an NLP in the continuous variables only is solved. The outcome of the third step is compared to previous iterates and the best iterate so far is used as linearization point in the next iterate. Crucially, the objective values and derivatives from all previous iterates are used to formulate the polyhedral trust region in the second step. The linear inequalities that define the trust region build on concepts from Generalized Benders’ Decomposition for MINLP and a Voronoi partitioning of the integer space. Though the presented MINLP algorithm is a heuristic method without any global optimality guarantee, it can be shown to converge to the exact integer solution when applied to convex MINLP with only linear outer structure. The talk is based on joint work with Andrea Ghezzi, Leo Simpson, Wim Van Roy, Adrian Bürger, Sebastian Sager, and Clemens Zeile.
Join at: imt.lu/sagrestia