----------------------------------------------------------------------------------------------------------------------

 

 

      Department of Systems Engineering and Engineering Management

                             The Chinese University of Hong Kong

 

----------------------------------------------------------------------------------------------------------------------

 

Date: 11:00am to 12:00pm, May 29, 2017 (Monday)

 

Title: Facial Reduction (FR) for Semidefinite Programming (SDP) with applications to Low-Rank Matrix Completion (LRMC)

 

Speaker: Professor Henry Wolkowicz, Professor of Mathematics in the Department of Combinatorics and Optimization, University of Waterloo

 

Abstract:

 

SDP relaxations are extremely successful for many numerically hard problems. Of interest is that many of these SDP relaxations are degenerate in that strict feasibility fails. We look at FR for regularizing the SDP relaxations. In addition, we show that the degeneracy can be turned to an advantage.

 

In particular, we look at LRMC. Minimization of the NN is often used as a surrogate, convex relaxation, for solving LRMC problems. The minimum NN problem can be solved as a trace minimization semidefinite program (SDP). The SDP and its dual are regular in the sense that they both satisfy strict feasibility. Here we take advantage of the structure at optimality for the NN minimization and show that even though strict feasibility holds, the FR framework can be successfully applied  to obtain a proper face that contains the optimal set. This can dramatically reduce the size of the final NN problem while guaranteeing a low-rank solution. We include numerical tests for  both exact and noisy cases.

 

Biography:

 

Henry Wolkowicz is currently a Professor of Mathematics in the Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada. He has been at Waterloo since 1986. He received my Ph.D. degree in 1978 from McGill University in Montreal, Canada. He has published more than 160 papers and edited several books in the areas of Optimization and Operations Research. He is a SIAM Fellow and have been elected Chair of the SIAM (Society of Industrial and Applied Mathematics) Activity Group on Optimization and elected to the SIAM and ILAS (International Linear Algebra Society) Boards.

 

Henry Wolkowicz has supervised approximately thirty Masters, Ph.D. and Postdoctoral Fellows. He now (and in the past) serves on the editorial board of several internationally renowned journals in optimization including: the two flagship journals of Operations Research, Operations Research; Mathematics of Operations Research; The top two journals in Optimization, SIAM J. of Optimization and Mathematical Programming, Series B; and also Computational optimization and applications; Optimization and Engineering; Journal of Combinatorial Optimization; American Journal of Mathematical and Management Sciences. He has organized several major conferences including SIOPT and ICCOPT and many sessions in major international conferences on optimization. (A list of publications and other activities can be found on his web page www.math.uwaterloo.ca/~hwolkowi)

 

This talk is hosted by Prof. Shiqian Ma.

 

Everyone is welcome to attend the talk!

 

 

Venue: Room 1009,

      William M.W. Mong Engineering Building (ERB),

      The Chinese University of Hong Kong.

 

SEEM-5202 Website: http://seminar.se.cuhk.edu.hk

Email: seem5202@se.cuhk.edu.hk