  


Finding a point in the relative interior of a polyhedron
Coralia Cartis(C.Cartisrl.ac.uk) Abstract: A new initialization or `Phase I' strategy for feasible interior point methods for linear programming is proposed that computes a point on the primaldual central path associated with the linear program. Provided there exist primaldual strictly feasible points  an allpervasive assumption in interior point method theory that implies the existence of the central path  our initial method (Algorithm 1) is globally Qlinearly and asymptotically Qquadratically convergent, with a provable worstcase iteration complexity bound. When this assumption is not met, the numerical behaviour of Algorithm 1 is highly disappointing, even when the problem is primaldual feasible. This is due to the presence of implicit equalities, inequality constraints that hold as equalities at all the feasible points. Controlled perturbations of the inequality constraints of the primaldual problems are introduced  geometrically equivalent to enlarging the primaldual feasible region and then systematically contracting it back to its initial shape  in order for the perturbed problems to satisfy the assumption. Thus Algorithm 1 can successfully be employed to solve each of the perturbed problems. We show that, when there exist primaldual strictly feasible points of the original problems, the resulting method, Algorithm 2, finds such a point in a finite number of changes to the perturbation parameters. When implicit equalities are present, but the original problem and its dual are feasible, Algorithm 2 asymptotically detects all the primaldual implicit equalities and generates a point in the relative interior of the primaldual feasible set. Algorithm 2 can also asymptotically detect primaldual infeasibility. Successful numerical experience with Algorithm 2 on linear programs from NETLIB and CUTEr, both with and without any significant preprocessing of the problems, indicates that Algorithm 2 may be used as an algorithmic preprocessor for removing implicit equalities, with theoretical guarantees of convergence. Keywords: interior point methods, linear programming Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: RAL Technical Report 2006016, CCLRC Rutherford Appleton Laboratory, Chilton, Didcot, United Kingdom, OX11 0QX, December 2006. http://www.numerical.rl.ac.uk/reports/reports.shtml Download: [Postscript][PDF] Entry Submitted: 12/26/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  