| 1. |
|
|
| 2. |
- Ankelhed, Daniel, et al.
(författare)
-
Suboptimal Model Reduction using LMIs with Convex Constraints
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- An approach to model reduction of LTI systems using Linear Matrix Inequalities (LMIs) in an H-infinity framework is presented, where non-convex constraints are replaced with stricter convex constraints thus making it suboptimal. The presented algorithms are compared with the Optimal Hankel reduction algorithm, and are shown to achieve better results (i.elower H-infinity errors) in cases where some of the Hankel singular values are close, but not equal to each other.
|
|
| 3. |
- Axehill, Daniel, et al.
(författare)
-
A Dual Gradient Projection Quadratic Programming Algorithm Tailored for Mixed Integer Predictive Control
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 4. |
- Axehill, Daniel, et al.
(författare)
-
A Low-Complexity High-Performance Preprocessing Algorithm for Multiuser Detection using Gold Sequences
- 2008
-
Ingår i: IEEE Transactions on Signal Processing. - Linköping : IEEE Signal Processing Society. - 1053-587X .- 1941-0476. ; 56:9, s. 4377-4385
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 5. |
- Axehill, Daniel, et al.
(författare)
-
A Mixed Integer Dual Quadratic Programming Algorithm Tailored for MPC
- 2007
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 6. |
- Axehill, Daniel, et al.
(författare)
-
A Preprocessing Algorithm Applicable to the Multiuser Detection Problem
- 2005
-
Ingår i: Proceedings of Radiovetenskap och Kommunikation 2005. - Linköping : Linköping University Electronic Press.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 7. |
- Axehill, Daniel, et al.
(författare)
-
A Preprocessing Algorithm for MIQP Solvers with Applications to MPC
- 2004
-
Ingår i: Proceeding of Reglermöte 2004. - Linköping : Linköping University Electronic Press. ; , s. 2497-2502
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 8. |
- Axehill, Daniel, et al.
(författare)
-
On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
- 2007
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 9. |
- Axehill, Daniel, et al.
(författare)
-
Relaxations Applicable to Mixed Integer Predictive Control - Comparisons and Efficient Computations
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 10. |
- Enqvist, Martin, 1976-, et al.
(författare)
-
The CDIO Initiative from an Automatic Control Project Course Perspective
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The CDIO (Conceive Design Implement Operate) Initiative is explained, and some of the results at the Applied Physics and Electrical Engineering program at Linköping University, Sweden, are presented. A project course in Automatic Control is used as an example. The projects within the course are carried out using the LIPS (Linköping interactive project steering) model. An example of a project, the golf playing industrial robot, and the results from this project are also covered.
|
|
