Serge Gratton – Page 3 – Optimization Online

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

Published: 2017/04/26

Unconstrained Optimization adaptive regularized framework using cubics, conjugate gradient method, energy norm, krylov subspace methods, line search algorithm, nonlinear optimization, trust-region methods, unconstrained optimization

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

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

Published: 2017/04/21, Updated: 2018/02/21

Serge Gratton

Clément W. Royer

Luis Nunes Vicente

Nonlinear Optimization, Unconstrained Optimization decoupling, first-order stationarity, global rates, second-order stationarity, trust-region methods, worst-case complexity

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

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

Published: 2017/02/17

Stochastic Programming, Unconstrained Optimization global rates, probabilistic models, trust-region methods, worst-case complexity

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

Direct search based on probabilistic feasible descent for bound and linearly constrained problems

Published: 2017/02/17

Bound-constrained Optimization, Nonlinear Optimization, Stochastic Programming bounds, derivative-free optimization, direct search, linear constraints, positive generators, probabilistic feasible descent

Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region and typically consist of positive generators of approximate tangent cones (which then … Read more

A second-order globally convergent direct-search method and its worst-case complexity

Published: 2015/06/04

Serge Gratton

Clément W. Royer

Luis Nunes Vicente

Nonlinear Optimization, Unconstrained Optimization derivative-free optimization, direct search, second-order, worst-case complexity

Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest … Read more

A Parallel Evolution Strategy for an Earth Imaging Problem in Geophysics

Published: 2015/01/15

Basic Sciences Applications, Global Optimization Applications, Optimization of Simulated Systems earth imaging, evolution strategy (es), full-waveform inversion (fwi), global convergence, high performance computing (hpc), inverse problems, search space reduction

In this paper we propose a new way to compute a warm starting point for a challenging global optimization problem related to Earth imaging in geophysics. The warm start consists of a velocity model that approximately solves a full-waveform inverse problem at low frequency. Our motivation arises from the availability of massively parallel computing platforms … Read more

Globally Convergent Evolution Strategies for Constrained Optimization.

Published: 2014/07/15

Youssef Diouane

Serge Gratton

Luis Nunes Vicente

Constrained Nonlinear Optimization bound and linear constraints, constrained optimization, evolution strategies, extreme barrier function, global convergence, projection, quadratic models, search step

In this work we propose, analyze, and test algorithms for linearly constrained optimization when no use of derivatives of the objective function is made. The proposed methodology is built upon the globally convergent evolution strategies previously introduced by the authors for unconstrained optimization. Two approaches are encompassed to handle the constraints. In a first approach, … Read more

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

Published: 2014/06/27

Elhoucine Bergou

Serge Gratton

Luis Nunes Vicente

Applications - Science and Engineering, Nonlinear Systems and Least-Squares, Stochastic Programming ensemble kalman filter/smoother, inexactness, kalman filter/smoother, levenberg-marquardt method, nonlinear least squares, random models, regularization, variational data assimilation

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

Direct search based on probabilistic descent

Published: 2014/03/19

Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming derivative-free optimization, direct search, polling, positive spanning sets, probabilistic descent, random directions

Direct-search methods are a class of popular derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions. When applied to the minimization of smooth functions, the polling directions are typically taken from positive spanning sets which in turn must have at least n+1 vectors in an n-dimensional … Read more

Quasi-Newton updates with weighted secant equations

Published: 2013/10/19

Serge Gratton

Vincent Malmedy

Philippe L. Toint

Nonlinear Systems and Least-Squares, Unconstrained Optimization multisecant methods, nonlinear optimization, quasi-newton methods

We provide a formula for variational quasi-Newton updates with multiple weighted secant equations. The derivation of the formula leads to a Sylvester equation in the correction matrix. Examples are given. Citation Report naXys-09-2013, Namur Centre for Complex Systems, Unibersity of Namur, Namur (Belgium) Article Download View Quasi-Newton updates with weighted secant equations