Nonlinear Optimization

ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions

  • Rommel Regis
  • Christine Shoemaker
  • Stefan M. Wild
    • Categories Optimization of Simulated Systems, Unconstrained Optimization Tags , , ,

    We present a new derivative-free algorithm, ORBIT, for unconstrained local optimization of computationally expensive functions. A trust-region framework using interpolating Radial Basis Function (RBF) models is employed. The RBF models considered often allow ORBIT to interpolate nonlinear functions using fewer function evaluations than the polynomial models considered by present techniques. Approximation guarantees are obtained by … Read more

    Extended Barzilai-Borwein method for unconstrained minimization problems

  • Yasushi Narushima
  • Hiroshi Yabe
  • Takahiko Wakamatsu
    • Categories Unconstrained Optimization Tags , ,

    In 1988, Barzilai and Borwein presented a new choice of step size for the gradient method for solving unconstrained minimization problems. Their method aimed to accelerate the convergence of the steepest descent method. The Barzilai-Borwein method requires few storage locations and inexpensive computations. Therefore, several authors have paid attention to the Barzilai-Borwein method and have … Read more

    A computational study of the use of an optimization-based method for simulating large multibody systems

  • Mihai Anitescu
  • Florian A. Potra
  • Bogdan Gavrea
  • Cosmin G. Petra
    • Categories Mechanical Engineering, Quadratic Programming

    The present work aims at comparing the performance of several quadratic programming (QP) solvers for simulating large-scale frictional rigid-body systems. Traditional time-stepping schemes for simulation of multibody systems are formulated as linear complementarity problems (LCPs) with copositive matrices. Such LCPs are generally solved by means of Lemketype algorithms and solvers such as the PATH solver … Read more

    A Matrix-free Algorithm for Equality Constrained Optimization Problems with Rank-deficient Jacobians

  • Frank E. Curtis
  • Jorge Nocedal
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Infinite Dimensional Optimization Tags , , , , ,

    We present a line search algorithm for large-scale constrained optimization that is robust and efficient even for problems with (nearly) rank-deficient Jacobian matrices. The method is matrix-free (i.e., it does not require explicit storage or factorizations of derivative matrices), allows for inexact step computations, and is applicable for nonconvex problems. The main components of the … Read more

    Automatically Assessing the Performance of an Optimization-Based Multigrid Method

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

    Many large nonlinear optimization problems are based upon discretizations of underlying function spaces. Optimization-based multigrid methods—that is, multigrid methods based on solving coarser versions of an optimization problem—are designed to solve such discretized problems efficiently by taking explicit advantage of the family of discretizations. The methods are generalizations of more traditional multigrid methods for solving … Read more

    A Primal-Dual Augmented Lagrangian

  • Philip E. Gill
  • Daniel P. Robinson
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we discuss the formulation of subproblems in which the objective is a primal-dual generalization of the Hestenes-Powell augmented Lagrangian function. This generalization has the crucial feature that it is minimized with respect to both … Read more

    Exact and heuristic solutions of the global supply chain problem with transfer pricing

  • Pierre Hansen
  • Sébastien Le Digabel
  • Sylvain Perron
  • Nenad Mladenovic
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Supply Chain Management Tags , , , , ,

    We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx (2001) proposed a bilinear model of this problem and solved it by an Alternate heuristic. We … Read more

    Accelerated line-search and trust-region methods

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
    • Categories Applications - Science and Engineering, Unconstrained Optimization Tags , , ,

    In numerical optimization, line-search and trust-region methods are two important classes of descent schemes, with well-understood global convergence properties. Here we consider “accelerated” versions of these methods, where the conventional iterate is allowed to be replaced by any point that produces at least as much decrease in the cost function as a fixed fraction of … Read more

    Concave programming for minimizing the zero-norm over polyhedral sets

  • Francesco Rinaldi
  • Fabio Schoen
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Data-Mining Tags , ,

    Given a non empty polyhedral set, we consider the problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This nonsmooth combinatorial optimization problem is NP-Hard and arises in various fields such as machine learning, pattern recognition, signal processing. We propose two … Read more

    A subspace minimization method for the trust-region step

  • Jennifer B. Erway
  • Philip E. Gill
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region constraint. The Steihaug-Toint method uses the conjugate-gradient (CG) algorithm to minimize the quadratic over a sequence of expanding subspaces until the iterates either converge to an interior point or cross the constraint boundary. … Read more