error when some elements of f are zero about homotopycontinuation.jl HOT 13 CLOSED

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.