## Journal papers

A sensor management method for joint multi-target search and track problems is proposed, where a single user-defined parameter allows for a trade-off between the two objectives. The multi-target density is propagated using the Poisson multi-Bernoulli mixture filter, which eliminates the need for a separate handling of undiscovered targets and provides the theoretical foundation for a unified search and track method. Monte Carlo simulations of two scenarios are used to evaluate the performance of the proposed method.

```
@article{diva2:1540474,
author = {Boström-Rost, Per and Axehill, Daniel and Hendeby, Gustaf},
title = {{Sensor management for search and track using the Poisson multi-Bernoulli mixture filter}},
journal = {IEEE Transactions on Aerospace and Electronic Systems},
year = {2021},
}
```

This paper presents a unified optimization-based path planning approach to efficiently compute locally optimal solutions to optimal path planning problems in unstructured environments. The approach is motivated by showing that a lattice-based planner can be cast and analyzed as a bilevel optimization problem. This insight is used to integrate a lattice-based planner and an optimal control-based method in a novel way. The lattice-based planner is applied to the problem in a first step using a discretized search space. In a second step, an optimal control-based method is applied using the lattice-based solution as an initial iterate. In contrast to prior work, the system dynamics and objective function used in the first step are chosen to coincide with those used in the second step. As an important consequence, the lattice planner provides a solution which is highly suitable as a warm-start to the optimal control step. This proposed combination makes, in a structured way, benefit of sampling-based methods ability to solve combinatorial parts of the problem and optimal control-based methods ability to obtain locally optimal solutions. Compared to previous work, the proposed approach is shown in simulations to provide significant improvements in terms of computation time, numerical reliability and objective function value.

```
@article{diva2:1517316,
author = {Bergman, Kristoffer and Ljungqvist, Oskar and Axehill, Daniel},
title = {{Improved Path Planning by Tightly Combining Lattice-Based Path Planning and Optimal Control}},
journal = {IEEE Transactions on Intelligent Vehicles},
year = {2021},
volume = {6},
number = {1},
pages = {57--66},
}
```

When solving a quadratic program (QP), one can improve the numerical stability of any QP solver by performing proximal-point outer iterations, resulting in solving a sequence of better conditioned QPs. In this letter we present a method which, for a given multi-parametric quadratic program (mpQP) and any polyhedral set of parameters, determines which sequences of QPs will have to be solved when using outer proximal-point iterations. By knowing this sequence, bounds on the worst-case complexity of the method can be obtained, which is of importance in, for example, real-time model predictive control (MPC) applications. Moreover, we combine the proposed method with previous work on complexity certification for active-set methods to obtain a more detailed certification of the proximal-point methods complexity, namely the total number of inner iterations.

```
@article{diva2:1512943,
author = {Arnström, Daniel and Bemporad, Alberto and Axehill, Daniel},
title = {{Complexity Certification of Proximal-Point Methods for Numerically Stable Quadratic Programming}},
journal = {IEEE CONTROL SYSTEMS LETTERS},
year = {2021},
volume = {5},
number = {4},
pages = {1381--1386},
}
```

The prediction uncertainty of a neural network is considered from a classical system identification point of view. To know this uncertainty is extremely important when using a network in decision and feedback applications. The asymptotic covariance of the internal parameters in the network due to noise in the observed dependent variables (output) and model class mismatch, i.e., the true system cannot be exactly described by the model class, is first surveyed. This is then applied to the prediction step of the network to get a closed form expression for the asymptotic, in training data information, prediction variance. Another interpretation of this expression is as the non-asymptotic Cramér-Rao Lower Bound. To approximate this expression, only the gradients and residuals, already computed in the gradient descent algorithms commonly used to train neural networks, are needed. Using a toy example, it is illustrated how the uncertainty in the output of a neural network can be estimated.

```
@article{diva2:1546958,
author = {Malmström, Magnus and Skog, Isaac and Axehill, Daniel and Gustafsson, Fredrik},
title = {{Asymptotic Prediction Error Variance for Feedforward Neural Networks}},
journal = {IFAC-PapersOnLine},
year = {2020},
volume = {53},
number = {2},
pages = {1108--1113},
}
```

In this letter we propose a method to exactly certify the complexity of an active-set method which is based on reformulating strictly convex quadratic programs to nonnegative least-squares problems. The exact complexity of the method is determined by proving the correspondence between the method and a standard primal active-set method for quadratic programming applied to the dual of the quadratic program to be solved. Once this correspondence has been established, a complexity certification method which has already been established for the primal active-set method is used to also certify the complexity of the nonnegative least-squares method. The usefulness of the proposed method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum.

```
@article{diva2:1522244,
author = {Arnström, Daniel and Bemporad, Alberto and Axehill, Daniel},
title = {{Exact Complexity Certification of a Nonnegative Least-Squares Method for Quadratic Programming}},
journal = {IEEE CONTROL SYSTEMS LETTERS},
year = {2020},
volume = {4},
number = {4},
pages = {1036--1041},
}
```

Maneuvering a general 2-trailer with a car-like tractor in backward motion is a task that requires a significant skill to master and is unarguably one of the most complicated tasks a truck driver has to perform. This paper presents a path planning and path-following control solution that can be used to automatically plan and execute difficult parking and obstacle avoidance maneuvers by combining backward and forward motion. A lattice-based path planning framework is developed in order to generate kinematically feasible and collision-free paths and a path-following controller is designed to stabilize the lateral and angular path-following error states during path execution. To estimate the vehicle state needed for control, a nonlinear observer is developed, which only utilizes information from sensors that are mounted on the car-like tractor, making the system independent of additional trailer sensors. The proposed path-planning and path-following control framework is implemented on a full-scale test vehicle and results from simulations and real-world experiments are presented.

```
@article{diva2:1370788,
author = {Ljungqvist, Oskar and Evestedt, Niclas and Axehill, Daniel and Cirillo, Marcello and Pettersson, Henrik},
title = {{A path planning and path-following control framework for a general 2-trailer with a car-like tractor}},
journal = {Journal of Field Robotics},
year = {2019},
volume = {36},
number = {8},
pages = {1345--1377},
}
```

Model predictive control (MPC) is one of the most widely spread advanced control schemes in industry today. In MPC, a constrained finite-time optimal control (CFTOC) problem is solved at each iteration in the control loop. The CFTOC problem can be solved using, for example, second-order methods, such as interior-point or active-set methods, where the computationally most demanding part often consists of computing the sequence of second-order search directions. Each search direction can be computed by solving a set of linear equations that corresponds to solving an unconstrained finite-time optimal control (UFTOC) problem. In this paper, different direct (noniterative) parallel algorithms for solving UFTOC problems are presented. The parallel algorithms are all based on a recursive variable elimination and solution propagation technique. Numerical evaluations of one of the parallel algorithms indicate that a significant boost in performance can be obtained, which can facilitate high-performance second-order MPC solvers.

```
@article{diva2:1338188,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{Direct Parallel Computations of Second-Order Search Directions for Model Predictive Control}},
journal = {IEEE Transactions on Automatic Control},
year = {2019},
volume = {64},
number = {7},
pages = {2845--2860},
}
```

The problem of path planning for mobilesensors with the task of target monitoring is considered. A receding horizon optimal control approach based on the information filter is presented, where the limited field of view of the sensor can be modeled by introducing binary variables. The resulting nonlinear mixed integer problem to be solved in each sample, with no apparent tractable solution, is shown to be equivalent to a problem that robustly can be solved to global optimality using off-the-shelf optimization tools.

```
@article{diva2:1250190,
author = {Boström-Rost, Per and Axehill, Daniel and Hendeby, Gustaf},
title = {{On Global Optimization for Informative Path Planning}},
journal = {IEEE Control Systems Letters},
year = {2018},
volume = {2},
number = {4},
pages = {833--838},
}
```

