Spjøtvold, Jørgen (Norwegian Univ. of Science and Tech.), Kerrigan, Eric Colin (Imperial Coll. London), Jones, Colin Neil (Univ. of Cambridge), Tøndel, Petter (Sintef), Johansen, Tor Arne (Norwegian Univ. of Science and Tech.)

The Facet-To-Facet Property of Solutions to Convex Parametric Quadratic Programs and a New Exploration Strategy

Scheduled for presentation during the Regular Session "Optimization" (TuP12), Tuesday, July 25, 2006, 17:00−17:25, Room 104b

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 27, 2023

Abstract

In some of the recently-developed algorithms for convex parametric quadratic programs it is implicitly assumed that the intersection of the closures of two adjacent critical regions is a facet of both closures; this will be referred to as the facet-to-facet property. It is shown by an example, whose solution is unique, that the facet-to-facet property does not hold in general, and consequently, some existing algorithms cannot guarantee that the entire parameter space will be explored. A simple modification of existing algorithms is presented for the purpose of overcoming this problem.