| 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 |
|