Comments (13)
By the way, is there a (practical) extension of these methods to find the extrema of a polynomial on a compact basic semialgebraic set? eg minimize p(x) on the sphere norm(x) <= 1?
For semialgebraic sets I don not see an immediate solution. For algebraic sets, however, you can solve the Langrange multipliers equations.
from homotopycontinuation.jl.
I saw #87 on "overdetermined systems", which have more equations m than variables n (as I read from here). so now dev should be able to handle non-square systems with m > n?
Yes and no. We can handle now overdetermined systems, but for this you have to provide explicit start solutions which we should track.
Would you expect that in general it would be faster to do the lagrangian approach or to just use the new dev functionality of this package on the overdetermined system?
You need to use the lagrangian approach since we cannot construct a suitable start system.
I read about the lagrangian equations for finding extrema of a polynomial on an algebraic set, as you suggested. Do you know if that process would be not too difficult to automate in Julia, or would I instead need to use a CAS (maybe nemo.jl)?
You can do this all with e.g. DynamicPolynomials
. Instead of your polynomial f
you consider the Lagrangian and hand to solve the gradient of it. You only need to introduce new variables (e.g. with similarvariable
) and the compute the gradient as you did previously.
I read about the witness set, which I understand is for "underdetermined" systems as @saschatimme mentioned before. Makes sense! Is there any plan to implement that?
There are plans for this, but at the moment we do not have a specific timeline in mind to get this implemented.
from homotopycontinuation.jl.
Hi,
I agree that the error message is not really helpful. That an error is thrown here is indeed a bug, but the problem is more fundamental.
We currently can only solve square systems of polynomials, i.e., the number of polynomials is the same as the number of variables. The assumption which is implicit in this statement is that all these polynomials are non-zero and algebraically independent. With this assumption the solution set is finite.
If now one or more of your polynomials are zero than your solution set is at least 1-dimensional (to be precise it is an affine variety of dimension at least 1). There are ways to handle this situation through something called a witness set but so far this is not implemented.
P.S.: Just that you know I currently work on a new and much improved version on the dev
branch. It is already working but will need some more polish until it will be released (I hope to get it done in the next 2-4 weeks).
from homotopycontinuation.jl.
OK, good to know, thanks! I'll close the issue.
from homotopycontinuation.jl.
But I think we can catch this case with an appropriate error message. I will keep the issue open until this is added.
from homotopycontinuation.jl.
Makes sense!
By the way, is there a (practical) extension of these methods to find the extrema of a polynomial on a compact basic semialgebraic set? eg minimize p(x) on the sphere norm(x) <= 1?
from homotopycontinuation.jl.
@PBrdng @saschatimme, thank you for the information! I am fairly unfamiliar with the terminology and theory in this area, as I'm coming from a numerical optimization background rather than an rigorous algebra background. I will need to use these sorts of methods as subroutines in my research in the near future, and I am keen to contribute down the track.
EDITS:
I saw #87 on "overdetermined systems", which have more equations m than variables n (as I read from here). so now dev should be able to handle non-square systems with m > n?
I read about the lagrangian equations for finding extrema of a polynomial on an algebraic set, as you suggested. Do you know if that process would be not too difficult to automate in Julia, or would I instead need to use a CAS (maybe nemo.jl)?
Would you expect that in general it would be faster to do the lagrangian approach or to just use the new dev functionality of this package on the overdetermined system?
(btw I am only concerned with real numbers)
from homotopycontinuation.jl.
EDIT:
I read about the witness set, which I understand is for "underdetermined" systems as @saschatimme mentioned before. Makes sense! Is there any plan to implement that? It sounds harder to do than the overdetermined case.
from homotopycontinuation.jl.
Thank you so much @saschatimme!
from homotopycontinuation.jl.
You need to use the lagrangian approach since we cannot construct a suitable start system.
For any choice of degree and number of variables of the polynomial, there is a suitable starting system as described by Robeva in Theorem 2.3 in https://arxiv.org/pdf/1409.6685.pdf
This starting system together with the Straight Line Homotopy should solve the Lagrangian equations efficiently. Implementing this is on my to-do-list!
from homotopycontinuation.jl.
I will close this issue since the warning for the original issue is on the current master branch.
from homotopycontinuation.jl.
Just wondering if there are any plans for implementing witness sets? Is there a public tracker for future dev plans/priorities?
from homotopycontinuation.jl.
Depends on what you exactly want. Making it easier to formulate intersections with linear spaces (#134) is on the agenda. We also offer a seminar this semester where one of the suggested projects is related to the degree of a variety, i.e., there some form of witness sets is needed. But this will probably be restricted to the case of an irreducible variety, or at most a pure dimensional one (i.e. each irreducible component has the same dimension).
Do you have a specific application in mind?
Is there a public tracker for future dev plans/priorities?
So far not but this is also partly due to the fact that only Paul and I are so far contributing to the package and our efforts are somewhat correlated with our own needs.
from homotopycontinuation.jl.
Related Issues (20)
- e not defined for sqrt() HOT 6
- Converting from Nemo.fmpq_mpoly to HomotopyContinuation.Expression HOT 3
- cache_min_length failing with empty iterator HOT 1
- Seed for mondromy not working as intended
- Symbolic linear system solving not supported by ModelKit HOT 2
- Issues dealing with BigFloat coefficients HOT 6
- find_start_pair failing on some linearly-parametrized square systems HOT 2
- `OP_POW` not defined HOT 5
- Add checkpoints for monodromy_solve
- HC fails to solve sanity check HOT 7
- Strange behaviour of numerical irreducible decomposition HOT 4
- Can't build a system with Unicode symbols in variable names HOT 2
- `Threads.resize_nthreads!` is deprecated HOT 1
- Non-real solution incorrectly certified as real
- Start System Complaints: Incorrect Rank Calculation HOT 2
- What is the best way to approximate trigonometric functions in HC HOT 2
- LaTeX pretty printing breaks for (negative) exponents HOT 2
- sing_accuracy not recognised as endgame parameter HOT 9
- Missing Solutions HOT 8
- Arblib dependencies incompatible with Oscar.jl HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from homotopycontinuation.jl.