Global Optimization

Nonconvex optimization problems involving the Euclidean norm: Challenges, progress, and opportunities

  • Anatoliy Kuznetsov
  • Nikolaos Sahinidis
    • Categories Global Optimization, Optimization Software Benchmark Tags , , ,

    The field of global optimization has advanced significantly over the past three decades. Yet, the solution of even small instances of many nonconvex optimization problems involving the Euclidean norm to global optimality remains beyond the reach of modern global optimization methods. These problems include numerous well-known and high-impact open research questions from a diverse collection … Read more

    Exploiting Sign Symmetries in Minimizing Sums of Rational Functions

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Semi-definite Programming Tags , , , ,

    This paper is devoted to the problem of minimizing a sum of rational functions over a basic semialgebraic set. We provide a hierarchy of sum of squares (SOS) relaxations that is dual to the generalized moment problem approach due to Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect offers two benefits: 1) … Read more

    Spatial branch-and-bound for nonconvex separable piecewise linear optimization

  • Thomas Hübner
  • Akshay Gupte
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Global Optimization Tags , , , ,

    Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization, using special ordered sets and mixed integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm (sBB) … Read more

    A Bilevel Hierarchy of Strengthened Complex Moment Relaxations for Complex Polynomial Optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    This paper proposes a bilevel hierarchy of strengthened complex moment relaxations for complex polynomial optimization. The key trick entails considering a class of positive semidefinite conditions that arise naturally in characterizing the normality of the so-called shift operators. The relaxation problem in this new hierarchy is parameterized by the usual relaxation order as well as … Read more

    Revisiting the fitting of the Nelson-Siegel and Svensson models

  • Dirk Banholzer
  • Jörg Fliege
  • Ralf Werner
    • Categories Finance and Economics, Global Optimization Applications, Nonlinear Systems and Least-Squares Tags , , , , ,

    The Nelson-Siegel and the Svensson models are two of the most widely used models for the term structure of interest rates. Even though the models are quite simple and intuitive, fitting them to market data is numerically challenging and various difficulties have been reported. In this paper, a novel mathematical analysis of the fitting problem … Read more

    The best approximation pair problem relative to two subsets in a normed space

  • Daniel Reem
  • Yair Censor
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Infinite Dimensional Optimization Tags , , , , , , , ,

    In the classical best approximation pair (BAP) problem, one is given two nonempty, closed, convex and disjoint subsets in a finite- or an infinite-dimensional Hilbert space, and the goal is to find a pair of points, each from each subset, which realizes the distance between the subsets. We discuss the problem in more general normed … Read more

    ε-Optimality in Reverse Optimization

  • Mounir El Maghri
    • Categories Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    The purpose of this paper is to completely characterize the global approximate optimality (ε-optimality) in reverse convex optimization under the general nonconvex constraint “h(x) ≥ 0″. The main condition presented is obtained in terms of Fenchel’s ε-subdifferentials thanks to El Maghri’s ε-efficiency in difference vector optimization [J. Glob. Optim. 61 (2015) 803–812], after converting the … Read more

    Lipschitz Based Lower Bound Construction for Surrogate Optimization

  • Mohammadsina Almasi
  • Hadis Anahideh
  • Jay Rosenberger
    • Categories Bound-constrained Optimization, Global Optimization, Global Optimization Applications Tags , , ,

    Bounds play a vital role in guiding optimization algorithms by enhancing convergence, improving solution quality, and quantifying optimality gaps. While Lipschitz-based lower bounds are well-established, their effectiveness is often constrained by the function’s topological properties. To address these limitations, we propose an approach that integrates nonlinear distance metrics with surrogate approximations, yielding more adaptive and … Read more

    Refined TSSOS

  • Daria Shaydurova
  • Volker Kaibel
  • Sebastian Sager
    • Categories Global Optimization Applications, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency … Read more