Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution. / Numeriska algoritmer för att effektivt lösa optimala styrningsproblem är en viktig komponent i avancerade regler- och estimeringsstrategier som exempelvis modellprediktiv reglering (eng. model predictive control (MPC)) och glidande horisont estimering (eng. moving horizon estimation (MHE)). MPC är en reglerstrategi som kan användas för att styra system med flera styrsignaler och/eller utsignaler samt ta hänsyn till exempelvis begränsningar i styrdon. Den grundläggande principen för MPC och MHE är att styrsignalen och de estimerade variablerna kan beräknas genom att lösa ett optimalt styrningsproblem. Detta optimeringsproblem måste lösas inom en kort tidsram varje gång som en styrsignal ska beräknas eller som variabler ska estimeras, och således är det viktigt att det finns effektiva algoritmer för att lösa denna typ av problem. Två vanliga sådana är inrepunkts-metoder (eng. interior-point (IP)) och aktivmängd-metoder (eng. active-set (AS)), där optimeringsproblemet löses genom att lösa ett antal enklare delproblem. Ett av huvudfokusen i denna avhandling är att beräkna lösningen till dessa delproblem på ett tidseffektivt sätt genom att utnyttja strukturen i delproblemen. Lösningen till ett delproblem beräknas genom att lösa ett linjärt ekvationssystem. Detta ekvationssystem kan man exempelvis lösa med generella metoder eller med så kallade Riccatirekursioner som utnyttjar strukturen i problemet. När man använder en AS-metod för att lösa MPC-problemet så görs endast små strukturerade ändringar av ekvationssystemet mellan varje delproblem, vilket inte har utnyttjats tidigare tillsammans med Riccatirekursionen. I denna avhandling presenteras ett sätt att utnyttja detta genom att bara göra små förändringar av Riccatirekursionen för att minska beräkningstiden för att lösa delproblemet. Idag har behovet av  parallella algoritmer för att lösa MPC och MHE problem ökat. Att algoritmerna är parallella innebär att beräkningar kan ske på olika delar av problemet samtidigt med syftet att minska den totala verkliga beräkningstiden för att lösa optimeringsproblemet. I denna avhandling presenteras parallella algoritmer som kan användas i både IP- och AS-metoder. Algoritmerna beräknar lösningen till delproblemen parallellt med ett förutbestämt antal steg, till skillnad från många andra parallella algoritmer där ett okänt (ofta stort) antal steg krävs. De parallella algoritmerna utnyttjar problemstrukturen för att lösa delproblemen effektivt, och en av dem har utvärderats på parallell hårdvara. Linjära MPC problem kan också lösas genom att utnyttja teori från multiparametrisk kvadratisk programmering (eng. multiparametric quadratic programming (mp-QP)) där den optimala lösningen beräknas i förhand och lagras i en tabell, vilket benämns explicit MPC. I detta fall behöver inte MPC problemet lösas varje gång en styrsignal beräknas, utan istället kan den förberäknade optimala styrsignalen slås upp. En nackdel med mp-QP är att det krävs mycket plats i minnet för att spara lösningen. I denna avhandling presenteras en strukturutnyttjande algoritm som kan minska behovet av minne för att spara lösningen, vilket kan öka det praktiska användningsområdet för mp-QP och explicit MPC.

<p>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 principles is the discrete-time method Model Predictive Control (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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple 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 different 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 multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two 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 simulations, the algorithm is applied to unconstrained MPC 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.</p> / Report code: LiU-TEK-LIC-2005:71.

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 principles is the discrete-time method Model Predictive Control (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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple 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 different 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 multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two 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 simulations, the algorithm is applied to unconstrained MPC 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. / <p>Report code: LiU-TEK-LIC-2005:71.</p>