nonlinear optimization

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • Philippe L. Toint
  • John L. Gardenghi
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization Tags , , ,

    The evaluation complexity of general nonlinear, possibly nonconvex,constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem’s function and their first $p$ derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, … Read more

    Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • Philippe L. Toint
  • John L. Gardenghi
    • Categories Unconstrained Optimization Tags , ,

    The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p\geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most … Read more

    Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

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

    The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined … Read more

    Simple examples for the failure of Newton’s method with line search for strictly convex minimization

  • Florian Jarre
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags ,

    In this paper two simple examples of a twice continuously differentiable strictly convex function $f$ are presented for which Newton’s method with line search converges to a point where the gradient of $f$ is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex … Read more

    A Trust Region Algorithm with a Worst-Case Iteration Complexity of ${\cal O}(\epsilon^{-3/2})$ for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , , , ,

    We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any $\bar\epsilon \in (0,\infty)$, the algorithm requires at most $\mathcal{O}(\epsilon^{-3/2})$ iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any $\epsilon \in (0,\bar\epsilon]$. This improves upon the $\mathcal{O}(\epsilon^{-2})$ bound known to hold for … Read more

    Adaptive Augmented Lagrangian Methods: Algorithms and Practical Numerical Experience

  • Frank E. Curtis
  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Hao Jiang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    In this paper, we consider augmented Lagrangian (AL) algorithms for solving large-scale nonlinear optimization problems that execute adaptive strategies for updating the penalty parameter. Our work is motivated by the recently proposed adaptive AL trust region method by Curtis et al. [An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 (2015), pp.201–245.]. … Read more

    An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Global Optimization, Nonlinear Optimization Tags , ,

    We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator … Read more

    An Augmented Lagrangian based Algorithm for Distributed Non-Convex Optimization

  • Moritz Diehl
  • Janick V Frasch
  • Boris Houska
    • Categories Constrained Nonlinear Optimization Tags , ,

    This paper is about distributed derivative-based algorithms for solving optimization problems with a separable (potentially nonconvex) objective function and coupled affine constraints. A parallelizable method is proposed that combines ideas from the fields of sequential quadratic programming and augmented Lagrangian algorithms. The method negotiates shared dual variables that may be interpreted as prices, a concept … Read more

    A DC (Difference of Convex functions) approach of the MPECs

  • Rafael Correa
  • Matthieu Marechal
    • Categories Constrained Nonlinear Optimization Tags , ,

    This article deals with a study of the MPEC problem based on a reformulation to a DC problem (Difference of Convex functions). This reformulation is obtained by a partial penalization of the constraints. In this article we prove that a classical optimality condition for a DC program, if a constraint qualification is satisfied for MPEC, … Read more

    A derivative-free trust-funnel method for equality-constrained nonlinear optimization

  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this work, we look into new derivative-free methods to solve equality-constrained optimization problems. Of particular interest, are the trust-region techniques, which have been investigated for the unconstrained and bound-constrained cases. For solving equality-constrained optimization problems, we introduce a derivative-free adaptation of the trust-funnel method combined with a self-correcting geometry scheme and present some encouraging … Read more