-------------------------------------------------------------------------------------------------------------------

 

 

      Department of Systems Engineering and Engineering Management

                             The Chinese University of Hong Kong

 

-------------------------------------------------------------------------------------------------------------------

Speaker:  Prof. Zaikun Zhang, Hong Kong PolyU

 

 

Title:  The Worst Case Complexity of Direct Search and beyond

 

 

Abstract:

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.

This talk is based on joint works with M. Dodangeh, S. Gratton, C. W. Royer, and L. N. Vicente. 

 

 

Short bio:

Zaikun Zhang got his PhD in 2012 from Chinese Academy of Sciences under the supervision of Professor Ya-Xiang Yuan. Then he worked as a postdoc at University of Coimbra (Coimbra, Portugal) from 2012 to 2014, and at IRIT-ENSEEIHT (Toulouse, France) from 2014 to 2016. He is now a Research Assistant Professor at the Department of Applied Mathematics of Hong Kong Polytechnic University. He works on optimization theory and algorithms, and his primary interests include derivative-free methods, randomized methods, and optimization based on inaccurate information.

 

 

This seminar is hosted by Prof. Shiqian Ma.

 

 

Venue: Room 1009,

      William M.W. Mong Engineering Building (ERB),

      (Engineering Building Complex Phase 2)

      The Chinese University of Hong Kong.