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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Integer Quadratic Programming for Control and Communication
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.ORCID iD: 0000-0001-6957-2603
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control methods is Model Predictive Control (MPC). In each sampling time, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem, which is known to have a computational complexity which grows exponentially in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel. To estimate the information originally sent, a maximum likelihood problem involving binary variables can be solved. The process of simultaneously estimating the information sent by multiple users is called Multiuser Detection (MUD). In this thesis, the problem to efficiently solve MIQP problems originating from MPC and MUD is addressed. Four different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In numerical experiments, the algorithm is applied to unconstrained MPC problems with a mixture of real valued and binary valued control signals, and the result shows that the performance gain can be significant compared to solving the problem using branch and bound. The preprocessing algorithm has also been applied to the MUD problem, where simulations have shown that the bit error rate can be significantly reduced compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the proposed QP solver and MIQP solver have lower computational complexity compared to corresponding generic solvers. Third, the dual active set QP algorithm is enhanced using ideas from gradient projection methods. The performance of this enhanced algorithm is shown to be comparable with the existing commercial state-of-the-art QP solver \cplex for some random linear MPC problems. Fourth, an algorithm for efficient computation of the search directions in an SDP solver for a proposed alternative SDP relaxation applicable to MPC problems with binary control signals is presented. The SDP relaxation considered has the potential to give a tighter lower bound on the optimal objective function value compared to the QP relaxation that is traditionally used in branch and bound for these problems, and its computational performance is better than the ordinary SDP relaxation for the problem. Furthermore, the tightness of the different relaxations is investigated both theoretically and in numerical experiments.

Place, publisher, year, edition, pages
Institutionen för systemteknik , 2008. , 231 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1158
Keyword [en]
Integer Quadratic Programming, Model Predictive Control, Hybrid Systems, Semidefinite Programming, Code Division Multiple Access, Multiuser Detection, Automatic Control, Communication
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-10642ISBN: 978-91-85523-03-0 (print)OAI: oai:DiVA.org:liu-10642DiVA: diva2:17358
Public defence
2008-02-27, Visionen, Hus C, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Note
This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Linköping University's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it.Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
List of papers
1. A Preprocessing Algorithm for MIQP Solvers with Applications to MPC
Open this publication in new window or tab >>A Preprocessing Algorithm for MIQP Solvers with Applications to MPC
2004 (English)In: Proceedings of the 43rd IEEE Conference on Decision and Control, 2004, 2497-2502 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper a preprocessing algorithm for unconstrained mixed integer quadratic programming problems and binary quadratic programming problems is presented. The algorithm applies to problems with certain properties, which are further described in the paper. When the algorithm is applied to a problem with these properties, the optimal value for some or all integer variables can be computed without approximations in polynomial time. The algorithm is first derived for the binary quadratic programming problem and the resultis then extended to the mixed integer quadratic programming problem by transforming the latter problem into the first problem. Both mentioned quadratic programming problems have several important applications. In this paper, the focus is on model predictive control problems with both real-valued and binary control signals. As an illustration of the method, the algorithm is applied to two different problems of this type.

Keyword
Predictive control, Integer programming, Quadratic programming
National Category
Engineering and Technology Control Engineering
Identifiers
urn:nbn:se:liu:diva-12902 (URN)10.1109/CDC.2004.1428790 (DOI)0-7803-8682-5 (ISBN)
Conference
43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, December, 2004
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
2. A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences
Open this publication in new window or tab >>A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences
2008 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 56, no 9, 4377-4385 p.Article in journal (Refereed) Published
Abstract [en]

The optimum multiuser detection problem can be formulated as a maximum likelihood problem, which yields a binary quadratic programming problem to be solved. Generally this problem is NP-hard and is therefore hard to solve in real time. In this paper, a preprocessing algorithm is presented which makes it possible to detect some or all users optimally for a low computational cost if signature sequences with low cross correlation, e.g., Gold sequences, are used. The algorithm can be interpreted as, e.g., an adaptive tradeoff between parallel interference cancellation and successive interference cancellation. Simulations show that the preprocessing algorithm is able to optimally compute more than 94,% of the bits in the problem when the users are time-synchronous, even though the system is heavily loaded and affected by noise. Any remaining bits, not computed by the preprocessing algorithm, can either be computed by a suboptimal detector or an optimal detector. Simulations of the time-synchronous case show that if a suboptimal detector is chosen, the bit error rate (BER) rate is significantly reduced compared with using the suboptimal detector alone.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2008
Keyword
Code division multiple access, Computational complexity, Error statistics, Interference suppression, Maximum likelihood detection, Multiuser detection, Quadratic programming, Sequences, CDMA channel models, Gold sequences, NP-hard problem, Binary quadratic programming problem, Bit error rate, Low cross correlation, Low-complexity high-performance preprocessing algorithm, Maximum likelihood problem, Optimal detector, Optimum multiuser detection problem, Parallel interference cancellation, Suboptimal detector, Successive interference cancellation, Time-synchronous users
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-12903 (URN)10.1109/TSP.2008.926190 (DOI)
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
3. A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC
Open this publication in new window or tab >>A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC
2006 (English)In: Proceedings of the 45th IEEE Conference on Decision and Control, 2006, 5693-5698 p.Conference paper, Published paper (Refereed)
Abstract [en]

