Linear, Cone and Semidefinite Programming

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

    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

    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

    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

    Tight global linear convergence rate bounds for operator splitting methods

  • Goran Banjac
  • Paul J. Goulart
    • Categories Convex Optimization, Linear Programming Tags , , , , , , ,

    In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding … 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

    Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Roxana Hess
    • Categories Semi-definite Programming Tags , , , , ,

    We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more

    A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Second-Order Cone Programming Tags , , , ,

    We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact … Read more

    The SCIP Optimization Suite 3.2

  • Tobias Fischer
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Gregor Hendel
  • Thorsten Koch
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Sebastian Schenker
  • Robert Schwarz
  • Yuji Shinano
  • Stefan Vigerske
  • Michael Winkler
  • Jonas T. Witt
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems

    The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic … Read more