Speaker: Pro.Kim-Chuan Toh（National University of Singapore）
Title: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints
Time: Fri, Mar.29, 2019, AM:9:45-11:30
Location: Room 4318, Building No.4, Wushan Campus
Abstract:
The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a DNN relaxation of the POP, and then solves the COP by applying the bisection and projection (BP) method. The COP is expressed with a linear objective function and constraints described as a single hyperplane and two cones, which are the Cartesian product of positive semidefinite cones and a polyhedral cone induced from the BBC constraints. BBCPOP aims to compute a tight lower bound for the optimal value of a large-scale POP in the class that is beyond the comfort zone of existing software packages. The robustness, reliability and efficiency of BBCPOP are demonstrated in comparison to the state-of-the-art software SDP package SDPNAL+ on randomly generated sparse POPs of degree 2 and 3 with up to a few thousands variables, and ones of degree from 5 to 8 with up to a few hundred variables. Numerical results on BBC constrained POPs that arise from quadratic assignment problems are also reported. The software package BBCPOP is available at https://sites.google.com/site/bbcpop1/.
Biography:
Dr Toh is a Professor at the Department of Mathematics, National University of Singapore (NUS). He obtained his BSc degree in Mathematics from NUS in 1990 and the PhD degree in Applied Mathematics from Cornell University in 1996 under the direction of Nick Trefethen. His current research focuses on designing efficient algorithms and software for convex programming and its applications, particularly large scale optimization problems arising from data science/machine learning, and large scale matrix optimization problems such as linear semidefinite programming (SDP) and convex quadratic semidefinite programming (QSDP).
Professor Toh is currently an Area Editor for Mathematical Programming Computation, an Associate Editor for the SIAM Journal on Optimization, Mathematical Programming, and ACM Transactions on Mathematical Software. He was an invited speaker at numerous conferences and workshops, including the SIAM Annual Meeting in 2010, and International Symposium in Mathematical Programing in 2006. He received the Farkas Prize awarded by the INFORMS Optimization Society in 2017 and the triennial Beale-Orchard Hays Prize awarded by the Mathematical Optimization Society in 2018. He was selected as a Fellow of the Society for Industrial and Applied Mathematics in 2018.
