nonlinear optimization

Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

  • Coralia Cartis
  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth nonconvex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this … Read more

    An Adaptive Augmented Lagrangian Method for Large-Scale Constrained Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Hao Jiang
    • Categories Nonlinear Optimization Tags , , , , ,

    We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented … Read more

    How much patience do you have? A worst-case perspective on smooth nonconvex optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The paper presents a survey of recent results in the field of worst-case complexity of algorithms for nonlinear (and possibly nonconvex) smooth optimization. Both constrained and unconstrained case are considered. Article Download View How much patience do you have? A worst-case perspective on smooth nonconvex optimization

    On the complexity of the steepest-descent with exact linesearches

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The worst-case complexity of the steepest-descent algorithm with exact linesearches for unconstrained smooth optimization is analyzed, and it is shown that the number of iterations of this algorithm which may be necessary to find an iterate at which the norm of the objective function’s gradient is less that a prescribed $\epsilon$ is, essentially, a multiple … Read more

    Using Inexact Gradients in a Multilevel Optimization Algorithm

  • Michael Lewis
  • Stephen G. Nash
    • Categories Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , ,

    Many optimization algorithms require gradients of the model functions, but computing accurate gradients can be computationally expensive. We study the implications of using inexact gradients in the context of the multilevel optimization algorithm MGOpt. MGOpt recursively uses (typically cheaper) coarse models to obtain search directions for finer-level models. However, MGOpt requires the gradient on the … Read more

    Two new weak constraint qualifications and applications

  • Roberto Andreani
  • Gabriel Haeser
  • Paulo J. S. Silva
  • María Laura Schuverdt
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We present two new constraint qualifications (CQ) that are weaker than the recently introduced Relaxed Constant Positive Linear Depen- dence (RCPLD) constraint qualification. RCPLD is based on the assump- tion that many subsets of the gradients of the active constraints preserve positive linear dependence locally. A major open question was to identify the exact set … Read more

    Optimal Newton-type methods for nonconvex smooth optimization problems

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Optimization Tags , ,

    We consider a general class of second-order iterations for unconstrained optimization that includes regularization and trust-region variants of Newton’s method. For each method in this class, we exhibit a smooth, bounded-below objective function, whose gradient is globally Lipschitz continuous within an open convex set containing any iterates encountered and whose Hessian is $\alpha-$Holder continuous (for … Read more

    Global Convergence of Radial Basis Function Trust Region Derivative-Free Algorithms

  • Christine Shoemaker
  • Stefan M. Wild
    • Categories Civil and Environmental Engineering, Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We analyze globally convergent derivative-free trust region algorithms relying on radial basis function interpolation models. Our results extend the recent work of Conn, Scheinberg, and Vicente to fully linear models that have a nonlinear term. We characterize the types of radial basis functions that fit in our analysis and thus show global convergence to first-order … Read more

    A Penalty-Interior-Point Algorithm for Nonlinear Constrained Optimization

  • Frank E. Curtis
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    Penalty and interior-point methods for nonlinear optimization problems have enjoyed great successes for decades. Penalty methods have proved to be effective for a variety of problem classes due to their regularization effects on the constraints. They have also been shown to allow for rapid infeasibility detection. Interior-point methods have become the workhorse in large-scale optimization … Read more

    Metal Artefact Reduction by Least-Squares Penalized-Likelihood Reconstruction with a Fast Polychromatic Projection Model

  • Jean-Pierre Dussault
  • Yves Goussard
  • Benoit Hamelin
    • Categories Biomedical Applications, Bound-constrained Optimization Tags , , , , ,

    We consider penalized-likelihood reconstruction for X-ray computed tomography of objects that contain small metal structures. To reduce the beam hardening artefacts induced by these structures, we derive the reconstruction algorithm from a projection model that takes into account the photon emission spectrum and nonlinear variation of attenuation to photon energy. This algorithm requires excessively long … Read more