Yiming Yan (University of Edinburgh)

Optimal active-set prediction for interior point methods using controlled perturbations
Wednesday 27 November 2013 at 15.30, JCMB 6301


We propose the use of controlled perturbations to address the well-known and challenging question of optimal active-set prediction for interior point methods. Namely, in the context of a standard-form linear programming problem, we consider perturbing the inequality constraints/bounds so as to enlarge the feasible set. We show that if the perturbations are chosen appropriately, the solution of the original problem lies on or close to the central path of the perturbed problem and that a primal-dual path-following algorithm applied to the perturbed problem is able to predict the optimal active-set of the original problem when the duality gap (for the perturbed problem) is not too small. Encouraging preliminary numerical experience is reported when comparing the activity prediction for the perturbed and unperturbed formulations for the purpose of crossover to simplex.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996