global optimization

Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming

  • Samuel Burer
  • Jieqiu Chen
    • Categories Global Optimization, Optimization Software and Modeling Systems, Quadratic Programming Tags , , , ,

    Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of … Read more

    An Exact Penalty Global Optimization Approach for Mixed-Integer Programming Problems

  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily de ne an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed integer problems. CitationDIS Technical Report n. 17, 2010.ArticleDownload … Read more

    Reduced RLT Representations for Nonconvex Polynomial Programming Problems

  • Evrim Dalkiran
  • Leo Liberti
  • Hanif D. Sherali
    • Categories Global Optimization Theory Tags , , , , ,

    This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules … Read more

    A modified DIRECT algorithm for a problem in astrophysics

  • Daniela di Serafino
  • Giampaolo Liuzzi
  • Veronica Piccialli
  • Gerardo Toraldo
  • Filippo Riccio
    • Categories Applications - Science and Engineering, Global Optimization Applications Tags , ,

    We present a modification of the DIRECT algorithm, called DIRECT-G, to solve a box-constrained global optimization problem arising in the detection of gravitational waves emitted by coalescing binary systems of compact objects. This is a hard problem since the objective function is highly nonlinear and expensive to evaluate, has a huge number of local extrema … Read more

    Exploiting Second-Order Cone Structure for Global Optimization

  • Ashutosh Mahajan
  • Todd S. Munson
    • Categories Global Optimization Theory Tags , ,

    Identifying and exploiting classes of nonconvex constraints whose feasible region is convex after branching can reduce the time to compute global solutions for nonlinear optimization problems. We develop techniques for identifying quadratic and nonlinear constraints whose feasible region can be represented as the union of a finite number of second-order cones, and we provide necessary … Read more

    Some Results on the Strength of Relaxations of Multilinear Functions

  • Jeff Linderoth
  • James R. Luedtke
  • Mahdi Namazifar
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term … Read more

    Euclidean Distance Matrix Completion Problems

  • Haw-ren Fang
  • Dianne P. O'Leary
    • Categories Chemical Engineering, Global Optimization Applications Tags , , , , ,

    A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches … Read more

    Separation and Relaxation for cones of quadratic forms

  • Samuel Burer
  • Hongbo Dong
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    Let P be a pointed, polyhedral cone in R_n. In this paper, we study the cone C = cone{xx^T: x \in P} of quadratic forms. Understanding the structure of C is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of C and construct a separation algorithm for C provided one … Read more

    Optimizing radial basis functions by D.C. programming and its use in direct search for global derivative-free optimization

  • Hoai An Le Thi
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Global Optimization, Nonlinear Optimization Tags , , , , , ,

    In this paper we address the global optimization of functions subject to bound and linear constraints without using derivatives of the objective function. We investigate the use of derivative-free models based on radial basis functions (RBFs) in the search step of direct-search methods of directional type. We also study the application of algorithms based on … Read more

    Machine Learning for Global Optimization

  • Andrea Cassioli
  • David Di Lorenzo
  • Marco Locatelli
  • Fabio Schoen
  • Marco Sciandrone
    • Categories Data-Mining, Global Optimization Tags , , ,

    In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine … Read more