Optimization Online


Membership testing for Bernoulli and tail-dependence matrices

Daniel Krause(daniel.krause***at***tum.de)
Matthias Scherer(scherer***at***tum.de)
Jonas Schwinn(jonas.schwinn***at***math.uni-augsburg.de)
Ralf Werner(ralf.werner***at***math.uni-augsburg.de)

Abstract: Testing a given matrix for membership in the family of Bernoulli matrices is a longstanding problem, the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. A novel approach towards this problem was taken by [Fiebig et al., 2017] for lowdimensional settings d <= 6. For the first time, they exploit the close relationship between the Bernoulli polytope (also known as correlation polytope) and the well-studied cut polytope, which plays a central role in membership testing of Bernoulli matrices. Inspired by this approach, we use results from [Deza and Laurent, 1997, Embrechts et al., 2016, Fiebig et al., 2017] in a pre-phase of our algorithm to check necessary and sufficient conditions, before actually testing a matrix on Bernoulli compatibility. In our main approach, we however build upon an early attempt by [Lee, 1993] based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To appropriately deal with the issue of exponentially many primal variables, we propose a specifically taylored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d = 40 on a broad variety of test problems.

Keywords: Bernoulli-compatible matrix, tail-dependence matrix, column generation, binary quadratic programming

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Applications -- OR and Management Sciences (Finance and Economics )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Working Paper, Institute of Mathematics, Augsburg University, August 2017.

Download: [PDF]

Entry Submitted: 08/16/2017
Entry Accepted: 08/16/2017
Entry Last Modified: 08/16/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society