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]])
end
push!(constraints, Constraint(0,psd_dict,Dict(), samples))
end
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.