Linear, Cone and Semidefinite Programming

Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274–1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more

    Linear complementarity problems over symmetric cones: Characterization of Qb-transformations and existence results

  • Julio López
  • Héctor Ramírez
  • Rubén López
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    This paper is devoted to the study of the {symmetric cone linear complementarity problem} (SCLCP). In this context, our aim is to characterize the class Q_b in terms of larger classes, such as Q and R_0. For this, we introduce the class F and García’s transformations. We studied them for concrete particular instances (such as … Read more

    Existence and stability results based on asymptotic analysis for semidefinite linear complementarity problems

  • Julio López
  • Héctor Ramírez
  • Rubén López
    • Categories Semi-definite Programming Tags , ,

    This work is devoted to the study of existence and stability results of semidefinite linear complementarity problems (SDLCP). Our approach consists of approximating the variational inequality formulation of the SDLCP by a sequence of suitable chosen variational inequalities. This provides particular estimates for the asymptotic cone of the solution set of the SDLCP. We thus … Read more

    The Gram dimension of a graph

  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , , ,

    The Gram dimension $\gd(G)$ of a graph is the smallest integer $k \ge 1$ such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in $\oR^k$, having the same inner products on the edges of the graph. The class of graphs satisfying $\gd(G) … Read more

    Strong formulations for convex functions over nonconvex sets

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Global Optimization, Nonsmooth Optimization, Second-Order Cone Programming Tags , ,

    In this paper we derive strong linear inequalities for sets of the form {(x, q) ∈ R^d × R : q ≥ Q(x), x ∈ R^d − int(P ) }, where Q(x) : R^d → R is a quadratic function, P ⊂ R^d and “int” denotes interior. Of particular but not exclusive interest is the … Read more

    A randomized Mirror-Prox method for solving structured large-scale matrix saddle-point problems

  • Michel Baes
  • Arkadi Nemirovski
  • Michael Bürgisser
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    In this paper, we derive a randomized version of the Mirror-Prox method for solving some structured matrix saddle-point problems, such as the maximal eigenvalue minimization problem. Deterministic first-order schemes, such as Nesterov’s Smoothing Techniques or standard Mirror-Prox methods, require the exact computation of a matrix exponential at every iteration, limiting the size of the problems … Read more

    On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector Fields

  • Amir Ali Ahmadi
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , ,

    It is well-known that asymptotic stability (AS) of homogeneous polynomial vector fields of degree one (i.e., linear systems) can be decided in polynomial time e.g. by searching for a quadratic Lyapunov function. Since homogeneous vector fields of even degree can never be AS, the next interesting degree to consider is equal to three. In this … Read more

    Improved Column Generation for Highly Degenerate Master Problems

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , ,

    Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more

    Lifts of Convex Sets and Cone Factorizations

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or ‘lift’ of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over … Read more

    A Complete Characterization of the Gap between Convexity and SOS-Convexity

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials via the definition of convexity, its first order characterization, and its second order characterization are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming … Read more