IE-OPIM Joint Seminar 22 October 2014 at 13.40 at FENS G032
From Farkas Theorem to the S-Lemma – Hidden Convexity inside the Nonconvex
By Ruey-Lin Sheu
Abstract: In this talk, linear programming and its duality theorem will be re-visited from the view point of the famous Farkas Lemma. The reason for doing so is due to recent developments for solving non-convex quadratic optimization problems via semi-definite programming with no relaxation gap. As the result, many once difficult non-convex quadratic programming problems are identified to be in Class P and can now be solved in polynomial time. The main bridge is connected from Farkas lemma, to Farkas Theorem, and to the S-lemma. Although the proof for the S-lemma is highly non-trivial and technical, its power for solving hard-core problems with just a few lines of formulae should be witnesssed. The audiences are invited to see the most contemporary progresses in nonlinear optimization.
Bio: Ruey-Lin Sheu received his BS in Mathematics at Tsing-Hua University (Hsin-Chu, Taiwan), and both his MS degree (in 1991) and Ph.D. degree (in 1992) in Operations Research at North Carolina State University (Raleigh, USA). After graduation, he first worked with AT&T Bell Laboratories (Holmdel, New Jersey) as a Member of Technical Staff on an airline crew scheduling problem. Then he went back to Taiwan joining with the Department of Mathematics at National Cheng-Kung University (Tainan, Taiwan) and later became the department chair (2008 - 2012). He has a broad interest in many areas of optimization, including linear/nonlinear programming, non-convex quadratic programming, fractional programming, networks and discrete optimization. He has served as an associate editor of the Journal of Global Optimization since 2006.