Application of semidefinite programming to truss design optimization

Abstract

Semidefinite Programming (SDP) is a fairly recent way of solving optimization problems which are becoming more and more important in our fast moving world. It is a minimization of linear function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e. non-linear but convex constraints. All linear problems and many engineering and combinatorial optimization problems can be expressed as SDP, so it is highly applicable. There are many packages that use different algorithms to solve SDP problems. They can be downloaded from internet and easily learnt how to use, two of these are SeDuMi and SDPT-3. In this paper truss structure optimization problem with the goal of minimizing the mass of the truss structure was solved. After doing some algebraic manipulation the problem was formulated suitably for Semidefinite Programming. SeDuMi and SDPT-3 packages were used to solve it. The choice of the initial solution had a great impact on the result using SeDuMi. The mass obtained using SDPT-3 was on average smaller than the one obtained using SeDuMi. Moreover, SDPT-3 worked more efficiently. However, the comparison of my approach and two versions of particle swarm optimization algorithm implied that semidefinite programming is in general more appropriate for solving such problems.

Article in English.

Santvaros optimizavimo uždavinių sprendimas taikant pusiau apibrėžtą programavimą

Santrauka 

Pusiau apibrėžtas programavimas yra iškiliojo optimizavimo posritis, kuriame tikslo funkcija tiesinė, o leistinoji sritis – pusiau teigiamai apibrėžtų matricų kūgio ir afininės erdvės sankirta. Tai gana naujas optimizavimo problemų sprendimo būdas, tačiau jau plačiai taikomas sprendžiant inžinerinius bei kombinatorinius optimizavimo uždavinius. Tokiems uždaviniams spręsti yra daug skirtingų paketų, taikančių įvairius algoritmus. Šiame darbe buvo naudojami SeDuMi ir SDPT-3 paketai, kuriuos, kaip ir daugumą kitų, galima parsisiųsti iš interneto. Tikslas buvo rasti minimalią santvaros masę atsižvelgiant į numatytus apribojimus. Naudojant SDPT-3 gauta optimali masė buvo vidutiniškai mažesnė nei naudojant SeDuMi. SDPT-3 veikė efektyviau ir pradinių sąlygų pasirinkimas neturėjo tokios didelės įtakos sprendiniui kaip naudojant SeDuMi paketą. Palyginus rezultatus su sprendiniais, gautais taikant dalelių spiečiaus optimizavimo algoritmą, nustatyta, kad tokio tipo uždaviniams pusiau apibrėžtas programavimas yra tinkamesnis.

Reikšminiai žodžiai: pusiau apibrėžtas programavimas, santvara, SeDuMi, SDPT-3.

Keyword : Semidefinite Programming, truss design, SeDuMi, SDPT-3