Bound-constrained Optimization

Polling Set Construction and Worst-Case Complexity for Direct Search under Polyhedral Convex Constraints

  • Lindon Roberts
  • Clément W. Royer
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Optimization

    Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is … Read more

    A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization

  • Dânâ Davar
  • Geovani Nunes Grapiglia
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. The proposed method does not require computing an approximate stationarity measure. For nonconvex problems, we establish a worst-case complexity bound of \(\mathcal{O}\!\left(n\left(\frac{L}{\sigma}\epsilon\right)^{-2}\right)\) function evaluations for the method to reach an \(\left(\frac{L}{\sigma}\epsilon\right)\)-approximate stationary point, where \(n\) is the … Read more

    Visiting exactly once all the vertices of {0,1,2}^3 with a 13-segment path that avoids self-crossing

  • Marco Ripà
    • Categories Bound-constrained Optimization, Combinatorial Optimization, Graphs and Matroids Tags , , , , , ,

    In the Euclidean space \(\mathbb{R}^3\), we ask whether one can visit each of the \(27\) vertices of the grid \(G_3:=\{0,1,2\}^3\) exactly once using as few straight-line segments, connected end to end, as possible (an optimal polygonal chain). We give a constructive proof that there exists a \(13\)-segment perfect simple path (i.e., an optimal chain that … Read more

    AS-BOX: Additional Sampling Method for Weighted Sum Problems with Box Constraints

  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Tijana Ostojić
  • Nemanja Vučićević
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , , , ,

    A class of optimization problems characterized by a weighted finite-sum objective function subject to box constraints is considered. We propose a novel stochastic optimization method, named AS-BOX (Additional Sampling for BOX constraints), that combines projected gradient directions with adaptive variable sample size strategies and nonmonotone line search. The method dynamically adjusts the batch size based … Read more

    Active-set Newton-MR methods for nonconvex optimization problems with bound constraints

  • Ernesto G. Birgin
  • Geovani Nunes Grapiglia
  • Diaulas S. Marcondes
    • Categories Bound-constrained Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    This paper presents active-set methods for minimizing nonconvex twice-continuously differentiable functions subject to bound constraints. Within the faces of the feasible set, we employ descent methods with Armijo line search, utilizing approximated Newton directions obtained through the Minimum Residual (MINRES) method. To escape the faces, we investigate the use of the Spectral Projected Gradient (SPG) … Read more

    Recursive Bound-Constrained AdaGrad with Applications to Multilevel and Domain Decomposition Minimization

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

    Two OFFO (Objective-Function Free Optimization) noise tolerant algorithms are presented that handle bound constraints, inexact gradients and use second-order information when available. The first is a multi-level method exploiting a hierarchical description of the problem and the second is a domain-decomposition method covering the standard addditive Schwarz decompositions. Both are generalizations of the first-order AdaGrad … Read more

    Fast Stochastic Second-Order Adagrad for Nonconvex Bound-Constrained Optimization

  • Stefania Bellavia
  • Serge Gratton
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , , ,

    ADAGB2, a generalization of the Adagrad algorithm for stochastic optimization is introduced, which is also applicable to bound-constrained problems and capable of using second-order information when available. It is shown that, given  delta in (0,1) and epsilon in (0,1], the ADAGB2 algorithm needs at most O(epsilon^{-2}) iterations to ensure an epsilon-approximate first-order critical point of … Read more

    A Rank-One-Update Method for the Training of Support Vector Machines

  • Florian Jarre
    • Categories Bound-constrained Optimization, Convex Optimization, Data Science Algorithms Tags , ,

    This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more

    A class of diagonal quasi-Newton penalty decomposition algorithms for sparse bound-constrained nonconvex optimization

  • Ahmad Mousavi
  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    This paper discusses an improved quasi-Newton penalty decomposition algorithm for the cardinality bound-constrained optimization problems whose simple bounds on the variables are assumed to be finite. Until an approximate stationary point is found, this algorithm approximates the solutions of a sequence of penalty subproblems by a two-block decomposition scheme. This scheme finds an approximate solution … Read more

    Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming

  • Kurt M. Anstreicher
  • Diane Puges
    • Categories Bound-constrained Optimization, Global Optimization Theory, Quadratic Programming Tags , ,

    Let Box_n = {x in R^n : 0<= x <= e }, and let QPB_n denote the convex hull of {(1, x’)'(1, x’) : x  in Box_n}. The quadratic programming problem min{x’Q x + q’x : x in Box_n} where Q is not positive semidefinite (PSD), is equivalent to a linear optimization problem over QPB_n … Read more