香港理工大学张在坤研究助理教授学术报告预告

报告题目：The Worst Case Complexity of Direct Search and beyond

报告摘要：Direct-search methods are a class of derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions, which are typically taken from positive spanning sets consisting of at least $n+1$ vectors in an $n$-dimensional variable space.

We introduce the worst case complexity theory of direct search, and discuss how to choose the positive spanning set so as to minimize the complexity bound. The discussion leads us to a long-standing open problem in Discrete Geometry. We present a recent result on this problem, which enables us to establish the optimal order for the worst case complexity of direct search.

After obtaining the optimal bound, we show how to achieve even better complexity bound by randomization. We prove that polling along two random directions in each iteration is sufficient to guarantee the convergence of direct search for any dimension, and the resultant algorithm enjoys lower complexity both in theory and in practice. Our analysis relies on martingale theory and large deviation techniques. 

报告时间：2016年6月8日（周三）下午15：30-16：30

报告地点：教学二楼2126

欢迎教师和同学参加！

报告人简介：2012年博士毕业于中国科学院，2012-2014年在葡萄牙Coimbra大学作博士后，2014-2016年在法国图卢兹IRIT-ENSEEIHT 作博士后。目前有数篇论文在Math. Program.，SIAM J. Optim等知名国际期刊发表。