According to one embodiment, a parameter optimization apparatus stores data sets which each include a first parameter value of a first number of dimensions and an observed value of an objective function corresponding to the first parameter value. The apparatus determines a search space of a second number of dimensions smaller than the first number of dimensions. The apparatus acquires one or more data sets each having a first parameter value present within a predetermined distance from the search space. The apparatus searches the search space for a first parameter value that may optimize the objective function, using a surrogate model of an objective function based on one or more data sets acquired.