cone

Hardness of some optimization problems over correlation polyhedra

  • Alberto Caprara
  • Fabio Furini
  • Claudio Gentile
  • Leo Liberti
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more

    Continuity of the conic hull

  • Michael Orlitzky
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In a real Hilbert space V, the conic hull of G is the set cone(G) consisting of all nonnegative linear combinations of elements of G. Many optimization problems are sensitive to the changes in cone(G) that result from changes in G itself. Motivated by one such problem, we derive necessary and sufficient conditions for the … Read more