liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Mixed Integer Predictive Control
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
2008 (English)Report (Other academic)
Abstract [en]

The objective of this work is to derive a Mixed Integer Quadratic Programming algorithm tailored for Model Predictive Control for hybrid systems. The Mixed Integer Quadratic Programming algorithm is built on the branch and bound method, where Quadratic Programming relaxations of the original problem are solved in the nodes of a binary search tree. The difference between these subproblems is often small and therefore it is interesting to be able to use a previous solution as a starting point in a new subproblem. This is referred to as a warm start of the solver. Because of its warm start properties, an algorithm that works similar to an active set method is desired. A drawback with classical active set methods is that they often require many iterations in order to find the active set in optimum. So-called gradient projection methods are known to be able to identify this active set very fast. In the algorithm presented in this report, an algorithm built on gradient projection and projection of a Newton search direction onto the feasible set is used. It is a variant of a previously presented algorithm by the authors and makes it straightforward to utilize the previous result, where it is shown how the Newton search direction for the dual MPC problem can be computed very efficiently using Riccati recursions. As in the previous work, this operation can be performed with linear computational complexity in the prediction horizon. Moreover, the gradient computation used in the gradient projection part of the algorithm is also tailored for the problem in order to decrase the computational complexity. Furthermore, is is shown how a Riccati recursion still can be useful in the case when the system of equations for the ordinary search directino is inconsistent. In numerical experiments, the algorithm shows good performance, and it seems like the gradient projection strategy efficiently cuts down the number of Newton steps necessary to compute in order to reach the solution. When the algorithm is used as a part of an MIQP solver for hybrid MPC, the performance is still very good for small problems. However, for more difficult problems, there still seems to be some more work to do in order to get the performance of the commercial state-of-the-art solver CPLEX.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2008. , 58 p.
LiTH-ISY-R, ISSN 1400-3902 ; 2833
Keyword [en]
Model predictive control, Hybrid systems, Quadratic programming, Mixed integer quadratic programming
National Category
Control Engineering
URN: urn:nbn:se:liu:diva-56157ISRN: LiTH-ISY-R-2833OAI: diva2:316941
Available from: 2010-04-30 Created: 2010-04-30 Last updated: 2014-06-19Bibliographically approved

Open Access in DiVA

fulltext(596 kB)147 downloads
File information
File name FULLTEXT01.pdfFile size 596 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Axehill, DanielHansson, Anders
By organisation
Automatic ControlThe Institute of Technology
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 147 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 98 hits
ReferencesLink to record
Permanent link

Direct link