Global Optimization

Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming

  • Kurt M. Anstreicher
    • Categories Global Optimization Theory, Semi-definite Programming Tags , ,

    We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that … Read more

    Jamming communication networks under complete uncertainty

  • Clayton W. Commander
  • Panos M. Pardalos
  • Valeriy Ryabchenko
  • Oleg Shylo
  • Stan Uryasev
  • Grigoriy Zrazhevsky
    • Categories Global Optimization Applications, Telecommunications

    This paper describes a problem of interdicting/jamming wireless communication networks in uncertain environments. Jamming communication networks is an important problem with many applications, but has received relatively little attention in the literature. Most of the work on network interdiction is focused on preventing jamming and analyzing network vulnerabilities. Here, we consider the case where there … Read more

    Sufficient Conditions for a Real Polynomial to be a Sum of Squares

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Linear Programming, Other Topics

    We provide explicit sufficient conditions for a polynomial $f$ to be a sum of squares (s.o.s.), linear in the coefficients of $f$. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most $2d$. We also provide a simple condition to ensure … Read more

    Computable representations for convex hulls of low-dimensional quadratic forms

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Bound-constrained Optimization, Global Optimization Theory Tags , ,

    Let C be the convex hull of points {(1;x)(1,x’)| x \in F\subset R^n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. If n

    Convex sets with semidefinite representation

  • Jean-Bernard Lasserre
    • Categories Convex Optimization, Global Optimization, Semi-definite Programming

    We provide a sufficient condition on a class of compact basic semialgebraic sets K for their convex hull to have a lifted semidefinite representation (SDr). This lifted SDr is explicitly expressed in terms of the polynomials that define K. Examples are provided. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we … Read more

    Global minimization using an Augmented Lagrangian method with variable lower-level constraints

  • Ernesto G. Birgin
  • Christodoulos A. Floudas
  • José Mario Martínez
    • Categories Global Optimization Tags , , ,

    A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB … 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

    On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

  • Samuel Burer
    • Categories Global Optimization, Integer Programming, Linear, Cone and Semidefinite Programming

    We establish that any nonconvex quadratic program having a mix of binary and continuous variables over a bounded feasible set can be represented as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of … 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. CitationCentER Discussion paper 2006-85 Tilburg University THe NetherlandsArticleDownload View PDF