Borderbasix

Let and . To solve the optimization problem

we consider the following (equivalent) problem

where is a positive measure. As any measure is uniquely determined by its moments:

the optimization problem (?) can be replaced by

where is the cone of moment sequences of positive measures with a support in .

To have a practical and efficient method to solve this problem, we truncate the sequence of moments in a given degree and relax the problem into the optimization of the linear form on the cone of matrices of the form

which are semi-definite positive. The condition that the support of is in the set translates as linear conditions on the moments . The condition that the support of is in the set translates into conditions of positivity on matrices, which entries are linear combinations of the moments . The truncated relaxation of (?) leads to the optimization of a linear form on the cone of semi-definite positive matrices intersected with a linear space. Such problems can be solved efficiently by interior points method [?].

The general approach proposed by J.B. Lasserre [?] to solve the polynomial optimization problem (?) consists in solving the Semi-Definite Programming problem truncated moment matrices, degree by degree, until the truncated sequence of moments uniquely characterizes the measure, which is solution of the problem (?).

The method that we use consists in combining the border basis computation, with the Semi-Definite Programming on truncated moment matrices, in order to obtain smaller moment problems and equations defining the minimizer points of (?). More precisely, in each step of the border basis computation, a SDP is solved and a basis of the kernel of the Moment matrix is computed to generate new polynomial equations defining the optimizers until a border basis of the minimizer ideal is computed. A flat extension test [?] is used to check if the moments characterizes a positive measure supported on points. See [?, ?] for more details.

Bibliography