Multi-objective optimization aims to find a set of solutions that achieve the best trade-off among multiple conflicting objective functions. While various multi-objective optimization algorithms have been proposed so far, most of them aim to find finite solutions as an approximation of the Pareto set, which may not adequately capture the entire structure of the Pareto set, especially when the number of variables is large. To overcome this limitation, we propose a method to obtain a parametric hypersurface representing the entire Pareto set instead of a finite set of points. Since the Pareto set of an $M$-objective optimization problem typically forms an $(M-1)$-dimensional simplex, we use a B{é}zier simplex as a model to express the Pareto set. We then develop a stochastic gradient descent-based algorithm that updates the B{é}zier simplex model toward the Pareto set, introducing a preconditioning matrix to enhance convergence. Our convergence analysis demonstrated that the proposed algorithm outperforms naive stochastic gradient descent in terms of convergence rate. Furthermore, we validate the effectiveness of our method through various multi-objective optimization problem instances, including real-world problems.

This article presents our generative model for rhythm action games together with applications in business operation. Rhythm action games are video games in which the player is challenged to issue commands at the right timings during a music session. The timings are rendered in the chart, which consists of visual symbols, called notes, flying through the screen. We introduce our deep generative model, GenéLive!, which outperforms the state-of-the-art model by taking into account musical structures through beats and temporal scales. Thanks to its favorable performance, GenéLive! was put into operation at KLab Inc., a Japan-based video game developer, and reduced the business cost of chart generation by as much as half. The application target included the phenomenal "Love Live!", which has more than 10 million users across Asia and beyond, and is one of the few rhythm action franchises that has led the online era of the genre. In this article, we evaluate the generative performance of GenéLive! using production datasets at KLab as well as open datasets for reproducibility, while the model continues to operate in their business. Our code and the model, tuned and trained using a supercomputer, are publicly available.

This paper proposes a two-phase framework with a Bézier simplex-based interpolation method (TPB) for computationally expensive multi-objective optimization. The first phase in TPB aims to approximate a few Pareto optimal solutions by optimizing a sequence of single-objective scalar problems. The first phase in TPB can fully exploit a state-of-the-art single-objective derivative-free optimizer. The second phase in TPB utilizes a Bézier simplex model to interpolate the solutions obtained in the first phase. The second phase in TPB fully exploits the fact that a Bézier simplex model can approximate the Pareto optimal solution set by exploiting its simplex structure when a given problem is simplicial. We investigate the performance of TPB on the 55 bi-objective BBOB problems. The results show that TPB performs significantly better than HMO-CMA-ES and some state-of-the-art meta-model-based optimizers.

The B'ezier simplex fitting is a novel data modeling technique which utilizes geometric structures of data to approximate the Pareto set of multi-objective optimization problems. There are two fitting methods based on different sampling strategies. The inductive skeleton fitting employs a stratified subsampling from skeletons of a simplex, whereas the all-at-once fitting uses a non-stratified sampling which treats a simplex as a single object. In this paper, we analyze the asymptotic risks of those B'ezier simplex fitting methods and derive the optimal subsample ratio for the inductive skeleton fitting. It is shown that the inductive skeleton fitting with the optimal ratio has a smaller risk when the degree of a B'ezier simplex is less than three. Those results are verified numerically under small to moderate sample sizes. In addition, we provide two complementary applications of our theory: a generalized location problem and a multi-objective hyper-parameter tuning of the group lasso. The former can be represented by a B'ezier simplex of degree two where the inductive skeleton fitting outperforms. The latter can be represented by a B'ezier simplex of degree three where the all-at-once fitting gets an advantage.

Multi-objective optimization problems require simultaneously optimizing two or more objective functions. Many studies have reported that the solution set of an M-objective optimization problem often forms an (M − 1)-dimensional topological simplex (a curved line for M = 2, a curved triangle for M = 3, a curved tetrahedron for M = 4, etc.). Since the dimensionality of the solution set increases as the number of objectives grows, an exponentially large sample size is needed to cover the solution set. To reduce the required sample size, this paper proposes a Bézier simplex model and its fitting algorithm. These techniques can exploit the simplex structure of the solution set and decompose a high-dimensional surface fitting task into a sequence of low-dimensional ones. An approximation theorem of Bézier simplices is proven. Numerical experiments with synthetic and real-world optimization problems demonstrate that the proposed method achieves an accurate approximation of high-dimensional solution sets with small samples. In practice, such an approximation will be conducted in the postoptimization process and enable a better trade-off analysis.

When and why can evolutionary multi-objective optimization (EMO) algorithms cover the entire Pareto set? That is a major concern for EMO researchers and practitioners. A recent theoretical study revealed that (roughly speaking) if the Pareto set forms a topological simplex (a curved line, a curved triangle, a curved tetrahedron, etc.), then decomposition-based EMO algorithms can cover the entire Pareto set. Usually, we cannot know the true Pareto set and have to estimate its topology by using the population of EMO algorithms during or after the runtime. This paper presents a data-driven approach to analyze the topology of the Pareto set. We give a theory of how to recognize the topology of the Pareto set from data and implement an algorithm to judge whether the true Pareto set may form a topological simplex or not. Numerical experiments show that the proposed method correctly recognizes the topology of high-dimensional Pareto sets within reasonable population size.

In many-objective optimization, the dimensionality of Pareto fronts becomes higher than three, and extracting preferable points for the decision maker is a key issue in the post-optimal analysis. The aim of this study is to develop a method to detect and visualize high-dimensional knee points. We propose a new definition of knee point and a graph-based approach to detect our knee points with a visualization of the geometry of the whole Pareto front. Our method is examined via Pareto front samples of synthetic problems and a real-world airplane design.

The recent development of multi-agent simulations brings about a need for population synthesis. It is a task of reconstructing the entire population from a sampling survey of limited size (1% or so), supplying the initial conditions from which simulations begin. This paper presents a new kernel density estimator for this task. Our method is an analogue of the classical Breiman-Meisel-Purcell estimator, but employs novel techniques that harness the huge degree of freedom which is required to model high-dimensional nonlinearly correlated datasets: the crossover kernel, the k-nearest neighbor restriction of the kernel construction set and the bagging of kernels. The performance as a statistical estimator is examined through real and synthetic datasets. We provide an "optimization-free" parameter selection rule for our method, a theory of how our method works and a computational cost analysis. To demonstrate the usefulness as a population synthesizer, our method is applied to a household synthesis task for an urban micro-simulator.

In our previous study, we have proposed Adaptive Weighted Aggregation (AWA), a framework of multi-starting optimization methods based on scalarization for solving multi objective function optimization problems. The experiments in the proposal show that AWA outperforms conventional multi starting descent methods at coverage of solutions. However, the suitable termination condition for AWA has not been understood. Coverage of AWA's solutions and computational cost of AWA strongly depends on the termination condition. In this paper, we derive the necessary and sufficient iteration count to achieve high coverage and the number of approximate solutions generated until AWA stops. Numerical experiments show that AWA still achieves better coverage than the conventional methods under the derived termination condition.

Adaptive Weighted Aggregation (AWA) is a frame work of multi-starting optimization methods based on scalarization for solving multiobjective function optimization problems. It progressively generates new solutions to refine the approximation of the Pareto set or the Pareto front by the subdivision, and iteratively estimates the appropriate weight vector for scalarization in each search by the weight adaptation. Our recent study shows that AWA's solution set combinatorially increases for the number of objectives. In this paper, we propose a new subdivision and weight adaptation scheme of AWA to improve its scalability. Numerical experiments show the effectiveness of the proposed method.

The multi-starting descent method is a promising approach to unimodal multiobjective function optimization problems because of its precision of obtained solutions. Descent methods can be classified into two categories; the multiobjective descent method directly using the Jacobian matrix of objective functions and the scalarized descent method using the gradient of a scalarized objective function. In the multiobjective descent method and the scalarized descent method, a convergent point depends on an initial solution and a weight vector, respectively. However, it is difficult to choose appropriate initial solutions or weight vectors for obtaining widely and evenly distributed solutions. In order to remedy the problems of the conventional methods, we propose a multi-starting scalarized descent method named AWA that employs the Chebyshev norm method as a scalarization method and an adaptive scheme of weight vectors for the scalarization method. We show the effectiveness of the proposed method through some experiments.