NDLI: Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems

Content Provider	Springer Nature Link
Author	Freund, Robert M. Toh, Kim Chuan Ordóñez, Fernando
Copyright Year	2006
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.
Ending Page	475
Page Count	31
Starting Page	445
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	2-3
Volume Number	109
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-09-20
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Semidefinite programming Complementarity Mathematical and Computational Physics Interior-point methods Degeneracy Mathematical Methods in Physics Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Behavioral measure Condition number Explicit machine computation and programs (not the theory of computation or programming) Abstract computational complexity for mathematical programming problems Combinatorics Interior-point method Semi-definite programming
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems (2005)

Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

Correlation with ipm iteration counts on semi-definite programming problems.

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

Generating and measuring instances of hard semidefinite programs

A primal–dual interior point method for nonlinear semidefinite programming

Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming

Merit functions for semi-definite complemetarity problems

Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems

Similar Documents

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems (2005)

Correlation with IPM Iteration Counts on Semi-Definite Programming Problems

Correlation with ipm iteration counts on semi-definite programming problems.

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

Generating and measuring instances of hard semidefinite programs

A primal–dual interior point method for nonlinear semidefinite programming

Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming

Merit functions for semi-definite complemetarity problems

Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity

Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems