Hi all. Given a parameter Vector{Float64} called x, I want to find x* such that f(x*) > f(x) for all possible permutations of x, where f maps x to a single Float64. I could (and have successfully) used a general optimization algorithm for this. However, this feels like overkill, since I know before I start the algorithm that I want the solution x* to be a permutation of the initial value of x (call it x0).
Are there some standard solutions to this problem already available in Julia? It occurred to me that a sorting algorithm might do the trick, ie an algorithm that swaps two elements in x and then checks whether this increases or decreases f(x). I could write my own custom sort for this purpose, but was wondering if anyone was aware of a clever way I could use the existing sort functions?
Thanks in advance to any responders. Cheers -Colin
EDIT: After thinking and reading, I don’t think there is any magic trick other than to perform a discrete optimization technique like simulated annealing or genetic algorithm. I’ll leave the post up just in case I’m missing something obvious.
it’s not hard to get all permutations of x, for example, you can use Combinatorics
The problem is then what – if you don’t have more information, the best you can do is try all the permutations and find minimum? it doesn’t feel like a sorting algorithm, just brute force
Yeah I think it was one of those moments where I thought I could do something clever, but upon deeper reflection it is actually a pretty standard problem, with the usual solutions (although I definitely can’t use brute force for this one as the vectors are too large - so heuristic algorithm looks to be the go).
f is a little difficult to unpack. f(x) itself is fairly straightforward: it is a measure of goodness of fit in a linear model. But x itself is used in the construction of the variables of that model in a fairly complex and non-linear way.
You may want to use a local search algorithm on the space of permutations. For example, using neighbourhoods consisting of single swaps from the currently evaluated permutation.
A local search algorithm could be Simulated Annealing. Obviously there are many variations to local search and even if they don’t produce the absolutely optimal answer, the permutation space is usually too big for complete enumeration.
