derivative-free optimization

Worst-case evaluation complexity of a derivative-free quadratic regularization method

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization Tags , , ,

    This short paper presents a derivative-free quadratic regularization method for unconstrained minimization of a smooth function with Lipschitz continuous gradient. At each iteration, trial points are computed by minimizing a quadratic regularization of a local model of the objective function. The models are based on forward finite-difference gradient approximations. By using a suitable acceptance condition … Read more

    Direct search based on probabilistic descent in reduced spaces

  • Lindon Roberts
  • Clément W. Royer
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Derivative-free algorithms seek the minimum value of a given objective function without using any derivative information. The performance of these methods often worsen as the dimension increases, a phenomenon predicted by their worst-case complexity guarantees. Nevertheless, recent algorithmic proposals have shown that incorporating randomization into otherwise deterministic frameworks could alleviate this effect for direct-search methods. … Read more

    A general mathematical framework for constrained mixed-variable blackbox optimization problems with meta and categorical variables

  • Charles Audet
  • Edward Hallé-Hannan
  • Sébastien Le Digabel
    • Categories Nonlinear Optimization Tags , , , ,

    A mathematical framework for modelling constrained mixed-variable optimization problems is presented in a blackbox optimization context. The framework introduces a new notation and allows solution strategies. The notation framework allows meta and categorical variables to be explicitly and efficiently modelled, which facilitates the solution of such problems. The new term meta variables is used to … Read more

    Handling of constraints in multiobjective blackbox optimization

  • Jean Bigeon
  • Sébastien Le Digabel
  • Ludovic Salomon
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    This work proposes the integration of two new constraint-handling approaches into the blackbox constrained multiobjective optimization algorithm DMulti-MADS, an extension of the Mesh Adaptive Direct Search (MADS) algorithm for single-objective constrained optimization. The constraints are aggregated into a single constraint violation function which is used either in a two-phase approach, where research of a feasible … Read more

    Exploiting Prior Function Evaluations in Derivative-Free Optimization

  • Frank E. Curtis
  • Shima Dezfulian
  • Andreas Wächter
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , ,

    A derivative-free optimization (DFO) algorithm is presented. The distinguishing feature of the algorithm is that it allows for the use of function values that have been made available through prior runs of a DFO algorithm for solving prior related optimization problems. Applications in which sequences of related optimization problems are solved such that the proposed … Read more

    Stochastic trust-region and direct-search methods: A weak tail bound condition and reduced sample sizing

  • Francesco Rinaldi
  • Luis Nunes Vicente
  • Damiano Zeffiro
    • Categories Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , ,

    Using tail bounds, we introduce a new probabilistic condition for function estimation in stochastic derivative-free optimization which leads to a reduction in the number of samples and eases algorithmic analyses. Moreover, we develop simple stochastic direct-search and trust-region methods for the optimization of a potentially non-smooth function whose values can only be estimated via stochastic … Read more

    Retraction based Direct Search Methods for Derivative Free Riemannian Optimization

  • Vyacheslav Kungurtsev
  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    Direct search methods represent a robust and reliable class of algorithms for solving black-box optimization problems. In this paper, we explore the application of those strategies to Riemannian optimization, wherein minimization is to be performed with respect to variables restricted to lie on a manifold. More specifically, we consider classic and line search extrapolated variants … Read more

    Hierarchically constrained blackbox optimization

  • Stéphane Alarie
  • Charles Audet
  • Paulin Jacquot
  • Sébastien Le Digabel
    • Categories Nonlinear Optimization Tags , ,

    In blackbox optimization, evaluation of the objective and constraint functions is time consuming. In some situations, constraint values may be evaluated independently or sequentially. The present work proposes and compares two strategies to define a hierarchical ordering of the constraints and to interrupt the evaluation process at a trial point when it is detected that … Read more

    Model-Based Derivative-Free Methods for Convex-Constrained Optimization

  • Matthew Hough
  • Lindon Roberts
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We present a model-based derivative-free method for optimization subject to general convex constraints, which we assume are unrelaxable and accessed only through a projection operator that is cheap to evaluate. We prove global convergence and a worst-case complexity of $O(\epsilon^{-2})$ iterations and objective evaluations for nonconvex functions, matching results for the unconstrained case. We introduce … Read more

    Adaptive Finite-Difference Interval Estimation for Noisy Derivative-Free Optimization

  • Hao-Jun Shi
  • Yuchen Xie
  • Melody Xuan
  • Jorge Nocedal
    • Categories Nonlinear Optimization Tags , , , ,

    A common approach for minimizing a smooth nonlinear function is to employ finite-difference approximations to the gradient. While this can be easily performed when no error is present within the function evaluations, when the function is noisy, the optimal choice requires information about the noise level and higher-order derivatives of the function, which is often … Read more