nonlinear optimization

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

    Iterative Reweighted Linear Least Squares for Exact Penalty Subproblems on Product Sets

  • James V. Burke
  • Frank E. Curtis
  • Hao Wang
  • Jiashan Wang
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

    We present two matrix-free methods for solving exact penalty subproblems on product sets that arise when solving large-scale optimization problems. The first approach is a novel iterative reweighting algorithm (IRWA), which iteratively minimizes quadratic models of relaxed subproblems while automatically updating a relaxation vector. The second approach is based on alternating direction augmented Lagrangian (ADAL) … Read more

    An Interior-Point Trust-Funnel Algorithm for Nonlinear Optimization

  • Frank E. Curtis
  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, … Read more

    Quasi-Newton updates with weighted secant equations

  • Serge Gratton
  • Vincent Malmedy
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    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. CitationReport naXys-09-2013, Namur Centre for Complex Systems, Unibersity of Namur, Namur (Belgium)ArticleDownload View PDF

    A Sequential Quadratic Optimization Algorithm with Rapid Infeasibility Detection

  • James V. Burke
  • Frank E. Curtis
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    We present a sequential quadratic optimization (SQO) algorithm for nonlinear constrained optimization. The method attains all of the strong global and fast local convergence guarantees of classical SQO methods, but has the important additional feature that fast local convergence is guaranteed when the algorithm is employed to solve infeasible instances. A two-phase strategy, carefully constructed … Read more

    An example of slow convergence for Newton’s method on a function with globally Lipschitz continuous Hessian

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

    An example is presented where Newton’s method for unconstrained minimization is applied to find an $\epsilon$-approximate first-order critical point of a smooth function and takes a multiple of $\epsilon^{-2}$ iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that … Read more