Polynomial maximum

Question

I have a polynomial of order N (where N is even). This polynomial is equal to minus infinity for x minus / plus infinity (thus it has a maximum). What I'm doing right now takes the derivative of the polynomial using a polyder , then I find the roots of the N-1st order polynomial using the roots function in Matlab, which returns the N-1 solutions. Then I choose a real root that really maximizes the polynomial. The problem is that I update my polynomial many times, and at each step I use the procedure described above to find the maximizer. Therefore, the root function takes too much computation time, which slows down my application. Is there a way, either in Matlab, or in the proposed algorithm that makes this maximization a computationally efficient way (i.e., just finding one solution instead of N-1 solutions)? Thanks.

Edit: I would also like to know if there is a procedure in Matlab that returns only real roots instead of roots , which returns all real / complex ones.

Answer 1

There is a file exchange message from Steve Morris, which finds all the real roots of the functions at a given interval. He does this by interpolating the polynomial by the Chebychev polynomial and finding its roots.

You can change the eig score of the companion matrix there eigs . This allows you to find only one (or several) roots and save time (there is a chance that Chebychev’s roots or extremes can be calculated analytically, although I could not find a good link for this (or even bad) one in this regard ...) )

Another attempt you can make in speeding up is that the polyder does nothing more than

 Pprime = (numel(P)-1:-1:1) .* P(1:end-1); 

for your polynomial P In addition, roots does nothing more than search for the eigenvalues ​​of the matrix of related devices, so you can find these eigenvalues ​​yourself, which prevents roots from being called. This can be useful because calls to non-built-in functions inside a loop prevent the Matlab JIT compiler from translating the loop into machine language. Otherwise, this can lead to a large increase in speed (ratios of 100 or more are not uncommon).

Answer 2

I think you are probably out of luck. If the coefficients of the polynomial vary at each time step in an arbitrary way, then ultimately you are faced with a separate and unrelated optimization problem at each stage. There is not enough information to calculate only a subset of the roots of a derivative polynomial - how would you know which derivative root provides the maximum stationary point of a polynomial without comparing the value of the function for ALL derivatives of the roots? If your polynomial coefficients were perturbed at each step only in a (limited) small amount or in a predictable way, then it is quite possible that you can try something iterative to refine the solution at each step (for example, something crude, such as using your previous roots as the starting point of a new set of iterations newton to identify updated derived roots), but the question does not suggest that this is actually the case, so I just guess. I could be completely wrong, but you might just be out of luck if you get something faster, if you cannot provide additional information about the existence of any relationship between the polynomials generated at each step.