Comparison of Two Structure-Exploiting Optimization Algorithms for Integral Quadratic Constraints
2003 (English)Report (Other academic)
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.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2003. , 14 p.
LiTH-ISY-R, ISSN 1400-3902 ; 2502
Interior-point algorithms, Semidefinite programs, Integral quadratic constraints
IdentifiersURN: urn:nbn:se:liu:diva-55925ISRN: LiTH-ISY-R-2502OAI: oai:DiVA.org:liu-55925DiVA: diva2:316809
FunderSwedish Research Council, 271-2000-770