Fix for Bug in Powell's Method, issue #51

[smilingprogrammer]

Motivation

This PR solves the bug in the current implementation of the Powell's Method, where the change in direction only happens orthogonally (or 90°) to the previous direction. Issue #51 .

Description of the changes

1. We now track the cycle start and end positions, by storing the best‑found position at the beginning of each n‑direction cycle in last_best_position. After completing all n one‑dimensional searches, it records the new best position in current_best_position.

2. It now computes displacement vector by calculating the displacement = current_best_position – last_best_position and normalize it to unit length. This now represents the “true” sweeping direction of the search over the last cycle.

3. It drops the oldest direction and append new_direction, allowing any angle in [0°, 180°] instead of only the coordinate axes.

4. Now in setup_line_search(), once the Hill-climb is instantiated, it immediately sets the Hill-climb’s

   positions_valid, scores_valid, best_pos, best_score, current_pos, pos_current
   

   to the grid‐index of the current global best so that every line search truly starts from the optimum, rather than from a random neighbor.

5. Removed the branch that used init_pos() for the first few sub‑iterations; now every sub‑step refines from the known best along that line.

Now through continuous‑angle updates which happens in update_search_directions() method, the optimizer measures how far it has moved during each complete cycle and then scales that movement to a unit vector. This unit vector replaces the oldest search direction, allowing the algorithm to adopt any angle between 0° and 180°. With this, It lets the optimizer follow the function’s actual main direction, instead of only moving in right‑angle turns.

[smilingprogrammer]

After carefully looking at the test failure, it seems the test failure came from setting the "random" in HillClimb initialize here to zero. It looks like there is an expectation of what should be set here, which afected the SimulatedAnnealingOptimizer expectations.

[SimonBlanke]

@smilingprogrammer Thanks for opening the PR :-) I will take a closer look into this PR on the weekend.

[SimonBlanke]

It just searches in 90-degree angles like before. Later it falls back to normal hill-climbing. I checked multiple of those search-path plots. It is always the same behaviour.

[smilingprogrammer]

Hi @SimonBlanke Thanks for the feedback, tto move forward, can you provide me with the code you used for the testing above, which displays how it works in real time.

And also what the simulation (above graph gif) expected to look like after making corrections.

I think this will help a lot, to get clarity on what the expectation should be.

[SimonBlanke]

The module I created the plot with can be found here: https://github.com/SimonBlanke/gradient-free-optimization-plots/blob/master/gradient_free_optimization_plots/search_path_gif/search_path_gif.py#L22

But beware, that I just use this privately for my work. At the moment this is not documented. An example of the API would look like this:

spg = SearchPathGif(path=".")
spg.add_optimizer(
    optimizer=optimizer_class,
    opt_para={},
    initialize=initialize,
    n_iter=n_iter,
    random_state=random_state,
)
spg.add_test_function(
    objective_function=objective_function,
    search_space=search_space,
    constraints=constraints_list,
)

spg.add_plot_layout(
    name="my_plot",
    title=True,
)
spg.create()

And also what the simulation (above graph gif) expected to look like after making corrections.

Algorithm from your PR: 90 degree angles and later normal hill-climbing

Algorithm as discussed: It should allow a continuous range of angles.

Please reread explanations of powell's direction method to understand the goal. Unfortunately I could not find the official paper for this. This presentation seems to offer some easy to follow explanations and plots: https://empossible.net/wp-content/uploads/2020/08/Lecture-Powells-Method-1.pdf

[smilingprogrammer]

Thank you for the detailed reply.

[smilingprogrammer]

Hi, sorry i have been away for a while. I have tried refactoring to solve the issues requirement. Before submitting a new PR, i have provided the new update here. Also this is the graph from my tests;

Looking forward to your response.

[SimonBlanke]

You do not have to open a new PR. You can add your corrections to this PR if you like.

Is the algorithm behaviour in this graph what you would expect from the powell's direction method?

[smilingprogrammer]

You do not have to open a new PR. You can add your corrections to this PR if you like.

Is the algorithm behaviour in this graph what you would expect from the powell's direction method?

Yes the graph direction behaviour was what i got from the new powell's method that i included in the gist link.

[SimonBlanke]

Yes the graph direction behaviour was what i got from the new powell's method that i included in the gist link.

yes I see that. My question was about the way powell's direction method should work (in theory/from literature) vs how your implementation of powell's direction method works according to the search-path-gif you provided. It is difficult to see how this represents the algorithm.

[smilingprogrammer]

What should be the expectation here? Will be better if there is a description of what the expectation should be. The Powell's method has a really low resource on it that is available online. The pdf you shared might even be the most informative i have come accross for this method.

[smilingprogrammer]

I have found the paper!!! https://sci-hub.se/10.1093/comjnl/7.2.155

Will take my time to go through it. Question; Should i still stick to the Hill Climb for the line search during implementation?

[SimonBlanke]

Question; Should i still stick to the Hill Climb for the line search during implementation?

Yes, you can do that. But it is not a requirement. The main focus is on fixing the limited angle when changing direction.