Skip to content

Add _compute_3d for hypervolume computation#6112

Merged
HideakiImamura merged 3 commits intooptuna:masterfrom
shmurai:hypervolume_3d
May 31, 2025
Merged

Add _compute_3d for hypervolume computation#6112
HideakiImamura merged 3 commits intooptuna:masterfrom
shmurai:hypervolume_3d

Conversation

@shmurai
Copy link
Copy Markdown
Contributor

@shmurai shmurai commented May 31, 2025 •
edited
Loading

Motivation

_compute_hv has room of improvement on 3D points.

Description of the changes

I implemented a dedicated function for 3D points (_compute_3d)

@not522 not522 self-assigned this May 31, 2025
@not522 not522 changed the title Add _compute_3d for hypervolume computation Add _compute_3d for hypervolume computation May 31, 2025
@toshihikoyanase toshihikoyanase added the enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. label May 31, 2025
@not522 not522 added the sprint-20250531 PR from the online sprint event May 31, 2025. label May 31, 2025
@not522
Copy link
Copy Markdown
Member

not522 commented May 31, 2025

Thank you for your PR! I confirmed this PR makes the following scripts faster.

import optuna

def objective(trial):
    x = trial.suggest_float("x", -100, 100)
    y = trial.suggest_int("y", -100, 100)
    return x**2 + y**2, (x - 2) ** 2 + (y - 2) ** 2, (x + 2) ** 2 + (y + 2) ** 2

sampler = optuna.samplers.TPESampler(seed=42)
study = optuna.create_study(sampler=sampler, directions=["minimize"]*3)
study.optimize(objective, n_trials=1000)
import optuna

def objective(trial):
    x = trial.suggest_float("x", 0, 1)
    y = trial.suggest_float("y", 0, 1)
    z = trial.suggest_float("z", 0, 1)
    trial.set_user_attr("constraints", [x ** 2 + y ** 2 + z ** 2 - 1])
    return x, y, z

def constraints_func(trial):
    return trial.user_attrs["constraints"]

sampler = optuna.samplers.NSGAIISampler(seed=42, constraints_func=constraints_func)
study = optuna.create_study(directions=["maximize", "maximize", "maximize"], sampler=sampler)
study.optimize(objective, n_trials=10000)

reference_point=[0, 0, 0]
optuna.visualization.plot_hypervolume_history(study, reference_point)

@not522
Copy link
Copy Markdown
Member

not522 commented May 31, 2025

Could you check the following points?

  1. Could you add a test to check _compute_3d and _compute_hv return the same results?
  2. I think this pre-computation is not necessary for _compute_3d.

    optuna/optuna/_hypervolume/wfg.py

    Lines 116 to 118 in d244295

    unique_lexsorted_loss_vals = np.unique(loss_vals, axis=0)
    on_front = _is_pareto_front(unique_lexsorted_loss_vals, assume_unique_lexsorted=True)
    sorted_pareto_sols = unique_lexsorted_loss_vals[on_front]

@shmurai
Copy link
Copy Markdown
Contributor Author

shmurai commented May 31, 2025

Precomputation (_is_pareto_front) is also O(N^2) and it will not do much harm even in the worst case.
Also, it can improve space complexity for the case in which the number of points on the pareto front is much smaller than that of all points:

  • _is_pareto_front requires O(N) space
  • _compute_3d uses Θ(N^2) space

Thus I think we may keep the precomputation.

@nabenabe0928
Copy link
Copy Markdown
Contributor

nabenabe0928 commented May 31, 2025

Note

not522
not522 approved these changes May 31, 2025
View reviewed changes
Copy link
Copy Markdown
Member

@not522 not522 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM!

@HideakiImamura HideakiImamura self-assigned this May 31, 2025
@HideakiImamura
Copy link
Copy Markdown
Member

HideakiImamura commented May 31, 2025 •
edited
Loading

I can't see any speedup with the following codes (same as @not522 suggested one). Am I misunderstanding something?

I completely misunderstood. I didn't run pip install -e ., so I measured the speed only on the master branch. I fixed and got the following improvements. About x2 improvement on the multi-objective TPESampler and about x5improvement on the hypervolume history plot.

  • Code
import optuna
import time

optuna.logging.set_verbosity(optuna.logging.WARNING)

def test_pr6112():
    def objective(trial):
        x = trial.suggest_float("x", -100, 100)
        y = trial.suggest_int("y", -100, 100)
        return x**2 + y**2, (x - 2) ** 2 + (y - 2) ** 2, (x + 2) ** 2 + (y + 2) ** 2

    sampler = optuna.samplers.TPESampler(seed=42)
    study = optuna.create_study(sampler=sampler, directions=["minimize"]*3)

    start = time.time()
    study.optimize(objective, n_trials=1000)
    end = time.time()
    print(f"Time taken: {end - start} seconds for optimization without constraints")

def test_pr6112_with_constraints():
    def objective(trial):
        x = trial.suggest_float("x", 0, 1)
        y = trial.suggest_float("y", 0, 1)
        z = trial.suggest_float("z", 0, 1)
        trial.set_user_attr("constraints", [x ** 2 + y ** 2 + z ** 2 - 1])
        return x, y, z

    def constraints_func(trial):
        return trial.user_attrs["constraints"]

    sampler = optuna.samplers.NSGAIISampler(seed=42, constraints_func=constraints_func)
    study = optuna.create_study(directions=["maximize", "maximize", "maximize"], sampler=sampler)

    start = time.time()
    study.optimize(objective, n_trials=10000)
    end = time.time()
    print(f"Time taken: {end - start} seconds for optimization with constraints")

    reference_point=[0, 0, 0]
    start = time.time()
    fig = optuna.visualization.plot_hypervolume_history(study, reference_point)
    end = time.time()
    print(f"Time taken for hypervolume plot: {end - start} seconds")
    fig.write_image("/path/to/hypervolume_plot.png")


if __name__ == "__main__":
    test_pr6112()
    test_pr6112_with_constraints()
  • Output on master
> python work/test-pr6112.py 
Time taken: 45.70528244972229 seconds for optimization without constraints
/usr/local/lib/python3.12/dist-packages/optuna/_experimental.py:31: ExperimentalWarning: Argument ``constraints_func`` is an experimental feature. The interface can change in the future.
  warnings.warn(
Time taken: 20.187578678131104 seconds for optimization with constraints
/xxx/test-pr6112.py:41: ExperimentalWarning: plot_hypervolume_history is experimental (supported from v3.3.0). The interface can change in the future.
  fig = optuna.visualization.plot_hypervolume_history(study, reference_point)
Time taken for hypervolume plot: 54.03933668136597 seconds
  • Output on this PR
> python work/test-pr6112.py 
Time taken: 23.279673099517822 seconds for optimization without constraints
/mnt/nfs-mnj-hot-99-home/mamu/optuna/optuna/_experimental.py:32: ExperimentalWarning: Argument ``constraints_func`` is an experimental feature. The interface can change in the future.
  warnings.warn(
Time taken: 24.83038330078125 seconds for optimization with constraints
/mnt/nfs-mnj-hot-99-home/mamu/optuna/work/test-pr6112.py:41: ExperimentalWarning: plot_hypervolume_history is experimental (supported from v3.3.0). The interface can change in the future.
  fig = optuna.visualization.plot_hypervolume_history(study, reference_point)
Time taken for hypervolume plot: 11.37790322303772 seconds

HideakiImamura
HideakiImamura approved these changes May 31, 2025
View reviewed changes
Copy link
Copy Markdown
Member

@HideakiImamura HideakiImamura left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks very good.

@HideakiImamura HideakiImamura merged commit 1fe6f76 into optuna:master May 31, 2025
14 checks passed
@HideakiImamura HideakiImamura added this to the v4.4.0 milestone May 31, 2025
@nabenabe0928 nabenabe0928 mentioned this pull request Jun 3, 2025
Merged
@nabenabe0928 nabenabe0928 mentioned this pull request Oct 16, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@not522 not522 not522 approved these changes

@HideakiImamura HideakiImamura HideakiImamura approved these changes

Assignees

@not522 not522

@HideakiImamura HideakiImamura

Labels

enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. sprint-20250531 PR from the online sprint event May 31, 2025.

Projects

None yet

Milestone

v4.4.0

Development

Successfully merging this pull request may close these issues.

5 participants

@shmurai @not522 @nabenabe0928 @HideakiImamura @toshihikoyanase