In Model Predictive Control (MPC), the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem at each sample in the control loop. The main computational effort when solving the CFTOC problem using an active-set (AS) method is often spent on computing the search directions, which in MPC corresponds to solving unconstrained finite-time optimal control (UFTOC) problems. This is commonly performed using Riccati recursions or generic sparsity exploiting algorithms. In this work the focus is efficient search direction computations for AS type methods. The system of equations to be solved at each AS iteration is changed only by a low-rank modification of the previous one, and exploiting this structured change is important for the performance of AS type solvers. In this paper, theory for how to exploit these low-rank changes by modifying the Riccati factorization between AS iterations in a structured way is presented. A numerical evaluation of the proposed algorithm shows that the computation time can be significantly reduced by modifying, instead of re-computing, the Riccati factorization. This speed-up can be important for AS type solvers used for linear, nonlinear and hybrid MPC.

```
@article{diva2:1155701,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{Low-Rank Modifications of Riccati Factorizations for Model Predictive Control}},
journal = {IEEE Transactions on Automatic Control},
year = {2018},
volume = {63},
number = {3},
pages = {872--879},
}
```

Merge scenarios confront drivers with some of the most complicated driving maneuvers in every day driving, requiring anticipatory reasoning of positions of other vehicles, and the own vehicles future trajectory. In congested traffic it might be impossible to merge without cooperation of up-stream vehicles, therefore, it is essential to gauge the effect of our own trajectory when planning a merge maneuver. For an autonomous vehicle to perform a merge maneuver in congested traffic similar capabilities are required. This includes a model describing the future evolution of the scene that allows for optimizing the autonomous vehicle's planned trajectory with respect to risk, comfort, and dynamical limitations. We present a probabilistic model that explicitly models interaction between vehicles and allows for evaluating the utility of a large number of candidate trajectories of an autonomous vehicle using a receding horizon approach in order to select an appropriate merge maneuver. The model is an extension of the intelligent driver model and the modeled behavior of other vehicles are adjusted using on-line model parameter estimation in order to give better predictions. The prediction model is evaluated using naturalistic traffic data and the merge maneuver planner is evaluated in simulation.

```
@article{diva2:1196713,
author = {Ward, Erik and Evestedt, Niclas and Axehill, Daniel and Folkesson, John},
title = {{Probabilistic Model for Interaction Aware Planning in Merge Scenarios}},
journal = {IEEE Transactions on Intelligent Vehicles},
year = {2017},
volume = {2},
number = {2},
pages = {133--146},
}
```

This note presents an efficient approach for the evaluation of multi-parametric mixed integer quadratic programming (mp-MIQP) solutions, occurring for instance in control problems involving discrete time hybrid systems with quadratic cost. Traditionally, the online evaluation requires a sequential comparison of piecewise quadratic value functions. We introduce a lifted parameter space in which the piecewise quadratic value functions become piecewise affine and can be merged to a single value function defined over a single polyhedral partition without any overlaps. This enables efficient point location approaches using a single binary search tree. Numerical experiments with a power electronics application demonstrate an online speedup up to an order of magnitude. We also show how the achievable online evaluation time can be traded off against the offline computational time.

```
@article{diva2:899519,
author = {Fuchs, Alexander and Axehill, Daniel and Morari, Manfred},
title = {{Lifted Evaluation of mp-MIQP Solutions}},
journal = {IEEE Transactions on Automatic Control},
year = {2015},
volume = {60},
number = {12},
pages = {3328--3331},
}
```

In optimization algorithms used for on-line Model Predictive Control (MPC), linear systems of equations are often solved in each iteration. This is true both for Active Set methods as well as for Interior Point methods, and for linear MPC as well as for nonlinear MPC and hybrid MPC. The main computational effort is spent while solving these linear systems of equations, and hence, it is of greatest interest to solve them efficiently. Classically, the optimization problem has been formulated in either of two ways. One leading to a sparse linear system of equations involving relatively many variables to compute in each iteration and another one leading to a dense linear system of equations involving relatively few variables. In this work, it is shown that it is possible not only to consider these two distinct choices of formulations. Instead it is shown that it is possible to create an entire family of formulations with different levels of sparsity and number of variables, and that this extra degree of freedom can be exploited to obtain even better performance with the software and hardware at hand. This result also provides a better answer to a recurring question in MPC; should the sparse or dense formulation be used.

```
@article{diva2:780367,
author = {Axehill, Daniel},
title = {{Controlling the level of sparsity in MPC}},
journal = {Systems \& control letters (Print)},
year = {2015},
volume = {76},
pages = {1--7},
}
```

In this article we present a parametric branch and bound algorithm for computation of optimal and suboptimal solutions to parametric mixed-integer quadratic programs and parametric mixed-integer linear programs. The algorithm returns an optimal or suboptimal parametric solution with the level of suboptimality requested by the user. An interesting application of the proposed parametric branch and bound procedure is suboptimal explicit MPC for hybrid systems, where the introduced user-defined suboptimality tolerance reduces the storage requirements and the online computational effort, or even enables the computation of a suboptimal MPC controller in cases where the computation of the optimal MPC controller would be intractable. Moreover, stability of the system in closed loop with the suboptimal controller can be guaranteed a priori.

```
@article{diva2:706645,
author = {Axehill, Daniel and Besselmann, Thomas and Martino Raimondo, Davide and Morari, Manfred},
title = {{A parametric branch and bound approach to suboptimal explicit hybrid MPC}},
journal = {Automatica},
year = {2014},
volume = {50},
number = {1},
pages = {240--246},
}
```

In optimization routines used for on-line Model Predictive Control (MPC), linear systems of equations are solved in each iteration. This is true both for Active Set (AS) solvers as well as for Interior Point (IP) solvers, and for linear MPC as well as for nonlinear MPC and hybrid MPC. The main computational effort is spent while solving these linear systems of equations, and hence, it is of great interest to solve them efficiently. In high performance solvers for MPC, this is performed using Riccati recursions or generic sparsity exploiting algorithms. To be able to get this performance gain, the problem has to be formulated in a sparse way which introduces more variables. The alternative is to use a smaller formulation where the objective function Hessian is dense. In this work, it is shown that it is possible to exploit the structure also when using the dense formulation. More specifically, it is shown that it is possible to efficiently compute a standard Cholesky factorization for the dense formulation. This results in a computational complexity that grows quadratically in the prediction horizon length instead of cubically as for the generic Cholesky factorization.

```
@article{diva2:475656,
author = {Axehill, Daniel and Morari, Manfred},
title = {{An Alternative use of the Riccati Recursion for Efficient Optimization}},
journal = {Systems \& control letters (Print)},
year = {2012},
volume = {61},
number = {1},
pages = {37--40},
}
```

The main objective in this work is to compare different convex relaxations for Model Predictive Control (MPC) problems with mixed real valued and binary valued control signals. In the problem description considered, the objective function is quadratic, the dynamics are linear, and the inequality constraints on states and control signals are all linear. The relaxations are related theoretically and the quality of the bounds and the computational complexities are compared in numerical experiments. The investigated relaxations include the Quadratic Programming (QP) relaxation, the standard Semidefinite Programming (SDP) relaxation, and an equality constrained SDP relaxation. The equality constrained SDP relaxation appears to be new in the context of hybrid MPC and the result presented in this work indicates that it can be useful as an alternative relaxation, which is less computationally demanding than the ordinary SDP relaxation and which often gives a better bound than the bound from the QP relaxation. Furthermore, it is discussed how the result from the SDP relaxations can be used to generate suboptimal solutions to the control problem. Moreover, it is also shown that the equality constrained SDP relaxation is equivalent to a QP in an important special case.

```
@article{diva2:355801,
author = {Axehill, Daniel and Vandenberghe, Lieven and Hansson, Anders},
title = {{Convex Relaxations for Mixed Integer Predictive Control}},
journal = {Automatica},
year = {2010},
volume = {46},
number = {9},
pages = {1540--1545},
}
```

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.

```
@article{diva2:17353,
author = {Axehill, Daniel and Hansson, Anders and Gunnarsson, Fredrik},
title = {{A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences}},
journal = {IEEE Transactions on Signal Processing},
year = {2008},
volume = {56},
number = {9},
pages = {4377--4385},
}
```

## Book chapters

In this chapter parallel implementations of hybrid MPC will be discussed. Different methods for achieving parallelism at different levels of the algorithms will be surveyed. It will be seen that there are many possible ways of obtaining parallelism for hybrid MPC, and it is by no means clear which possibilities that should be utilized to achieve the best possible performance. To answer this question is a challenge for future research.

```
@incollection{diva2:709563,
author = {Axehill, Daniel and Hansson, Anders},
title = {{Parallel implementation of hybrid MPC}},
booktitle = {Distributed Model Predictive Control Made Easy},
year = {2014},
pages = {375--392},
publisher = {Springer Netherlands},
}
```

## Conference papers

Stabilizing multi-steered articulated vehicles in backward motion is a complex task for any human driver. Unless the vehicle is accurately steered, its structurally unstable joint-angle kinematics during reverse maneuvers can cause the vehicle segments to fold and enter a jack-knife state. In this work, a model predictive path-following controller is proposed enabling automatic low-speed steering control of multi-steered articulated vehicles, comprising a car-like tractor and an arbitrary number of trailers with passive or active steering. The proposed path-following controller is tailored to follow nominal paths that contains full state and control-input information, and is designed to satisfy various physical constraints on the vehicle states as well as saturations and rate limitations on the tractors curvature and the trailer steering angles. The performance of the proposed model predictive path-following controller is evaluated in a set of simulations for a multi-steered 2-trailer with a car-like tractor where the last trailer has steerable wheels. Copyright (C) 2020 The Authors.

```
@inproceedings{diva2:1574170,
author = {Ljungqvist, Oskar and Axehill, Daniel},
title = {{A predictive path-following controller for multi-steered articulated vehicles}},
booktitle = {IFAC PAPERSONLINE},
year = {2020},
pages = {15725--15732},
publisher = {ELSEVIER},
}
```

The task of maneuvering a multi-steered articulated vehicle in confined environments is difficult even for experienced drivers. In this work, we present an optimization-based trajectory planner targeting low-speed maneuvers in unstructured environments for multi-steered N-trailer vehicles, which are comprised of a car-like tractor and an arbitrary number of interconnected trailers with fixed or steerable wheels. The proposed trajectory planning framework is divided into two steps, where a lattice-based trajectory planner is used in a first step to compute a resolution optimal solution to a discretized version of the trajectory planning problem. The output from the lattice planner is then used in a second step to initialize an optimal control problem solver, which enables the framework to compute locally optimal trajectories that start at the vehicles initial state and reaches the goal state exactly. The performance of the proposed optimization-based trajectory planner is evaluated in a set of practically relevant scenarios for a multi-steered 3-trailer vehicle with a car-like tractor where the last trailer is steerable. Copyright (C) 2020 The Authors.

```
@inproceedings{diva2:1574166,
author = {Ljungqvist, Oskar and Bergman, Kristoffer and Axehill, Daniel},
title = {{Optimization-based motion planning for multi-steered articulated vehicles}},
booktitle = {IFAC PAPERSONLINE},
year = {2020},
pages = {15580--15587},
publisher = {ELSEVIER},
}
```

This paper presents an optimization-based receding horizon trajectory planning algorithm for dynamical systems operating in unstructured and cluttered environments. The proposed approach is a two-step procedure that uses a motion planning algorithm in a first step to efficiently find a feasible, but possibly suboptimal, nominal solution to the trajectory planning problem where in particular the combinatorial aspects of the problem are solved. The resulting nominal trajectory is then improved in a second optimization-based receding horizon planning step which performs local trajectory refinement over a sliding time window. In the second step, the nominal trajectory is used in a novel way to both represent a terminal manifold and obtain an upper bound on the cost-to-go online. This enables the possibility to provide theoretical guarantees in terms of recursive feasibility, objective function value, and convergence to the desired terminal state. The established theoretical guarantees and the performance of the proposed algorithm are verified in a set of challenging trajectory planning scenarios for a truck and trailer system. Copyright (C) 2020 The Authors.

```
@inproceedings{diva2:1574092,
author = {Bergman, Kristoffer and Ljungqvist, Oskar and Glad, Torkel and Axehill, Daniel},
title = {{An Optimization-Based Receding Horizon Trajectory Planning Algorithm}},
booktitle = {IFAC PAPERSONLINE},
year = {2020},
pages = {15550--15557},
publisher = {ELSEVIER},
}
```

In this paper we present a method to exactly certify the iteration complexity of a primal active-set algorithm for quadratic programs which is terminated early, given a specific multi-parametric quadratic program. The primal active-set algorithms real-time applicability is, hence, improved by early termination, increasing its computational efficiency, and by the proposed certification method, providing guarantees on worst-case behaviour. The certification method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum, for which the relationship between allowed suboptimality and iterations needed by the primal active-set algorithm is presented. Copyright (C) 2020 The Authors.

```
@inproceedings{diva2:1572658,
author = {Arnström, Daniel and Axehill, Daniel},
title = {{Exact Complexity Certification of an Early-Terminating Standard Primal Active-Set Method for Quadratic Programming}},
booktitle = {IFAC PAPERSONLINE},
year = {2020},
pages = {6509--6515},
publisher = {ELSEVIER},
}
```

This paper presents an optimization-based receding horizon trajectory planning algorithm for dynamical systems operating in unstructured and cluttered environments. The proposed approach is a two-step procedure that uses a motion planning algorithm in a first step to efficiently find a feasible, but possibly suboptimal, nominal solution to the trajectory planning problem where in particular the combinatorial aspects of the problem are solved. The resulting nominal trajectory is then improved in a second optimization-based receding horizon planning step which performs local trajectory refinement over a sliding time window. In the second step, the nominal trajectory is used in a novel way to both represent a terminal manifold and obtain an upper bound on the cost-to-go online. This enables the possibility to provide theoretical guarantees in terms of recursive feasibility, objective function value, and convergence to the desired terminal state. The established theoretical guarantees and the performance of the proposed algorithm are verified in a set of challenging trajectory planning scenarios for a truck and trailer system.

```
@inproceedings{diva2:1546066,
author = {Bergman, Kristoffer and Ljungqvist, Oskar and Glad, Torkel and Axehill, Daniel},
title = {{An Optimization-Based Receding Horizon Trajectory Planning Algorithm}},
booktitle = {IFAC-PapersOnLine},
year = {2020},
pages = {15550--15557},
}
```

The task of maneuvering ships in confined environments is a difficult task for a human operator. One major reason is due to the complex and slow dynamics of the ship which need to be accounted for in order to successfully steer the vehicle. In this work, a two-step optimization-based motion planner is proposed for autonomous maneuvering of ships in constrained environments such as harbors. A lattice-based motion planner is used in a first step to compute a feasible, but suboptimal solution to a discretized version of the motion planning problem. This solution is then used to enable efficient warm-start and as a terminal manifold for a second receding-horizon improvement step. Both steps of the algorithm use a high-fidelity model of the ship to plan feasible and energy-efficient trajectories. Moreover, a novel algorithm is proposed for automatic computation of spatial safety envelopes around the trajectory computed by the lattice-based planner. These safety envelopes are used in the second improvement step to obtain collision-avoidance constraints which complexity scales very well with an increased number of surrounding obstacles. The proposed optimization-based motion planner is evaluated with successful results in a simulation study for autonomous docking problems in a model of the Cape Town harbor.

