Applications of Integer Quadratic Programming

The main topic of this thesis is integer quadratic programming with applications to prob-

lems arising in the areas of automatic control and communication. One of the most

widespread modern control principles is the discrete-time method Model Predictive Con-

trol (MPC). The main advantage with MPC, compared to most other control principles,

is that constraints on control signals and states can easily be handled. In each time step,

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 from

constrained linear systems 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. Gener-

ally, for this type of optimization problems, the computational complexity is exponential

in the number of binary optimization variables. In modern communication systems, mul-

tiple users share a so-called multi-access channel, where the information sent by different

users is separated by using almost orthogonal codes. Since the codes are not completely

orthogonal, the decoded information at the receiver is slightly correlated between differ-

ent users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The

process of simultaneously estimating the information sent by multiple users is called mul-

tiuser detection. In this thesis, the problem to efficiently solveMIQP problems originating

fromMPC is addressed. Two different algorithms are presented. First, a polynomial com-

plexity 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 simulations, the algorithm is applied to unconstrainedMPC

problems with a mixture of real and binary control signals. It has also been applied to the

multiuser detection problem, where simulations have shown that the bit error rate can

be significantly reduced by using the proposed algorithm as 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 QP solver and the MIQP solver proposed have lower computational

complexity than corresponding generic solvers.

Title
Subtitle
Author
Publisher
Pages
Year
ISBN
Content
Link1	Download
Link2