Semi-definite Programming

Decision Rule Approaches for Pessimistic Bilevel Linear Programs under Moment Ambiguity with Facility Location Applications

  • Akshit Goyal
  • Yiling Zhang
  • Chuan He
    • Categories Robust Optimization, Semi-definite Programming Tags , , , ,

    We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds a continuous wait-and-see decision after observing the leader’s action and revelation of uncertainty. Only the information of the mean, covariance, and support is known. We formulate the problem as … Read more

    Accelerated first-order methods for a class of semidefinite programs

  • Alex L. Wang
  • Fatma Kılınç-Karzan
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    This paper introduces a new storage-optimal first-order method (FOM), CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs , is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard … Read more

    Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more

    Exact SDP relaxations for quadratic programs with bipartite graph structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , ,

    For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … Read more

    An SDP Relaxation for the Sparse Integer Least Square Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … Read more

    Solving Two-Trust-Region Subproblems using Semidefinite Optimization with Eigenvector Branching

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more

    The Chvátal-Gomory Procedure for Integer SDPs with Applications in Combinatorial Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more

    A barrier Lagrangian dual method for multi-stage stochastic convex semidefinite optimization

  • Baha Alzalg
  • Asma Gafour
    • Categories Nonlinear Optimization, Semi-definite Programming, Stochastic Programming Tags , , , ,

    In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more

    Stochastic Dual Dynamic Programming for Optimal Power Flow Problems under Uncertainty

  • Adriana Kiszka
  • David Wozabal
    • Categories Energy, Semi-definite Programming, Stochastic Programming Tags , , ,

    We propose the first computationally tractable framework to solve multi-stage stochastic optimal power flow (OPF) problems in alternating current (AC) power systems. To this end, we use recent results on dual convex semi-definite programming (SDP) relaxations of OPF problems in order to adapt the stochastic dual dynamic programming (SDDP) algorithm for problems with a Markovian … Read more

    Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives

  • Didier Henrion
  • Felix Kirschner
  • Etienne de Klerk
  • Jean-Bernard Lasserre
  • Victor Magron
    • Categories Finance and Economics, Semi-definite Programming Tags , ,

    In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more