Linköping studies in science and technology. Thesis. No. 1367
A Structure Utilizing Inexact Primal-Dual Interior-Point Method for Analysis of Linear Differential Inclusions Janne Harju Johansson
LERTEKNIK REG
AU T
O MA RO TI C C O N T
L
LINKÖPING
Division of Automatic Control Department of Electrical Engineering Linköping University, SE-581 83 Linköping, Sweden http://www.control.isy.liu.se
[email protected] Linköping 2008
This is a Swedish Licentiate’s Thesis. Swedish postgraduate education leads to a Doctor’s degree and/or a Licentiate’s degree. A Doctor’s Degree comprises 240 ECTS credits (4 years of full-time studies). A Licentiate’s degree comprises 120 ECTS credits, of which at least 60 ECTS credits constitute a Licentiate’s thesis.
Linköping studies in science and technology. Thesis. No. 1367 A Structure Utilizing Inexact Primal-Dual Interior-Point Method for Analysis of Linear Differential Inclusions
Janne Harju Johansson
[email protected] www.control.isy.liu.se Department of Electrical Engineering Linköping University SE-581 83 Linköping Sweden ISBN 978-91-7393-871-6
ISSN 0280-7971
LiU-TEK-LIC-2008:25
c 2008 Janne Harju Johansson Copyright Printed by LiU-Tryck, Linköping, Sweden 2008
To Elin & “Sprattel”!
Abstract The ability to analyze system properties for large scale systems is an important part of modern engineering. Although computer power increases constantly, there is still need to develop tailored methods that are able to handle large scale systems, since sometimes standard methods cannot handle the large scale problems that occur. In this thesis the focus is on system analysis, in particular analysis methods that result in optimization problems with a specific problem structure. In order to solve these optimization problems, primal-dual interior-point methods have been tailored to the specific structure. A convergence proof for the suggested algorithm is also presented. It is the structure utilization and the use of an iterative solver for the search directions that enables the algorithm to be applied to optimization problems with a large number of variables. However, the use of an iterative solver to find the search directions will give infeasible iterates in the optimization algorithm. This make the use of an infeasible method desirable and hence is such a method proposed. Using an iterative solver requires a good preconditioner. In this work two different preconditioners are used for different stages of the algorithm. The first preconditioner is used in the initial stage, while the second preconditioner is applied when the iterates of the algorithm are close to the boundary of the feasible set. The proposed algorithm is evaluated in a simulation study. It is shown that problems which are unsolvable for a standard solver are solved by the proposed algorithm.
v
Acknowledgments My deepest gratitude goes to Prof. Anders Hansson. Without his insightful comments, questions and guidance, my research would not have been the same. An important person for us all at the Automatic Control group is Prof. Lennart Ljung. His positive mindset towards research and teaching is always a source of inspiration. A person that perhaps does not work with control research, but is in total control and have a major impact on our daily work is Ulla Salaneck, always with a smile on her face. In order to include everybody that have helped me, I would like to thank the entire staff at the Automatic Control group. It is always great fun to discuss important and sometimes not so impor