In this paper we develop, analyze, and test a new algorithm for the global minimization of a function subject to simple bounds without the use of derivatives. The underlying algorithm is a pattern search method, more specifically a coordinate search method, which guarantees convergence to stationary points from arbitrary starting points. In the optional search … Read more
We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus … Read more
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
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
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
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
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
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
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
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