global optimization

Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

    A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

  • Samuel Burer
  • Jieqiu Chen
    • Categories 0-1 Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , ,

    Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

    Dissimilarity Measures for Population-Based Global Optimization Algorithms

  • Andrea Cassioli
  • Marco Locatelli
  • Fabio Schoen
    • Categories Basic Sciences Applications, Global Optimization, Stochastic Approaches Tags , , ,

    Very hard optimization problems, i.e., problems with a large number of variables and local minima, have been effectively attacked with algorithms which mix local searches with heuristic procedures in order to widely explore the search space. A Population Based Approach based on a Monotonic Basin Hopping optimization algorithm has turned out to be very effective … Read more

    Another Face of DIRECT

  • Lakhdar Chiter
    • Categories Global Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , ,

    It is shown that, contrary to a claim of [D. E. Finkel, and C. T. Kelley, Additive scaling and the DIRECT algorithm, J. Glob. Optim. 36 (2006) 597-608], it is possible to divide the smallest hypercube which contains the low function value by considering hyperrectangles whose points are located on the diagonal of the center … Read more

    Solving systems of nonlinear equations with continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Global Optimization, Meta Heuristics, Stochastic Approaches Tags , , , , , , , ,

    A method for finding all roots of a system of nonlinear equations is described. Our method makes use of C-GRASP, a recently proposed continuous global optimization heuristic. Given a nonlinear system, we solve a corresponding adaptively modified global optimization problem multiple times, each time using C-GRASP, with areas of repulsion around roots that have already … Read more

    A continuous GRASP to determine the relationship between drugs and adverse reactions

  • Michael J. Hirsch
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • M. A. Ragle
    • Categories Biomedical Applications, Meta Heuristics, Stochastic Approaches Tags , , , , , , ,

    Adverse drug reactions (ADRs) are estimated to be one of the leading causes of death. Many national and international agencies have set up databases of ADR reports for the express purpose of determining the relationship between drugs and adverse reactions that they cause. We formulate the drug-reaction relationship problem as a continuous optimization problem and … Read more

    The complexity of optimizing over a simplex, hypercube or sphere: a short survey

  • Etienne de Klerk
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems have many applications. We review known approximation results as well as negative (inapproximability) results from the recent literature. Citation CentER Discussion paper 2006-85 Tilburg University THe Netherlands Article Download View The complexity … Read more

    Speeding up continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Global Optimization, Meta Heuristics, Stochastic Approaches Tags , , , , , , , ,

    Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2006). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In … Read more

    Solving molecular distance geometry problems by global optimization algorithms

  • Andrea Grosso
  • Marco Locatelli
  • Fabio Schoen
    • Categories Biomedical Applications, Global Optimization, Stochastic Approaches Tags , , ,

    In this paper we consider global optimization algorithms based on multiple local searches for the Molecular Distance Geometry Problem (MDGP). Three distinct approaches (Multistart, Monotonic Basin Hopping, Population Basin Hopping) are presented and for each of them a computational analysis is performed. The results are also compared with those of two other approaches in the … Read more

    A Particle Swarm Pattern Search Method for Bound Constrained Nonlinear Optimization

  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Global Optimization, Nonlinear Optimization, Optimization Software Benchmark Tags , , , , ,

    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