Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

CORMSIS Seminar Event

16:00 - 17:00
30 October 2014
Building 02 Room 3041

For more information regarding this event, please telephone Houdou Qi on +23683 or email .

Event details

Probability, Polynomial and Optimization: From Coin Tossing to Approximation Algorithms

Coin tossing is a naive, simple, but sometimes powerful method in statistics and the design of randomized algorithms. In a typical application, random sampling based on coin tossing can be applied to estimate an extreme value, say maximum, of a function f over a set S. To do so, one may select a simpler (even finite) subset S0, randomly take some samples over S0 for a number of times, and pick the best sample. The hope is to find a good approximate solution with reasonable chance. In this talk, we set out to present a number of scenarios for f, S and S0 where certain probability bounds can be established, leading to a quality assurance of the procedure. For example, if f is a homogeneous polynomial of degree d in n variables and F is its corresponding symmetric tensor, and x_i (i = 1, 2, ..., n) are random variables taking 1 or -1 based on independent coin tossing, then Prob{ f(x_1, x_2, ..., x_n) > c1 n^{-d/2} \|F\|_1 } > c2, where c1, c2 are two positive universal constants. Several new inequalities concerning probabilities of the above nature are presented. Moreover, the bounds are tight in most cases. Applications of the results in polynomial optimization are discussed as well.

Speaker information

Dr Zhening Li,Zhening Li is a lecturer in the Department of Mathematics and a member of the Centre for Operational Research and Logistics in the University of Portsmouth. He received BSc degree in Mathematics from Peking University in 1999, MA degree in Mathematics and Financial Engineering from York University in 2003, and PhD degree in Systems Engineering and Engineering Management from The Chinese University of Hong Kong in 2011. Zhening's research is at the interface of Operations Research and Mathematics. In particular, he works on theoretical and computational optimization, algorithm design and analysis, with applications in finance, engineering, game theory, etc. His recent research focuses on algorithms and applications of polynomial optimization, theory and computation methods for tensor optimization models.

Privacy Settings