Example: Clustering

Here we give a small example in which it is beneficial to use the option as_free to model positive semidefinite variables as free variables. We focus on the constraints. Suppose you want to solve a semidefinite program with the constraint that

\[\begin{align*} \langle Y, A(x) \rangle \end{align*}\]

is nonnegative on a union of $k$ semialgebraic sets

\[\begin{align*} G_i = \{x \in \mathbb{R}^n : g_{i,j}(x) \geq 0, j=1, \ldots, m_i\} \end{align*}\]

and suppose that these semialgebraic sets are archimedean, so that we can use Putinar's theorem. Then this translates into $k$ sum-of-squares constraints; one for each semialgebraic set.

Assuming that the matrix A is defined before, as well as the polynomials g[i][j], the basis sosbasis[i][j] of the correct degrees and the sample points samples, this gives the code

    constraints = []
    for i=1:k
        psd_dict = Dict()
        # this is the same everywhere
        psd_dict[:Y] = A
        for j=1:m[i]
            # this differs per constraint
            # note that different sum-of-square matrices have different names
            psd_dict[(:sos,i,j)] = LowRankMatPol([-g[i][j]], [sosbasis[i][j]])
        push!(constraints, Constraint(0,psd_dict,Dict(), samples))

Since the positive semidefinite matrix variable $Y$ occurs in every constraint, the corresponding cluster contains $k \cdot |S|$ constraints after sampling, where $|S|$ is the number of samples. To split this into $k$ clusters of $|S|$ constraints, we use the function model_psd_variables_as_free_variables to model $Y$ as free variables:

    problem = Problem(Minimize(obj), constraints)
    problem = model_psd_variables_as_free_variables(problem, [:Y])

This adds auxilliary free variables $X_{ij}$, adds the constraints $X_{ij} = Y_{ij}$, and replaces the $Y_{ij}$ in the constraints by $X_{ij}$. Then the only positive semidefinite variables in the polynomial constraints are the sums-of-squares matrices, which causes each sums-of-squares constraint to be assigned to its own cluster.