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 second-order 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ña’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.675), 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.
相似文献