Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10107-006-0035-y
Title: Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems
Authors: Freund, R.M.
Ordóñez, F.
Toh, K.-C. 
Keywords: Behavioral measure
Complementarity
Condition number
Degeneracy
Interior-point method
Semi-definite programming
Issue Date: Mar-2007
Citation: Freund, R.M., Ordóñez, F., Toh, K.-C. (2007-03). Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems. Mathematical Programming 109 (2-3) : 445-475. ScholarBank@NUS Repository. https://doi.org/10.1007/s10107-006-0035-y
Abstract: We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the sample correlation (CORR) between these measures and IPM iteration counts (solved using the software SDPT3) when these measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.901), and provides a very good explanation of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. © Springer-Verlag 2007.
Source Title: Mathematical Programming
URI: http://scholarbank.nus.edu.sg/handle/10635/104538
ISSN: 00255610
DOI: 10.1007/s10107-006-0035-y
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

13
checked on Dec 19, 2018

WEB OF SCIENCETM
Citations

11
checked on Dec 19, 2018

Page view(s)

29
checked on Nov 2, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.