jump-dev / jump-dev/SumOfSquares.jl
Implement constraint on semialgebraic set
- Dominant language
- Julia
- Stars
- 131
- Forks
- 26
- PR merge metrics
- No merged PRs in 30d
Description
Let's check the different way we can implement the SOS constraint
``` julia
@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
``` julia
@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
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the constraint semantics in section 3.1.6 of the cited book, then review the related issues #10, #11, and #6. Resolve how equality constraints should behave when inequalities define the domain, choose the supported ideal-handling approach, and document the resulting behavior as done.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100