Message Boards Message Boards

Finding large graph cuts with SemidefiniteOptimization

Yaroslav Bulatov, Together AI
Posted 3 years ago

POSTED BY: Yaroslav Bulatov
9 Replies
Sort By:

BTW, you can make the Step 2 objective convex by adding a large quadratic term to each dimension. I think this makes it a Quadratically Constrained Quadratic Program.

There are some specialized solvers for QCQP, it would be neat if they were easily accessible from Mathematica.

It seems arbitrary polynomial minimization problem can be reformulated as sparse QCQP -- [Rank-2 Matrix Solution for Semidefinite Relaxations of Arbitrary Polynomial Optimization Problems](https://lavaei.ieor.berkeley.edu/CDC_Polynomial_2014.pdf)
POSTED BY: Yaroslav Bulatov

This one GraphData[{"Wheel",5}] -- SDP formulation finds solution with value 6.25, FindMinimum finds one with 4.5
POSTED BY: Yaroslav Bulatov

OK, it looks like optimality is not guaranteed and SDP can generally find better solutions, the simplest example is the wheel graph
POSTED BY: Yaroslav Bulatov

"the simplest example is the wheel graph"

Wheely?
POSTED BY: Daniel Lichtblau

I agree this is really nice.

I wonder if the Step 2 part would do better using FindMinimum with Method set to `"InteriorPoint"?
POSTED BY: Daniel Lichtblau

Oh interesting, is it guaranteed to work for indefinite QPs?

That does seem to give the correct solution in a few graphs I tried:
POSTED BY: Yaroslav Bulatov

I do not know if it is guaranteed unless convexity holds (I don't know if that is the case for the SDP formulation). Many years ago I did something similar as a heuristic for finding a maximal clique in a graph. That was not a convex formulation and the results, while solid in random tests I performed, were nonetheless heuristic. But it was a fun talk, on Halloween no less (the WTC was held relatively late that year).
POSTED BY: Daniel Lichtblau

Very nice! Readers should also take a look at this reference section

SemidefiniteOptimization > Applications > Graph Problems

https://reference.wolfram.com/language/ref/SemidefiniteOptimization.html
POSTED BY: Vitaliy Kaurov

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!
POSTED BY: EDITORIAL BOARD
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract