global optimization

Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, 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

    Branching and bounds tightening techniques for non-convex MINLP

  • Pietro Belotti
  • Jon Lee
  • Leo Liberti
  • François Margot
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , ,

    Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named COUENNE (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this paper, we present the structure of couenne and discuss in detail our … Read more

    On Non-Convex Quadratic Programming with Box Constraints

  • Samuel Burer
  • Adam N. Letchford
    • Categories 0-1 Programming, Convex Optimization, Global Optimization Theory Tags , ,

    Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more

    A stochastic algorithm for function minimization

  • Su Dongcai
  • Dong Junwei
  • Zheng Zuduo
    • Categories Constrained Nonlinear Optimization, Stochastic Approaches, Unconstrained Optimization Tags , ,

    Focusing on what an optimization problem may comply with, the so-called convergence conditions have been proposed and sequentially a stochastic optimization algorithm named as DSZ algorithm is presented in order to deal with both unconstrained and constrained optimizations. Its principle is discussed in the theoretical model of DSZ algorithm, from which we present a practical … Read more

    Value-at-Risk optimization using the difference of convex algorithm

  • David Wozabal
    • Categories Finance and Economics, Global Optimization Applications, Stochastic Programming Tags , ,

    Value-at-Risk (VaR) is an integral part of contemporary financial regulations. Therefore, the measurement of VaR and the design of VaR optimal portfolios are highly relevant problems for financial institutions. This paper treats a VaR constrained Markowitz style portfolio selection problem when the distribution of returns of the considered assets are given in the form of … Read more

    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