convex envelope

Deterministic global optimization with trained neural networks: What is the benefit of the envelope of single neurons?

  • Clara Witte
  • Jannik Lüthje
  • Victor Schulte
  • Alexander Mitsos
  • Dominik Bongartz
    • Categories Global Optimization, Global Optimization Applications, Optimization in Data Science Tags , , ,

    Optimization problems containing trained neural networks remain challenging due to their nonconvexity. Deterministic global optimization relies on relaxations that should be tight, quickly convergent, and cheap to evaluate. While envelopes of common activation functions have been established for several years, the envelope of an entire neuron had not. Recently, Carrasco and Mu\~{n}oz (arXiv.2410.23362, 2024) proposed … Read more

    A proof for multilinear error bounds

  • Alberto Costa
    • Categories Nonlinear Optimization, Polyhedra Tags , , , ,

    We derive the error bounds for multilinear terms in $[0,1]^n$ using a proof methodology based on the polyhedral representation of the convex hull. We extend the result for multilinear terms in $[\boldsymbol{L},\boldsymbol{0}] \times [\boldsymbol{0},\boldsymbol{U}]\subset\mathbb{R}^n$. ArticleDownload View PDF

    Convex envelopes of bounded monomials on two-variable cones

  • Pietro Belotti
    • Categories Global Optimization Theory Tags , ,

    We consider an \(n\)-variate monomial function that is restricted both in value by lower and upper bounds and in domain by two homogeneous linear inequalities. Such functions are building blocks of several problems found in practical applications, and that fall under the class of Mixed Integer Nonlinear Optimization. We show that the upper envelope of … Read more

    Enhancements of Extended Locational Marginal Pricing – Advancing Practical Implementation

  • Yonghong Chen
  • Congcong Wang
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    Price formation is critical to efficient wholesale electricity markets that support reliable operation and efficient investment. The Midcontinent Independent System Operator (MISO) developed the Extended Locational Marginal Pricing (ELMP) with the goal of more completely reflecting resource costs and generally improving price formation to better incent market participation. MISO developed ELMP based on the mathematical … Read more

    Distributionally Robust Optimization under Distorted Expectations

  • Jun Cai
  • Jonathan Yu-Meng Li
  • Tiantian Mao
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization (DRO) has arose as an important paradigm to address the issue of distributional ambiguity in decision optimization. In its standard form, DRO seeks an optimal solution against the worst-possible expected value evaluated based on a set of candidate distributions. In the case where a decision maker is not risk neutral, the most … Read more

    Solving Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification – a Case Study for Gas Networks

  • Frauke Liers
  • Maximilian Merkert
  • Alexander Martin
  • Nick Mertens
  • Dennis Michaels
    • Categories Applications - Science and Engineering, Global Optimization, Network Optimization Tags , , ,

    Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each … Read more

    On the computation of convex envelopes for bivariate functions through KKT conditions

  • Marco Locatelli
    • Categories Global Optimization Theory Tags , ,

    In this paper we exploit a slight variant of a result previously proved in [11] to define a procedure which delivers the convex envelope of some bivariate functions over polytopes. The procedure is based on the solution of a KKT system and simplifies the derivation of the convex envelope with respect to previously proposed techniques. … Read more

    On convex relaxations for quadratically constrained quadratic programming

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

    We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let F denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on F is dominated by an alternative … Read more

    What Shape is your Conjugate? A Survey of Computational Convex Analysis and its Applications

  • Yves Lucet
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , , , , ,

    Computational Convex Analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of Computational Convex Analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is … 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