A way to approximate the volume of semi algebraic sets using SDPs
On Wednesday 30.01.2020 as part of a reading group I presented the work of:
D. Henrion, J. B. Lasserre and C. Savorgnan on: Approximate Volume and Integration for Basic Semi-algebraic Sets. [ https://doi.org/10.1137/080730287 ]
I wish to share some interesting bits of knowledge I came across. It is not my intention to fully and rigorously reproduce the contents of the above mentioned paper. Hence, if you are interested in the topic mentioned then please consult the paper.
I was suggested this paper by Monique because it shows two things. The first being that finding the volume of a compact basic semi-algebraic set K that is Archemedean (on the polynomials g_i defining K),
can be recast as a minimisation problem over measures (see Theorem 3.1).
The second thing that is shown is that this problem can be approximated by a hierarchy of SDP approximations that return the moments of a minimising measure. Both of these topics fall well within the scope of POEMA. Clearly the second point is the meat of the paper. Usually asking for a Lebesgue measure supported on a "oddly shaped" domain is asking too much but once one shifts to dealing with the respective moments of said measure the task reduces to more familiar algebra.
The premise is to somehow create an optimisation problem with essentially unique minimiser: the Lebesque measure supported on K. This is achieved by using the (normalised) Lebesque measure (denoted \mu_2 in Theorem 3.1 below), which is restricted to a simple domain B containing K, so that its moments are explicitly known. One may choose for instance B to be a box containing K.
Here \mathcal{B} is the Borel Sigma algebra generated from B, \mu_2 is the normalised Lebesque measure with support on B, and M(K) is the set of all finite Borel measures with support on K.
The paper then uses the work of Putinar to show hierarchies of SDP's that approximate the original optimisation problem. The paper also shows analogous results for LP approximations but I have chosen to focus on the SDP part as it is closer to my project. The SDP hierarchy given for the above problem is:
where L_{y_1} (x^\alpha) = y_1(\alpha) and M_d(y_i) is the moment matrix for vector y_i of moments and the r_j's are appropriate integers for consistency.
I was particularly pleased with how the natural link between measures and their moment matrices are used to define the hierarchy. This becomes clear when one sees that ordering of measures translate to the PSD order on the respective moment matrices. There is a very rich theory behind the moment problem that gives results similar to the following:
and the celebrated Putinar Positivstellensatz gives a bridge from moments to measures.
The task then shifts to showing monotone convergence of the hierarchy, which was achieved in the paper. What is not shown is the convergence rate nor the effect of different B and mononomial basis.
As a side bonus the paper uses quite a few well known and classical results e.g. Banach-Alaoglu, theorem Urysohn's Lemma, Stone Weierstrass theorem to sketch clearly the proofs.
If you want more details see the paper.
D. Henrion, J. B. Lasserre and C. Savorgnan on: Approximate Volume and Integration for Basic Semi-algebraic Sets. [ https://doi.org/10.1137/080730287 ]
I wish to share some interesting bits of knowledge I came across. It is not my intention to fully and rigorously reproduce the contents of the above mentioned paper. Hence, if you are interested in the topic mentioned then please consult the paper.
I was suggested this paper by Monique because it shows two things. The first being that finding the volume of a compact basic semi-algebraic set K that is Archemedean (on the polynomials g_i defining K),
The second thing that is shown is that this problem can be approximated by a hierarchy of SDP approximations that return the moments of a minimising measure. Both of these topics fall well within the scope of POEMA. Clearly the second point is the meat of the paper. Usually asking for a Lebesgue measure supported on a "oddly shaped" domain is asking too much but once one shifts to dealing with the respective moments of said measure the task reduces to more familiar algebra.
The premise is to somehow create an optimisation problem with essentially unique minimiser: the Lebesque measure supported on K. This is achieved by using the (normalised) Lebesque measure (denoted \mu_2 in Theorem 3.1 below), which is restricted to a simple domain B containing K, so that its moments are explicitly known. One may choose for instance B to be a box containing K.
Here \mathcal{B} is the Borel Sigma algebra generated from B, \mu_2 is the normalised Lebesque measure with support on B, and M(K) is the set of all finite Borel measures with support on K.The paper then uses the work of Putinar to show hierarchies of SDP's that approximate the original optimisation problem. The paper also shows analogous results for LP approximations but I have chosen to focus on the SDP part as it is closer to my project. The SDP hierarchy given for the above problem is:
where L_{y_1} (x^\alpha) = y_1(\alpha) and M_d(y_i) is the moment matrix for vector y_i of moments and the r_j's are appropriate integers for consistency. 
As a side bonus the paper uses quite a few well known and classical results e.g. Banach-Alaoglu, theorem Urysohn's Lemma, Stone Weierstrass theorem to sketch clearly the proofs.
If you want more details see the paper.
Comments
Post a Comment