  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.
