BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Global optimization via eigenvalues - Yuji Nakatsu
kasa (Oxford University)
DTSTART:20161201T120000Z
DTEND:20161201T130000Z
UID:TALK2240AT
URL:/talk/index/2240
DESCRIPTION:While non-convex optimization problems are general
ly regarded as difficult or computationally intrac
table\, the Courant-Fischer theorem for symmetric
eigenvalue problems suggests that each eigenpair c
orresponds to a stationary point of a non-convex o
ptimization problem (in this case the\nRayleigh qu
otient). More generally\, matrix eigenvalue proble
ms can be regarded as an important class of optimi
zation problems that can be solved efficiently. Th
is observation suggests conversely that perhaps a
global solution for some non-convex optimization p
roblems can be obtained by solving an eigenvalue p
roblem. In this work we identify such optimization
problems\, and show that they lead to a variety o
f eigenvalue problems\, including\ngeneralized\, p
olynomial and multiparameter eigenvalue problems\,
all of which can be solved reliably and in polyno
mial time\, and essentially non-iteratively.\nSpec
ifically\, we consider non-convex QCQP (quadratica
lly constrained quadratic programming). QCQP is kn
own to be NP-hard in general (when the number of c
onstraints k is not fixed)\, and for k ≥ 2 fixed\,
it has been an open problem whether they are poly
nomial-time solvable until recently. We show that
(i) for QCQP with one constraint\, k = 1\, it can
be reduced to essentially a single generalized eig
envalue problem\, (ii) for QCQP with two constrain
ts\, k = 2\, the problem can be reduced to a two-p
arameter eigenvalue problem\, and (iii) unconstrai
ned optimization problems with cubic regularizatio
n can be reduced to quadratic eigenvalue problems.
\n\nBased on joint work with Satoru Adachi\, Sator
u Iwata\, Shinsaku Sakaue and Akiko Takeda (Univer
sity of Tokyo).\n\n
LOCATION:University House\, room 108
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR