Extreme points of well-posed polytopes

References

• Ashmanov , SA . 1981 . Stability conditions for linear programming problems . USSR Computational Mathematics and Mathematical Physics , 21 ( 6 ) : 40 – 49 .
   Google Scholar
• Bonnans , F and Shapiro , A . 1998 . Optimization problems with perturbations: a guided tour . SIAM Review , 40 ( 2 ) : 228 – 264 .
   Web of Science ®Google Scholar
• Bonnans , F and Shapiro , A . 2000 . Perturbation Analysis of Optimization Problems , New York : Springer-Verlag .
   Google Scholar
• Cánovas , MJ , López , MA , Parra , J and Todorov , MI . 1999 . Stability and well-posedness in linear semi-infinite programming . SIAM Journal on Optimization , 10 ( 1 ) : 82 – 98 .
   Web of Science ®Google Scholar
• Cánovas , MJ , López , MA , Parra , J and Toledo , FJ . 2005 . Distance to ill-posedness and consistency value of linear semi-infinite inequality systems . Mathematical Programming , 103 ( 1 ) : 95 – 126 .
   Web of Science ®Google Scholar
• Cheung , D and Cucker , F . 2001 . A new condition number for linear programming . Mathematical Programming , 91 ( 1 ) October : 163 – 174 .
   Web of Science ®Google Scholar
• Cristianini , N and Shawe-Taylor , J . 2002 . An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods , New York : Cambridge University Press .
   Google Scholar
• Cucker , F and Peña , J . 2002 . A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine . SIAM Journal on Optimization , 12 ( 2 ) : 522 – 554 .
   Google Scholar
• Epelman , M and Freund , RM . 2000 . Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system . Mathematical Programming , 88 ( 3 ) : 451 – 485 .
   Web of Science ®Google Scholar
• Filipowski , S . 1995 . On the complexity of solving feasible systems of linear inequalities specified with approximate data . Mathematical Programming , 71 ( 3 ) : 259 – 288 .
   Google Scholar
• Filipowski , S . 1997 . On the complexity of solving sparse symmetric linear programs specified with approximate data . Mathematics of Operations Research , 22 ( 4 ) : 769 – 792 .
   Google Scholar
• Filipowski , S . 1999 . On the complexity of solving feasible linear programs specified with approximate data . SIAM Journal on Optimization , 9 ( 4 ) : 1010 – 1040 .
   Google Scholar
• Freund , RM . 1985 . “ Postoptimality analysis of a linear program under simultaneous changes in matrix coefficients ” . In Mathematical Programming Study 24 , Edited by: Cottle , RW . 1 – 13 . Amsterdam : North-Holland .
   Google Scholar
• Freund , RM and Vera , JR . 1999 . Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm . SIAM Journal on Optimization , 10 ( 1 ) : 155 – 176 .
   Google Scholar
• Freund , RM and Vera , JR . 1999 . Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system . Mathematical Programming , 86 ( 2 ) : 225 – 260 .
   Google Scholar
• Freund , RM and Vera , JR . 2003 . On the complexity of computing estimates of condition measures of a conic linear system . Mathematics of Operations Research , 28 ( 4 ) : 625 – 648 .
   Google Scholar
• Gal , T . 1975 . Rim multiparametric linear programming . Management Science , 21 ( 5 ) : 567 – 575 .
   Google Scholar
• Gal , T . 1984 . “ Linear parametric programming – a brief survey. ” . In Mathematical Programming Study 21 , 43 – 68 . Amsterdam : North-Holland .
   Google Scholar
• Gordon , AD . 1999 . Classification , 2nd Edn , Boca Raton, , Florida : Chapman & Hall/CRC .
   Google Scholar
• Hand , DJ . 1981 . Discrimination and Classification , New York : John Wiley & Sons, Inc. .
   Google Scholar
• Khachiyan , LG . 1979 . A polynomial algorithm in linear programming . Soviet Mathematics Doklady , 20 ( 1 ) : 191 – 194 .
   Google Scholar
• Kim , W , Park , C and Park , S . 1999 . An ε-sensitivity analysis in the primal-dual interior point method . European Journal of Operational Research , 116 ( 3 ) : 629 – 639 .
   Google Scholar
• Levitin , ES . 1994 . Perturbation Theory in Mathematical Programming and its Applications , New York : John Wiley & Sons, Inc. .
   Google Scholar
• Mangasarian , OL . 1981 . A stable theorem of the alternative: an extension of the Gordan theorem . Linear Algebra and its Applications , 41 : 209 – 223 .
   Web of Science ®Google Scholar
• Manne , AS . 1953 . Notes on parametric linear programming . 1953 . Technical Report , pp. 468 RAND Corporation .
   Google Scholar
• Mardia , KV , Kent , JT and Bibby , JM . 1994 . Multivariate Analysis , San Diego, CA : Academic Press .
   Google Scholar
• Mills , HD . 1956 . “ Marginal values of matrix games and linear programs ” . In Linear Inequalities and Related Systems , Edited by: Kuhn , HW and Tucker , AW . 183 – 193 . Princeton, , New Jersey : Princeton University Press .
   Google Scholar
• Nayakkankuppam , MV and Overton , ML . 1999 . Conditioning of semidefinite programs . Mathematical Programming , 85 ( 3 ) : 525 – 540 .
   Google Scholar
• Nunez , MA . 2002 . A characterization of ill-posed data instances for convex programming . Mathematical Programming , 91 ( 2 ) : 375 – 390 .
   Google Scholar
• Nunez , MA and Freund , RM . 1998 . Condition measures and properties of the central trajectory of a linear program . Mathematical Programming , 83 ( 1 ) : 1 – 28 .
   Google Scholar
• Nunez , MA and Freund , RM . 2001 . Condition measure bounds on the behaviour of the central trajectory of a semidefinite program . SIAM Journal on Optimization , 11 ( 3 ) : 818 – 836 .
   Google Scholar
• Peña , J . 2000 . Understanding the geometry of infeasible perturbations of a conic linear system . SIAM Journal on Optimization , 10 ( 2 ) : 534 – 550 .
   Web of Science ®Google Scholar
• Peña , J . 2001 . Conditioning of convex programs from a primal-dual perspective . Mathematics of Operations Research , 26 ( 2 ) : 206 – 220 .
   Google Scholar
• Peña , J and Renegar , J . 2000 . Computing approximate solutions for convex conic systems of constraints . Mathematical Programming , 87 ( 3 ) : 351 – 383 .
   Google Scholar
• Ravi , N and Wendell , RE . 1985 . The tolerance approach to sensitivity analysis of matrix coefficients in linear programming: general perturbations . Journal of the Operations Research Society , 36 ( 10 ) : 943 – 950 .
   Web of Science ®Google Scholar
• Ravi , N and Wendell , RE . 1989 . The tolerance approach to sensitivity analysis of matrix coefficients in linear programming . Management Science , 35 ( 9 ) : 1106 – 1119 .
   Web of Science ®Google Scholar
• Renegar , J . 1994 . Some perturbation theory for linear programming . Mathematical programming , 65 ( 1 ) : 73 – 91 .
   Google Scholar
• Renegar , J . 1995 . Incorporating condition measures into the complexity theory of linear programming . SIAM Journal on Optimization , 5 ( 3 ) : 506 – 524 .
   Google Scholar
• Renegar , J . 1995 . Linear programming, complexity theory, and elementary functional analysis . Mathematical Programming , 70 ( 3 ) : 279 – 351 .
   Google Scholar
• Renegar , J . 1996 . Condition numbers, the barrier method, and the conjugate gradient method . SIAM Journal on Optimization , 6 ( 4 ) : 879 – 912 .
   Google Scholar
• Renegar , J . 2001 . A Mathematical View of Interior-Point Methods in Convex Optimization , Philadelphia : Society for Industrial and Applied Mathematics (SIAM) .
   Google Scholar
• Robinson , SM . 1975 . Stability theory for systems of inequalities. Part I: linear systems . SIAM Journal on Numerical Analysis , 12 ( 5 ) : 754 – 769 .
   Google Scholar
