Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5540
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.creator | Cai, Zhi | - |
dc.creator | Freund, Robert M. | - |
dc.date | 2004-09-14T18:11:56Z | - |
dc.date | 2004-09-14T18:11:56Z | - |
dc.date | 2004-09-13 | - |
dc.date.accessioned | 2013-10-09T02:39:56Z | - |
dc.date.available | 2013-10-09T02:39:56Z | - |
dc.date.issued | 2013-10-09 | - |
dc.identifier | http://hdl.handle.net/1721.1/5540 | - |
dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
dc.description | We evaluate the practical relevance of two measures of conic convex problem complexity as applied to second-order cone problems solved using the homogeneous self-dual (HSD) embedding model in the software SeDuMi. The first measure we evaluate is Renegar’s data-based condition measure C(d), and the second measure is a combined measure of the optimal solution size and the initial infeasibility/optimality residuals denoted by S (where the solution size is measured in a norm that is naturally associated with the HSD model). We constructed a set of 144 secondorder cone test problems with widely distributed values of C(d) and S and solved these problems using SeDuMi. For each problem instance in the test set, we also computed estimates of C(d) (using PeË na’s method) and computed S directly. Our computational experience indicates that SeDuMi iteration counts and log(C(d)) are fairly highly correlated (sample correlation R = 0.676), whereas SeDuMi iteration counts are not quite as highly correlated with S (R = 0.600). Furthermore, the experimental evidence indicates that the average rate of convergence of SeDuMi iterations is affected by the condition number C(d) of the problem instance, a phenomenon that makes some intuitive sense yet is not directly implied by existing theory. | - |
dc.description | This research has been partially supported through the MIT-Singapore Alliance | - |
dc.format | 232591 bytes | - |
dc.format | application/pdf | - |
dc.language | en_US | - |
dc.publisher | Massachusetts Institute of Technology, Operations Research Center | - |
dc.relation | Operations Research Center Working Paper Series;OR 371-04 | - |
dc.title | On Two Measures of Problem Instance Complexity and Their Correlation with the Performance of SeDuMi on Second-Order Cone Problems | - |
dc.type | Working Paper | - |
Appears in Collections: | MIT Items |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.