Seminar by Georgina Hall, Princeton University
Event details
| Date | 06.10.2016 |
| Hour | 15:00 › 16:30 |
| Speaker | Georgina Hall, Princeton University |
| Location | |
| Category | Conferences - Seminars |
"Sum of squares optimization: scalability improvements and applications to difference of convex programming"
Abstract
Over the past decade, sum of squares techniques have impacted many areas of computational mathematics, including optimization, controls, statistics, and operations research. It is well known however that sum of squares (sos) problems are limited by the large semidefinite programs (SDPs) that they generate, which are slow to solve with current technology. In the first part of the talk, we describe methods to approximate such SDPs by a series of linear or second order cone programs in order to obtain more scalable algorithms. In the second part of this talk, we show how sos techniques can be used to tackle the problem of optimizing over convex polynomials. We focus on applications of this problem to computer vision and to nonconvex polynomial optimization. In particular, we prove that any nonconvex polynomial can be decomposed efficiently (via semidefinite programming) as the difference of two convex polynomials and present the impacts that such a result has on a subclass of optimization problems called difference of convex programming.
Abstract
Over the past decade, sum of squares techniques have impacted many areas of computational mathematics, including optimization, controls, statistics, and operations research. It is well known however that sum of squares (sos) problems are limited by the large semidefinite programs (SDPs) that they generate, which are slow to solve with current technology. In the first part of the talk, we describe methods to approximate such SDPs by a series of linear or second order cone programs in order to obtain more scalable algorithms. In the second part of this talk, we show how sos techniques can be used to tackle the problem of optimizing over convex polynomials. We focus on applications of this problem to computer vision and to nonconvex polynomial optimization. In particular, we prove that any nonconvex polynomial can be decomposed efficiently (via semidefinite programming) as the difference of two convex polynomials and present the impacts that such a result has on a subclass of optimization problems called difference of convex programming.
Practical information
- General public
- Free