Janez Povh

On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    The well-known result stating that any non-convex quadratic problem over the nonnegative orthant with some additional linear and binary constraints can be rewritten as linear problem over the cone of completely positive matrices (Burer, 2009) is generalized by replacing the nonnegative orthant with an arbitrary closed convex cone. This set-semidefinite representation result implies new semidefinite … Read more

    NCSOSTOOLS: A COMPUTER ALGEBRA SYSTEM FOR SYMBOLIC AND NUMERICAL COMPUTATION WITH NONCOMMUTATIVE POLYNOMIALS

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , , ,

    Abstract. NCSOStools is a Matlab toolbox for – symbolic computation with polynomials in noncommuting variables; – constructing and solving sum of hermitian squares (with commutators) programs for polynomials in noncommuting variables. It can be used in combination with semidefi nite programming software, such as SeDuMi, SDPA or SDPT3 to solve these constructed programs. This paper provides … Read more

    The tracial moment problem and trace-optimization of polynomials

  • Sabine Burgdorf
  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Global Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , , ,

    The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace f(A) can attain for a tuple of matrices A? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not … Read more

    On the nonexistence of sum of squares certificates for the BMV conjecture

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Semi-definite Programming Tags , , , , ,

    The algebraic reformulation of the BMV conjecture is equivalent to a family of dimensionfree tracial inequalities involving positive semidefinite matrices. Sufficient conditions for these to hold in the form of algebraic identities involving polynomials in noncommuting variables have been given by Markus Schweighofer and the second author. Later the existence of these certificates has been … Read more

    Semidefinite programming and sums of hermitian squares of noncommutative polynomials

  • Igor Klep
  • Janez Povh
    • Categories Optimization Software Design Principles, Semi-definite Programming Tags , , ,

    An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the “Newton chip method”, a noncommutative analog of the classical Newton polytope method, and semide finite programming. CitationI. Klep and J. Povh. Semide nite programming and sums of hermitian squares of noncommutative polynomials. J. Pure Appl. … Read more

    Regularization methods for semidefinite programming

  • Jérôme Malick
  • Janez Povh
  • Franz Rendl
  • Angelika Wiegele
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    This paper studies an alternative technique to interior point methods and nonlinear methods for semidefinite programming (SDP). The approach based on classical quadratic regularizations leads to an algorithm, generalizing a recent method called “boundary point method”. We study the theoretical properties of this algorithm and we show that in practice it behaves very well on … Read more

    Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

  • Janez Povh
  • Franz Rendl
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it … Read more

    A copositive programming approach to graph partitioning

  • Janez Povh
  • Franz Rendl
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more