liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Structure Exploitation in Semidefinite Programming for Control
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
2010 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Many control problems can be cast as semidefinite programs. However, since the size of these problems grow quite quickly, the computational time to solve them can be quite substantial. In order to reduce the computational time, many proposals of how to tailormake algorithms to various types of control problems can be found in the literature. In this thesis, two papers with similar ambitions are presented.

The first paper deals with the case where the constraints of the optimization problem are of the type that stems from the Kalman-Yakubovic-Popov lemma, and where some of these constraints are so called complicating constraints. This means the optimization problem will be greatly simplified if these constraints were not present. By the use of Lagrangian relaxation, the optimization problem is decomposed into smaller ones, which can be solved independently of each other. Computational results show that for some classes of problems, this algorithm can reduce the computational time compared to using a solver which does not take into account the nature of the complicating constraints.

In the second paper, the fact that many control-related semidefinite programs have matrix-valued variables is utilized to speed up computations. This implies that the corresponding basis matrices have a certain low-rank structure which can be exploited when formulating the equations for the search directions, something that was discovered in the 90s and is implemented in LMI Lab. However, much has happened in the area of semidefinite programming since the release of LMI Lab, and new, faster algorithms have been developed. However, the idea of using the lowrank structure in the basis matrices can still be used. We implement this, using the publicly available solver SDPT3 in combination with our code for formulating the system of equations for the search directions. In order to facilitate for potential users, we also describe how the modeling language YALMIP is changed so that this lowrank structure can be tracked, and how the code can be easily interfaced. Computational results show that the computational time is decreased.

Place, publisher, year, edition, pages
Linköping: Linköping University , 2010. , 58 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1430
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-98178Local ID: LiU-TEK-LIC-2010:1ISBN: 978-91-7393-441-1 (print)OAI: oai:DiVA.org:liu-98178DiVA: diva2:652429
Supervisors
Available from: 2013-10-09 Created: 2013-09-30 Last updated: 2013-10-09Bibliographically approved
List of papers
1. A Decomposition Algorithm for KYP-SDPs
Open this publication in new window or tab >>A Decomposition Algorithm for KYP-SDPs
2009 (English)In: Proceedings of the 10th European Control Conference (ECC), 2009, 3202-3207 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, a structure exploiting algorithm for semidefinite programs derived from the Kalman-Yakubovich-Popov lemma, where some of the constraints appear as complicating constraints is presented. A decomposition algorithm is proposed, where the structure of the problem can be utilized. In a numerical example, where a controller that minimizes the sum of the H2-norm and the H-norm is designed, the algorithm is shown to be faster than SeDuMi and the special purpose solver KYPD.

Keyword
Optimization, Optimization Algorithms
National Category
Computational Mathematics Engineering and Technology Control Engineering
Identifiers
urn:nbn:se:liu:diva-21937 (URN)10.3166/EJC.18.249-256 (DOI)
Conference
10th European Control Conference (ECC), Budapest, Hungary, August, 2009
Available from: 2009-10-07 Created: 2009-10-06 Last updated: 2013-10-09
2. Low-Rank Exploitation in Semidefinite Programming for Control
Open this publication in new window or tab >>Low-Rank Exploitation in Semidefinite Programming for Control
2010 (English)Report (Other academic)
Abstract [en]

Many control related problems can be cast as semidefinite programs but, even though there exist polynomial time algorithms and good publicly available solvers, the time it takes to solve these problems can be long. Something many of these problems have in common, is that some of the variables enter as matrix valued variables. This leads to a low-rank structure in the basis matrices which can be exploited when forming the Newton equations. In this paper, we describe how this can be done, and show how our code can be used when using SDPT3. The idea behind this is old and is implemented in LMI Lab, but we show that when using a modern algorithm, the computational time can be reduced. Finally, we describe how the modeling language YALMIP is changed in such a way that our code can be interfaced using standard YALMIP commands, which greatly simplifies for the user.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2010. 7 p.
Series
LiTH-ISY-R, ISSN 1400-3902 ; 2927
Keyword
Semidefinite programming, Structure exploitation, Mathematical programming, Matrix algebra
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-56215 (URN)LiTH-ISY-R-2927 (ISRN)
Available from: 2010-04-30 Created: 2010-04-30 Last updated: 2014-06-19Bibliographically approved

Open Access in DiVA

No full text

By organisation
Automatic ControlThe Institute of Technology
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 521 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf