Please use this identifier to cite or link to this item:
Title: Computation of condition numbers for linear programming problems using Peña's method
Authors: Chai, J.-S.
Toh, K.-C. 
Keywords: Complexity
Conic optimization
Interior-point methods
Linear programming
Renegar condition number
Issue Date: 1-Jun-2006
Citation: Chai, J.-S., Toh, K.-C. (2006-06-01). Computation of condition numbers for linear programming problems using Peña's method. Optimization Methods and Software 21 (3) : 419-443. ScholarBank@NUS Repository.
Abstract: We present the computation of the condition numbers for linear programming (LP) problems from the NETLIB suite. The method of Peña [Peña, J., 1998, Computing the distance to infeasibility: theoretical and practical issues. Technical report, Center for Applied Mathematics, Cornell University.] was used to compute the bounds on the distance to ill-posedness ?( d ) of a given problem instance with data d, and the condition number was computed as C ( d )?=?? d ?/?( d ). We discuss the efficient implementation of Peñas method and compare the tightness of the estimates on C ( d ) computed by Peñas method to that computed by the method employed by Ordóñez and Freund [Ordóñez, F. and Freund, R.M., 2003, Computational experience and the explanatory value of condition measures for linear optimization. SIAM Journal on Optimization, 14, 307-333.]. While Peñas method is generally much cheaper, the bounds provided are generally not as tight as those computed by Ordóñez and Freund. As a by-product, we use the computational results to study the correlation between log C ( d ) and the number of interior-point method iterations taken to solve a LP problem instance. Our computational findings on the preprocessed problem instances from NETLIB suite are consistent with those reported by Ordóñez and Freund.
Source Title: Optimization Methods and Software
ISSN: 10556788
DOI: 10.1080/10556780500098599
Appears in Collections:Staff Publications

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


checked on Feb 22, 2019


checked on Feb 5, 2019

Page view(s)

checked on Oct 26, 2018

Google ScholarTM



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