Optimization Online


Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization

A. S. Bandeira (ajsb***at***math.princeton.edu)
K. Scheinberg (katyas***at***lehigh.edu)
L. N. Vicente (lnv***at***mat.uc.pt)

Abstract: Interpolation-based trust-region methods are an important class of algorithms for Derivative-Free Optimization which rely on locally approximating an objective function by quadratic polynomial interpolation models, frequently built from less points than there are basis components. Often, in practical applications, the contribution of the problem variables to the objective function is such that many pairwise correlations between variables are negligible, implying, in the smooth case, a sparse structure in the Hessian matrix. To be able to exploit Hessian sparsity, existing optimization approaches require the knowledge of the sparsity structure. The goal of this paper is to develop and analyze a method where the sparse models are constructed automatically. The sparse recovery theory developed recently in the field of compressed sensing characterizes conditions under which a sparse vector can be accurately recovered from few random measurements. Such a recovery is achieved by minimizing the l1-norm of a vector subject to the measurements constraints. We suggest an approach for building sparse quadratic polynomial interpolation models by minimizing the l1-norm of the entries of the model Hessian subject to the interpolation conditions. We show that this procedure recovers accurate models when the function Hessian is sparse, using relatively few randomly selected sample points. Motivated by this result, we developed a practical interpolation-based trust-region method using deterministic sample sets and minimum l1-norm quadratic models. Our computational results show that the new approach exhibits a promising numerical performance both in the general case and in the sparse one.

Keywords: Derivative-free optimization, interpolation-based trust-region methods, random sampling, sparse recovery, compressed sensing, l1-minimization.

Category 1: Convex and Nonsmooth Optimization

Category 2: Nonlinear Optimization

Citation: preprint 11-14, Dept. Mathematics, Univ. Coimbra

Download: [PDF]

Entry Submitted: 04/15/2011
Entry Accepted: 04/15/2011
Entry Last Modified: 06/24/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society