Linear, Cone and Semidefinite Programming

Intrinsic Representation of Tangent Vectors and Vector transport on Matrix Manifolds

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • Wen Huang
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming, Nonlinear Optimization

    In Riemannian optimization problems, commonly encountered manifolds are $d$-dimensional matrix manifolds whose tangent spaces can be represented by $d$-dimensional linear subspaces of a $w$-dimensional Euclidean space, where $w > d$. Therefore, representing tangent vectors by $w$-dimensional vectors has been commonly used in practice. However, using $w$-dimensional vectors may be the most natural but may not … Read more

    Matrices with high completely positive semidefinite rank

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Linear, Cone and Semidefinite Programming

    A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more

    A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem

  • Joachim Dahl
  • Etienne de Klerk
  • Ahmadreza Marandi
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , ,

    The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre, Toh, and Yang [EURO J. Comput. Optim., 2015] constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal value of the original … Read more

    Completely positive semidefinite rank

  • Anupam Prakash
  • Jamie Sikora
  • Antonios Varvitsiotis
  • Zhaohui Wei
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite {matrices} $\{P_i\}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}= {\rm Tr}(P_iP_j),$ for all $i,j \in \{ 1, \ldots, n \}$. The cpsd-rank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation … Read more

    Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning

  • Yiran Cui
  • Takashi Tsuchiya
  • Ken Hayami
  • Keiichi Morikuni
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The employed Krylov subspace methods do not suffer from rank-deficiency and therefore no … Read more

    On the Grassmann condition number

  • Javier F. Peña
  • Vera Roshchina
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We give new insight into the Grassmann condition of the conic feasibility problem \[ x \in L \cap K \setminus\{0\}. \] Here $K\subseteq V$ is a regular convex cone and $L\subseteq V$ is a linear subspace of the finite dimensional Euclidean vector space $V$. The Grassmann condition of this problem is the reciprocal of the … Read more

    Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

  • Tristan Gally
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more

    A Framework for Solving Mixed-Integer Semidefinite Programs

  • Tristan Gally
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems, Semi-definite Programming

    Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more

    Computational study of valid inequalities for the maximum hBccut problem

  • Miguel F. Anjos
  • Sébastien Le Digabel
  • Vilmar Jefté Rodrigues de Sousa
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more

    A doubly nonnegative relaxation for modularity density maximization

  • Yoichi Izunaga
  • Tomomi Matsui
  • Yoshitsugu Yamamoto
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. However, some authors pointed out drawbacks of the modularity, the main issue of which is resolution limit. Resolution limit refers to the sensitivity of the modularity to the … Read more