global optimization

Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization Tags , , , ,

    Placing $N$ non-overlapping circles in a smallest container is a well known, widely studied problem that can be easily formulated as a mathematical programming model. Solving this problem is notoriously extremely hard. Recently a public contest has been held for finding putative optimal solutions to a special case in circle packing. The contest saw the … Read more

    On the complexity of optimization over the standard simplex

  • Etienne de Klerk
  • Dick den Hertog
  • Gamal Elabwabi
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on … Read more

    A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming Tags , , , , , ,

    This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more

    Disk Packing in a Square: A New Global Optimization Approach

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Stochastic Approaches Tags , , , , ,

    We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we … Read more

    Simulated Entropy and Global Optimization

  • Asaad M. Sultan
  • Andrew B. Templeman
    • Categories Combinatorial Optimization, Global Optimization Tags , ,

    Nonlinear optimization deals with the problem of optimizing a single objective function, such as physical weight or cost, in the presence of equality and inequality constraints. Usually engineering design applications are highly non-linear and engineers are always interested in not finding a feasible design that is locally optimal in the design space, but globally optimal … Read more

    Solving a Quantum Chemistry problem with Deterministic Global Optimization

  • Marco Antonio Chaer Nascimento
  • Carlile Lavor
  • Leo Liberti
  • Nelson Maculan
    • Categories Basic Sciences Applications, Biomedical Applications, Global Optimization Applications Tags , , ,

    The Hartree-Fock method is well known in quantum chemistry, and widely used to obtain atomic and molecular eletronic wave functions, based on the minimization of a functional of the energy. This gives rise to a multi-extremal, nonconvex, polynomial optimization problem. We give a novel mathematical programming formulation of the problem, which we solve by using … Read more

    GRASP for nonlinear optimization

  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Stochastic Approaches Tags , , , ,

    We propose a Greedy Randomized Adaptive Search Procedure (GRASP) for solving continuous global optimization problems subject to box constraints. The method was tested on benchmark functions and the computational results show that our approach was able to find, in a few seconds, optimal solutions for all tested functions despite not using any gradient information about … Read more

    New results for molecular formation under pairwise potential minimization

  • Bernardetta Addis
  • Immanuel M. Bomze
  • Werner Schachinger
  • Fabio Schoen
    • Categories Global Optimization, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    We establish new lower bounds on the distance between two points of a minimum energy configuration of $N$ points in $\mathbb{R}^3$ interacting according to a pairwise potential function. For the Lennard-Jones case, this bound is 0.67985 (and 0.7633 in the planar case). A similar argument yields an estimate for the minimal distance in Morse clusters, … Read more

    Phylogenetic Analysis Via DC Programming

  • Steven Ellis
  • Madhu Nayakkankuppam
    • Categories Biomedical Applications, Global Optimization Applications Tags , , , ,

    The evolutionary history of species may be described by a phylogenetic tree whose topology captures ancestral relationships among the species, and whose branch lengths denote evolution times. For a fixed topology and an assumed probabilistic model of nucleotide substitution, we show that the likelihood of a given tree is a d.c. (difference of convex) function … Read more

    An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances

  • Miguel F. Anjos
    • Categories 0-1 Programming, Basic Sciences Applications, Semi-definite Programming Tags , , , ,

    This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. We present an explicit semidefinite programming problem with dimension linear in … Read more