An optimal-basis identification technique for interior-point linear programming algorithms, Export

@article{citeulike:4041863, abstract = {This work concerns a method for identifying an optimal basis for linear programming problems in the setting of interior-point methods. To each iterate x k generated by a primal interior-point algorithm, say, we associate an indicator vector q k with the property that if x k converges to a nondegenerate vertex x * , then q k converges to the 0–1 vector sign( x * ). More interestingly, we show that the convergence of q k is quadratically faster than that of x k in the sense that || q k − q 7 ast ; ||= O (|| x k − x * || 2 ). This clear-cut separation and rapid convergence allow one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. We also show that under suitable assumptions this method is applicable to dual as well as primal-dual algorithms and can be extended to handle certain types of degeneracy. Numerical examples are included to corroborate the convergence properties of the indicators. The practical limitations of the indicator technique are also discussed.}, author = {Tapia, R.}, citeulike-article-id = {4041863}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0024-3795(91)90281-Z}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/0024-3795(91)90281-Z}, day = {1}, doi = {10.1016/0024-3795(91)90281-Z}, issn = {00243795}, journal = {Linear Algebra and its Applications}, keywords = {article, indicators, interiorpoint, masters}, month = {July}, number = {1}, pages = {343--363}, posted-at = {2009-02-13 00:45:59}, priority = {2}, title = {An optimal-basis identification technique for interior-point linear programming algorithms,}, url = {http://dx.doi.org/10.1016/0024-3795(91)90281-Z}, volume = {152}, year = {1991} }

TY - JOUR ID - citeulike:4041863 L3 - citeulike-article-id:4041863 N2 - This work concerns a method for identifying an optimal basis for linear programming problems in the setting of interior-point methods. To each iterate x k generated by a primal interior-point algorithm, say, we associate an indicator vector q k with the property that if x k converges to a nondegenerate vertex x * , then q k converges to the 0–1 vector sign( x * ). More interestingly, we show that the convergence of q k is quadratically faster than that of x k in the sense that || q k − q 7 ast ; ||= O (|| x k − x * || 2 ). This clear-cut separation and rapid convergence allow one to infer at an intermediate stage of the iterative process which variables will be zero at optimality and which will not. We also show that under suitable assumptions this method is applicable to dual as well as primal-dual algorithms and can be extended to handle certain types of degeneracy. Numerical examples are included to corroborate the convergence properties of the indicators. The practical limitations of the indicator technique are also discussed. IS - 1 JF - Linear Algebra and its Applications SN - 00243795 EP - 363 TI - An optimal-basis identification technique for interior-point linear programming algorithms, VL - 152 SP - 343 KW - article KW - indicators KW - interiorpoint KW - masters AU - Tapia, R PY - 1991/07/01/ UR - http://dx.doi.org/10.1016/0024-3795(91)90281-Z ER -