Nonlinear Optimization

BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    A direct-search derivative-free Matlab optimizer for bound-constrained problems is described, whose remarkable features are its ability to handle a mix of continuous and discrete variables, a versatile interface as well as a novel self-training option. Its performance compares favourably with that of NOMAD, a state-of-the art package. It is also applicable to multilevel equilibrium- or … Read more

    Nonlinear Programming Strategies on High-Performance Computers

  • Naiyuan Chiang
  • Carl D. Laird
  • Victor M. Zavala
  • Jia Kang
    • Categories Constrained Nonlinear Optimization, Parallel Algorithms, Systems governed by Differential Equations Optimization

    We discuss structured nonlinear programming problems arising in control applications, and we review software and hardware capabilities that enable the efficient exploitation of such structures. We focus on linear algebra parallelization strategies and discuss how these interact and influence high-level algorithmic design elements required to enforce global convergence and deal with negative curvature in a … 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

    On Solving L-SR1 Trust-Region Subproblems

  • Johannes Brust
  • Jennifer B. Erway
  • Roummel F. Marcia
    • Categories Optimization Software and Modeling Systems, Unconstrained Optimization Tags , , ,

    In this article, we consider solvers for large-scale trust-region subproblems when the quadratic model is defined by a limited-memory symmetric rank-one (L-SR1) quasi-Newton matrix. We propose a solver that exploits the compact representation of L-SR1 matrices. Our approach makes use of both an orthonormal basis for the eigenspace of the L-SR1 matrix and the Sherman- … Read more

    On the steepest descent algorithm for quadratic functions

  • Clóvis Caesar Gonzaga
  • Ruana Schneider
    • Categories Unconstrained Optimization Tags ,

    The steepest descent algorithm with exact line searches (Cauchy algorithm) is inefficient, generating oscillating step lengths and a sequence of points converging to the span of the eigenvectors associated with the extreme eigenvalues. The performance becomes very good if a short step is taken at every (say) 10 iterations. We show a new method for … Read more

    New multi-commodity flow formulations for the pooling problem

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications

    The pooling problem is a nonconvex nonlinear programming problem with numerous applications. The nonlinearities of the problem arise from bilinear constraints that capture the blending of raw materials. Bilinear constraints are well-studied and significant progress has been made in solving large instances of the pooling problem to global optimality. This is due in no small … Read more

    Generic properties for semialgebraic programs

  • Gue Myung Lee
  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    In this paper we study genericity for the following parameterized class of nonlinear programs: \begin{eqnarray*} \textrm{minimize } f_u(x) := f(x) – \langle u, x \rangle \quad \textrm{subject to } \quad x \in S, \end{eqnarray*} where $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is a polynomial function and $S \subset \mathbb{R}^n$ is a closed semialgebraic set, which is … Read more

    Stability and genericity for semi-algebraic compact programs

  • Gue Myung Lee
  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    In this paper we consider the class of polynomial optimization problems with inequality and equality constraints, in which every problem of the class is obtained by perturbations of the objective function, while the constraint functions are kept fixed. Under certain assumptions, we establish some stability properties (e.g., strong H\”older stability with explicitly determined exponents, semicontinuity, … Read more

    Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

  • Uwe Clausen
  • J. Fabian Meier
    • Categories Integer Programming, Quadratic Programming, Transportation

    The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more

    A second-order globally convergent direct-search method and its worst-case complexity

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest … Read more