Seminar

Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong

Title: From Incomplete Data to Decision Making: Structured Convex Optimization Approaches

Speaker: Dr. Shiqian MA
               Institute for Mathematics and its Applications (IMA)
               University of Minnesota

Date: May 3, 2012 (Thursday)

Time: 11:15 a.m. - 12:30 p.m.

Venue: Room 513
            William M.W. Mong Engineering Building
            (Engineering Building Complex Phase 2)
            CUHK

Abstract:

Decision making from incomplete data is a very important topic in Operations Research. Incomplete data occur frequently in different areas in practice. For example, in stock return data from financial markets, incomplete data occur because there are hidden factors that cannot be observed in the market. Another example is the rating data from online recommendation systems, in which the data are sometimes manipulated by some people in purpose. In this talk, we show that a lot of decision making problems with incomplete data arising from Finance, Statistics and Machine Learning can be formulated as structured convex optimization problems. In particular, we consider the formulations that require the solutions to have sparse or low-rank properties. These problems are usually large-scale with millions of variables and constraints and thus are very challenging to solve. We propose several alternating direction methods that take advantage of the special structures of the problems to solve them. Specifically, we propose alternating linearization methods (ALM) for solving convex optimization problems with two sets of variables. We show that our basic and accelerated ALMs need respectively O(1/eps) and O(1/sqrt(eps)) iterations to obtain an eps-optimal solution. To the best of our knowledge, these are the first iteration complexity results that have been given for alternating direction type methods.
We then propose alternating proximal gradient method (APGM) that can solve convex optimization problems with three or more sets of variables. We prove that APGM globally converges to an optimal solution under very mild assumptions.  Numerical results on problems arising from Finance, Statistics, Machine Learning, Facility Location and Compressed Sensing are shown to demonstrate the efficacy
of the proposed approaches.

Biography:

Shiqian Ma is currently an NSF postdoctoral associate in the Institute for Mathematics and Its Applications (IMA) at University of Minnesota. He obtained his Ph.D. from the Department of Industrial Engineering and Operations Research at Columbia University in 2011, M.S. degree from Chinese Academy of Sciences in 2006 and B.S. degree from Peking University in 2003. Shiqian received the 2010 INFORMS Optimization Society Best Student Paper Prize, Honorable Mention of the 2011 INFORMS George Nicholson  Student Paper Prize, and was among the six finalists of the 2011 IBM Herman Goldstine Fellowship. Shiqian's research interests lie in theory and algorithms for large-scale optimization with an emphasis in convex programming and their applications in Finance,
Statistics, Machine Learning and Signal Processing.

************************* ALL ARE WELCOME ************************
Host: Prof. Duan Li

Tel: (852) 3943-8316/8323

Email: dli@se.cuhk.edu.hk

Enquries: Prof. Nan Chen or Prof. Sean X. Zhou
                Department of Systems Engineering and Engineering Management
                CUHK

Website: http://www.se.cuhk.edu.hk/~seem5201

Email: seem5201@se.cuhk.edu.hk

********************************************************************