• Robinson , SM . 1976 . Stability theory for systems of inequalities. Part II: nonlinear systems . SIAM Journal on Numerical Analysis , 13 ( 4 ) : 497 – 513 .
   Web of Science ®Google Scholar
• Robinson , SM . 1977 . A characterization of stability in linear programming . Operations Research , 25 ( 3 ) : 435 – 447 .
   Google Scholar
• Rockafellar , T . 1970 . Convex Analysis , Princeton, , N.J. : Princeton University Press .
   Google Scholar
• Saaty , TL . 1959 . Coefficient perturbation of a constrained extremum . Operations Research , 7 : 294 – 302 .
   Google Scholar
• Scholtes , S . 1996 . On the computability of the condition number for certain inconsistent systems . 1996 , Cambridge, England. Technical report , Department of Engineering and The Judge Institute of Management Studies, University of Cambridge .
   Google Scholar
• Sturm , JF and Zhang , S . 1998 . On sensitivity of central solutions in semidefinite programming . 1998 , Rotterdam, The Netherlands. Econometric Institute report No. 9813/A , Econometric Institute, Erasmus University .
   Google Scholar
• Thuraisingham , B . 1999 . Data Mining, Technologies, Techniques, Tools, and Trends , Boca Raton, , Florida : CRC Press .
   Google Scholar
• Tunçel , L . 1999 . Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard . Mathematical Programming , 86 ( 1 ) : 219 – 223 .
   Google Scholar
• Vavasis , SA and Ye , Y . 1996 . “ Identifying an optimal basis in linear programming ” . In Annals of Operations Research 62 , Edited by: Anstreicher , KM and Freund , RM . 565 – 572 . The Netherlands : Baltzer Science Publishers .
   Google Scholar
• Vavasis , SA and Ye , Y . 1996 . A primal-dual interior point method whose running time depends only on the constraint matrix . Mathematical Programming , 74 ( 1 ) : 79 – 120 .
   Google Scholar
• Vera , JR . 1992 . Ill-posedness and the computation of solutions to linear programs with approximate data . 1992 . Technical report , Cornell University .
   Google Scholar
• Vera , JR . 1996 . Ill-posedness and complexity of deciding existence of solutions to linear programs . SIAM Journal on Optimization , 6 ( 3 ) : 549 – 569 .
   Web of Science ®Google Scholar
• Vera , JR . 1998 . On the complexity of linear programming under finite precision arithmetic . Mathematical Programming , 80 ( 1 ) : 91 – 123 .
   Google Scholar
• Wendell , RE . 1984 . Using bounds on the data in linear programming: the tolerance approach to sensitivity analysis . Mathematical Programming , 29 ( 3 ) : 304 – 322 .
   Web of Science ®Google Scholar
• Wendell , RE . 1985 . The tolerance approach to sensitivity analysis in linear programming . Management Science , 31 ( 5 ) : 564 – 578 .
   Web of Science ®Google Scholar
• Wright , M . 1998 . Ill-conditioning and computational error in interior methods for nonlinear programming . SIAM Journal on Optimization , 9 ( 1 ) : 84 – 111 .
   Google Scholar
• Wright , SJ . 1997 . Primal-Dual Interior-Point Methods , Philadelphia : Society for Industrial and Applied Mathematics (SIAM) .
   Google Scholar
• Ye , Y . 1994 . Toward a probalistic analysis of interior point algorithms for linear programming . Mathematics of Operations Research , 19 ( 1 ) : 38 – 52 .
   Web of Science ®Google Scholar
• Ye , Y . 1997 . Interior Point Algorithms, Theory and Analysis , New York : John Wiley & Sons, Inc. .
   Google Scholar
• Yildirim , A . 2003 . An interior-point perspective on sensitivity analysis in semidefinite programming . Mathematics of Operations Research , 28 ( 4 ) : 649 – 676 .
   Web of Science ®Google Scholar
• Yildirim , A and Todd , M . 2001 . Sensitivity analysis in linear programming and semidefinite programming using interior-point methods . Mathematical Programming , 90 ( 2 ) : 229 – 261 .
   Google Scholar