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

DOI10.1007/S10107-012-0578-ZzbMath1254.65072DBLPjournals/mp/BandeiraSV12arXiv1306.5729OpenAlexW2106120648WikidataQ58040551 ScholiaQ58040551MaRDI QIDQ715240

Michael Martin A. S. Bandeira, Luis Nunes Vicente, Katya Scheinberg

Publication date: 2 November 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.5729

zbMATH Keywords

algorithmnumerical examplesrandom samplingderivative-free optimizationsparse recoverycompressed sensing\(\ell _{1}\)-minimizationinterpolation-based trust-region methodssparse quadratic polynomial interpolation models

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Derivative-free methods and methods using generalized derivatives (90C56) Interior-point methods (90C51)

Related Items (23)

Gradient and diagonal Hessian approximations using quadratic interpolation models and aligned regular bases ⋮ On the numerical performance of finite-difference-based methods for derivative-free optimization ⋮ Full-low evaluation methods for derivative-free optimization ⋮ A theoretical and empirical comparison of gradient approximations in derivative-free optimization ⋮ A Stochastic Levenberg--Marquardt Method Using Random Models with Complexity Results ⋮ Anisotropic Diffusion in Consensus-Based Optimization on the Sphere ⋮ Scalable subspace methods for derivative-free nonlinear least-squares optimization ⋮ Sobolev seminorm of quadratic functions with applications to derivative-free optimization ⋮ Optimization by moving ridge functions: derivative-free optimization for computationally intensive functions ⋮ A subset-selection-based derivative-free optimization algorithm for dynamic operation optimization in a steel-making process ⋮ Partial \(S\)-goodness for partially sparse signal recovery ⋮ Restricted \(p\)-isometry properties of partially sparse signal recovery ⋮ A Derivative-Free Trust-Region Algorithm for the Optimization of Functions Smoothed via Gaussian Convolution Using Adaptive Multiple Importance Sampling ⋮ Optimality analysis on partial \(l_1\)-minimization recovery ⋮ A surrogate management framework using rigorous trust-region steps ⋮ Derivative-free separable quadratic modeling and cubic regularization for unconstrained optimization ⋮ Trust-Region Methods for the Derivative-Free Optimization of Nonsmooth Black-Box Functions ⋮ A second-order globally convergent direct-search method and its worst-case complexity ⋮ Trust-Region Methods Without Using Derivatives: Worst Case Complexity and the NonSmooth Case ⋮ Derivative-free optimization methods ⋮ Uniqueness Conditions for A Class of ℓ₀-Minimization Problems ⋮ A derivative-free trust-funnel method for equality-constrained nonlinear optimization ⋮ Recent advances in trust region algorithms

Uses Software

• Unnamed Item
• CUTEr
• SifDec
• LIPSOL
• DFO
• COBYLA2
• GQTPAR
• DFO-TRNS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse Legendre expansions via \(\ell_1\)-minimization
• The road to deterministic matrices with the restricted isometry property
• The restricted isometry property and its implications for compressed sensing
• A simple proof of the restricted isometry property for random matrices
• On trust region methods for unconstrained minimization without derivatives
• Second-order cone programming
• Least Frobenius norm updating of quadratic models that satisfy interpolation conditions
• A short note on compressed sensing with partially known signal support
• Stability and instance optimality for Gaussian measurements in compressed sensing
• Self-Correcting Geometry in Model-Based Algorithms for Derivative-Free Unconstrained Optimization
• An active-set trust-region method for derivative-free nonlinear bound-constrained optimization
• Computing a Trust Region Step
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On the geometry phase in model-based algorithms for derivative-free optimization
• Introduction to Derivative-Free Optimization
• Solving large-scale linear programs by interior-point methods under the Matlab^∗Environment^†
• Trust Region Methods
• Modified-CS: Modifying Compressive Sensing for Problems With Partially Known Support
• Global Convergence of General Derivative-Free Trust-Region Algorithms to First- and Second-Order Critical Points
• CUTEr and SifDec
• Optimality Measures for Performance Profiles
• Optimizing partially separable functions without derivatives
• Benchmarking optimization software with performance profiles.

This page was built for publication: Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization