This talk starts by describing a relaxed clustering method via dominant sets, a method which has proved quite successful in recent years, in Image Segmentation as well in many other fields. Algorithmic implementations of this idea will lead us to the simplest quadratic optimization problem which is NP-hard, namely minimizing an indefinite quadratic form over the standard simplex: the so-called Standard Quadratic Optimization Problem (StQP).
Many algorithms have been proposed to obtain (local) solutions to StQPs. Here we address the large class of growth transformations which yields monotonic improvements, and present the Infection-Immunization Dynamics (InfImmDyn), a method particularly well suited to large problems: InfImmDyn selects from 2n search directions and performs an exact line search in closed form. Both space and time requirements of one iteration step are linear in the dimension n.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
