Elhoucine Bergou

A Nonmonotone Matrix-Free Algorithm for Nonlinear Equality-Constrained Least-Squares Problems

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares

    Least squares form one of the most prominent classes of optimization problems, with numerous applications in scientific computing and data fitting. When such formulations aim at modeling complex systems, the optimization process must account for nonlinear dynamics by incorporating constraints. In addition, these systems often incorporate a large number of variables, which increases the difficulty … Read more

    Complexity iteration analysis for stongly convex multi-objective optimization using a Newton path-following procedure

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
    • Categories Unconstrained Optimization

    In this note we consider the iteration complexity of solving strongly convex multi objective optimization. We discuss the precise meaning of this problem, and indicate it is loosely defined, but the most natural notion is to find a set of Pareto optimal points across a grid of scalarized problems. We derive that in most cases, … Read more

    A Subsampling Line-Search Method with Second-Order Results

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
  • V. Kunc
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    In many contemporary optimization problems such as those arising in machine learning, it can be computationally challenging or even infeasible to evaluate an entire function or its derivatives. This motivates the use of stochastic algorithms that sample problem data, which can jeopardize the guarantees obtained through classical globalization techniques in optimization such as a trust … Read more

    A stochastic Levenberg-Marquardt method using random models with complexity results and application to data assimilation

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Clément W. Royer
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    Globally convergent variants of the Gauss-Newton algorithm are often the methods of choice to tackle nonlinear least-squares problems. Among such frameworks, Levenberg-Marquardt and trust-region methods are two well-established, similar paradigms. Both schemes have been studied when the Gauss-Newton model is replaced by a random model that is only accurate with a given probability. Trust-region schemes … Read more

    A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , ,

    Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method … Read more

    Convergence and Complexity Analysis of a Levenberg-Marquardt Algorithm for Inverse Problems

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
    • Categories Nonlinear Optimization, Unconstrained Optimization

    The Levenberg-Marquardt algorithm is one of the most popular algorithms for finding the solution of nonlinear least squares problems. Across different modified variations of the basic procedure, the algorithm enjoys global convergence, a competitive worst case iteration complexity rate, and a guaranteed rate of local convergence for both zero and nonzero small residual problems, under … Read more

    On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , , , ,

    We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The … Read more

    Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation

  • Elhoucine Bergou
  • Serge Gratton
  • Luis Nunes Vicente
    • Categories Applications - Science and Engineering, Nonlinear Systems and Least-Squares, Stochastic Programming Tags , , , , , , ,

    The Levenberg-Marquardt algorithm is one of the most popular algorithms for the solution of nonlinear least squares problems. Motivated by the problem structure in data assimilation, we consider in this paper the extension of the classical Levenberg-Marquardt algorithm to the scenarios where the linearized least squares subproblems are solved inexactly and/or the gradient model is … Read more