An exact solution method for binary equilibrium problems with compensation and the power market uplift problem

  • Daniel Huppmann
  • Sauleh Siddiqui
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Game Theory Tags , , , , , ,

    We propose a novel method to fi nd Nash equilibria in games with binary decision variables by including compensation payments and incentive-compatibility constraints from non-cooperative game theory directly into an optimization framework in lieu of using first order conditions of a linearization, or relaxation of integrality conditions. The reformulation off ers a new approach to obtain and … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more

    Preconditioning of a Generalized Forward-Backward Splitting and Application to Optimization on Graphs

  • Loïc Landrieu
  • Hugo Raguet
    • Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity

    We present a preconditioning of a generalized forward-backward splitting algorithm for finding a zero of a sum of maximally monotone operators \sum_{i=1}^n A_i + B with B cocoercive, involving only the computation of B and of the resolvent of each A_i separately. This allows in particular to minimize functionals of the form \sum_{i=1}^n g_i + … Read more

    Quantum and classical coin-flipping protocols based on bit-commitment and their point games

  • Ashwin Nayak
  • Jamie Sikora
  • Levent Tunçel
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , ,

    We focus on a family of quantum coin-flipping protocols based on quantum bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. … Read more

    Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

  • Amir Beck
  • Shimrit Shtern
    • Categories Convex Optimization

    We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear … Read more

    Bridging the Gap Between Multigrid, Hierarchical, and Receding-Horizon Control

  • Victor M. Zavala
    • Categories Distributed Control, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We analyze the structure of the Euler-Lagrange conditions of a lifted long-horizon optimal control problem. The analysis reveals that the conditions can be solved by using block Gauss-Seidel schemes and we prove that such schemes can be implemented by solving sequences of short-horizon problems. The analysis also reveals that a receding-horizon control scheme is equivalent … Read more

    A Two-Level Approach to Large Mixed-Integer Programs with Application to Cogeneration in Energy-Efficient Buildings

  • Sven Leyffer
  • Todd S. Munson
  • Fu Lin
    • Categories (Mixed) Integer Linear Programming Tags , , , , , ,

    We study a two-stage mixed-integer linear program (MILP) with more than 1 million binary variables in the second stage. We develop a two-level approach by constructing a semi-coarse model (coarsened with respect to variables) and a coarse model (coarsened with respect to both variables and constraints). We coarsen binary variables by selecting a small number … Read more

    Extended Formulations for Independence Polytopes of Regular Matroids

  • Volker Kaibel
  • Jon Lee
  • Matthias Walter
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , ,

    We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem … Read more

    Stochastic Optimization using a Trust-Region Method and Random Models

  • Ruobing Chen
  • Matt Menickelly
  • Katya Scheinberg
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function $f(x)$, obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis … Read more

    Distributed Gradient Methods with Variable Number of Working Nodes

  • Dragana Bajović
  • Dušan Jakovetić
  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Convex Optimization, Network Optimization Tags , , , ,

    We consider distributed optimization where $N$ nodes in a connected network minimize the sum of their local costs subject to a common constraint set. We propose a distributed projected gradient method where each node, at each iteration $k$, performs an update (is active) with probability $p_k$, and stays idle (is inactive) with probability $1-p_k$. Whenever … Read more