Embedded Mixed-Integer Quadratic Optimization using Accelerated Dual Gradient Projection. Issue 1 (July 2017)

• Record Type: Journal Article
• Authors: Naik, Vihangkumar V.; Bemporad, Alberto
• Is Part Of: IFAC-PapersOnLine. Volume 50:Issue 1(2017)
• Page Start: 10723
• Page End: 10728
• Publication Date: 2017-07
• Subjects: Mixed-integer quadratic programming -- quadratic programming -- Accelerated gradient projection -- model predictive control -- hybrid systems; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2017.08.2235
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: The execution of a hybrid model predictive controller (MPC) on an embedded platform requires solving a Mixed-Integer Quadratic Programming (MIQP) in real time. The MIQP problem is NP-hard, which poses a major challenge in an environment where computational and memory resources are limited. To address this issue, we propose the use of accelerated dual gradient projection (GPAD) to find both the exact and an approximate solution of the MIQP problem. In particular, an existing GPAD algorithm is specialized to solve the relaxed Quadratic Programming (QP) subproblems that arise in a Branch and Bound (B&B) method for solving the MIQP to optimality. Furthermore, we present an approach to find a suboptimal integer feasible solution of a MIQP problem without using B&B. The GPAD algorithm is very simple to code and requires only basic arithmetic operations which makes it well suited for an embedded implementation. The performance of the proposed approaches is comparable with the state of the art MIQP solvers for small-scale problems.