Implement constraint on semialgebraic set

[blegat]

Let's check the different way we can implement the SOS constraint

@polyconstraint q(x) >= 0 domain=[f_1(x) = 0, ..., f_m(x) = 0, g_1(x) >= 0, ..., g_p(x) >= 0])

There are basically two ways to handle this:

• either q(x) + qmodule(g_1(x), ..., g_p(x)) ∈ ⟨f_1(x), ..., f_m(x)⟩
• or q(x) + preorder(g_1(x), ..., g_p(x)) ∈ ⟨f_1(x), ..., f_m(x)⟩

where

• qmodule(g_1(x), ..., g_p(x)) = {s_1(x) g_1(x) + ... + s_p(x) g_p(x) | s_i(x) is SOS} #9,
• preorder(g_1(x), ..., g_p(x)) = {sum s_i(x)g_i(x) + sum s_ij(x) g_i(x)g_j(x) + ... + s_1..p g_1(x) ... g_p(x) | s_i(x) is SOS} (e.g. preorder(g_1(x), g_2(x)) = {s_1(x)g_1(x) + s_2(x)g_2(x) + s_12(x) s_12(x)g_1(x)g_2(x) | s_1(x), s_2(x), s_12(x) is SOS} #10 and
• ⟨f_1(x), ..., f_m(x)⟩ = {r_1(x) f_1(x) + ... + r_p(x) f_p(x) | r_i(x) is a polynomial} is the ideal of f_1(x), ..., f_m(x) #11.

See section 3.1.6 of

Blekherman, G., Parrilo, P. A., & Thomas, R. R. (Eds.). Semidefinite optimization and convex algebraic geometry SIAM 2013

For the ideal, we can do something else than creating the coefficients r_i(x):

• Groener basis #8
• Sampling #6

Not let's look at the equality constraint

@polyconstraint q(x) == 0 domain=[f_1(x) = 0, ..., f_m(x) = 0, g_1(x) >= 0, ..., g_p(x) >= 0])

If p is zero then we can simply do q(x) ∈ ⟨f_1(x), ..., f_m(x)⟩ using either of the 3 possible ways to handle ideas. But if p is not zero, what do we do ? Throw an error ? Replace it by q(x) >= 0 and q(x) <= 0 (by throwing a warning ?) ? Compute the variety determined by an algebraic set ? Any idea ?

I have split each separate task in a separate issue.

• [x] Implement qmodule #9
• [ ] Implement preorder #10
• [ ] handles ìdeals with coefficients #11
• [x] handles ideals with groebner basis #8
• [ ] handles ideals with sampling #6
• [ ] handles hypercubes faster #12

[joehuchette]

Did you intend to move all 6 of the child issues to the 0.1.0 milestone as well? Are you opposed to releasing a 0.0.1 release in the meantime? I have some time over the next few days to help get things in shape for that.

[blegat]

Glad to hear that! I created the two milestones 0.0.1 and 0.1.0 to split issues that are a priority or easier with the other issues that might take more time to address. Of course, we might want to split 0.0.1 into 0.0.1 and 0.0.2. The child issues in the 0.0.1 milestone weren't assigned by mistake but they can certainly be reassigned to 0.0.2