Unconstrained Optimization

A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyzes of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order … Read more

    Automatic Differentiation of the Open CASCADE Technology CAD System and its coupling with an Adjoint CFD Solver

  • Salvatore Auriemma
  • Herve Legrand
  • Mladen Banovic
  • Jens-Dominik Müller
  • Orest Mykhaskiv
  • Andrea Walther
    • Categories Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , ,

    Automatic Differentiation (AD) is applied to the open-source CAD system Open CASCADE Technology using the AD software tool ADOL-C (Automatic Differentiation by OverLoading in C++). The differentiated CAD system is coupled with a discrete adjoint CFD solver, thus providing the first example of a complete differentiated design chain built from generic, multi-purpose tools. The design … Read more

    BFGS convergence to nonsmooth minimizers of convex functions

  • Jiayi Guo
  • Adrian Lewis
    • Categories Nonsmooth Optimization, Unconstrained Optimization

    The popular BFGS quasi-Newton minimization algorithm under reasonable conditions converges globally on smooth convex functions. This result was proved by Powell in 1976: we consider its implications for functions that are not smooth. In particular, an analogous convergence result holds for functions, like the Euclidean norm, that are nonsmooth at the minimizer. CitationManuscript: School of … Read more

    Exploiting Negative Curvature in Deterministic and Stochastic Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although some prior work has established convergence results for algorithms that integrate both descent and negative curvature directions, there has not yet been numerical evidence showing that such methods offer significant performance improvements. In … Read more

    Complexity and global rates of trust-region methods based on probabilistic models

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    Trust-region algorithms have been proved to globally converge with probability one when the accuracy of the trust-region models is imposed with a certain probability conditioning on the iteration history. In this paper, we study their complexity, providing global rates and worst case complexity bounds on the number of iterations (with overwhelmingly high probability), for both … Read more

    On the steplength selection in gradient methods for unconstrained optimization

  • Daniela di Serafino
  • Gerardo Toraldo
  • Luca Zanni
  • Valeria Ruggiero
    • Categories Unconstrained Optimization Tags , ,

    The seminal paper by Barzilai and Borwein [IMA J. Numer. Anal. 8 (1988)] has given rise to an extensive investigation aimed at developing effective gradient methods, able to deal with large-scale optimization problems. Several steplength rules have been first designed for unconstrained quadratic problems and then extended to general nonlinear problems; these rules share the … Read more

    Optimization Algorithms for Data Analysis

  • Stephen Wright
    • Categories Data-Mining, Nonsmooth Optimization, Unconstrained Optimization Tags ,

    We describe the fundamentals of algorithms for minimizing a smooth nonlinear function, and extensions of these methods to the sum of a smooth function and a convex nonsmooth function. Such objective functions are ubiquitous in data analysis applications, as we illustrate using several examples. We discuss methods that make use of gradient (first-order) information about … Read more

    On the Existence of Pareto Solutions for Polynomial Vector Optimization Problems

  • Do Sang Kim
  • Tiên-So'n Pham
  • Nguyen Van Tuyen
    • Categories Multi-Criteria Optimization, Unconstrained Optimization Tags , , , , ,

    We are interested in the existence of Pareto solutions to the vector optimization problem $$\text{\rm Min}_{\,\mathbb{R}^m_+} \{f(x) \,|\, x\in \mathbb{R}^n\},$$ where $f\colon\mathbb{R}^n\to \mathbb{R}^m$ is a polynomial map. By using the {\em tangency variety} of $f$ we first construct a semi-algebraic set of dimension at most $m – 1$ containing the set of Pareto values of … Read more

    Multilevel Optimization Methods: Convergence and Problem Structure

  • Chin Pang Ho
  • Panos Parpas
    • Categories Convex Optimization, Unconstrained Optimization

    Building upon multigrid methods, the framework of multilevel optimization methods was developed to solve structured optimization problems, including problems in optimal control, image processing, etc. In this paper, we give a broader view of the multilevel framework and establish some connections between multilevel algorithms and the other approaches. An interesting case of the so called … Read more

    Quadratic regularization with cubic descent for unconstrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Unconstrained Optimization Tags , , , ,

    Cubic-regularization and trust-region methods with worst case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. … Read more