This may be a repeat of a previous question i asked, but i want to make such a statement in a paper, and want to evaluate if it can be refuted beforehand:
Are there (non-linear) optimization problems where it is not/ no longer possible to walk from one local solution, to a better local solution?
And can one define the global solution in this way - the inability to walk from a local solution to a better local solution?
Then, Can one base this on higher order partial derivatives?
I am currently using higher order partial derivatives to indicate if steps are still possible, post excel solver NLP (and evolutionary), and to identify such steps.
If i obtain steps still possible this way, i am walking to better solutions.
If i no longer am able to identify steps through higher order partial derivatives, can i say i have reached the global solution?
A higher order partial derivative would be the delta in objective function in response to a delta change in 3 or more coefficients. It differs from 2nd order partial derivatives, and this is evident when you consider the actual calculation.
I would not make such a statement in a paper. It can easily be refuted.
If an algorithm is unable to walk from a local solution to a better local solution, it only means that it locally converges. The global solution could be far away from that local one.
In general, I would use a set of uniformly distributed random starting points for finding a set of local optimal solutions. If these local solutions found from the different starting points are close enough to each other (or the same), then it is likely that this is the global solution. The more random starting points you use (the bigger the density of the starting points in the solution domain) the higher the probability that the solution is global one. However, there is no rigorous proof of that. This will be just a heuristic judgement.
I would refrain from the use of higher order partial derivatives (higher than 2). Numerical calculation of high order partial derivatives is computationally unstable, lose the numerical accuracy very fast, up to total non-usability for deciding on the new step in search of the solution.
My optimization problem is sensitive to the initial solution. So i will simply interpret this as the (non-linear) nature of the problem, and also in terms of your heuristic of a set of initial solutions or (as) starting points.
I will need to think what such a set would look like in my case.
you mention numerical calculation of higher order partial derivatives. And that they are unstable. I use both numerical and empirical calculation of higher order partial derivatives. And yes, sometimes the numerical ones are less accurate.
Your answer is in terms of the algorithm converging on a local solution. And then a set of starting points.
I appreciate this and have no issue with this.
But lets argue that this is the outside to inside way of doing it. I have no better words to state it. Working from the outside, inwards. If that statement even holds.
It implies that there may also be the inside to outside approach. The opposite approach. I dont know if it will be more or less efficient. But i am interested in whether it is possible at all.
Is it mathematically possible at all?
If the current local solution still has a positive gradient, it can still walk - improve.
It then depends on whether or how the particular algorithm considers this.
I am using higher order partial derivatives to test for remaining positive gradient.
I consider both numerical and empirical higher order partial derivatives.
And it seems i do a bit more than higher order partial derivatives to determine remaining positive gradient.
i calculate it as:
PD(xyz) ~ PD(x) + PD(y) + PD(z)
This would be a 3rd order partial derivative.
But i am also multiplying with all sign combinations
In the case of the 3rd order partial derivative it would be:
PD(xyz) ~ aPD(x) + bPD(y) + cPD(z)
a, b, c =
---
--+
-+-
-++
+--
+-+
++-
+++
It can also be stated as an optimization sub-problem, to identify whether a positive gradient is still possible from among the set of coefficient gradients.
If at best, it forms a test whether a better local solution to the current local solution is still possible.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics