| 1. |
- Andersen, Martin S., et al.
(författare)
-
Reduced-Complexity Semidefinite Relaxations of Optimal Power Flow Problems
- 2014
-
Ingår i: IEEE Transactions on Power Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 0885-8950 .- 1558-0679. ; 29:4, s. 1855-1863
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a new method for generating semidefinite relaxations of optimal power flow problems. The method is based on chordal conversion techniques: by dropping some equality constraints in the conversion, we obtain semidefinite relaxations that are computationally cheaper, but potentially weaker, than the standard semidefinite relaxation. Our numerical results show that the new relaxations often produce the same results as the standard semidefinite relaxation, but at a lower computational cost.
|
|
| 2. |
- Annergren, Mariette, 1982-
(författare)
-
Application-Oriented Input Design and Optimization Methods Involving ADMM
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis is divided into two main parts. The first part considers application-oriented input design, specifically for model predictive control (MPC). The second part considers alternating direction method of multipliers (ADMM) for ℓ1 regularized optimization problems and primal-dual interior-point methods.The theory of system identification provides methods for estimating models of dynamical systems from experimental data. This thesis is focused on identifying models used for control, with special attention to MPC. The objective is to minimize the cost of the identification experiment while guaranteeing, with high probability, that the obtained model gives an acceptable control performance. We use application-oriented input design to find such a model. We present a general procedure of implementing application-oriented input design to unknown, possibly nonlinear, systems controlled using MPC. The practical aspects of application-oriented input design are addressed and the method is tested in an experimental study.In addition, a MATLAB-based toolbox for solving application-oriented input design problems is presented. The purpose of the toolbox is threefold: it is used in research; it facilitates communication of research results; it helps an engineer to use application-oriented input design.Several important problems in science can be formulated as convex optimization problems. As such, there exist very efficient algorithms for finding the solutions. We are interested in methods that can handle optimization problems with a very large number of variables. ADMM is a method capable of handling such problems. We derive a scalable and efficient algorithm based on ADMM for two ℓ1 regularized optimization problems: ℓ1 mean and covariance filtering, and ℓ1 regularized MPC. The former occurs in signal processing and the latter is a specific type of model based control.We are also interested in optimization problems with certain structural limitations. These limitations inhibit the use of a central computational unit to solve the problems. We derive a distributed method for solving them instead. The method is a primal-dual interior-point method that uses ADMM to distribute all the calculations necessary to solve the optimization problem at hand.
|
|
| 3. |
- Axehill, Daniel, et al.
(författare)
-
Convex Relaxations for Mixed Integer Predictive Control
- 2010
-
Ingår i: Automatica. - : Elsevier. - 0005-1098 .- 1873-2836. ; 46:9, s. 1540-1545
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
- Axehill, Daniel, et al.
(författare)
-
On Relaxations Applicable to Model Predictive Control for Systems with Binary Control Signals
- 2007
-
Ingår i: Proceedings of the 7th IFAC Symposium on Nonlinear Control Systems. - : Curran Associates, Inc.. - 9783902661289 ; , s. 585-590
-
Konferensbidrag (refereegranskat)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 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- Axehill, Daniel, et al.
(författare)
-
Relaxations Applicable to Mixed Integer Predictive Control – Comparisons and Efficient Computations
- 2007
-
Ingår i: Proceedings of the 46th IEEE Conference on Decision and Control. - 9781424414970 - 9781424414987 ; , s. 4103-4109
-
Konferensbidrag (refereegranskat)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.
|
|
| 8. |
- Hansson, Anders, et al.
(författare)
-
A Primal-Dual Potential Reduction Method for Integral Quadratic Constraints
- 2001
-
Ingår i: Proceedings of the 2001 American Control Conference. - : IEEE. - 0780364953 ; , s. 3013-3018
-
Konferensbidrag (refereegranskat)abstract
- We discuss how to implement an efficient interior-point algorithm for semi-definite programs that result from integral quadratic constraints. The algorithm is a primal-dual potential reduction method, and the computational effort is dominated by a least-squares system that has to be solved in each iteration. The key to an efficient implementation is to utilize iterative methods and the specific structure of integral quadratic constraints. The algorithm has been implemented in Matlab. To give a rough idea of the efficiencies obtained, it is possible to solve problems resulting in a linear matrix inequality of dimension 130 × 130 with approximately 5000 variables in about 5 minutes on a lap-top. Problems with approximately 20000 variable and a linear matrix inequality of dimension 230 × 230 are solved in about 45 minutes. It is not assumed that the system matrix has no eigenvalues on the imaginary axis, nor is it assumed that it is Hurwitz.
|
|
| 9. |
- Hansson, Anders, et al.
(författare)
-
Comparison of Two Structure-Exploiting Optimization Algorithms for Integral Quadratic Constraints
- 2003
-
Ingår i: Proceedings of the 4th IFAC symposium on Robust Control Design. - Linköping : Linköping University Electronic Press. - 9780080440125
-
Konferensbidrag (refereegranskat)abstract
- As the semidefinite programs that result from integral quadratic contstraints are usually large it is important to implement efficient algorithms. The interior-point algorithms in this paper are primal-dual potential reduction methods and handle multiple constraints. Two approaches are made. For the first approach the computational cost is dominated by a least-squares problem that has to be solved in each iteration. The least squares problem is solved using an iterative method, namely the conjugate gradient method. The computational effort for the second approach is dominated by forming a linear system of equations. This systems of equations is used to compute the search direction in each iteration. If the number of variables are reduced by solving a smaller subproblem the resulting system has a very nice structure and can be solved efficiently. The first approach is more efficient for larger problems but is not as numerically stable.
|
|
| 10. |
- Hansson, Anders, et al.
(författare)
-
Sampling method for semidefinite programmes with non-negative Popov function constraints
- 2014
-
Ingår i: International Journal of Control. - : Taylor and Francis: STM, Behavioural Science and Public Health Titles. - 0020-7179 .- 1366-5820. ; 87:2, s. 330-345
-
Tidskriftsartikel (refereegranskat)abstract
- An important class of optimisation problems in control and signal processing involves the constraint that a Popov function is non-negative on the unit circle or the imaginary axis. Such a constraint is convex in the coefficients of the Popov function. It can be converted to a finite-dimensional linear matrix inequality via the Kalman-Yakubovich-Popov lemma. However, the linear matrix inequality reformulation requires an auxiliary matrix variable and often results in a very large semidefinite programming problem. Several recently published methods exploit problem structure in these semidefinite programmes to alleviate the computational cost associated with the large matrix variable. These algorithms are capable of solving much larger problems than general-purpose semidefinite programming packages. In this paper, we address the same problem by presenting an alternative to the linear matrix inequality formulation of the non-negative Popov function constraint. We sample the constraint to obtain an equivalent set of inequalities of low dimension, thus avoiding the large matrix variable in the linear matrix inequality formulation. Moreover, the resulting semidefinite programme has constraints with low-rank structure, which allows the problems to be solved efficiently by existing semidefinite programming packages. The sampling formulation is obtained by first expressing the Popov function inequality as a sum-of-squares condition imposed on a polynomial matrix and then converting the constraint into an equivalent finite set of interpolation constraints. A complexity analysis and numerical examples are provided to demonstrate the performance improvement over existing techniques.
|
|
