Everyone is welcome to attend the next N&O seminar with Alex L Wang with the title 'First-order methods for nonconvex quadratically constrained quadratic programs'.
Abstract: Quadratically constrained quadratic programs (QCQPs) are a class of nonconvex optimization problems capable of capturing rich nonconvexity structures. One classic approach to tackle this NP-hard optimization problem is via its convex semidefinite program (SDP) relaxation. After reviewing some recent work towards understanding when the SDP relaxation of a QCQP is exact, we ask the algorithmic question: Is it possible to leverage the assumption that this SDP relaxation has a rank-one solution to solve it efficiently and/or using low memory? We give positive answers in this direction. Specifically, we will see how to apply accelerated gradient descent methods to (the SDP relaxations of) the generalized trust region subproblem and other "strongly convex" nonconvex QCQPs.
Based on joint work with Fatma Kılınç-Karzan.
