jump-dev / jump-dev/SumOfSquares.jl

Implement constraint on semialgebraic set

Open
#4 2 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.