```
@inproceedings{diva2:1517304,
author = {Bergman, Kristoffer and Ljungqvist, Oskar and Linder, Jonas and Axehill, Daniel},
title = {{An Optimization-Based Motion Planner for Autonomous Maneuvering of Marine Vessels in Complex Environments}},
booktitle = {2020 59th IEEE Conference on Decision and Control (CDC)},
year = {2020},
pages = {5283--5290},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

An approach for belief space planning is presented, where knowledge about the landmark density is used as prior, instead of explicit landmark positions.

Having detailed maps of landmark positions in a previously unvisited environment is considered unlikely in practice. Instead, it is argued that landmark densities should be used, as they could be estimated from other sources, such as ordinary maps or aerial imagery.

It is shown that it is possible to use virtual landmarks to approximate the landmark density to solve the presented problem. This approximation is also shown to give small errors during evaluation.

The approach is tested in a simulated environment, in conjunction with an extended information filter (EIF), where the computed path is shown to be superior compared to other alternative paths used as benchmarks.

```
@inproceedings{diva2:1461041,
author = {Jonas, Nordlöf and Hendeby, Gustaf and Axehill, Daniel},
title = {{Belief Space Planning using Landmark Density Information}},
booktitle = {Proceedings of the 23rd International Conference on Information Fusion (FUSION)},
year = {2020},
publisher = {IEEE},
}
```

For a given radar system on an unmanned air vehicle, this work proposes a method to find the optimal tracking rangeand the optimal beamwidth for tracking a maneuvering target. An inappropriate optimal range or beamwidth is indicative ofthe need for a redesign of the radar system. An extended Kalman filter (EKF) is employed to estimate the state of the target using measurements of the range and bearing from the sensor to the target. The proposed method makes use of an alpha-beta filter to predict the expected tracking performanceof the EKF. Using an assumption of the maximum acceleration of the target, the optimal tracking range (or beamwidth) is determined as the one that minimizes the maximum mean squared error (MMSE) of the position estimates while satisfying a user-defined constraint on the probability of losing track of the target.The applicability of the design method is verified using Monte Carlo simulations.

```
@inproceedings{diva2:1441438,
author = {Boström-Rost, Per and Axehill, Daniel and Blair, William Dale and Hendeby, Gustaf},
title = {{Optimal Range and Beamwidth for Radar Tracking of Maneuvering Targets Using Nearly Constant Velocity Filters}},
booktitle = {Proceedings of 2020 IEEE Aerospace Conference},
year = {2020},
series = {IEEE Aerospace Conference},
}
```

Model Predictive Control (MPC) requires an optimization problem to be solved at each time step. For real-time MPC, it is important to solve these problems efficiently and to have good upper bounds on how long time the solver needs to solve them. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving QPs is primal active-set methods, where a sequence of equality constrained QP subproblems are solved. This paper presents a method for computing which sequence of subproblems a primal active-set method will solve, for every parameter of interest in the parameter space. Knowledge about exactly which sequence of subproblems that will be solved can be used to compute a worst-case bound on how many iterations, and ultimately the maximum time, the active-set solver needs to converge to the solution. Furthermore, this information can be used to tailor the solver for the specific control task. The usefulness of the proposed method is illustrated on a set of MPC problems, where the exact worst-case number of iterations a primal active-set method requires to reach optimality is computed.

```
@inproceedings{diva2:1466581,
author = {Arnström, Daniel and Axehill, Daniel},
title = {{Exact Complexity Certification of a Standard Primal Active-Set Method for Quadratic Programming}},
booktitle = {2019 IEEE 58TH CONFERENCE ON DECISION AND CONTROL (CDC)},
year = {2019},
series = {IEEE Conference on Decision and Control},
pages = {4317--4324},
publisher = {IEEE},
}
```

In this paper, we propose a framework for generating motion primitives for lattice-based motion planners automatically. Given a family of systems, the user only needs to specify which principle types of motions, which are here denoted maneuvers, that are relevant for the considered system family. Based on the selected maneuver types and a selected system instance, the algorithm not only automatically optimizes the motions connecting pre-defined boundary conditions, but also simultaneously optimizes the end-point boundary conditions as well. This significantly reduces the time consuming part of manually specifying all boundary value problems that should be solved, and no exhaustive search to generate feasible motions is required. In addition to handling static a priori known system parameters, the framework also allows for fast automatic re-optimization of motion primitives if the system parameters change while the system is in use, e.g, if the load significantly changes or a trailer with a new geometry is picked up by an autonomous truck. We also show in several numerical examples that the framework can enhance the performance of the motion planner in terms of total cost for the produced solution.

```
@inproceedings{diva2:1394150,
author = {Bergman, Kristoffer and Ljungqvist, Oskar and Axehill, Daniel},
title = {{Improved Optimization of Motion Primitives for Motion Planning in State Lattices}},
booktitle = {2019 30TH IEEE INTELLIGENT VEHICLES SYMPOSIUM (IV19)},
year = {2019},
series = {IEEE Intelligent Vehicles Symposium},
pages = {2307--2314},
}
```

This paper considers the problem of gathering information about features of interest in adversarial environments using mobile robots equipped with sensors. The problem is formulated as an informative path planning problem where the objective is to maximize the gathered information while minimizing the tracking performance of the adversarial observer. The optimization problem, that at first glance seems intractable to solve to global optimality, is shown to be equivalent to a mixed-integer semidefinite program that can be solved to global optimality using off-the-shelf optimization tools.

```
@inproceedings{diva2:1342204,
author = {Boström-Rost, Per and Axehill, Daniel and Hendeby, Gustaf},
title = {{Informative Path Planning in the Presence of Adversarial Observers}},
booktitle = {2019 22th International Conference on Information Fusion (FUSION)},
year = {2019},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

This paper proposes a method to generate informative trajectories for a mobile sensor that tracks agile targets.The goal is to generate a sensor trajectory that maximizes the tracking performance, captured by a measure of the covariance matrix of the target state estimate. The considered problem is acombination of estimation and control, and is often referred to as informative path planning (IPP). When using nonlinear sensors, the tracking performance depends on the actual measurements, which are naturally unavailable in the planning stage.The planning problem hence becomes a stochastic optimization problem, where the expected tracking performance is used inthe objective function. The main contribution of this work is anapproximation of the problem based on deterministic sampling of the predicted target distribution. This is in contrast to prior work, where only the most likely target trajectory is considered.It is shown that the proposed method greatly improves the ability to track agile targets, compared to a baseline approach.

```
@inproceedings{diva2:1353344,
author = {Boström-Rost, Per and Axehill, Daniel and Hendeby, Gustaf},
title = {{Informative Path Planning for Active Tracking of Agile Targets}},
booktitle = {Proceedings of 2019 IEEE Aerospace Conference},
year = {2019},
series = {IEEE AEROSPACE CONFERENCE},
pages = {1--11},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

In order to guarantee that a self-driving vehicle is behaving as expected, stability of the closed-loop system needs to be rigorously analyzed. The key components for the lowest levels of control in self-driving vehicles are the controlled vehicle, the low-level controller and the local planner.The local planner that is considered in this work constructs a feasible trajectory by combining a finite number of precomputed motions. When this local planner is considered, we show that the closed-loop system can be modeled as a nonlinear hybrid system. Based on this, we propose a novel method for analyzing the behavior of the tracking error, how to design the low-level controller and how to potentially impose constraints on the local planner, in order to guarantee that the tracking error is bounded and decays towards zero. The proposed method is applied on a truck and trailer system and the results are illustrated in two simulation examples.

```
@inproceedings{diva2:1260273,
author = {Ljungqvist, Oskar and Axehill, Daniel and Löfberg, Johan},
title = {{On stability for state-lattice trajectory tracking control}},
booktitle = {2018 Annual American Control Conference (ACC)\emph{}},
year = {2018},
series = {American Control Conference (ACC)},
pages = {5868--5875},
publisher = {IEEE},
}
```

A key requirement of autonomous vehicles is the capability to safely navigate in their environment. However, outside of controlled environments, safe navigation is a very difficult problem. In particular, the real-world often contains both complex 3D structure, and dynamic obstacles such as people or other vehicles. Dynamic obstacles are particularly challenging, as a principled solution requires planning trajectories with regard to both vehicle dynamics, and the motion of the obstacles. Additionally, the real-time requirements imposed by obstacle motion, coupled with real-world computational limitations, make classical optimality and completeness guarantees difficult to satisfy. We present a unified optimization-based motion planning and control solution, that can navigate in the presence of both static and dynamic obstacles. By combining optimal and receding-horizon control, with temporal multi-resolution lattices, we can precompute optimal motion primitives, and allow real-time planning of physically-feasible trajectories in complex environments with dynamic obstacles. We demonstrate the framework by solving difficult indoor 3D quadcopter navigation scenarios, where it is necessary to plan in time. Including waiting on, and taking detours around, the motions of other people and quadcopters.

```
@inproceedings{diva2:1256821,
author = {Andersson, Olov and Ljungqvist, Oskar and Tiger, Mattias and Axehill, Daniel and Heintz, Fredrik},
title = {{Receding-Horizon Lattice-based Motion Planning with Dynamic Obstacle Avoidance}},
booktitle = {2018 IEEE Conference on Decision and Control (CDC)},
year = {2018},
series = {Conference on Decision and Control (CDC)},
volume = {2018},
pages = {4467--4474},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

This paper presents a systematic approach for computing local solutions to motion planning problems in non-convex environments using numerical optimal control techniques. It extends the range of use of state-of-the-art numerical optimal control tools to problem classes where these tools have previously not been applicable. Today these problems are typically solved using motion planners based on randomized or graph search. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. In this work, it is shown that by combining a Sequential Quadratic Programming (SQP) method with a homotopy approach that gradually transforms the problem from a relaxed one to the original one, practically relevant locally optimal solutions to the motion planning problem can be computed. The approach is demonstrated in motion planning problems in challenging 2D and 3D environments, where the presented method significantly outperforms both a state-of-the-art numerical optimal control method and a state-of-the-art open-source optimizing sampling-based planner commonly used as benchmark.

```
@inproceedings{diva2:1249261,
author = {Bergman, Kristoffer and Axehill, Daniel},
title = {{Combining Homotopy Methods and Numerical Optimal Control to Solve Motion Planning Problems}},
booktitle = {Proceedings of the 29th IEEE Intelligent Vehicles Symposium},
year = {2018},
pages = {347--354},
publisher = {IEEE},
}
```

Motion planning for a general 2-trailer system poses a hard problem for any motion planning algorithm and previous methods have lacked any completeness or optimality guarantees. In this work we present a lattice-based motion planning framework for a general 2-trailer system that is resolution complete and resolution optimal. The solution will satisfy both differential and obstacle imposed constraints and is intended either as a part of an autonomous system or as a driver support system to automatically plan complicated maneuvers in backward and forward motion. The proposed framework relies on a precomputing step that is performed offline to generate a finite set of kinematically feasible motion primitives. These motion primitives are then used to create a regular state lattice that can be searched for a solution using standard graph-search algorithms. To make this graph-search problem tractable for real-time applications a novel parametrization of the reachable state space is proposed where each motion primitive moves the system from and to a selected set of circular equilibrium configurations. The approach is evaluated over three different scenarios and impressive real-time performance is achieved.

```
@inproceedings{diva2:1192090,
author = {Ljungqvist, Oskar and Evestedt, Niclas and Cirillo, Marcello and Axehill, Daniel and Holmer, Olov},
title = {{Lattice-based Motion Planning for a General 2-trailer system}},
booktitle = {2017 28TH IEEE INTELLIGENT VEHICLES SYMPOSIUM (IV 2017)},
year = {2017},
series = {IEEE Intelligent Vehicles Symposium},
pages = {819--824},
publisher = {IEEE},
}
```

In order to meet the requirements for autonomous systems in real world applications, reliable path following controllers have to be designed to execute planned paths despite the existence of disturbances and model errors. In this paper we propose a Linear Quadratic controller for stabilizing a 2-trailer system with possible off-axle hitching around preplanned paths in backward motion. The controller design is based on a kinematic model of a general 2-trailer system including the possibility for off-axle hitching. Closed-loop stability is proved around a set of paths, typically chosen to represent the possible output from the path planner, using theory from linear differential inclusions. Using convex optimization tools a single quadratic Lyapunov function is computed for the entire set of paths.

```
@inproceedings{diva2:1109032,
author = {Ljungqvist, Oskar and Axehill, Daniel and Helmersson, Anders},
title = {{Path following control for a reversing general 2-trailer system}},
booktitle = {2016 IEEE 55TH CONFERENCE ON DECISION AND CONTROL (CDC)},
year = {2016},
series = {IEEE Conference on Decision and Control},
pages = {2455--2461},
publisher = {IEEE},
}
```

Reversing with a dolly steered trailer configura- tion is a hard task for any driver without extensive training. In this work we present a motion planning and control framework that can be used to automatically plan and execute complicated manoeuvres. The unstable dynamics of the reversing general 2- trailer configuration with off-axle hitching is first stabilised by an LQ-controller and then a pure pursuit path tracker is used on a higher level giving a cascaded controller that can track piecewise linear reference paths. This controller together with a kinematic model of the trailer configuration is then used for forward simulations within a Closed-Loop Rapidly Exploring Random Tree framework to generate motion plans that are not only kinematically feasible but also include the limitations of the controller’s tracking performance when reversing. The approach is evaluated over a series of Monte Carlo simulations on three different scenarios and impressive success rates are achieved. Finally the approach is successfully tested on a small scale test platform where the motion plan is calculated and then sent to the platform for execution.

```
@inproceedings{diva2:1066727,
author = {Evestedt, Niclas and Ljungqvist, Oskar and Axehill, Daniel},
title = {{Motion planning for a reversing general 2-trailer configuration using Closed-Loop RRT}},
booktitle = {2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
year = {2016},
series = {Intelligent Robots and Systems},
volume = {2016},
pages = {3690--3697},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

In many traffic situations there are times where interaction with other drivers is necessary and unavoidable in order to safely progress towards an intended destination. This is especially true for merge manoeuvres into dense traffic, where drivers sometimes must be somewhat aggressive and show the intention of merging in order to interact with the other driver and make the driver open the gap needed to execute the manoeuvre safely. Many motion planning frameworks for autonomous vehicles adopt a reactive approach where simple models of other traffic participants are used and therefore need to adhere to large margins in order to behave safely. However, the large margins needed can sometimes get the system stuck in congested traffic where time gaps between vehicles are too small. In other situations, such as a highway merge, it can be significantly more dangerous to stop on the entrance ramp if the gaps are found to be too small than to make a slightly more aggressive manoeuvre and let the driver behind open the gap needed. To remedy this problem, this work uses the Intelligent Driver Model (IDM) to explicitly model the interaction of other drivers and evaluates the risk by their required deceleration in a similar manner as the Minimum Overall Breaking Induced by Lane change (MOBIL) model that has been used in large scale traffic simulations before. This allows the algorithm to evaluate the effect on other drivers depending on our own trajectory plans by simulating the nearby traffic situation. Finding a globally optimal solution is often intractable in these situations so instead a large set of candidate trajectories are generated that are evaluated against the traffic scene by forward simulations of other traffic participants. By discretization and using an efficient trajectory generator together with efficient modelling of the traffic scene real-time demands can be met.

```
@inproceedings{diva2:1066724,
author = {Evestedt, Niclas and Ward, Erik and Folkesson, John and Axehill, Daniel},
title = {{Interaction aware trajectory planning for merge scenarios in congested traffic situations}},
booktitle = {2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC)},
year = {2016},
series = {Intelligent Transportation Systems},
volume = {2016},
pages = {465--472},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

In multiparametric programming an optimization problem which is dependent on a parameter vector is solved parametrically. In control, multiparametric quadratic programming (mp-QP) problems have become increasingly important since the optimization problem arising in Model Predictive Control (MPC) can be cast as an mp-QP problem, which is referred to as explicit MPC. One of the main limitations with mp-QP and explicit MPC is the amount of memory required to store the parametric solution and the critical regions. In this paper, a method for exploiting low rank structure in the parametric solution of an mp-QP problem in order to reduce the required memory is introduced. The method is based on ideas similar to what is done to exploit low rank modifications in generic QP solvers, but is here applied to mp-QP problems to save memory. The proposed method has been evaluated experimentally, and for some examples of relevant problems the relative memory reduction is an order of magnitude compared to storing the full parametric solution and critical regions.

```
@inproceedings{diva2:1062078,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{Reduced Memory Footprint in Multiparametric Quadratic Programming by Exploiting Low Rank Structure}},
booktitle = {55th Conference on Decision and Control (CDC), 2016 IEEE},
year = {2016},
series = {IEEE Conference on Decision and Control},
pages = {3654--3661},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

In this paper a cascaded approach for stabilizationand path tracking of a general 2-trailer vehicle configurationwith an off-axle hitching is presented. A low level LinearQuadratic controller is used for stabilization of the internalangles while a pure pursuit path tracking controller is used ona higher level to handle the path tracking. Piecewise linearityis the only requirement on the control reference which makesthe design of reference paths very general. A Graphical UserInterface is designed to make it easy for a user to design controlreferences for complex manoeuvres given some representationof the surroundings. The approach is demonstrated with challengingpath following scenarios both in simulation and on asmall scale test platform.

```
@inproceedings{diva2:957204,
author = {Evestedt, Niclas and Ljungqvist, Oskar and Axehill, Daniel},
title = {{Path tracking and stabilization for a reversing general 2-trailer configuration using a cascaded control approach}},
booktitle = {Intelligent Vehicles Symposium (IV), 2016 IEEE},
year = {2016},
pages = {1156--1161},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

In Moving Horizon Estimation (MHE) the computed estimate is found by solving a constrained finite-time optimal estimation problem in real-time at each sample in a receding horizon fashion. The constrained estimation problem can be solved by, e.g., interior-point (IP) or active-set (AS) methods, where the main computational effort in both methods is known to be the computation of the search direction, i.e., the Newton step. This is often done using generic sparsity exploiting algorithms or serial Riccati recursions, but as parallel hardware is becoming more commonly available the need for parallel algorithms for computing the Newton step is increasing. In this paper a newly developed tailored, non-iterative parallel algorithm for computing the Newton step using the Riccati recursion for Model Predictive Control (MPC) is extended to MHE problems. The algorithm exploits the special structure of the Karush-Kuhn-Tucker system for the optimal estimation problem. As a result it is possible to obtain logarithmic complexity growth in the estimation horizon length, which can be used to reduce the computation time for IP and AS methods when applied to what is today considered as challenging estimation problems. Furthermore, promising numerical results have been obtained using an ANSI-C implementation of the proposed algorithm, which uses Message Passing Interface (MPI) together with InfiniBand and is executed on true parallel hardware. Beyond MHE, due to similarities in the problem structure, the algorithm can be applied to various forms of on-line and off-line smoothing problems.

```
@inproceedings{diva2:945951,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{An O(log N) Parallel Algorithm for Newton Step Computations with Applications to Moving Horizon Estimation}},
booktitle = {Proceedings of the 2016 European Control Conference},
year = {2016},
pages = {1630--1636},
}
```

In this paper an extension to the sampling based motion planning framework CL-RRT is presented. The framework uses a system model and a stabilizing controller to sample the perceived environment and build a tree of possible trajectories that are evaluated for execution. Complex system models and constraints are easily handled by a forward simulation making the framework widely applicable. To increase operational safety we propose a sampling recovery scheme that performs a deterministic brake profile regeneration using collision information from the forward simulation. This greatly increases the number of safe trajectories and also reduces the number of samples that produce infeasible results. We apply the framework to a Scania G480 mining truck and evaluate the algorithm in a simple yet challenging obstacle course and show that our approach greatly increases the number of feasible paths available for execution.

```
@inproceedings{diva2:849916,
author = {Evestedt, Niclas and Axehill, Daniel and Trincavelli, Marco and Gustafsson, Fredrik},
title = {{Sampling Recovery for Closed Loop Rapidly Expanding Random Tree using Brake Profile Regeneration}},
booktitle = {Intelligent Vehicles Symposium (IV), 2015 IEEE},
year = {2015},
series = {IEEE Intelligent Vehicles Symposium},
pages = {101--106},
publisher = {IEEE},
}
```

The extended Kalman filter (EKF) has been animportant tool for state estimation of nonlinear systems sinceits introduction. However, the EKF does not possess the same optimality properties as the Kalman filter, and may perform poorly. By viewing the EKF as an optimization problem it is possible to, in many cases, improve its performance and robustness. The paper derives three variations of the EKF by applying different optimisation algorithms to the EKF costfunction and relate these to the iterated EKF. The derived filters are evaluated in two simulation studies which exemplify the presented filters.

```
@inproceedings{diva2:844060,
author = {Skoglund, Martin and Hendeby, Gustaf and Axehill, Daniel},
title = {{Extended Kalman Filter Modifications Based on an Optimization View Point}},
booktitle = {18th International Conference of Information Fusion},
year = {2015},
publisher = {Institute of Electrical and Electronics Engineers (IEEE)},
}
```

```
@inproceedings{diva2:722121,
author = {Axelsson, Patrik and Axehill, Daniel and Glad, Torkel and Norrlöf, Mikael},
title = {{Iterative Learning Control - From a Controllability Point of View}},
booktitle = {Proceedings of Reglermöte 2014},
year = {2014},
}
```

In optimization algorithms used for on-line Model Predictive Control (MPC), the main computational effort is spent while solving linear systems of equations to obtain search directions. Hence, it is of greatest interest to solve them efficiently, which commonly is performed using Riccati recursions or generic sparsity exploiting algorithms. The focus in this work is efficient search direction computation for active-set methods. In these methods, the system of equations to be solved in each iteration is only changed by a low-rank modification of the previous one. This highly structured change of the system of equations from one iteration to the next one is an important ingredient in the performance of active-set solvers. It seems very appealing to try to make a structured update of the Riccati factorization, which has not been presented in the literature so far. The main objective of this paper is to present such an algorithm for how to update the Riccati factorization in a structured way in an active-set solver. The result of the work is that the computational complexity of the step direction computation can be significantly reduced for problems with bound constraints on the control signal. This in turn has important implications for the computational performance of active-set solvers used for linear, nonlinear as well as hybrid MPC.

```
@inproceedings{diva2:689259,
author = {Nielsen, Isak and Ankelhed, Daniel and Axehill, Daniel},
title = {{Low-rank Modifications of Riccati Factorizations with Applications to Model Predictive Control}},
booktitle = {Proceedings of 52nd IEEE Conference on Decision and Control},
year = {2013},
pages = {3684--3690},
publisher = {IEEE conference proceedings},
}
```

In this chapter parallel implementations of hybrid MPC will be discussed. Different methods for achieving parallelism at different levels of the algorithms will be surveyed. It will be seen that there are many possible ways of obtaining parallelism for hybrid MPC, and it is by no means clear which possibilities that should be utilized to achieve the best possible performance. To answer this question is a challenge for future research.

```
@inproceedings{diva2:475600,
author = {Axehill, Daniel and Hansson, Anders},
title = {{Towards Parallel Implementation of Hybrid MPC:
A Survey and Directions for Future Research}},
booktitle = {Distributed decision making and control},
year = {2012},
series = {Lecture Notes in Control and Information Sciences},
volume = {417},
pages = {313--338},
publisher = {Springer London},
}
```

The paper deals with the problem of active fault detection and control for multiple models. It is assumed that a fault detector is given and the goal is to design an input signal generator such that detection and control aims are achieved. Since these two aim are conflicting, it is necessary to express a desired compromise between them. The paper investigates three formulations that allow for respecting both competing aims. In the first formulation both aims are combined into a single criterion. In other two formulations, one aim is reflected in the criterion and the other aim is enforced as a constraint.

```
@inproceedings{diva2:475612,
author = {Siroky, Jan and Simandl, Miroslav and Axehill, Daniel and Puncochar, Ivo},
title = {{An Optimization Approach to Resolve the Competing Aims of Active Fault Detection and Control}},
booktitle = {Proceedings of the 50th IEEE Conference on Decision and Control},
year = {2011},
pages = {3712--3717},
}
```

In this paper we describe a procedure for computation of optimal and suboptimal explicit MPC controllers for hybrid systems. This procedure is based on a parametric branch and bound approach, which allows the user to specify a state-dependent suboptimality tolerance. Depending on the choice of the tolerance, an optimal solution can be sought for, a merely feasible solution can be sought for, a certain suboptimality can be enforced, or a priori stability guarantees can be given. Moreover, the proposed procedure does not require that the computation of the optimal solution is tractable.

```
@inproceedings{diva2:475606,
author = {Axehill, Daniel and Besselmann, Thomas and Raimondo, Davide and Morari, Manfred},
title = {{Suboptimal Explicit Hybrid MPC via Branch and Bound}},
booktitle = {Proceedings of the 18th IFAC World Congress},
year = {2011},
pages = {10281--10286},
}
```

In this work, the computational effort of Mixed Integer Quadratic Programming solvers based on branch and bound is studied. The origin of this interest is that hybrid MPC problems for Mixed Logical Dynamical systems can be formulated as optimization problems in this form and since these have to be solved in real-time, it is interesting to be able to compute a good bound on the computational complexity. Classically, the bound on the worst case computational complexity is given by the case when it is necessary to expand all nodes in the entire tree. The usefulness of branch and bound relies on the fact that this worst case scenario is very rare in practice. The objective in this work is to reduce the gap between the conservative worst case bound on the number of nodes and the number of nodes actually necessary to explore on-line in the optimization routine. Approaches to compute this bound are presented and motivated theoretically and the performance of the analysis is evaluated in numerical examples.

```
@inproceedings{diva2:937540,
author = {Axehill, Daniel and Morari, Manfred},
title = {{Improved complexity analysis of branch and bound for hybrid MPC}},
booktitle = {Proceedings of the 49th IEEE Conference on Decision and Control (CDC)},
year = {2010},
pages = {4216--4222},
}
```

This paper deals with efficient point location in large polytopic data sets, as required for the implementation of Explicit Model Predictive Control laws. The focus is on linear decision functions (LDF) which performs scalar product evaluations and an interval search to return the index set of candidate polytopes possibly containing the query point. We generalize a special LDF which uses the euclidean directions of the state space and the projection of the polytopes bounding boxes onto these directions to identify the candidate polytopes. Our generalized LDF may use any vector of the state space as direction and the projection of any points contained in the polytopes. We prove that there is a finite number of LDFs returning different index sets and show how to find the one returning the lowest worst-case number of candidate polytopes, a number that can be seen as a performance measure. Based on the results from an exhaustive study of low complexity problems, heuristics for the choice of the LDF are derived, involving the mean shift algorithm from pattern recognition. The result of extensive simulations on a larger problem attest the generalized LDF a 40% gain in performance, mainly through adjusted directions, at a small additional storage cost.

```
@inproceedings{diva2:937526,
author = {Fuchs, Alexander and Axehill, Daniel and Morari, Manfred},
title = {{On the choice of the linear decision functions for point location in polytopic data sets - Application to Explicit MPC}},
booktitle = {Proceedings of the 49th IEEE Conference on Decision and Control (CDC)},
year = {2010},
pages = {5283--5288},
}
```

The existence of market power is a serious concern in modern electric energy markets. Systems and processes that monitor the trading is needed and much research and many proposals on how to deal with the problem have been introduced over the past couple of years. A challenge to all such methods is execution speed, since the identification of market power needs to be done in real-time as market prices are settled. To overcome this challenge the methods need to be simple, involving limited computational effort. This paper presents a simple method with the potential of overcoming the challenge of execution speed. The method is based on the idea of determining the participants with the ability to make considerable increases in price raises without losing all market shares. Such determination can be made in advance during day ahead trading to identify critical areas. During realtime settlement, the method can then be used in a second iteration to study the identified critical areas. In the paper we propose a way to calculate the remaining market shares after a large price raise and refer to these as Monopolistic Energy Levels. These calculated levels of energy, that are deliverable by a single certain participant or by a certain group of participants, are caused by the active congestions in the network. The method detects the quantity of these energy levels and their respective locations in the network. This is a prospective method when used with a prediction of the following days demand. The paper presents the background and development of the proposed method. The use of AC and DC power flow as means to determine the monopolistic energy levels are analyzed and discussed. The paper is concluded with examples of application of the method to a simple multi area power system.

```
@inproceedings{diva2:709592,
author = {Elfstadius, Martin and Gecer, Daniel and Nordström, Lars and Axehill, Daniel},
title = {{Method to detect and measure potential market power on electricity markets using the concept of monopolistic energy}},
booktitle = {Proceedings of the Power Systems Conference and Exposition, 2009},
year = {2009},
pages = {1--7},
publisher = {IEEE},
}
```

The objective of this work is to derive a QPalgorithm tailored for MPC. More speciﬁc, the primary targetapplication is MPC for discrete-time hybrid systems. A desiredproperty of the algorithm is that warm starts should be possibleto perform efﬁciently. This property is very important for online linear MPC, and it is crucial in branch and bound forhybrid MPC. In this paper, a dual active set-like QP methodwas chosen because of its warm start properties. A drawbackwith classical active set methods is that they often requiremany iterations in order to ﬁnd the active set in optimum.Gradient projection methods are methods known to be ableto identify this active set very fast and such a method wastherefore chosen in this work. The gradient projection methodwas applied to the dual QP problem and it was tailored for theMPC application. Results from numerical experiments indicatethat the performance of the new algorithm is very good, bothfor linear MPC as well as for hybrid MPC. It is also noticed thatthe number of QP iterations is significantly reduced compared to classical active set methods.

```
@inproceedings{diva2:606915,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Model Predictive Control}},
booktitle = {Proceedings of Reglermöte 2008},
year = {2008},
pages = {202--209},
}
```

The objective of this work is to derive a QP algorithm tailored for MPC. More specifically, the primary target application is MPC for discrete-time hybrid systems. A desired property of the algorithm is that warm starts should be possible to perform efficiently. This property is very important for on-line linear MPC, and it is crucial in branch and bound for hybrid MPC. In this paper, a dual active set-like QP method was chosen because of its warm start properties. A drawback with classical active set methods is that they often require many iterations in order to find the active set in optimum. Gradient projection methods are methods known to be able to identify this active set very fast and such a method was therefore chosen in this work. The gradient projection method was applied to the dual QP problem and it was tailored for the MPC application. Results from numerical experiments indicate that the performance of the new algorithm is very good, both for linear MPC as well as for hybrid MPC. It is also noticed that the number of QP iterations is significantly reduced compared to classical active set methods.

```
@inproceedings{diva2:265198,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Model Predictive Control}},
booktitle = {Proceedings of the 47th IEEE Conference on Decision and Control},
year = {2008},
pages = {3057--3064},
}
```

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.

```
@inproceedings{diva2:17357,
author = {Axehill, Daniel and Hansson, Anders and Vandenberghe, Lieven},
title = {{Relaxations Applicable to Mixed Integer Predictive Control -- Comparisons and Efficient Computations}},
booktitle = {Proceedings of the 46th IEEE Conference on Decision and Control},
year = {2007},
pages = {4103--4109},
}
```

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.

```
@inproceedings{diva2:17356,
author = {Axehill, Daniel and Vandenberghe, Lieven and Hansson, Anders},
title = {{On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals}},
booktitle = {Proceedings of the 7th IFAC Symposium on Nonlinear Control Systems},
year = {2007},
series = {LiTH-ISY-R},
volume = {2771},
pages = {585--590},
publisher = {Curran Associates, Inc.},
}
```

The objective with 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.

```
@inproceedings{diva2:257820,
author = {Axehill, Daniel and Hansson, Anders},
title = {{Mixed Integer Predictive Control Using a Tailored Mixed Integer Dual Quadratic Programming Algorithm}},
booktitle = {Proceedings of Reglermöte 2006},
year = {2006},
}
```

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.

```
@inproceedings{diva2:17354,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC}},
booktitle = {Proceedings of the 45th IEEE Conference on Decision and Control},
year = {2006},
pages = {5693--5698},
}
```

In this paper a preprocessing algorithm for binary quadratic programming problems is presented. For some types of binary quadratic programming problems, the algorithm can compute the optimal value for some or all integer variables without approximations in polynomial time. When the optimal multiuser detection problem is formulated as a maximum likelihood problem, a binary quadratic programming problem has to be solved. Fortunately, the low correlation between different users in the multiuser detection problem enables the use of the preprocessing algorithm. Simulations show that the preprocessing algorithm is able to compute almost all variables in the problem, even though the system is heavily loaded and affected by noise.

```
@inproceedings{diva2:252416,
author = {Axehill, Daniel and Gunnarsson, Fredrik and Hansson, Anders},
title = {{A Preprocessing Algorithm Applicable to the Multiuser Detection Problem}},
booktitle = {Proceedings of Radiovetenskap och Kommunikation 2005},
year = {2005},
}
```

An Adaptive Cruise Controller (ACC) is an extension of an ordinary cruise controller. In addition to maintaining a desired set speed, an ACC can also maintain a desired time gap to the vehicle ahead. For this end, both the engine and the brakes are controlled. The interest in the MPC-controller as a solution to the problem was to achieve automatic actuator switching, thus with no explicitly defined switch points. The MPC-controller is based on a model of the system including bounds on the control signals and on linear combinations of the states. Using this knowledge, the MPC-controller will choose the correct actuator for the current driving situation. Among the drawbacks, it can be mentioned that the variant of MPC, used in this paper, is too complex to implement in the control system currently used in trucks.

```
@inproceedings{diva2:244542,
author = {Axehill, Daniel and Sjöberg, Johan and Lindqvist, Kristian},
title = {{Adaptive Cruise Control for Heavy Vehicles}},
booktitle = {Proceedings of Reglermöte 2004},
year = {2004},
}
```

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 result is 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.

```
@inproceedings{diva2:242861,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Preprocessing Algorithm for MIQP Solvers with Applications to MPC}},
booktitle = {Proceeding of Reglermöte 2004},
year = {2004},
}
```

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.

```
@inproceedings{diva2:17352,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Preprocessing Algorithm for MIQP Solvers with Applications to MPC}},
booktitle = {Proceedings of the 43rd IEEE Conference on Decision and Control},
year = {2004},
pages = {2497--2502},
}
```

## Theses

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.

```
@phdthesis{diva2:17358,
author = {Axehill, Daniel},
title = {{Integer Quadratic Programming for Control and Communication}},
school = {Linköping University},
type = {{Linköping Studies in Science and Technology. Dissertations No. 1158}},
year = {2008},
address = {Sweden},
}
```

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.

```
@phdthesis{diva2:21239,
author = {Axehill, Daniel},
title = {{Applications of Integer Quadratic Programming in Control and Communication}},
school = {Linköping University},
type = {{Linköping Studies in Science and Technology. Thesis No. 1218}},
year = {2005},
address = {Sweden},
}
```

## Reports

Model Predictive Control (MPC) is increasing in popularity in industry as more efficient algorithms for solving the related optimization problem are developed. The main computational bottle-neck in on-line MPC is often the computation of the search step direction, \ie the Newton step, which is often done using generic sparsity exploiting algorithms or Riccati recursions. However, as parallel hardware is becoming increasingly popular the demand for efficient parallel algorithms for solving the Newton step is increasing. In this paper a tailored, non-iterative parallel algorithm for computing the Riccati factorization is presented. The algorithm exploits the special structure in the MPC problem, and when sufficiently many processing units are available, the complexity of the algorithm scales logarithmically in the prediction horizon. Computing the Newton step is the main computational bottle-neck in many MPC algorithms and the algorithm can significantly reduce the computation cost for popular state-of-the-art MPC algorithms.

```
@techreport{diva2:749137,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{A Parallel Riccati Factorization Algorithm with Applications to Model Predictive Control}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2014},
type = {Other academic},
number = {LiTH-ISY-R, 3078},
address = {Sweden},
}
```

*O*(log

*N*) Parallel Algorithm for Newton Step Computation in Model Predictive Control", LiTH-ISY-R, No. 3073, 2014.

The use of Model Predictive Control in industry is steadily increasing as more complicated problems can be addressed. Due to that online optimization is usually performed, the main bottleneck with Model Predictive Control is the relatively high computational complexity. Hence, a lot of research has been performed to find efficient algorithms that solve the optimization problem. As parallelism is becoming more commonly used in hardware, the demand for efficient parallel solvers for Model Predictive Control has increased. In this paper, a tailored parallel algorithm that can adopt different levels of parallelism for solving the Newton step is presented. With sufficiently many processing units, it is capable of reducing the computational growth to logarithmic growth in the prediction horizon. Since the Newton step computation is where most computational effort is spent in both interior-point and active-set solvers, this new algorithm can significantly reduce the computational complexity of highly relevant solvers for Model Predictive Control.

```
@techreport{diva2:707876,
author = {Nielsen, Isak and Axehill, Daniel},
title = {{An \emph{O}(log \emph{N}) Parallel Algorithm for Newton Step Computation in Model Predictive Control}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2014},
type = {Refereed},
number = {LiTH-ISY-R, 3073},
address = {Sweden},
}
```

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.

```
@techreport{diva2:316942,
author = {Axehill, Daniel and Hansson, Anders and Gunnarsson, Fredrik},
title = {{A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2008},
type = {Other academic},
number = {LiTH-ISY-R, 2840},
address = {Sweden},
}
```

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.

```
@techreport{diva2:316943,
author = {Axehill, Daniel and Hansson, Anders and Vandenberghe, Lieven},
title = {{Relaxations Applicable to Mixed Integer Predictive Control - Comparisons and Efficient Computations}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2008},
type = {Other academic},
number = {LiTH-ISY-R, 2839},
address = {Sweden},
}
```

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.

```
@techreport{diva2:316941,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Mixed Integer Predictive Control}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2008},
type = {Other academic},
number = {LiTH-ISY-R, 2833},
address = {Sweden},
}
```

```
@techreport{diva2:316960,
author = {Axehill, Daniel},
title = {{Att handleda en uppgift utan facit}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2007},
type = {Other academic},
number = {LiTH-ISY-R, 2817},
address = {Sweden},
}
```

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.

```
@techreport{diva2:316819,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2007},
type = {Other academic},
number = {LiTH-ISY-R, 2761},
address = {Sweden},
}
```

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 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 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 much less computationally demanding compared to the standard SDP relaxation. Furthermore, for a special case, it is shown that the equality constrained SDP relaxation can be cast in the form of a QP. This makes it possible to replace the ordinary QP relaxation usually used in branch and bound for these problems witha tighter SDP relaxation. Numerical experiments indicate that this relaxation can decrease the overall computational time spent in branch and bound.

```
@techreport{diva2:316510,
author = {Axehill, Daniel and Vandenberghe, Lieven and Hansson, Anders},
title = {{On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2007},
type = {Other academic},
number = {LiTH-ISY-R, 2771},
address = {Sweden},
}
```

In this paper a preprocessing algorithm for binary quadratic programming problems is presented. For some types of binary quadratic programming problems, the algorithm can compute the optimal value for some or all integer variables without approximations in polynomial time. When the optimal multiuser detection problem is formulated as a maximum likelihood problem, a binary quadratic programming problem has to be solved. Fortunately, the low correlation between different users in the multiuser detection problem enables the use of the preprocessing algorithm. Simulations show that the preprocessing algorithm is able to compute almost all variables in the problem, even though the system is heavily loaded and affected by noise.

```
@techreport{diva2:316895,
author = {Axehill, Daniel and Gunnarsson, Fredrik and Hansson, Anders},
title = {{A Preprocessing Algorithm Applicable to the Multiuser Detection Problem}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2005},
type = {Other academic},
number = {LiTH-ISY-R, 2716},
address = {Sweden},
}
```

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 result is 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.

```
@techreport{diva2:316748,
author = {Axehill, Daniel and Hansson, Anders},
title = {{A Preprocessing Algorithm for MIQP solvers with Applications to MPC}},
institution = {Linköping University, Department of Electrical Engineering},
year = {2004},
type = {Other academic},
number = {LiTH-ISY-R, 2607},
address = {Sweden},
}
```

## Associate Professor in Automatic Control

**Phone:**- +46 13 28 40 42

**Mobile (private):**- +46 708 78 36 70

**E-mail:**- daniel.axehill@liu.se

**Address:**- Dept. of Electrical Engineering
- Linköping University
- SE-581 83 Linköping
- Sweden

**Visiting Address:**- Campus Valla
- Building B
- Room 2A:479 (in the A corridor on the ground floor between entrance 27 and 29)

Page responsible: Daniel Axehill

Last updated: 2012-10-25