Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5540| Title: | On Two Measures of Problem Instance Complexity and Their Correlation with the Performance of SeDuMi on Second-Order Cone Problems |
| Issue Date: | 9-Oct-2013 |
| Publisher: | Massachusetts Institute of Technology, Operations Research Center |
| 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. This research has been partially supported through the MIT-Singapore Alliance |
| URI: | http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
| Other Identifiers: | http://hdl.handle.net/1721.1/5540 |
| 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.