Membership testing for Bernoulli and tail-dependence matrices
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.
Entry Submitted: 08/16/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|