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

Content Provider	Springer Nature Link
Author	Scheinberg, K. Vicente, L. N. Bandeira, A. S.
Copyright Year	2012
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 ℓ 1-norm of a vector subject to the measurements constraints. We suggest an approach for building sparse quadratic polynomial interpolation models by minimizing the ℓ 1-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 ℓ 1-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.
Ending Page	257
Page Count	35
Starting Page	223
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1
Volume Number	134
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-07-08
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Random sampling Applications of mathematical programming Interpolation-based trust-region methods Theoretical, Mathematical and Computational Physics ℓ 1-Minimization Derivative-free optimization Derivative-free methods and methods using generalized derivatives Interpolation Mathematical Methods in Physics Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Sparse recovery Nonlinear programming Combinatorics Compressed sensing
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Geometry of interpolation sets in derivative free optimization

On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization

Sobolev seminorm of quadratic functions with applications to derivative-free optimization

ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions

A globally convergent trust-region algorithm for unconstrained derivative-free optimization

Worst case complexity of direct search under convexity

Analysis of direct searches for discontinuous functions

Verifiable conditions of ℓ 1-recovery for sparse signals with sign restrictions

Global Convergence of Radial Basis Function Trust-Region Algorithms for Derivative-Free Optimization

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

Similar Documents

Geometry of interpolation sets in derivative free optimization

On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization

Sobolev seminorm of quadratic functions with applications to derivative-free optimization

ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions

A globally convergent trust-region algorithm for unconstrained derivative-free optimization

Worst case complexity of direct search under convexity

Analysis of direct searches for discontinuous functions

Verifiable conditions of ℓ 1-recovery for sparse signals with sign restrictions

Global Convergence of Radial Basis Function Trust-Region Algorithms for Derivative-Free Optimization

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