instituto de matemáticas universidad de sevilla
Antonio de Castro Brzezicki
imus-logo
The complexity of simple models - a study of worst and typical hard cases of the StQP
Seminario Doctorado
Actividad del Programa de Doctorado
ATENCIÓN CAMBIO DE FECHA: Estaba programado incialmente el día 26 de abril.
In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this model is quite versatile. Applications are numerous, ranging from the famous Markowitz portfolio selection problem in Finance, Evolutionary Game Theory through Machine Learning to life science applications, e.g. in Population Genetics  and Ecology.
StQPs lie at the core of Copositive Optimization; in fact, determining the StQP solution of a slack matrix in a copositive problem immediately gives a very strong bound for a wide class of MINLP problems with manifold Energy applications.
 
Non-convex StQP instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. In this study, we improve upon existing lower bounds for the number of strict local solutions by a new technique to construct instances with a rich solution structure, studying the influence of perturbations of a matrix on its pattern.
Moreover, to gain insight on typical hard cases and their distribution, we conducted extensive experimental results on potentially hard instance matrices. The results suggest that confidence in tractability of copositive bound determination may be justified, at least from an average case point of view.
 In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this model is quite versatile. Applications are numerous, ranging from the famous Markowitz portfolio selection problem in Finance, Evolutionary Game Theory through Machine Learning to life science applications, e.g. in Population Genetics  and Ecology.
StQPs lie at the core of Copositive Optimization; in fact, determining the StQP solution of a slack matrix in a copositive problem immediately gives a very strong bound for a wide class of MINLP problems with manifold Energy applications.
 
Non-convex StQP instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. In this study, we improve upon existing lower bounds for the number of strict local solutions by a new technique to construct instances with a rich solution structure, studying the influence of perturbations of a matrix on its pattern.
Moreover, to gain insight on typical hard cases and their distribution, we conducted extensive experimental results on potentially hard instance matrices. The results suggest that confidence in tractability of copositive bound determination may be justified, at least from an average case point of view.

Joint work with W.Schachinger and R.Ullrich

Compártelo: