Global Optimization

A Branch and Bound Algorithm for Nonconvex Quadratic Optimization with Ball and Linear Constraints

  • Amir Beck
  • Dror Pan
    • Categories Global Optimization

    We suggest a branch and bound algorithm for solving continuous optimization problems where a (generally nonconvex) objective function is to be minimized under nonconvex inequality constraints which satisfy some specific solvability assumptions. The assumptions hold for some special cases of nonconvex quadratic optimization problems. We show how the algorithm can be applied to the problem … Read more

    MultiGLODS: Global and Local Multiobjective Optimization using Direct Search

  • Ana Luisa Custódio
  • J. F. A. Madeira
    • Categories Global Optimization, Nonlinear Optimization Tags , , , ,

    The optimization of multimodal functions is a challenging task, in particular when derivatives are not available for use. Recently, in a directional direct search framework, a clever multistart strategy was proposed for global derivative-free optimization of single objective functions. The goal of the current work is to generalize this approach to the computation of global … Read more

    Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Network Optimization

    We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied … Read more

    Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches

  • Veronika Grimm
  • Frauke Liers
  • Martin Schmidt
  • Thomas Kleinert
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design … Read more

    Characterizations of Mixed Binary Convex Quadratic Representable Sets

  • Alberto Del Pia
  • Jeffrey Poskin
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this paper we study the sets that appear in the feasibility version of mixed binary convex quadratic optimization problems. We provide a complete characterization of the sets that can be obtained as the … Read more

    Global Solution Strategies for the Network-Constrained Unit Commitment Problem With AC Transmission Constraints

  • Anya Castillo
  • Carl D. Laird
  • Jean-Paul Watson
  • Jianfeng Liu
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , ,

    We propose a novel global solution algorithm for the network-constrained unit commitment problem that incorporates a nonlinear alternating current model of the transmission network, which is a nonconvex mixed-integer nonlinear programming (MINLP) problem. Our algorithm is based on the multi-tree global optimization methodology, which iterates between a mixed-integer lower-bounding problem and a nonlinear upper-bounding problem. … Read more

    Generalized Symmetric ADMM for Separable Convex Optimization

  • Jianchao Bai
  • Jicheng Li
  • Fengmin Xu
  • Hongchao Zhang
    • Categories Convex Optimization, Global Optimization Theory Tags , , , , , ,

    The Alternating Direction Method of Multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a Generalized Symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two … Read more

    Dynamic Spectrum Management: A Complete Complexity Characterization

  • Ya-Feng Liu
    • Categories Applications - OR and Management Sciences, Global Optimization Theory, Telecommunications Tags , , ,

    Consider a multi-user multi-carrier communication system where multiple users share multiple discrete subcarriers. To achieve high spectrum efficiency, the users in the system must choose their transmit power dynamically in response to fast channel fluctuations. Assuming perfect channel state information, two formulations for the spectrum management (power control) problem are considered in this paper: the … Read more

    Open research areas in distance geometry

  • Carlile Lavor
  • Leo Liberti
    • Categories Basic Sciences Applications, Data-Mining, Global Optimization Applications Tags , , , ,

    Distance Geometry is based on the inverse problem that asks to find the positions of points, in a Euclidean space of given dimension, that are compatible with a given set of distances. We briefly introduce the field, and discuss some open and promising research areas. ArticleDownload View PDF

    The Multilinear polytope for acyclic hypergraphs

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , ,

    We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the Multilinear polytope … Read more