This section describes how to use moment matrics and conic programming, semidefinite programming(SDP) and second-order cone programming(SOCP) to construct variational relaxations.

We spent a good amount of time going over the background information in the section. First we discussed the definition of a moment matrix and the property that any valid moment matrix is positive semidefinite. Next we looked at the definition of two different bases, the multinomial base and the indicator base and went trhough the lemma that shows that it is always possible to convert between the two. Lastly, we looked at the new definition of the marginal polytope for hypergraphs in terms of the multinomial base.

Next we went over how the Lasserre sequence(moment matrices) provides a nested hierarchy of outer bounds on the marginal polytope. For any hypergraph on m nodes, the where t=m provides and exact characterization of the margional polytope.

The last section discussed an alternate second-order cone relaxation technique, which we deffered discussing until next week’s meeting.

### Like this:

Like Loading...

*Related*

The proof in appendix E.2 is not too difficult to follow, but there are a few typos on page 288 that can initially be confusing.

In the very first equation on the page, the second should be . This changes the last summation to be over such that and not the other way around, and the last exponent is rather than the other way around.

Then in equation (E.7), the in the exponent should be , as in .

One point which I initially glossed over, but which is important, is why it is necessary in the equation before (E.7) that and not simply .

Comment by Gary — September 1, 2009 @ 3:02 pm |