The objective of this work is to derive an MIQP solver tailored for MPC. The MIQP solver is built on the branch and bound method, where QP relaxations of the original problem are solved in the nodes of a binary search tree. The difference between the 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 good warm start properties, a dual active set QP method was chosen. The method is tailored for MPC by solving a part of the KKT system using a Riccati recursion, which makes the computational complexity of the QP iterations grow linearly with the prediction horizon. Simulation results are presented both for the QP solver itself and when it is incorporated as a part of the MIQP solver. In both cases the computational complexity is significantly reduced compared to if a primal active set solver not utilizing structure is used.

Keyword
Riccati equations, Computational complexity, Integer programming, Iterative methods, Predictive control, Quadratic programming, Tree searching, KKT system, QP iterations, QP relaxations, Riccati recursion, Binary search tree, Branch and bound method, Computational complexity, Mixed integer dual quadratic programming algorithm, Model predictive control, Prediction horizon
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-12904 (URN)10.1109/CDC.2006.377215 (DOI)1-4244-0171-2 (ISBN)
Conference
45th IEEE Conference on Decision and Control, San Diego, CA, USA, December, 2006
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31
4. A dual gradient projection quadratic programming algorithm tailored for mixed integer predictive control
Open this publication in new window or tab >>A dual gradient projection quadratic programming algorithm tailored for mixed integer predictive control
Manuscript (Other academic)
Identifiers
urn:nbn:se:liu:diva-12905 (URN)
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2010-01-13
5. On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
Open this publication in new window or tab >>On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
2007 (English)In: Proceedings of the 7th IFAC Symposium on Nonlinear Control Systems, Curran Associates, Inc., 2007, 585-590 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality constrained SDP relaxation. The relaxations are related theoretically, and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The result is that for long prediction horizons, the equality constrained SDP relaxation proposed in this paper provides a good trade-off between the quality of the relaxation and the computational time.

Place, publisher, year, edition, pages
Curran Associates, Inc., 2007
Series
LiTH-ISY-R, ISSN 1400-3902 ; 2771
Keyword
Predictive control, Hybrid systems, Binary control, Integer programing, Semidefinite programming
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-12906 (URN)10.3182/20070822-3-ZA-2920.00096 (DOI)978-3-902661-28-9 (ISBN)
Conference
7th IFAC Symposium on Nonlinear Control Systems, Pretoria, South Africa, August, 2007
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31Bibliographically approved
6. Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations
Open this publication in new window or tab >>Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations
2007 (English)In: Proceedings of the 46th IEEE Conference on Decision and Control, 2007, 4103-4109 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this work, different relaxations applicable to an MPC problem with a mix of real valued and binary valued control signals are compared. In the problem description considered, there are linear inequality constraints on states and control signals. The relaxations are related theoretically and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The relaxations considered are the quadratic programming (QP) relaxation, the standard semidefinite programming (SDP) relaxation and an equality constrained SDP relaxation. The result is that the standard SDP relaxation is the one that usually gives the best bound and is most computationally demanding, while the QP relaxation is the one that gives the worst bound and is least computationally demanding. The equality constrained relaxation presented in this paper often gives a better bound than the QP relaxation and is less computationally demanding compared to the standard SDP relaxation. Furthermore, it is also shown how the equality constrained SDP relaxation can be efficiently computed by solving the Newton system in an Interior Point algorithm using a Riccati recursion. This makes it possible to compute the equality constrained relaxation with approximately linear computational complexity in the prediction horizon.

Keyword
Newton method, Riccati equations, Computational complexity, Predictive control, Quadratic programming, Relaxation theory, Interior point algorithm, Newton system, Riccati recursion, Linear computational complexity, Linear inequality constraints, Mixed integer predictive control
National Category
Engineering and Technology Control Engineering
Identifiers
urn:nbn:se:liu:diva-12907 (URN)10.1109/CDC.2007.4434608 (DOI)978-1-4244-1497-0 (ISBN)978-1-4244-1498-7 (ISBN)
Conference
46th IEEE Conference on Decision and Control, New Orleans, LA, USA, December, 2007
Available from: 2008-03-18 Created: 2008-03-18 Last updated: 2016-08-31Bibliographically approved

Open Access in DiVA

cover(198 kB)46 downloads
File information
File name COVER01.pdfFile size 198 kBChecksum SHA-1
1992683a7e47b84553490408b6be4c7f6a71dee06e1ea40a5cb6a06acd5e5ecf9a1e3aa9
Type coverMimetype application/pdf
fulltext(1414 kB)2659 downloads
File information
File name FULLTEXT01.pdfFile size 1414 kBChecksum SHA-1
ff16813a4c7018bdc0883c5374e696d8797a43dc191f7ae40ad75c59e9b63e6a7aa43665
Type fulltextMimetype application/pdf

Authority records BETA

Axehill, Daniel

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 2659 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 5381 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf