Bound-constrained Optimization

Complexity results and active-set identification of a derivative-free method for bound-constrained problems

  • Andrea Brilli
  • Andrea Cristofari
  • Giampaolo Liuzzi
  • Stefano Lucidi
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , ,

    In this paper, we analyze a derivative-free line search method designed for bound-constrained problems. Our analysis demonstrates that this method exhibits a worst-case complexity comparable to other derivative-free methods for unconstrained and linearly constrained problems. In particular, when minimizing a function with $n$ variables, we prove that at most ${\cal O(n\epsilon^{-2})}$ iterations are needed to … Read more

    Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds constraints

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , ,

    A parametric class of trust-region algorithms for constrained nonconvex optimization is analyzed, where the objective function is never computed. By defining appropriate first-order stationarity criteria, we are able to extend the Adagrad method to the newly considered problem and retrieve the standard complexity rate of the projected gradient method that uses both the gradient and … Read more

    Model Construction for Convex-Constrained Derivative-Free Optimization

  • Lindon Roberts
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

    We develop a new approximation theory for linear and quadratic interpolation models, suitable for use in convex-constrained derivative-free optimization (DFO). Most existing model-based DFO methods for constrained problems assume the ability to construct sufficiently accurate approximations via interpolation, but the standard notions of accuracy (designed for unconstrained problems) may not be achievable by only sampling … Read more

    Lipschitz Based Lower Bound Construction for Surrogate Optimization

  • Mohammadsina Almasi
  • Hadis Anahideh
  • Jay Rosenberger
    • Categories Bound-constrained Optimization, Global Optimization, Global Optimization Applications Tags , , ,

    Bounds play a vital role in guiding optimization algorithms by enhancing convergence, improving solution quality, and quantifying optimality gaps. While Lipschitz-based lower bounds are well-established, their effectiveness is often constrained by the function’s topological properties. To address these limitations, we propose an approach that integrates nonlinear distance metrics with surrogate approximations, yielding more adaptive and … Read more

    Full-low evaluation methods for bound and linearly constrained derivative-free optimization

  • Clément W. Royer
  • Oumaima Sohab
  • Luis Nunes Vicente
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , ,

    Derivative-free optimization (DFO) consists in finding the best value of an objective function without relying on derivatives. To tackle such problems, one may build approximate derivatives, using for instance finite-difference estimates. One may also design algorithmic strategies that perform space exploration and seek improvement over the current point. The first type of strategy often provides … Read more

    Heuristic methods for noisy derivative-free bound-constrained mixed-integer optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Global Optimization Tags

    This paper introduces MATRS, a novel matrix adaptation trust-region strategy designed to solve noisy derivative-free mixed-integer optimization problems with simple bounds in low dimensions. MATRS operates through a repeated cycle of five phases: mutation, selection, recombination, trust-region, and mixed-integer, executed in this sequence. But if in the mutation phase a new best point (the point … Read more

    An active set method for bound-constrained optimization

  • Arnold Neumaier
  • Behzad Azmi
  • Morteza Kimiaei
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags

    In this paper, a class of algorithms is developed for bound-constrained optimization. The new scheme uses the gradient-free line search along bent search paths. Unlike traditional algorithms for bound-constrained optimization, our algorithm ensures that the reduced gradient becomes arbitrarily small. It is also proved that all strongly active variables are found and fixed after finitely … Read more

    On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Bound-constrained Optimization, Global Optimization, Quadratic Programming Tags , , ,

    Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

    Efficient composite heuristics for integer bound constrained noisy optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories Bound-constrained Optimization, Integer Programming, Optimization Software Benchmark Tags , , , ,

    This paper discusses a composite algorithm for bound constrained noisy derivative-free optimization problems with integer variables. This algorithm is an integer variant of the matrix adaptation evolution strategy. An integer derivative-free line search strategy along affine scaling matrix directions is used to generate candidate points. Each affine scaling matrix direction is a product of the … 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