ICCOPT 2013 Plenary Session Thu.P.AA, Auditorium A, Thursday, August 1, 15:00-16:00

 Speaker: Yinyu Ye, Department of Management Science and Engineering and Institute for Computational and Mathematical Engineering, Stanford University, USA
 Title: Complexity analysis beyond convex optimization
 Chair: Tamás Terlaky

Scientific Program

A powerful approach to solving difficult optimization problems is convex relaxation. In a typical application, the problem is first formulated as a cardinality-constrained linear program (LP) or rank-constrained semidefinite program (SDP), where the cardinality or rank corresponds to the target support size or dimension. Then, the non-convex cardinality or rank constraint is either dropped or replaced by a convex surrogate, thus resulting in a convex optimization problem. In this talk, we explore the use of a non-convex surrogate of the cardinality or rank function, namely the so-called Schatten quasi-norm. Although the resulting optimization problem is non-convex, we show, for many cases, that a first and second order critical point can be approximated to arbitrary accuracy in polynomial time by an interior-point algorithm. Moreover, we show that such a critical point is already sufficient for recovering the solution of the original problem in the target cardinality or dimension, if the input instance satisfies certain established uniqueness properties in the literature. Finally, our simulation results show that the proposed algorithm could achieve more accurate results than the standard LP or SDP relaxations of the problem. We also generalize and summarize our complexity analysis to more general non-convex optimization.

 Short Bio:
Scientific Program

Yinyu Ye is currently the K.T. Li Professor of Engineering at Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering, Stanford University. He is also the Director of the MS\&E Industrial Affiliates Program. He received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, China, and the M.S. and Ph.D. degrees in Engineering-Economic Systems and Operations Research from Stanford University. His current research interests include Continuous and Discrete Optimization, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric Distance Geometry, Dynamic Resource Allocation, and Stochastic and Robust Decision Making, etc. He is an INFORMS (The Institute for Operations Research and The Management Science) Fellow, and has received several academic awards including the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization, the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2006 Farkas Prize on Optimization, the 2009 IBM Faculty Award, etc.. He has supervised numerous doctoral students at Stanford who received the 2008 Nicholson Prize and the 2006 and 2010 INFORMS Optimization Prizes for Young Researchers.

 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage