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

This paper studies the $$H^1$$ Sobolev seminorm of quadratic functions. The research is motivated by the least-norm interpolation that is widely used in derivative-free optimization. We express the $$H^1$$ seminorm of a quadratic function explicitly in terms of the Hessian and the gradient when the underlying domain is a ball. The seminorm gives new insights into least-norm interpolation. It clarifies the analytical and geometrical meaning of the objective function in least-norm interpolation. We employ the seminorm to study the extended symmetric Broyden update proposed by Powell. Numerical results show that the new thoery helps improve the performance of the update. Apart from the theoretical results, we propose a new method of comparing derivative-free solvers, which is more convincing than merely counting the numbers of function evaluations.

• Publication year

  2011

• Venue

  Mathematical programming

• Publication date

  2011-11-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10107-013-0679-3arXiv 1111.4576
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SID-PSM: A pattern search method guided by simplex derivatives for use in derivative-free optimization (version 1.3)

  2014cited by this paper
• Sobolev Spaces

  2013cited by this paper
• Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization

  2012influential reference
• Beyond symmetric Broyden for updating quadratic models in minimization without derivatives

  2012influential reference
• Implicit Filtering

  2011cited by this paper
• Introduction to derivative-free optimization

  2010influential reference
• Incorporating minimum Frobenius norm models in direct search

  2010influential reference
• The BOBYQA algorithm for bound constrained optimization without derivatives

  2009cited by this paper
• Boosters: A Derivative-Free Algorithm Based on Radial Basis Functions

  2009cited by this paper
• Using simplex gradients of nonsmooth functions in direct search methods

  2008cited by this paper
• Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems

  2008cited by this paper
• A derivative-free nonmonotone line-search technique for unconstrained optimization

  2008cited by this paper
• ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions

  2008cited by this paper
• MNH: A Derivative-Free Optimization Algorithm Using Minimal Norm Hessians

  2008influential reference
• Developments of NEWUOA for minimization without derivatives

  2008influential reference
• Using Sampling and Simplex Derivatives in Pattern Search Methods

  2007cited by this paper
• A New Derivative-Free Algorithm for the Medical Image Registration Problem

  2007cited by this paper
• Large-Scale Nonlinear Optimization

  2006cited by this paper
• The NEWUOA software for unconstrained optimization without derivatives

  2006influential reference
• DERIVATIVE-FREE OPTIMIZATION METHODS FOR HANDLING FIXED COSTS IN OPTIMAL GROUNDWATER REMEDIATION DESIGN

  2006cited by this paper
• CONDOR, a new parallel, constrained extension of Powell's UOBYQA algorithm: experimental results and comparison with the DFO algorithm

  2005cited by this paper
• Trust-region methods based on radial basis functions with application to biomedical imaging

  2005cited by this paper
• Least Frobenius norm updating of quadratic models that satisfy interpolation conditions

  2004influential reference
• On trust region methods for unconstrained minimization without derivatives

  2003cited by this paper
• CUTEr and SifDec: A constrained and unconstrained testing environment, revisited

  2003cited by this paper
• A Derivative-Free Algorithm based on Radial Basis Functions (RBF)

  2003cited by this paper
• Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods

  2003cited by this paper
• Wedge trust region methods for derivative free optimization

  2002cited by this paper
• UOBYQA: unconstrained optimization by quadratic approximation

  2002cited by this paper
• A brief introduction to implicit filtering

  2002cited by this paper
• Benchmarking optimization software with performance profiles

  2001cited by this paper
• Practical Methods of Optimization: Fletcher/Practical Methods of Optimization

  2000influential reference
• Trust Region Methods

  2000cited by this paper
• Direct-numerical and large-eddy simulations of a non-equilibrium turbulent Kolmogorov flow

  1999cited by this paper
• Superlinear Convergence and Implicit Filtering

  1999cited by this paper
• Direct search algorithms for optimization calculations

  1998cited by this paper
• A derivative free optimization algorithm in practice

  1998influential reference
• Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions

  1998influential reference
• Optimization Using Surrogate Objectives on a Helicopter Test Example

  1998cited by this paper
• Managing surrogate objectives to optimize a helicopter rotor design - Further experiments

  1998cited by this paper
• A rigorous framework for optimization of expensive functions by surrogates

  1998cited by this paper
• The Simplex Gradient and Noisy Optimization Problems

  1998cited by this paper
• On the convergence of derivative-free methods for unconstrained optimization

  1997influential reference
• Recent progress in unconstrained nonlinear optimization without derivatives

  1997influential reference
• An Algorithm using Quadratic Interpolation for Unconstrained Derivative Free Optimization

  1996influential reference
• An Implicit Filtering Algorithm for Optimization of Functions with Many Local Minima

  1995cited by this paper
• A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation

  1994cited by this paper
• Performance of a multifrontal scheme for partially separable optimization

  1994influential reference
• Lancelot: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A)

  1992influential reference
• Least Change Secant Updates for Quasi-Newton Methods

  1978cited by this paper
• Table errata: Algorithms for minimization without derivatives (Prentice-Hall, Englewood Cliffs, N. J., 1973)

  1975cited by this paper
• Algorithms for minimization without derivatives

  1974cited by this paper
• Function Minimization by Interpolation in a Data Table

  1973cited by this paper
• On the Local and Superlinear Convergence of Quasi-Newton Methods

  1973influential reference
• A Modification of Davidon's Minimization Method to Accept Difference Approximations of Derivatives

  1967cited by this paper
• A Simplex Method for Function Minimization

  1965influential reference

• A Derivative-Free Method Using a New Underdetermined Quadratic Interpolation Model

  2025cites this paper
• A novel numerical method tailored for unconstrained optimization problems

  2025cites this paper
• ReMU: Regional Minimal Updating for Model-Based Derivative-Free Optimization

  2025cites this paper
• A spectral Levenberg-Marquardt-Deflation method for multiple solutions of semilinear elliptic systems

  2025cites this paper
• Model Construction for Convex-Constrained Derivative-Free Optimization

  2024cites this paper
• An optimal interpolation set for model-based derivative-free optimization methods

  2023cites this paper
• PDFO: a cross-platform package for Powell’s derivative-free optimization solvers

  2023cites this paper
• Least $H^2$ Norm Updating Quadratic Interpolation Model Function for Derivative-free Trust-region Algorithms

  2023influential citation
• practices for comparing optimization algorithms

  2022cites this paper
• Anisotropic Diffusion in Consensus-Based Optimization on the Sphere

  2021cites this paper
• Introduction

  2021cites this paper
• A derivative-free algorithm for spherically constrained optimization

  2020cites this paper
• A Derivative-Free Geometric Algorithm for Optimization on a Sphere

  2020cites this paper
• Derivative-free optimization methods

  2019cites this paper
• Hill-Climbing Algorithm with a Stick for Unconstrained Optimization Problems

  2017cites this paper
• Best practices for comparing optimization algorithms

  2017cites this paper
• Recent advances in trust region algorithms

  2015influential citation
• Notes on the Sobolev (Semi)Norms of Quadratic Functions

  2012cites this paper