Sanjay Mehrotra (left), Afonso Bandeira, and Simge Küçükyavuz.
Citation
Afonso Bandeira (Princeton University, formerly University of Coimbra) is selected as the winner of the 2013 INFORMS Optimization Society Student Paper Prize for his paper "Computation of Sparse Low Degree Interpolating Polynomials and their Application to Derivative-Free Optimization", Mathematical Programming, 134 (2012) 223-257, with Katya Scheinberg and Luis Nunes Vicente.
The novelty of this paper is in the application of sparse signal recovery to the construction of polynomial interpolation models of functions with sparse Hessians. In general, constructing an accurate second-order interpolation model of a smooth function requires O(n^2) samples. Bandeira et al. show that if the Hessian contains only s nonzeros, then using sparse recovery via l-1 minimization, one can construct an accurate second-order model using only O(s log^4(n)) samples. When applied to derivative-free optimization, the techniques developed significantly reduce the number of evaluations necessary for function approximation via sampling, and thus accelerate the optimization of complex systems such as those whose objective functions are calculated by a costly black-box simulation.
Selection Committee
Santanu S. Dey, Simge Küçükyavuz (Chair), Guanghui Lan