trust-region methods

Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization

  • Roger Behling
  • Clóvis Caesar Gonzaga
  • Gabriel Haeser
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , ,

    We consider the minimization of a convex function on a compact polyhedron defined by linear equality constraints and nonnegative variables. We define the Levenberg-Marquardt (L-M) and central trajectories starting at the analytic center and using the same parameter, and show that they satisfy a primal-dual relationship, being close to each other for large values of … Read more

    Scalable Nonlinear Programming Via Exact Differentiable Penalty Functions and Trust-Region Newton Methods

  • Mihai Anitescu
  • Victor M. Zavala
    • Categories Control Applications, Nonlinear Optimization Tags , , , , ,

    We present an approach for nonlinear programming (NLP) based on the direct minimization of an exact di erentiable penalty function using trust-region Newton techniques. As opposed to existing algorithmic approaches to NLP, the approach provides all the features required for scalability: it can eciently detect and exploit directions of negative curvature, it is superlinearly convergent, and … Read more

    On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere

  • Zhang Lei-Hong
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    Given symmetric matrices $B,D\in R^{n\times n}$ and a symmetric positive definite matrix $W\in R^{n\times n},$ maximizing the sum of the Rayleigh quotient $x^T Dx$ and the generalized Rayleigh quotient $x^T Bx/x^TWx$ on the unit sphere not only is of mathematical interest in its own right, but also finds applications in practice. In this paper, we … 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 surrogate management framework using rigorous trust-regions steps

  • Serge Gratton
  • Luis Nunes Vicente
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Optimization of Simulated Systems Tags , , ,

    Surrogate models and heuristics are frequently used in the optimization engineering community as convenient approaches to deal with functions for which evaluations are expensive or noisy, or lack convexity. These methodologies do not typically guarantee any type of convergence under reasonable assumptions and frequently render slow convergence. In this paper we will show how to … Read more

    A Note on the Implementation of an Interior-Point Algorithm for Nonlinear Optimization with Inexact Step Computations

  • Frank E. Curtis
  • Johannes Huber
  • Olaf Schenk
    • Categories Constrained Nonlinear Optimization Tags , , , , , , ,

    This paper describes an implementation of an interior-point algorithm for large-scale nonlinear optimization. It is based on the algorithm proposed by Curtis et al. (SIAM J Sci Comput 32:3447–3475, 2010), a method that possesses global convergence guarantees to first-order stationary points with the novel feature that inexact search direction calculations are allowed in order to … Read more

    A surrogate management framework using rigorous trust-regions steps

  • Serge Gratton
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Optimization of Simulated Systems Tags , , ,

    Surrogate models and heuristics are frequently used in the optimization engineering community as convenient approaches to deal with functions for which evaluations are expensive or noisy, or lack convexity. These methodologies do not typically guarantee any type of convergence under reasonable assumptions and frequently render slow convergence. In this paper we will show how to … Read more

    Second-Order-Cone Constraints for Extended Trust-Region Subproblems

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidefinite program with additional linear and second-order-cone constraints. For … Read more

    On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds

  • Margherita Porcelli
    • Categories Bound-constrained Optimization, Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , ,

    We introduce an inexact Gauss-Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. … Read more

    Derivative-free Optimization of Expensive Functions with Computational Error Using Weighted Regression

  • Stephen Billups
  • Peter Graf
  • Jeffrey Larson
    • Categories Unconstrained Optimization Tags , , ,

    We propose a derivative-free algorithm for optimizing computationally expensive functions with computational error. The algorithm is based on the trust region regression method by Conn, Scheinberg, and Vicente [4], but uses weighted regression to obtain more accurate model functions at each trust region iteration. A heuristic weighting scheme is proposed which simultaneously handles i) differing … Read more