Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization

## Abstract

Abstract Multi-objective optimization can be found in many real-world applications where some conflicting objectives can not be optimized by a single solution. Existing optimization methods often focus on finding a set of Pareto solutions with different optimal trade-offs among the objectives. However, the required number of solutions to well approximate the whole Pareto optimal set could be exponentially large with respect to the number of objectives, which makes these methods unsuitable for handling many optimization objectives. In this work, instead of finding a dense set of Pareto solutions, we propose a novel Tchebycheff set scalarization method to find a few representative solutions (e.g., 5) to cover a large number of objectives (e.g., > 100 absent 100 >100 ) in a collaborative and complementary manner. In this way, each objective can be well addressed by at least one solution in the small solution set. In addition, we further develop a smooth Tchebycheff set scalarization approach for efficient optimization with good theoretical guarantees. Experimental studies on different problems with many optimization objectives demonstrate the effectiveness of our proposed method.

## 1 Introduction

In real-world applications, it is very often that many optimization objectives should be considered at the same time. Examples include manufacturing or engineering design with various specifications to achieve [, ], decision-making systems with different factors to consider [, ], and molecular generation with multiple criteria to satisfy [, ]. For a non-trivial problem, these optimization objectives conflict one another. Therefore, it is very difficult, if not impossible, for a single solution to accommodate all objectives at the same time [, ].

In the past several decades, much effort has been made to develop efficient algorithms for finding a set of Pareto solutions with diverse optimal trade-offs among different objectives. However, the Pareto set that contains all optimal trade-off solutions could be manifold in the decision space, of which the dimensionality can be large for a problem with many objectives []. The number of required solutions to well approximate the whole Pareto set will increase exponentially with the number of objectives, which leads to prohibitively high computational overhead. In addition, a large solution set with high-dimensional objective vectors could easily become unmanageable for decision-makers. Indeed, a problem with more than $3$ objectives is already called the many-objective optimization problem [, ], and existing methods will struggle to deal with problems with a significantly larger number of optimization objectives [].

In this work, we investigate a new approach for many-objective optimization, which aims to find a small set of solutions (e.g., $5$) to handle a large number of objectives (e.g., $>100$). In the optimal case, each objective should be well addressed by at least one solution in the small solution set as illustrated in Figure [1](#S2.F1)(d). This setting is important for different real-world applications with many objectives to optimize, such as finding complementary engineering designs to satisfy various criteria [], producing a few different versions of advertisements to serve a large group of diverse audiences [, ], and building a small set of models to handle many different data [, ] or tasks [, ]. However, this demand has received little attention from the multi-objective optimization community. To properly handle this setting, this work makes the following contributions:

- •
We propose a novel Tchebycheff set (TCH-Set) scalarization approach to find a few optimal solutions in a collaborative and complementary manner for many-objective optimization.
- •
We further develop a smooth Tchebycheff set (STCH-Set) scalarization approach to tackle the non-smoothness of TCH-Set scalarization for efficient gradient-based optimization.
- •
We provide theoretical analyses to show that both the proposed TCH-Set and STCH-Set scalarization approaches enjoy good theoretical properties for multi-objective optimization.
- •
We conduct experiments on various multi-objective optimization problems with many objectives to demonstrate the efficiency of our proposed method. (^1^11Our code to reproduce all experimental results will be released upon publication.)

## 2 Preliminaries and Related Work

### 2.1 Multi-Objective Optimization

Figure: (a) $10$ Solutions
Refer to caption: /html/2405.19650/assets/x1.png

In this work, we consider the following multi-objective optimization problem:

$$ $\min_{\boldsymbol{x}\in\mathcal{X}}\ \boldsymbol{f}(\boldsymbol{x})=(f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\cdots,f_{m}(\boldsymbol{x})),$ (1) $$

where $\boldsymbol{x}\in\mathcal{X}$ is a solution and $\boldsymbol{f}(\boldsymbol{x})=(f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\cdots,f_{m}(\boldsymbol{x}))\in\mathbb{R}^{m}$ are $m$ differentiable objective functions. For a non-trivial problem, there is no single solution $\boldsymbol{x}^{*}$ that can optimize all objective functions at the same time. Therefore, we have the following definitions of dominance, (weakly) Pareto optimality, and Pareto set/front for multi-objective optimization []:

###### Definition 1 (Dominance and Strict Dominance) .

Let $\boldsymbol{x}^{(a)},\boldsymbol{x}^{(b)}\in\mathcal{X}$ be two solutions for problem ([1](#S2.E1)), $\boldsymbol{x}^{(a)}$ is said to dominate $\boldsymbol{x}^{(b)}$, denoted as $\boldsymbol{f}(\boldsymbol{x}^{(a)})\prec\boldsymbol{f}(\boldsymbol{x}^{(b)})$, if and only if $f_{i}(\boldsymbol{x}^{(a)})\leq f_{i}(\boldsymbol{x}^{(b)})\ \forall i\in\{1,...,m\}$ and $f_{j}(\boldsymbol{x}^{(a)})<f_{j}(\boldsymbol{x}^{(b)})\ \exists j\in\{1,...,m\}$. In addition, $\boldsymbol{x}^{(a)}$ is said to strictly dominate $\boldsymbol{x}^{(b)}$ (i.e., $\boldsymbol{f}(\boldsymbol{x}^{(a)})\prec_{\text{strict}}\boldsymbol{f}(\boldsymbol{x}^{(b)})$), if and only if $f_{i}(\boldsymbol{x}^{(a)})<f_{i}(\boldsymbol{x}^{(b)})\ \forall i\in\{1,...,m\}$.

###### Definition 2 ((Weakly) Pareto Optimality) .

A solution $\boldsymbol{x}^{\ast}\in\mathcal{X}$ is Pareto optimal if there is no $\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\boldsymbol{x})\prec\boldsymbol{f}(\boldsymbol{x}^{\ast})$. A solution $\boldsymbol{x}^{\prime}\in\mathcal{X}$ is weakly Pareto optimal if there is no $\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\boldsymbol{x})\prec_{\text{strict}}\boldsymbol{f}(\boldsymbol{x}^{\prime})$.

###### Definition 3 (Pareto Set and Pareto Front) .

The set of all Pareto optimal solutions $\boldsymbol{X}^{*}=\{\boldsymbol{x}\in\mathcal{X}|\boldsymbol{f}(\hat{}\boldsymbol{x})\nprec\boldsymbol{f}(\boldsymbol{x})\ \forall\hat{}\boldsymbol{x}\in\mathcal{X}\}$ is called the Pareto set. Its image in the objective space $\boldsymbol{f}(\boldsymbol{X}^{*})=\{\boldsymbol{f}(\boldsymbol{x})\in\mathbb{R}^{m}|\boldsymbol{x}\in\boldsymbol{X}^{*}\}$ is called the Pareto front.

Under mild conditions, the Pareto set and front could be on an $(m-1)$-dimensional manifold in the decision or objective space [], which contains infinite Pareto solutions. Many optimization methods have been proposed to find a finite set of solutions to approximate the Pareto set and front [, , ]. If at least $k$ solutions are needed to handle each dimension of the Pareto front, the required number of solutions could be $O(k^{(m-1)})$ for a problem with $m$ optimization objectives. Two illustrative examples with a set of solutions to approximate the Pareto front for problems with $2$ and $3$ objectives are shown in Figure [1](#S2.F1). However, the required number of solutions will increase exponentially with the objective number $m$, leading to an extremely high computational overhead. It could also be very challenging for decision-makers to efficiently handle such a large set of solutions. Indeed, for a problem with many optimization objectives, a large portion of the solutions could become non-dominated and hence incomparable with each other [, ].

In the past few decades, different heuristic and evolutionary algorithms have been proposed to tackle the many-objective black-box optimization problems [, , ]. These algorithms typically aim to find a set of a few hundred solutions to handle problems with $4$ to a few dozen optimization objectives [, ]. However, they still struggle to tackle problems with significantly many objectives (e.g., $>100$), and cannot efficiently solve large-scale differentiable optimization problems.

###### Definition 1 (Dominance and Strict Dominance) .

###### Definition 2 ((Weakly) Pareto Optimality) .

###### Definition 3 (Pareto Set and Pareto Front) .

### 2.2 Gradient-based Multi-Objective Optimization

When all objective functions are differentiable with gradient $\{\nabla f_{i}(\boldsymbol{x})\}_{i=1}^{m}$, we have the following definition for Pareto stationarity:

###### Definition 4 (Pareto Stationary Solution) .

A solution $\boldsymbol{x}\in\mathcal{X}$ is Pareto stationary if there exists a set of weights $\boldsymbol{\alpha}\in\boldsymbol{\Delta}^{m-1}=\{\boldsymbol{\alpha}|\sum_{i=1}^{m}\alpha_{i}=1,\alpha_{i}\geq 0\ \forall i\}$ such that the convex combination of gradients $\sum_{i=1}^{m}\alpha_{i}\nabla f_{i}(\boldsymbol{x})=\bm{0}$.

###### Definition 4 (Pareto Stationary Solution) .

#### Multiple Gradient Descent Algorithm

One popular gradient-based approach is to find a valid gradient direction such that the values of all objective functions can be simultaneously improved [, , ]. The multiple gradient descent algorithm (MGDA) [, ] obtains a valid gradient $\boldsymbol{d}_{t}=\sum_{i=1}^{m}\alpha_{i}\nabla f_{i}(\boldsymbol{x})$ by solving the following quadratic programming problem at each iteration:

$$ $\displaystyle\min_{\alpha_{i}}||\sum\nolimits_{i=1}^{m}\alpha_{i}\nabla f_{i}(\boldsymbol{x}_{t})||_{2}^{2},~{}~{}~{}s.t.~{}\sum\nolimits_{i=1}^{m}\alpha_{i}=1,~{}~{}~{}\alpha_{i}\geq 0,\forall i=1,...,m,$ (2) $$

and updates the current solution by a simple gradient descent $\boldsymbol{x}_{t+1}=\boldsymbol{x}_{t}-\eta_{t}\boldsymbol{d}_{t}$. If $\boldsymbol{d}_{t}=\bm{0}$, it means that there is no valid gradient direction that can improve all objectives at the same time, and therefore $\boldsymbol{x}_{t}$ is a Pareto stationary solution [, ]. This idea has inspired many adaptive gradient methods for multi-task learning [, , , , , , , , , ]. Different stochastic multiple gradient methods have also been proposed in recent years [, , , , ].

The location of solutions found by the original MGDA is not controllable, and several extensions have been proposed to find a set of diverse solutions with different trade-offs [, , , ]. However, a large number of solutions is still required for a good approximation to the Pareto front. For solving problems with many objectives, MGDA and its extensions will suffer from a high computational overhead due to the high-dimensional quadratic programming problem ([2](#S2.E2)) at each iteration. In addition, since a large portion of solutions is non-dominated with each other, it could be very hard to find a valid gradient direction to optimize all objectives at the same time.

#### Scalarization Method

Another popular class of methods for multi-objective optimization is the scalarization approach [, ]. The most straightforward method is linear scalarization []:

$$ (Linear Scalarization) $\displaystyle\min_{\boldsymbol{x}\in\mathcal{X}}g^{(\text{LS})}(\boldsymbol{x}|\boldsymbol{\lambda})=\sum_{i=1}^{m}\lambda_{i}f_{i}(\boldsymbol{x}),$ (3) $$

where $\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{m})$ is a preference vector over $m$ objectives on the simplex $\boldsymbol{\Delta}^{m-1}=\{\boldsymbol{\lambda}|\sum_{i=1}^{m}\lambda_{i}=1,\lambda_{i}\geq 0\ \forall i\}$. A set of diverse solutions can be obtained by solving the scalarization problem ([3](#S2.E3)) with different preferences. Although it is simple and straightforward, linear scalarization cannot find any Pareto solution on the non-convex part of the Pareto front [, ].

Many other scalarization methods have been proposed in past decades. Among them, the Tchebycheff scalarization with good theoretical properties is a promising alternative [, ]:

$$ (Tchebycheff Scalarization) $\displaystyle\min_{\boldsymbol{x}\in\mathcal{X}}g^{(\text{TCH})}(\boldsymbol{x}|\boldsymbol{\lambda})=\max_{1\leq i\leq m}\left\{\lambda_{i}(f_{i}(\boldsymbol{x})-z^{*}_{i})\right\},$ (4) $$

where $\boldsymbol{\lambda}\in\boldsymbol{\Delta}^{m-1}$ is the preference and $\boldsymbol{z}^{*}\in\mathbb{R}^{m}$ is the ideal point (e.g., $z^{*}_{i}=\min f_{i}(\boldsymbol{x})-\epsilon$ with a small $\epsilon>0$). It is well-known that the Tchebycheff scalarization is able to find all weakly Pareto solutions for any Pareto front []. However, the $\max$ operator makes it become nonsmooth and hence suffers from a slow convergence rate by subgradient descent [] for differentiable multi-objective optimization. Recently, a smooth Tchebycheff scalarization approach [] has been proposed to tackle the nonsmoothness issue:

$$ (Smooth Tchebycheff Scalarization) $\displaystyle\min_{\boldsymbol{x}\in\mathcal{X}}g^{(\text{STCH})}_{\mu}(\boldsymbol{x}|\boldsymbol{\lambda})=\mu\log\left(\sum_{i=1}^{m}e^{\frac{\lambda_{i}(f_{i}(\boldsymbol{x})-z^{*}_{i})}{\mu}}\right),$ (5) $$

where $\mu$ is the smooth parameter with a small positive value (e.g., $0.1$). According to [], this smooth scalarization approach enjoys a fast convergence rate for the gradient-based method, while also having good theoretical properties for multi-objective optimization.

These scalarization methods do not have to solve a quadratic programming problem at each iteration and thus have lower pre-iteration complexity than MGDA. However, they still need to solve a large number of scalarization problems with different preferences to obtain a dense set of solutions to approximate the whole Pareto set.

## 3 Tchebycheff Set Scalarization for Many Objective Optimization

Figure: (a) Solution 1
Refer to caption: /html/2405.19650/assets/x5.png

### 3.1 Small Solution Set for Many-Objective Optimization

Unlike previous methods, this work does not aim to find a huge set of solutions for approximating the whole Pareto set. Instead, we want to find a small set of solutions in a collaborative and complementary way such that each optimization objective can be well addressed by at least one solution. We have the following formulation of our targeted set optimization problem:

$$ $\min_{\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}}\boldsymbol{f}(\boldsymbol{x})=(\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{1}(\boldsymbol{x}),\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{2}(\boldsymbol{x}),\cdots,\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{m}(\boldsymbol{x})),$ (6) $$

where $\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}$ is a set of $K$ solutions to tackle all $m$ objectives $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$. With a large $K\geq m$, we will have a degenerated problem:

$$ $\displaystyle\min_{\boldsymbol{X}_{K}}\boldsymbol{f}(\boldsymbol{x})=(\min_{\boldsymbol{x}^{(1)}\in\mathcal{X}}f_{1}(\boldsymbol{x}),\min_{\boldsymbol{x}^{(2)}\in\mathcal{X}}f_{2}(\boldsymbol{x}),\cdots,\min_{\boldsymbol{x}^{(m)}\in\mathcal{X}}f_{m}(\boldsymbol{x})),$ (7) $$

where each objective function $f_{i}$ is independently solved by its corresponding solution $\boldsymbol{x}^{(i)}\in\mathcal{X}$ via single objective optimization and the rest $(K-m)$ solutions are redundant. If $K=1$, the set optimization problem ([6](#S3.E6)) will be reduced to the standard multi-objective optimization problem ([1](#S2.E1)).

In this work, we are more interested in the case $1<K\ll m$, which finds a small set of solutions (e.g., $K=5$) to tackle a large number of objectives (e.g., $m\geq 100$) as illustrated in Figure [2](#S3.F2). Very recently, a similar setting has been investigated in two concurrent works [, ]. Ding et al.[] study the sum-of-minimum (SoM) optimization problem $\frac{1}{m}\sum_{i=1}^{m}\min\{f_{i}(\boldsymbol{x}^{(1)}),f_{i}(\boldsymbol{x}^{(2)}),\ldots,f_{i}(\boldsymbol{x}^{(K)})\}$ that can be found in many machine learning applications such as mixed linear regression [, ]. They generalize the classic k-means++ [] and Lloyd’s algorithm [] for clustering to tackle this problem, but do not take multi-objective optimization into consideration. Li et al. [] propose a novel Many-objective multi-solution Transport (MosT) framework to tackle many-objective optimization. With a bi-level optimization formulation, they adaptively construct a few weighted multi-objective optimization problems that are assigned to different representative
regions on the Pareto front. By solving these weighted problems with MGDA, a diverse set of solutions can be obtained to well cover all objectives. In this work, we propose a straightforward and efficient set scalarization approach to explicitly optimize all objectives by a small set of solutions. A detailed experimental comparison with these methods can be found in Section [4](#S4).

### 3.2 Tchebycheff Set Scalarization

The set optimization formulation ([6](#S3.E6)) is still a multi-objective optimization problem. In non-trivial cases, there is no single small solution set $\boldsymbol{X}_{K}$ with $K<m$ solutions that can optimize all $m$ objective functions $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$ at the same time. To tackle this optimization problem, we propose the following Tchebycheff set (TCH-Set) scalarization approach:

$$ $\displaystyle\min_{\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}}g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ $\displaystyle=\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}$ $\displaystyle=\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i})\right\},$ (8) $$

where $\boldsymbol{\lambda}=(\lambda_{1},\dots,\lambda_{m})$ and $\boldsymbol{z}^{*}=(z^{*}_{1},\dots,z^{*}_{m})$ are the preference and ideal point for each objective function. In this way, all objective values $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$ among the whole solution set $\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}$ are scalarized into a single function $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. A simple uniform vector $\boldsymbol{\lambda}=(\frac{1}{m},\ldots,\frac{1}{m})$ can be used if there is no specific preference among the objectives. By optimizing this TCH-Set scalarization function ([8](#S3.E8)), we want to find an optimal small solution set $\boldsymbol{X}^{*}_{K}$ such that each objective can be well addressed by at least one solution $\boldsymbol{x}^{(k)}\in\boldsymbol{X}_{K}$ with a low worst objective value $\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i})\right\}$. When the solution set contains only one single solution (e.g., $K=1$), it will be reduced to the classic single-solution Tchebycheff scalarization ([4](#S2.E4)).

In this work, we assume that no pair of the optimization objectives will share exactly the same optimal solution. Therefore, no solution in the optimal solution set $\boldsymbol{X}^{*}_{K}=\operatorname*{arg\,min}_{\boldsymbol{X}_{k}}g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ will be redundant, which means

$$ $g^{(\text{TCH-Set})}(\boldsymbol{X}^{*}_{K}|\boldsymbol{\lambda})<g^{(\text{TCH-Set})}(\boldsymbol{X}^{*}_{K}\setminus\{\boldsymbol{x}^{(k)}\}|\boldsymbol{\lambda})$ (9) $$

holds for any $1\leq k\leq K\leq m$ with a all positive preference $\boldsymbol{\lambda}$. In addition, the optimal solution set also enjoys a good theoretical property for multi-objective optimization:

###### Theorem 1 (Pareto Optimality for Tchebycheff Set Scalarization) .

All solutions in the optimal solution set $\boldsymbol{X}^{*}_{K}$ for the Tchebycheff set scalarization optimization problem ([8](#S3.E8)) are weakly Pareto optimal of the original multi-objective optimization problem ([1](#S2.E1)). In addition, if the optimal set $\boldsymbol{X}^{*}_{K}$ is unique, all solutions in $\boldsymbol{X}^{*}_{K}$ are Pareto optimal.

###### Proof Sketch.

This theorem can be proved by contradiction based on Definition [2](#Thmdefinition2) for (weakly) Pareto optimality and the form of Tchebycheff set Scalarization ([8](#S3.E8)). A detailed proof is provided in Appendix [A.1](#A1.SS1).
∎

In other words, a small set of (weakly) Pareto solutions can be found by solving the TCH-Set scalarization optimization problem ([8](#S3.E8)), which complementarily addresses all objectives to achieve a low worst performance $\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i})\right\}$. However, the non-smoothness of TCH-Set scalarization might hinder its practical usage for efficient optimization.

###### Theorem 1 (Pareto Optimality for Tchebycheff Set Scalarization) .

###### Proof Sketch.

### 3.3 Smooth Tchebycheff Set Scalarization

The Tchebycheff set scalarization formulation ([8](#S3.E8)) involves a $\max$ and a $\min$ operator, which leads to its non-smoothness even when all objective functions $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$ are smooth. In other words, the Tchebycheff set scalarization $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ is not differentiable and will suffer from a slow convergence rate by subgradient descent. To address this issue, we leverage the smooth optimization approach [, , ] to propose a smooth Tchebycheff set scalarization for multi-objective optimization.

According to [], for the maximization among all objectives $\max_{1\leq i\leq m}\{f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\ldots,f_{m}(\boldsymbol{x})\}$, we have the smooth maximization function:

$$ $\operatorname*{smax}_{1\leq i\leq m}\{f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\ldots,f_{m}(\boldsymbol{x})\}=\mu\log\left(\sum_{i=1}^{m}e^{\frac{f_{i}(\boldsymbol{x})}{\mu}}\right),$ (10) $$

where $\mu$ is a smooth parameter. Similarly, for the minimization among different solutions for the $i$-th objective $\min_{1\leq k\leq K}\{f_{i}(\boldsymbol{x}^{(1)}),f_{i}(\boldsymbol{x}^{(2)}),\ldots,f_{i}(\boldsymbol{x}^{(K)})\}$, we have the smooth minimization function:

$$ $\operatorname*{smin}_{1\leq k\leq K}\{f_{i}(\boldsymbol{x}^{(1)}),f_{i}(\boldsymbol{x}^{(2)}),\ldots,f_{i}(\boldsymbol{x}^{(K)})\}=-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-\frac{f_{i}(\boldsymbol{x}^{(k)})}{\mu_{i}}}\right),$ (11) $$

where $\mu_{i}$ is a smooth parameter.

By leveraging the above smooth maximization and minimization functions, we propose the smooth Tchebycheff set scalarization (STCH-Set) scalarization for multi-objective optimization:

$$ $\displaystyle\min_{\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ $\displaystyle=\operatorname*{smax}_{1\leq i\leq m}\left\{\lambda_{i}\operatorname*{smin}\limits_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right\}$ $\displaystyle=\mu\log\left(\sum_{i=1}^{m}e^{\frac{\lambda_{i}\left(\operatorname*{smin}\limits_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)}{\mu}}\right)$ $\displaystyle=\mu\log\left(\sum_{i=1}^{m}e^{\frac{\lambda_{i}\left(-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)-z^{*}_{i}\right)}{\mu}}\right).$ (12) $$

If the same smooth parameter $\mu_{1}=\ldots=\mu_{m}=\mu$ are used for all smooth terms, we have the following simplified formulation:

$$ $\min_{\boldsymbol{X}_{K}=\{\boldsymbol{x}^{(k)}\}_{k=1}^{K}}g_{\mu}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\mu\log\left(\sum_{i=1}^{m}e^{\lambda_{i}\left(-\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu}}\right)-z^{*}_{i}\right)}\right).$ (13) $$

When $K=1$, it will reduce to the single-solution smooth Tchebycheff scalarization ([5](#S2.E5)). Similarly to the non-smooth TCH-Set counterpart, the STCH-Set scalarization also has good theoretical properties for multi-objective optimization:

###### Theorem 2 (Pareto Optimality for Smooth Tchebycheff Set Scalarization) .

All solutions in the optimal solution set $\boldsymbol{X}^{*}_{K}$ for the smooth Tchebycheff set scalarization problem ([12](#S3.E12)) are weakly Pareto optimal of the original multi-objective optimization problem ([1](#S2.E1)). In addition, the solutions are Pareto optimal if either

- 1.
the optimal solution set $\boldsymbol{X}^{*}_{K}$ is unique, or
- 2.
all preference coefficients are positive ($\lambda_{i}>0\ \forall i$).

###### Proof Sketch.

This theorem can be proved by contradiction based on Definition [2](#Thmdefinition2) for (weakly) Pareto optimality and the form of smooth Tchebycheff set scalarization ([12](#S3.E12)). We provide a detailed proof in Appendix [A.2](#A1.SS2).
∎

###### Theorem 3 (Uniform Smooth Approximation) .

The smooth Tchebycheff set (STCH-Set) scalarization $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ is a uniform smooth approximation of the Tchebycheff set (TCH-Set) scalarization $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$, and we have:

$$ $\lim_{\mu\downarrow 0,\mu_{i}\downarrow 0\ \forall i}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ (14) $$

for any valid set $\boldsymbol{X}_{k}\subset\mathcal{X}$.

###### Proof Sketch.

This theorem can be proved by deriving the upper and lower bounds of the TCH-Set scalarization $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ with respect to the smooth $\operatorname*{smax}$ and $\operatorname*{smin}$ operators in the STCH-Set scalarization $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. A detailed proof is provided in Appendix [A.3](#A1.SS3).
∎

Figure: Algorithm 1 STCH-Set Scalarization for Multi-Objective Optimization

According to these theorems, for any smooth parameters $\mu$ and $\{\mu\}_{i=1}^{m}$, all solutions in the optimal set $\boldsymbol{X}^{*}_{K}$ for STCH-Set scalarization ([12](#S3.E12)) are also (weakly) Pareto optimal. In addition, with small smooth parameters $\mu\downarrow 0,\mu_{i}\downarrow 0\ \forall i$, the value of $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ will be close to its non-smooth counterpart $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ for all valid solution sets $\boldsymbol{X}_{K}$, which is also the case for the optimal set $\boldsymbol{X}^{*}_{K}=\operatorname*{arg\,min}_{\boldsymbol{X}_{K}}g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. Therefore, it is reasonable to find an approximate optimal solution set for the original $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ by optimizing its smooth counterpart $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ with small smooth parameters $\mu$ and $\{\mu_{i}\}_{i=1}^{m}$.

The STCH-Set scalarization function $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ can be efficiently optimized by any gradient-based optimization method. A simple gradient descent algorithm for STCH-Set is shown in Algorithm [1](#alg1). However, when the objective functions $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$ are highly non-convex, it could be very hard to find the global optimal set $\boldsymbol{X}^{*}_{K}$ for $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. In this case, we have the Pareto stationarity guarantee for the gradient-based method:

###### Theorem 4 (Convergence to Pareto Stationary Solution) .

If there exists a solution set $\hat{}\boldsymbol{X}_{K}$ such that $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$ for all $\hat{}\boldsymbol{x}^{(k)}\in\hat{}\boldsymbol{X}_{K}$, then all solutions in $\hat{}\boldsymbol{X}_{K}$ are Pareto stationary solutions of the original multi-objective optimization problem ([1](#S2.E1)).

###### Proof Sketch.

We can prove this theorem by analyzing the form of gradient for STCH-Set scalarization $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$ for each solution $\boldsymbol{x}^{(k)}$ with the condition for Pareto stationarity in Definition [4](#Thmdefinition4). A detailed proof is provided in Appendix [A.4](#A1.SS4).
∎

When $K$ reduces to $1$, all these theorems exactly match their counterpart theorems for single-solution Tchebycheff scalarization [, ] and smooth Tchebycheff scalarization [].

**Table 1: The results on convex optimization problems with different numbers of solutions $K$. Mean worst and average objective values over $50$ runs are reported. Best results are highlighted in bold.**
|  |  | LS | TCH | STCH | MosT | SoM | TCH-Set | STCH-Set |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| number of objectives $m=128$ |  |  |  |  |  |  |  |  |
|  | worst | 4.64e+00(+) | 4.44e+00(+) | 4.41e+00(+) | 2.12e+00(+) | 1.86e+00(+) | 1.02e+00(+) | 6.08e-01 |
| K = 3 | average | 8.61e-01(+) | 8.03e-01(+) | 7.80e-01(+) | 3.45e-01(+) | 2.02e-01(-) | 3.46e-01(+) | 2.12e-01 |
|  | worst | 4.23e+00(+) | 3.83e+00(+) | 3.68e+00(+) | 1.48e+00(+) | 1.12e+00(+) | 6.74e-01(+) | 3.13e-01 |
| K = 4 | average | 7.45e-01(+) | 6.54e-01(+) | 6.41e-01(+) | 1.85e-01(+) | 1.12e-01(+) | 2.27e-01(+) | 9.44e-02 |
|  | worst | 4.17e+00(+) | 3.56e+00(+) | 3.51e+00(+) | 1.02e+00(+) | 9.20e-01(+) | 4.94e-01(+) | 1.91e-01 |
| K = 5 | average | 7.08e-01(+) | 5.75e-01(+) | 5.05e-01(+) | 9.81e-02(+) | 7.95e-02(+) | 1.60e-01(+) | 5.12e-02 |
|  | worst | 3.81e+00(+) | 3.41e+00(+) | 3.20e+00(+) | 9.56e-01(+) | 7.03e-01(+) | 3.72e-01(+) | 1.36e-01 |
| K = 6 | average | 6.72e-01(+) | 5.31e-01(+) | 5.15e-01(+) | 8.34e-02(+) | 5.34e-02(+) | 1.19e-01(+) | 3.15e-02 |
|  | worst | 3.69e+00(+) | 2.94e+00(+) | 2.61e+00(+) | 8.32e-01(+) | 5.20e-01(+) | 2.84e-01(+) | 1.02e-01 |
| K = 8 | average | 6.16e-01(+) | 4.57e-01(+) | 4.22e-01(+) | 6.91e-02(+) | 3.40e-02(+) | 8.53e-02(+) | 1.78e-02 |
|  | worst | 3.68e+00(+) | 2.69e+00(+) | 2.40e+00(+) | 6.27e-01(+) | 4.07e-01(+) | 1.95e-01(+) | 7.99e-02 |
| K = 10 | average | 5.69e-01(+) | 4.07e-01(+) | 3.20e-01(+) | 4.59e-02(+) | 2.43e-02(+) | 5.92e-02(+) | 1.34e-02 |
| number of objectives $m=1024$ |  |  |  |  |  |  |  |  |
|  | worst | 4.71e+00(+) | 7.84e+00(+) | 7.33e+00(+) | - | 3.36e+00(+) | 2.39e+00(+) | 1.87e+00 |
| K = 3 | average | 1.15e+00(+) | 9.92e-01(+) | 9.70e-01(+) | - | 3.54e-01(-) | 4.55e-01(+) | 3.92e-01 |
|  | worst | 4.48e+00(+) | 6.77e+00(+) | 6.57e+00(+) | - | 2.34e+00(+) | 1.68e+00(+) | 9.93e-01 |
| K = 5 | average | 1.09e+00(+) | 8.02e-01(+) | 7.65e-01(+) | - | 1.95e-01(+) | 2.59e-01(+) | 1.87e-01 |
|  | worst | 4.25e+00(+) | 5.65e+00(+) | 5.58e+00(+) | - | 1.74e+00(+) | 1.25e+00(+) | 4.90e-01 |
| K = 8 | average | 1.03e+00(+) | 6.69e-01(+) | 6.49e-01(+) | - | 1.02e-01(+) | 1.66e-01(+) | 8.31e-02 |
|  | worst | 4.16e+00(+) | 5.61e+00(+) | 5.44e+00(+) | - | 1.78e+00(+) | 1.16e+00(+) | 4.05e-01 |
| K = 10 | average | 1.00e+00(+) | 6.07e-01(+) | 5.99e-01(+) | - | 8.14e-02(+) | 1.41e-01(+) | 5.94e-02 |
|  | worst | 4.06e+00(+) | 4.78e+00(+) | 4.91e+00(+) | - | 1.54e+00(+) | 9.06e-01(+) | 2.85e-01 |
| K = 15 | average | 9.78e-01(+) | 5.15e-01(+) | 4.99e-01(+) | - | 5.98e-02(+) | 1.01e-01(+) | 3.31e-02 |
|  | worst | 3.97e+00(+) | 4.64e+00(+) | 4.57e+00(+) | - | 1.52e+00(+) | 8.04e-01(+) | 2.28e-01 |
| K = 20 | average | 9.56e-01(+) | 4.63e-01(+) | 4.68e-01(+) | - | 5.30e-02(+) | 8.40e-02(+) | 2.27e-02 |
| Wilcoxon Rank-Sum Test Summary |  |  |  |  |  |  |  |  |
|  | worst | 12/0/0 | 12/0/0 | 12/0/0 | 6/0/0 | 12/0/0 | 12/0/0 | - |
| +/=/- | average | 12/0/0 | 12/0/0 | 12/0/0 | 6/0/0 | 10/0/2 | 12/0/0 | - |

**Table 2: The results on mixed linear regression with noisy level $\sigma=0.1$. Full table in Appendix [C.1](#A3.SS1).**
|  |  | LS | TCH | STCH | SoM | TCH-Set | STCH-Set |
| --- | --- | --- | --- | --- | --- | --- | --- |
| K = 5 | worst | 3.84e+01(+) | 2.45e+01(+) | 2.43e+01(+) | 2.50e+00(+) | 4.19e+00(+) | 2.10e+00 |
|  | average | 2.70e+00(+) | 1.46e+00(+) | 1.44e+00(+) | 1.88e-01(-) | 6.53e-01(+) | 4.72e-01 |
|  | worst | 2.21e+01(+) | 2.49e+01(+) | 3.92e+01(+) | 3.46e+00(+) | 2.04e+00(+) | 5.00e-01 |
| K = 10 | average | 1.09e+00(+) | 1.19e+00(+) | 3.01e+00(+) | 2.33e-01(+) | 3.83e-01(+) | 2.00e-01 |
|  | worst | 4.20e+01(+) | 2.11e+01(+) | 2.21e+01(+) | 2.57e+00(+) | 1.64e+00(+) | 2.70e-01 |
| K = 15 | average | 3.07e+00(+) | 1.02e+00(+) | 1.02e+00(+) | 1.97e-01(+) | 3.22e-01(+) | 1.66e-01 |
|  | worst | 4.20e+01(+) | 2.14e+01(+) | 2.04e+01(+) | 1.44e+00(+) | 1.79e+00(+) | 2.27e-01 |
| K = 20 | average | 3.09e+00(+) | 8.35e-01(+) | 8.87e-01(+) | 1.84e-01(+) | 3.29e-01(+) | 1.66e-01 |

###### Theorem 2 (Pareto Optimality for Smooth Tchebycheff Set Scalarization) .

###### Proof Sketch.

###### Theorem 3 (Uniform Smooth Approximation) .

###### Proof Sketch.

###### Theorem 4 (Convergence to Pareto Stationary Solution) .

###### Proof Sketch.

## 4 Experiments

#### Baseline Methods

In this section, we compare our proposed TCH-Set and STCH-Set scalarization with (1) linear scalarization (LS) with randomly sampled preferences, (2) Tchebycheff scalarization (TCH) with randomly sampled preferences, (3) smooth Tchebycheff scalarization (STCH) with randomly sampled preferences [], (4) the many-objective multi-solution transport (MosT) method [], and (5) the efficient sum-of-minimum (SoM) optimization method [].

#### Experimental Setting

This work aims to find a small set $\boldsymbol{X}_{K}$ with $K$ solutions to address all $m$ objectives in each problem. For each objective $f_{i}(\boldsymbol{x})$, we care about the best objective value $\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})$ achieved by the solutions in $\boldsymbol{X}_{K}$. Both the worst obtained value among all objectives $\max_{1\leq i\leq m}\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})$ and the average objective value $\frac{1}{m}\sum_{i=1}^{m}\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})$ are reported for comparison. Detailed experimental settings for each problem can be found in Appendix [B](#A2).

### 4.1 Experimental Results and Analysis

#### Convex Many-Objective Optimization

We first test our proposed methods for solving convex multi-objective optimization with $m=128$ or $m=1,024$ objective functions with different numbers of solutions (from $3$ to $20$). We independently run each comparison $50$ times. In each run, we randomly generate $m$ independent convex quadratic functions as the optimization objectives for all methods. The mean worst and average objective values for each method over $50$ runs are reported in Table [1](#S3.T1). We also conduct the Wilcoxon rank-sum test between STCH-Set and other methods for all comparisons at the $0.05$ significant level. The $(+/=/-)$ symbol means the result obtained by STCH-Set is significantly better, equal to, or worse than the results of the compared method.

According to the results, the traditional methods (e.g., LS/TCH/STCH) fail to properly tackle the few solutions for many objectives setting considered in this work. MosT achieves much better performance than the traditional methods by actively finding a set of diverse solutions to cover all objectives, but it cannot tackle the problems with $1024$ objectives in a reasonable time. In addition, MosT is outperformed by SoM and our proposed STCH-Set, which directly optimizes the performance for each objective. Our proposed STCH-Set performs the best in achieving the low worst objective values for all comparisons. In addition, although not explicitly designed, STCH-Set also achieves a very promising mean average performance for most comparisons since all objectives are well addressed. The importance of smoothness for set optimization is fully confirmed by the observation that STCH-Set significantly outperforms TCH-Set on all comparisons.

Figure: (a) LS
Refer to caption: /html/2405.19650/assets/x11.png

**Table 3: The results on mixed linear regression with noisy level $\sigma=0.1$. Full table in Appendix [C.2](#A3.SS2).**
|  |  | LS | TCH | STCH | SoM | TCH-Set | STCH-Set |
| --- | --- | --- | --- | --- | --- | --- | --- |
| K = 5 | worst | 2.34e+02 (+) | 1.68e+02(+) | 1.57e+02(+) | 1.68e+01(+) | 1.94e+01(+) | 7.43e+00 |
|  | average | 9.19e+00(+) | 8.50e+00(+) | 7.90e+00(+) | 8.54e-01(-) | 3.48e+00(+) | 1.89e+00 |
|  | worst | 3.23e+02(+) | 1.72e+02(+) | 1.57e+02(+) | 4.42e+00(+) | 6.07e+00(+) | 6.28e-01 |
| K = 10 | average | 8.70e+00 (+) | 6.65e+00(+) | 5.85e+00(+) | 1.22e-01(+) | 1.03e+00(+) | 5.99e-02 |
|  | worst | 3.65e+02(+) | 2.10e+02(+) | 1.62e+02(+) | 1.10e+00(+) | 1.57e+00(+) | 2.05e-01 |
| K = 15 | average | 8.33e+00(+) | 5.66e+00(+) | 4.89e+00(+) | 1.47e-01(+) | 3.27e-01(+) | 1.27e-02 |
|  | worst | 3.36e+02(+) | 2.04e+02(+) | 1.81e+02(+) | 5.59e+00(+) | 4.37e+00(+) | 6.22e-01 |
| K = 20 | average | 8.81e+00(+) | 6.92e+00(+) | 6.23e+00(+) | 1.24e-01(+) | 9.09e-01(+) | 6.27e-02 |

#### Noisy Mixed Linear Regression

We then test different methods’ performance on the noisy mixed linear regression problem as in []. For each comparison, $1,000$ data points are randomly generated from $K$ ground truth linear models with noise. Then, with different optimization methods, we train $K$ linear regression models to tackle all $1,000$ data points where the objectives are the squared error for each point. Each comparison are run $50$ times, and the detailed experiment setting is in Appendix [B](#A2).

We conduct comparison with different numbers of $K=\{5,10,15,20\}$ and noise levels $\sigma=\{0.1,0.5,1.0\}$. The results with $\sigma=0.1$ are shown in Table [2](#S3.T2), and the full results can be found in Appendix [C.1](#A3.SS1). According to the results, our proposed STCH-Set can always achieve the lowest worst objective value, and achieves the best average objective value in most comparisons.

#### Noisy Mixed Nonlinear Regression

Following [], we also compare different methods on the noisy mixed nonlinear regression. The problem setting (details in Appendix [B](#A2)) is similar to the mixed linear regression, but we now build simple nonlinear neural networks as the models. According to the results in Table [3](#S4.T3) and Appendix [C.2](#A3.SS2), STCH-Set can still obtain the best overall performance for most comparisons. We visualize different methods’ performance on $100$ sampled data in Figure [3](#S4.F3).

## 5 Conclusion, Limitation and Future Work

#### Conclusion

In this work, we have proposed a novel Tchebycheff set (TCH-Set) scalarization and a smooth Tchebycheff set (STCH-Set) scalarization to find a small set of solutions for many-objective optimization. When properly optimized, each objective in the original problem should be well addressed by at least one solution in the found solution set. Both theoretical analysis and experimental studies have been conducted to demonstrate the promising properties and efficiency of TCH-Set/STCH-Set. Our proposed methods could provide a promising alternative to the current methods for tackling many-objective optimization.

#### Limitation and Future Work

This work proposes general optimization methods for multi-objective optimization which are not tied to particular applications. We do not see any specific potential societal impact of the proposed methods. This work only focuses on the deterministic optimization setting that all objectives are always available. One potential future research direction is to investigate how to deal with only partially observable objective values in practice.

## Appendix A Detailed Proof

### A.1 Proof of Theorem 1

Theorem [1](#Thmtheorem1) (Pareto Optimality for Tchebycheff Set Scalarization).
All solutions in the optimal solution set $\boldsymbol{X}^{*}_{K}$ for the Tchebycheff set scalarization optimization problem ([8](#S3.E8)) are weakly Pareto optimal of the original multi-objective optimization problem ([1](#S2.E1)). In addition, if the optimal set $\boldsymbol{X}^{*}_{K}$ is unique, all solutions in $\boldsymbol{X}^{*}_{K}$ are Pareto optimal.

###### Proof.

This theorem can be proved by contradiction based on Definition [2](#Thmdefinition2) for (weakly) Pareto optimality and the form of TCH-Set Scalarization ([8](#S3.E8)).

###### Proof.

#### Weakly Pareto Optimality

We first prove all the solutions in $\boldsymbol{X}^{*}_{K}$ are weakly Pareto optimal. Let $\boldsymbol{X}^{*}_{K}$ be an optimal solution set for the Tchebycheff set scalarization problem ([8](#S3.E8)), we have:

$$ $\boldsymbol{X}^{*}_{K}=\operatorname*{arg\,min}_{\boldsymbol{X}_{K}}\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\},$ (15) $$

where $\boldsymbol{X}^{*}_{K}=\{\boldsymbol{x}^{*(k)}\}_{k=1}^{K}$.

Without loss of generality, we further suppose the $k$-th solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ is not weakly Pareto optimal for the original multi-objective optimization problem ([1](#S2.E1)). According to Definition [2](#Thmdefinition2) for weakly Pareto optimality, there exists a valid solution $\hat{}\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\hat{}\boldsymbol{x})\prec_{\text{strict}}\boldsymbol{f}(\boldsymbol{x}^{*(k)})$. In other words, we have:

$$ $f_{i}(\hat{}\boldsymbol{x})<f_{i}(\boldsymbol{x}^{*(k)})\quad\forall i\in\{1,...,m\}.$ (16) $$

If we replace the solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ by $\hat{}\boldsymbol{x}$ (e.g., $\hat{}\boldsymbol{X}_{K}=(\boldsymbol{X}^{*}_{K}\setminus\{\boldsymbol{x}^{*(k)}\})\cup\{\hat{}\boldsymbol{x}\}$), we have the new solution set $\hat{}\boldsymbol{X}_{K}=\{\boldsymbol{x}^{*(1)},\ldots,\boldsymbol{x}^{*(k-1)},\hat{}\boldsymbol{x},\boldsymbol{x}^{*(k+1)},\ldots,\boldsymbol{x}^{*(K)}\}$. Based on the above inequalities, it is easy to check:

$$ $\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\hat{}\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}<\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\boldsymbol{X}^{*}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}.$ (17) $$

There is a contradiction between ([17](#A1.E17)) and the optimality of $\boldsymbol{X}^{*}_{K}$ for the Tchebycheff set scalarization ([15](#A1.E15)). Therefore, every $\boldsymbol{x}^{*(k)}$ should be a weakly Pareto optimal solution for the original multi-objective optimization problem ([1](#S2.E1)).

#### Pareto Optimality for Unique Optimal Solution Set

Similar to the above proof, without loss of generality, we suppose the $k$-th solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ is not Pareto optimal, which means there exists a valid solution $\hat{}\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\hat{}\boldsymbol{x})\prec\boldsymbol{f}(\boldsymbol{x}^{*(k)})$. In other words, we have:

$$ $f_{i}(\hat{}\boldsymbol{x})\leq f_{i}(\boldsymbol{x}^{*(k)}),\forall i\in\{1,...,m\}\text{ and }f_{j}(\hat{}\boldsymbol{x})<f_{j}(\boldsymbol{x}^{*(k)}),\exists j\in\{1,...,m\}.$ (18) $$

Also let $\hat{}\boldsymbol{X}_{K}=(\boldsymbol{X}^{*}_{K}\setminus\{\boldsymbol{x}^{*(k)}\})\cup\{\hat{}\boldsymbol{x}\}$, we have:

$$ $\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\hat{}\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}\leq\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\boldsymbol{X}^{*}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}.$ (19) $$

On the other hand, according to the uniqueness of $\boldsymbol{X}^{*}_{K}$, we have:

$$ $\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\hat{}\boldsymbol{X}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}>\max_{1\leq i\leq m}\left\{\lambda_{i}(\min_{\boldsymbol{x}\in\boldsymbol{X}^{*}_{K}}f_{i}(\boldsymbol{x})-z^{*}_{i})\right\}.$ (20) $$

The above two inequalities ([19](#A1.E19)) and ([20](#A1.E20)) are contradicted with each other. Therefore, every solution $\boldsymbol{x}^{*(k)}$ in the unique optimal solution set $\boldsymbol{X}^{*}_{K}$ should be Pareto optimal.

∎

### A.2 Proof of Theorem 2

Theorem [2](#Thmtheorem2) (Pareto Optimality for Smooth Tchebycheff Set Scalarization).
All solutions in the optimal solution set $\boldsymbol{X}^{*}_{K}$ for the smooth Tchebycheff set scalarization problem ([12](#S3.E12)) are weakly Pareto optimal of the original multi-objective optimization problem ([1](#S2.E1)). In addition, the solutions are Pareto optimal if either

- 1.
the optimal solution set $\boldsymbol{X}^{*}_{K}$ is unique, or
- 2.
all preference coefficients are positive ($\lambda_{i}>0\ \forall i$).

###### Proof.

Similarly to the above proof for Theorem [1](#Thmtheorem1), this theorem can be proved by contradiction based on Definition [2](#Thmdefinition2) for (weakly) Pareto optimality and the form of smooth Tchebycheff set scalarization ([12](#S3.E12)).

###### Proof.

#### Weakly Pareto Optimality

We first prove all the solutions in $\boldsymbol{X}^{*}_{K}$ are weakly Pareto optimal. Let $\boldsymbol{X}^{*}_{K}$ be an optimal solution set for the smooth Tchebycheff set scalarization problem ([12](#S3.E12)), we have:

$$ $\boldsymbol{X}^{*}_{K}=\operatorname*{arg\,min}_{\boldsymbol{X}_{K}}\ \mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right),$ (21) $$

where $\boldsymbol{X}^{*}_{K}=\{\boldsymbol{x}^{*(k)}\}_{k=1}^{K}$.

Without loss of generality, we further suppose the $k$-th solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ is not weakly Pareto optimal for the original multi-objective optimization problem ([1](#S2.E1)). According to Definition [2](#Thmdefinition2) for weakly Pareto optimality, there exists a valid solution $\hat{}\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\hat{}\boldsymbol{x})\prec_{\text{strict}}\boldsymbol{f}(\boldsymbol{x}^{*(k)})$. In other words, we have:

$$ $f_{i}(\hat{}\boldsymbol{x})<f_{i}(\boldsymbol{x}^{*(k)})\quad\forall i\in\{1,...,m\}.$ (22) $$

If we replace the solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ by $\hat{}\boldsymbol{x}$ (e.g., $\hat{}\boldsymbol{X}_{K}=(\boldsymbol{X}^{*}_{K}\setminus\{\boldsymbol{x}^{*(k)}\})\cup\{\hat{}\boldsymbol{x}\}$), we have the new solution set $\hat{}\boldsymbol{X}_{K}=\{\boldsymbol{x}^{*(1)},\ldots,\boldsymbol{x}^{*(k-1)},\hat{}\boldsymbol{x},\boldsymbol{x}^{*(k+1)},\ldots,\boldsymbol{x}^{*(K)}\}$. Based on the above inequalities, and further let $\hat{}\boldsymbol{x}^{*(j)}=\boldsymbol{x}^{*(j)},\forall j\neq k$ and $\hat{}\boldsymbol{x}^{*(k)}=\hat{}\boldsymbol{x}$, it is easy to check:

$$ $\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\hat{}\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right)<\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right).$ (23) $$

There is a contradiction between ([23](#A1.E23)) and the optimality of $\boldsymbol{X}^{*}_{K}$ for the smooth Tchebycheff set scalarization ([21](#A1.E21)). Therefore, every $\boldsymbol{x}^{*(k)}$ should be a weakly Pareto optimal solution for the original multi-objective optimization problem ([1](#S2.E1)).

Then we prove the two sufficient conditions for all solutions in $\boldsymbol{X}^{*}_{K}$ be Pareto optimal.

#### 1. Unique Optimal Solution Set

Without loss of generality, we suppose the $k$-th solution $\boldsymbol{x}^{*(k)}$ in $\boldsymbol{X}^{*}_{K}$ is not Pareto optimal, which means there exists a valid solution $\hat{}\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\hat{}\boldsymbol{x})\prec\boldsymbol{f}(\boldsymbol{x}^{*(k)})$. In other words, we have:

$$ $f_{i}(\hat{}\boldsymbol{x})\leq f_{i}(\boldsymbol{x}^{*(k)}),\forall i\in\{1,...,m\}\text{ and }f_{j}(\hat{}\boldsymbol{x})<f_{j}(\boldsymbol{x}^{*(k)}),\exists j\in\{1,...,m\}.$ (24) $$

Also let $\hat{}\boldsymbol{X}_{K}=(\boldsymbol{X}^{*}_{K}\setminus\{\boldsymbol{x}^{*(k)}\})\cup\{\hat{}\boldsymbol{x}\}$ where $\hat{}\boldsymbol{x}^{*(j)}=\boldsymbol{x}^{*(j)},\forall j\neq k$ and $\hat{}\boldsymbol{x}^{*(k)}=\hat{}\boldsymbol{x}$, we have:

$$ $\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\hat{}\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right)\leq\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right).$ (25) $$

On the other hand, according to the uniqueness of $\boldsymbol{X}^{*}_{K}$, we have:

$$ $\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\hat{}\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right)>\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right).$ (26) $$

The above two inequalities ([25](#A1.E25)) and ([26](#A1.E26)) are contradicted with each other. Therefore, every solution in the unique optimal solution set $\boldsymbol{x}^{*(k)}$ should be Pareto optimal.

2. All Positive Preferences Similar to the above proof, suppose the solution $\boldsymbol{x}^{*(k)}$ is not Pareto optimal, and there exists a valid solution $\hat{}\boldsymbol{x}\in\mathcal{X}$ such that $\boldsymbol{f}(\hat{}\boldsymbol{x})\prec\boldsymbol{f}(\boldsymbol{x}^{*(k)})$. Since all preferences $\boldsymbol{\lambda}=\{\lambda_{i}\}_{i=1}^{m}$ are positive, according to the set of inequalities in ([24](#A1.E24)), it is easy to check:

$$ $\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\hat{}\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right)<\mu\log\left(\sum_{i=1}^{m}e^{\frac{-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{\lambda_{i}(f_{i}(\boldsymbol{x}^{*(k)})-z^{*}_{i})}/{\mu_{i}}}\right)}{\mu}}\right)$ (27) $$

which contradicts the STCH-Set optimality of $\boldsymbol{X}^{*}_{K}$ in ([21](#A1.E21)). Therefore, all solutions in $\boldsymbol{X}^{*}_{K}$ should be Pareto optimal.

It should be noted that all positive preferences are not a sufficient conditions for the solution to be Pareto optimal for the original (nonsmooth) Tchebycheff set (TCH-Set) scalarization. With all positive preferences, each component (e.g., all objective-solution pairs) in STCH-Set scalarization will contribute to the scalarization value, which is not the case for the (non-smooth) TCH-Set scalarization.

∎

### A.3 Proof of Theorem 3

Theorem [3](#Thmtheorem3) (Uniform Smooth Approximation).
The smooth Tchebycheff set (STCH-Set) scalarization $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ is a uniform smooth approximation of the Tchebycheff set (TCH-Set) scalarization $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$, and we have:

$$ $\lim_{\mu\downarrow 0,\mu_{i}\downarrow 0\ \forall i}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ (28) $$

for any valid set $\boldsymbol{X}_{k}\subset\mathcal{X}$.

###### Proof.

This theorem can be proved by deriving the upper and lower bounds of $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ with respect to the smooth $\operatorname*{smax}$ and $\operatorname*{smin}$ operators in $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. We first provide the upper and lower bounds for the classic smooth approximation for $\max$ and $\min$, and then derive the bounds for $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$.

###### Proof.

#### Classic Bounds for max \max and min \min

The log-sum-exp function $\log\sum_{i=1}^{n}e^{y_{i}}$ is a widely-used smooth approximation for the maximization function $\max\{y_{1},y_{2},\ldots,y_{n}\}$. Its lower and upper bounds are also well-known in convex optimization [, ]:

$$ $\displaystyle\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}$ $\displaystyle=\log(e^{\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}})$ $\displaystyle\leq\log(\sum_{i=1}^{n}e^{y_{i}})$ $\displaystyle\leq\log(n\cdot e^{\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}})$ $\displaystyle=\log{n}+\log(e^{\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}})$ $\displaystyle=\log{n}+e^{\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}}.$ (29) $$

By rearranging the above inequalities, we have:

$$ $\log\sum_{i=1}^{m}e^{y_{i}}-\log{n}\leq\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}\leq\log\sum_{i=1}^{m}e^{y_{i}}.$ (30) $$

With a smooth parameter $\mu>0$, it is also easy to show [, ]:

$$ $\mu\log\sum_{i=1}^{m}e^{y_{i}/\mu}-\mu\log{n}\leq\max\left\{y_{1},y_{2},\ldots,y_{n}\right\}\leq\mu\log\sum_{i=1}^{m}e^{y_{i}/\mu}.$ (31) $$

Similarly, we have the lower and upper bounds for the minimization function:

$$ $-\mu\log\sum_{i=1}^{m}e^{-y_{i}/\mu}\leq\min\left\{y_{1},y_{2},\ldots,y_{n}\right\}\leq-\mu\log\sum_{i=1}^{m}e^{-y_{i}/\mu}+\mu\log{n}.$ (32) $$

#### Lower and Upper Bounds for g ( TCH-Set ) ​ ( 𝑿 K | 𝝀 ) superscript 𝑔 TCH-Set conditional subscript 𝑿 𝐾 𝝀 g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})

By leveraging the above classic bounds, it is straightforward to derive the lower and upper bounds for the $\max$ operator over $m$ optimization objectives for $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\max_{1\leq i\leq m}\left\{\lambda_{i}\left(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)\right\}$:

$$ $\displaystyle\max_{1\leq i\leq m}\left\{\lambda_{i}\left(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)\right\}\geq\mu\log\left(\sum_{i=1}^{m}e^{{\lambda_{i}\left(\min\limits_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)}/{\mu}}\right)-\mu\log{m},$ (33) $\displaystyle\max_{1\leq i\leq m}\left\{\lambda_{i}\left(\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)\right\}\leq\mu\log\left(\sum_{i=1}^{m}e^{{\lambda_{i}\left(\min\limits_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})-z^{*}_{i}\right)}/{\mu}}\right),$ (34) $$

where the bounds are tight if $\mu\downarrow 0$.

In a similar manner, we can obtain the bounds for the $\min$ operator over $K$ solutions for each objective function $f_{i}(\boldsymbol{x})$:

$$ $-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)\leq\min_{1\leq k\leq K}f_{i}(\boldsymbol{x}^{(k)})\leq-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)+\mu_{i}\log{K},$ (35) $$

where the bounds are tight if $\mu_{i}\downarrow 0$.

Combing the results above, we have the upper bound and lower bounds for the Tchebycheff setscalarization $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$:

$$ $\displaystyle g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})\geq\mu\log\left(\sum_{i=1}^{m}e^{{\lambda_{i}\left(-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)-z^{*}_{i}\right)}/{\mu}}\right)-\mu\log{m},$ (36) $\displaystyle g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})\leq\mu\log\left(\sum_{i=1}^{m}e^{{\lambda_{i}\left(-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)+\mu_{i}\log{K}-z^{*}_{i}\right)}/{\mu}}\right),$ (37) $$

which means $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ is properly bounded from above and below, and the bounds are tight if $\mu\downarrow 0$ and $\mu_{i}\downarrow 0$ for all $1\leq i\leq m$. It is straightforward to see:

$$ $\lim_{\mu\downarrow 0,\mu_{i}\downarrow 0\ \forall i}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ (38) $$

for all valid solution sets $\boldsymbol{X}_{K}$ that include the optimal set $\boldsymbol{X}^{*}_{K}=\operatorname*{arg\,min}_{\boldsymbol{X}_{K}}g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$. Therefore, according to Nesterov (2005) [], $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}$ is a uniform smooth approximation of $g^{(\text{TCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$.

∎

### A.4 Proof of Theorem 4

Theorem [4](#Thmtheorem4) (Convergence to Pareto Stationary Solution).
If there exists a solution set $\hat{}\boldsymbol{X}_{K}$ such that $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$ for all $\hat{}\boldsymbol{x}^{(k)}\in\hat{}\boldsymbol{X}_{K}$, then all solutions in $\hat{}\boldsymbol{X}_{K}$ are Pareto stationary solutions of the original multi-objective optimization problem ([1](#S2.E1)).

###### Proof.

We can prove this theorem by analyzing the form of gradient for STCH-Set scalarization $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$ for each solution $\boldsymbol{x}^{(k)}$ with the condition for Pareto stationarity in Definition [4](#Thmdefinition4).

We first let

$$ $\displaystyle g_{i}(\boldsymbol{x})=-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)\ \forall 1\leq i\leq m,$ (39) $\displaystyle\boldsymbol{y}=\boldsymbol{\lambda}(\boldsymbol{g}(\boldsymbol{x})-\boldsymbol{z}^{*})\in\mathbb{R}^{m},$ (40) $\displaystyle h(\boldsymbol{y})=-\mu\log\left(\sum_{i=1}^{m}e^{-{\boldsymbol{y}_{i}}/{\mu}}\right).$ (41) $$

For the STCH scalarization, we have:

$$ $\displaystyle g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ $\displaystyle=\mu\log\left(\sum_{i=1}^{m}e^{\frac{\lambda_{i}\left(-\mu_{i}\log\left(\sum_{k=1}^{K}e^{-{f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}\right)-z^{*}_{i}\right)}{\mu}}\right)$ (42) $\displaystyle=\mu\log\left(\sum_{i=1}^{m}e^{\frac{\lambda_{i}\left(g_{i}(\boldsymbol{x})-z^{*}_{i}\right)}{\mu}}\right)$ (43) $\displaystyle=\mu\log\left(\sum_{i=1}^{m}e^{\frac{y_{i}}{\mu}}\right)$ (44) $\displaystyle=h(\boldsymbol{y}).$ (45) $$

Therefore, according to the chain rule, the gradient of $g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ with respect to a solution $\boldsymbol{x}^{(k)}$ in the set $\boldsymbol{X}_{K}$ can be written as:

$$ $\displaystyle\nabla_{\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ $\displaystyle=\nabla_{\boldsymbol{y}}h(\boldsymbol{y})\cdot\frac{\partial\boldsymbol{y}}{\partial\boldsymbol{g}}\cdot\frac{\partial\boldsymbol{g}}{\partial\boldsymbol{x}^{(k)}}.$ (46) $$

It is straightforward to show

$$ $\nabla_{\boldsymbol{y}}h(\boldsymbol{y})=\frac{e^{{\boldsymbol{y}}/{\mu}}}{\sum_{i}e^{{y_{i}}/{\mu}}},\quad\frac{\partial\boldsymbol{y}}{\partial\boldsymbol{g}}=\boldsymbol{\lambda},\quad\frac{\partial\boldsymbol{g}_{i}}{\partial\boldsymbol{x}^{(k)}}=\frac{e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}{\sum_{k}e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}.$ (47) $$

Therefore, we have

$$ $\nabla_{\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\sum_{i=1}^{m}\frac{\lambda_{i}e^{{y_{i}}/{\mu}}}{\sum_{i}e^{{y_{i}}/{\mu}}}\frac{e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}{\sum_{k}e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}\nabla f_{i}(\boldsymbol{x}^{(k)}).$ (48) $$

Let $w_{i}=\frac{\lambda_{i}e^{{y_{i}}/{\mu}}}{\sum_{i}e^{{y_{i}}/{\mu}}}\frac{e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}{\sum_{k}e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}$, it is easy to check $w_{i}\geq 0\ \forall 1\leq i\leq m$. If set $s=\sum_{i=1}^{m}w_{i}>0$ and $\bar{w}_{i}=w_{i}/s$, we have:

$$ $\displaystyle\nabla_{\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\boldsymbol{X}_{K}|\boldsymbol{\lambda})$ $\displaystyle=\sum_{i=1}^{m}\frac{\lambda_{i}e^{{y_{i}}/{\mu}}}{\sum_{i}e^{{y_{i}}/{\mu}}}\frac{e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}{\sum_{k}e^{{-f_{i}(\boldsymbol{x}^{(k)})}/{\mu_{i}}}}\nabla f_{i}(\boldsymbol{x}^{(k)}),$ (49) $\displaystyle=\sum_{i=1}^{m}w_{i}\nabla f_{i}(\boldsymbol{x})=s\sum_{i=1}^{m}\bar{w}_{i}\nabla f_{i}(\boldsymbol{x})$ (50) $\displaystyle\propto\sum_{i=1}^{m}\bar{w}_{i}\nabla f_{i}(\boldsymbol{x}),$ (51) $$

where $\bar{}\boldsymbol{w}\in\boldsymbol{\Delta}^{m-1}=\{\bar{}\boldsymbol{w}|\sum_{i=1}^{m}\bar{w}_{i}=1,\bar{w}_{i}\geq 0\ \forall i\}$. For a solution $\hat{}\boldsymbol{x}^{(k)}\in\hat{}\boldsymbol{X}_{K}$, if $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$, we have:

$$ $\sum_{i=1}^{m}\bar{w}_{i}\nabla f_{i}(\boldsymbol{x})=\bm{0}\text{ with }\bar{}\boldsymbol{w}\in\boldsymbol{\Delta}^{m-1}=\{\bar{}\boldsymbol{w}|\sum_{i=1}^{m}\bar{w}_{i}=1,\bar{w}_{i}\geq 0\ \forall i\}.$ (52) $$

According to Definition [4](#Thmdefinition4), the solution $\boldsymbol{x}^{(k)}$ is Pareto stationary for the multi-objective optimization problem ([1](#S2.E1)).

Therefore, when $\nabla_{\hat{}\boldsymbol{x}^{(k)}}g_{\mu,\{\mu_{i}\}_{i=1}^{m}}^{(\text{STCH-Set})}(\hat{}\boldsymbol{X}_{K}|\boldsymbol{\lambda})=\bm{0}$ for all $\hat{}\boldsymbol{x}^{(k)}\in\hat{}\boldsymbol{X}_{K}$, all solutions in $\hat{}\boldsymbol{X}_{K}$ are Pareto stationary for the original multi-objective optimization problem ([1](#S2.E1)).

∎

###### Proof.

## Appendix B Problem and Experimental Settings

### B.1 Convex Multi-Objective Optimization

In this experiment, we compare different methods on solving $m$ convex optimization problems with $K$ solutions. We consider two numbers of objectives $m=\{128,1024\}$ and six different numbers of solutions $K=\{3,4,5,6,8,10\}$ or $K=\{3,5,8,10,15,20\}$ for the $128$-objective and $1024$-objective problems separately. Therefore, there are total $2\times 6=12$ comparisons.

For each comparison, we randomly generate $m$ independent quadratic functions $\{f_{i}(\boldsymbol{x})\}_{i=1}^{m}$ as the optimization objectives, of which the minimum values are all 0 0. Therefore, the optimal worst and average objective values are both 0 0 for all comparisons. Since the $m$ objectives are randomly generated and with different optimal solution, the optimal worst and average objective value 0 0 cannot be achieved by any algorithms unless $K\geq m$. In all comparison, we let all solution be $10$-dimensional vector $\boldsymbol{x}\in\mathbb{R}^{10}$. We repeat each comparison $50$ times and report the mean worst and average objective value over $50$ runs for each method.

### B.2 Noisy Mixed Linear Regression

We follow the noisy mixed linear regression setting from []. The $i$-th optimization objective is defined as:

$$ $f_{i}(\boldsymbol{x})=\frac{1}{2}(\boldsymbol{a}^{(i)T}\boldsymbol{x}-b^{(i)})^{2}+\frac{\beta}{2}||\boldsymbol{x}||^{2}$ (53) $$

where $\{(\boldsymbol{a}^{(i)},b^{(i)})\}_{i=1}^{m}$ are $m$ data points and $\beta=0.01$ is a fixed penalty parameter. The dataset $\{(\boldsymbol{a}^{(i)},b^{(i)})\}_{i=1}^{m}$ is randomly generated in the following steps:

- •
Randomly sample $K$ i.i.d. ground truth $\{\hat{}\boldsymbol{x}^{(k)}\}_{k=1}^{K}\sim N(\bm{0},\bm{I}_{d})$;
- •
Randomly sample $m$ i.i.d. data $\{\boldsymbol{a}^{(i)}\}_{i=1}^{m}\sim N(\bm{0},\bm{I}_{d})$, class index $\{c_{i}\}_{i=1}^{m}\sim\text{Uniform}([k])$, and noise $\{\epsilon_{i}\}_{i=1}^{m}\sim N(\bm{0},\sigma^{2})$;
- •
Compute $b^{(i)}=\boldsymbol{a}^{(i)T}\hat{}\boldsymbol{x}^{(c_{i})}+\epsilon_{i}$.

Our goal is to build $K$ linear model with parameter $\boldsymbol{x}^{(k)}$ to tackle all $m$ data points. In this experiment, we set $m=1000$ and $\boldsymbol{x}\in\mathbb{R}^{10}$ for all comparisons. We consider three noise levels $\sigma=\{0.1,0.5,1\}$ and four different numbers of solutions $K=\{5,10,15,20\}$ for each noise level, so there are total $3\times 4=12$ comparisons. All comparisons are run $50$ times, and we compare the mean worst and average objective values for each method.

### B.3 Noisy Mixed Nonlinear Regression

The experimental setting for noisy mixed nonlinear regression is also from [] and similar to the linear regression counterpart. For nonlinear regression, the $i$-th optimization objective is defined as:

$$ $f_{i}(\boldsymbol{x})=\frac{1}{2}(\psi(\boldsymbol{a}_{i};\boldsymbol{x})-b_{i})^{2}+\frac{\beta}{2}||\boldsymbol{x}||^{2}$ (54) $$

where $\{(a_{i},b_{i})\}_{i=1}^{m}$ are $m$ data points and $\beta=0.01$ is a fixed penalty parameter as in the previous linear regression case. However, now the model $\psi(\boldsymbol{a}_{i},\boldsymbol{x})$ is a neural network with trainale model parameters $\boldsymbol{x}=(\boldsymbol{W},\boldsymbol{p},\boldsymbol{q},o)$ with the form:

$$ $\psi(\boldsymbol{a};\boldsymbol{x})=\psi(\boldsymbol{a};\boldsymbol{W},\boldsymbol{p},\boldsymbol{q},o)=\boldsymbol{p}^{T}\text{ReLU}(\boldsymbol{W}\boldsymbol{a}+q)+o,$ (55) $$

where $\boldsymbol{a}\in\mathbb{R}^{d_{I}},\boldsymbol{W}\in\mathbb{R}^{d_{H}\times d_{I}},\boldsymbol{p},\boldsymbol{q}\in\mathbb{R}^{d_{H}}$ and $o\in\mathbb{R}$. The $d_{I}$ and $d_{H}$ are the input dimension and hidden dimension, respectively. The data set $\{(\boldsymbol{a}^{(i)},b^{(i)})\}_{i=1}^{m}$ can be generated similar to linear regression but with $K$ ground truth neural network models. We set $d_{I}=10$ and $d_{H}=10$ in all comparisons.

## Appendix C More Experimental Results

### C.1 Noisy Mixed Linear Regression

**Table 4: The results on the noisy mixed linear regression with different different noisy levels $\sigma$ and different numbers of solutions $K$. We report the mean worst and average objective values over $50$ independent runs for each method. The best results are highlighted in bold with the gray background.**
|  |  | LS | TCH | STCH | SoM | TCH-Set | STCH-Set |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\sigma=0.1$ |  |  |  |  |  |  |  |
| K = 5 | worst | 3.84e+01(+) | 2.45e+01(+) | 2.43e+01(+) | 2.50e+00(+) | 4.19e+00(+) | 2.10e+00 |
|  | average | 2.70e+00(+) | 1.46e+00(+) | 1.44e+00(+) | 1.88e-01(-) | 6.53e-01(+) | 4.72e-01 |
|  | worst | 2.21e+01(+) | 2.49e+01(+) | 3.92e+01(+) | 3.46e+00(+) | 2.04e+00(+) | 5.00e-01 |
| K = 10 | average | 1.09e+00(+) | 1.19e+00(+) | 3.01e+00(+) | 2.33e-01(+) | 3.83e-01(+) | 2.00e-01 |
|  | worst | 4.20e+01(+) | 2.11e+01(+) | 2.21e+01(+) | 2.57e+00(+) | 1.64e+00(+) | 2.70e-01 |
| K = 15 | average | 3.07e+00(+) | 1.02e+00(+) | 1.02e+00(+) | 1.97e-01(+) | 3.22e-01(+) | 1.66e-01 |
|  | worst | 4.20e+01(+) | 2.14e+01(+) | 2.04e+01(+) | 1.44e+00(+) | 1.79e+00(+) | 2.27e-01 |
| K = 20 | average | 3.09e+00(+) | 8.35e-01(+) | 8.87e-01(+) | 1.84e-01(+) | 3.29e-01(+) | 1.66e-01 |
| $\sigma=0.5$ |  |  |  |  |  |  |  |
|  | worst | 3.93e+01(+) | 2.53e+01(+) | 2.50e+01(+) | 5.33e+00(+) | 4.37e+00(+) | 2.45e+00 |
| K = 5 | average | 2.74e+00(+) | 1.51e+00(+) | 1.52e+00(+) | 3.08e-01(-) | 7.05e-01(+) | 5.54e-01 |
|  | worst | 4.20e+01(+) | 2.39e+01(+) | 2.56e+01(+) | 3.68e+00(+) | 2.38e+00(+) | 6.03e-01 |
| K = 10 | average | 3.25e+00(+) | 1.28e+00(+) | 1.20e+00(+) | 2.46e-01(+) | 4.18e-01(+) | 2.24e-01 |
|  | worst | 4.36e+01(+) | 2.37e+01(+) | 2.35e+01(+) | 3.00e+00(+) | 1.72e+00(+) | 3.07e-01 |
| K = 15 | average | 3.30e+00(+) | 1.02e+00(+) | 1.09e+00(+) | 2.06e-01(+) | 3.46e-01(+) | 1.78e-01 |
|  | worst | 4.36e+01(+) | 2.18e+01(+) | 2.23e+01(+) | 1.93e+00(+) | 1.27e+00(+) | 2.39e-01 |
| K = 20 | average | 3.22e+00(+) | 9.15e-01(+) | 9.99e-01(+) | 1.92e-01(+) | 2.94e-01(+) | 1.74e-01 |
| $\sigma=1$ |  |  |  |  |  |  |  |
|  | worst | 4.76e+01(+) | 3.24e+01(+) | 3.48e+01(+) | 1.00e+01(+) | 5.49e+00(+) | 3.48e+00 |
| K = 5 | average | 3.39e+00(+) | 1.71e+00(+) | 1.93e+00(+) | 5.21e-01(-) | 8.45e-01(+) | 7.44e-01 |
|  | worst | 4.86e+01(+) | 2.93e+01(+) | 3.30e+01(+) | 4.86e+00(+) | 3.31e+00(+) | 7.82e-01 |
| K = 10 | average | 3.81e+00(+) | 1.45e+00(+) | 1.55e+00(+) | 2.88e-01(+) | 5.30e-01(+) | 2.80e-01 |
|  | worst | 5.23e+01(+) | 3.11e+01(+) | 2.78e+01(+) | 3.41e+00(+) | 2.45e+00(+) | 3.55e-01 |
| K = 15 | average | 3.84e+00(+) | 1.19e+00(+) | 1.16e+00(+) | 2.32e-01(+) | 4.51e-01(+) | 2.04e-01 |
|  | worst | 5.37e+01(+) | 2.54e+01(+) | 2.61e+01(+) | 2.47e+00(+) | 2.04e+00(+) | 2.68e-01 |
| K = 20 | average | 3.81e+00(+) | 1.08e+00(+) | 1.08e+00(+) | 2.12e-01(+) | 3.81e-01(+) | 1.94e-01 |
| Wilcoxon Rank-Sum Test Summary |  |  |  |  |  |  |  |
|  | worst | 12/0/0 | 12/0/0 | 12/0/0 | 12/0/0 | 12/0/0 | - |
| +/=/- | average | 12/0/0 | 12/0/0 | 12/0/0 | 12/0/0 | 9/0/3 | - |

The full results for the noisy mixed linear regression problem are shown in Table [4](#A3.T4). According to the results, STCH-Set can always obtain the lowest worst objective values for all noise levels and different numbers of solutions. In addition, it also obtains the best average objective values for most comparisons. The sum-of-minimum (SoM) optimization method can achieve good and even better average objective values, but with a significantly higher worst objective value.

### C.2 Noisy Mixed Nonlinear Regression

**Table 5: The results on the noisy mixed nonlinear regression with different noisy levels $\sigma$ and different numbers of solutions $K$. We report the mean worst and average objective values over $50$ independent runs for each method. The best results are highlighted in bold with gray background.**
|  |  | LS | TCH | STCH | SoM | TCH-Set | STCH-Set |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\sigma=0.1$ |  |  |  |  |  |  |  |
| K = 5 | worst | 2.34e+02 (+) | 1.68e+02(+) | 1.57e+02(+) | 1.68e+01(+) | 1.94e+01(+) | 7.43e+00 |
|  | average | 9.19e+00(+) | 8.50e+00(+) | 7.90e+00(+) | 8.54e-01(-) | 3.48e+00(+) | 1.89e+00 |
|  | worst | 3.23e+02(+) | 1.72e+02(+) | 1.57e+02(+) | 4.42e+00(+) | 6.07e+00(+) | 6.28e-01 |
| K = 10 | average | 8.70e+00 (+) | 6.65e+00(+) | 5.85e+00(+) | 1.22e-01(+) | 1.03e+00(+) | 5.99e-02 |
|  | worst | 3.65e+02(+) | 2.10e+02(+) | 1.62e+02(+) | 1.10e+00(+) | 1.57e+00(+) | 2.05e-01 |
| K = 15 | average | 8.33e+00(+) | 5.66e+00(+) | 4.89e+00(+) | 1.47e-01(+) | 3.27e-01(+) | 1.27e-02 |
|  | worst | 3.36e+02(+) | 2.04e+02(+) | 1.81e+02(+) | 5.59e+00(+) | 4.37e+00(+) | 6.22e-01 |
| K = 20 | average | 8.81e+00(+) | 6.92e+00(+) | 6.23e+00(+) | 1.24e-01(+) | 9.09e-01(+) | 6.27e-02 |
| $\sigma=0.5$ |  |  |  |  |  |  |  |
|  | worst | 2.14e+02(+) | 1.87e+02(+) | 1.62e+02(+) | 2.00e+01(+) | 1.82e+01(+) | 1.20e+01 |
| K = 5 | average | 9.17e+00(+) | 8.53e+00(+) | 7.96e+00(+) | 8.63e-01(-) | 3.49e+00(+) | 2.31e+00 |
|  | worst | 3.36e+02(+) | 2.04e+02(+) | 1.81e+02(+) | 5.59e+00(+) | 4.37e+00(+) | 6.22e-01 |
| K = 10 | average | 8.81e+00(+) | 6.92e+00(+) | 6.23e+00(+) | 1.24e-01(+) | 9.09e-01(+) | 6.27e-02 |
|  | worst | 3.46e+02(+) | 1.99e+02(+) | 1.53e+02(+) | 2.00e+00(+) | 2.15e+00(+) | 1.57e-01 |
| K = 15 | average | 8.38e+00(+) | 5.63e+00(+) | 4.59e+00(+) | 1.81e-02(+) | 3.97e-01(+) | 1.26e-02 |
|  | worst | 3.75e+02(+) | 1.54e+02(+) | 1.27e+02(+) | 5.05e-01(+) | 6.60e-01(+) | 1.12e-01 |
| K = 20 | average | 6.95e+00(+) | 4.23e+00(+) | 3.32e+00(+) | 3.96e-03(-) | 1.35e-01(+) | 6.72e-03 |
| $\sigma=1$ |  |  |  |  |  |  |  |
|  | worst | 3.47e+02(+) | 1.50e+02(+) | 1.39e+02(+) | 1.81e-01(+) | 4.65e-01(+) | 9.49e-02 |
| K = 5 | average | 6.95e+00(+) | 4.34e+00(+) | 3.32e+00(+) | 1.26e-03(-) | 1.11e-01(+) | 6.65e-03 |
|  | worst | 3.08e+02(+) | 2.26e+02(+) | 1.68e+02(+) | 5.08e+00(+) | 6.91e+00(+) | 6.44e-01 |
| K = 10 | average | 9.18e+00(+) | 7.10e+00(+) | 6.13e+00(+) | 1.32e-01(+) | 1.10e+00(+) | 5.77e-02 |
|  | worst | 3.35e+02(+) | 2.03e+02(+) | 1.64e+02(+) | 1.89e+00(+) | 1.91e+00(+) | 2.11e-01 |
| K = 15 | average | 8.47e+00(+) | 6.19e+00(+) | 4.92e+00(+) | 2.11e-02(+) | 3.93e-01(+) | 1.30e-02 |
|  | worst | 3.40e+02(+) | 1.83e+02(+) | 1.21e+02(+) | 1.81e-01(+) | 4.65e-01(+) | 9.08e-02 |
| K = 20 | average | 7.20e+00(+) | 4.44e+00(+) | 3.45e+00(+) | 3.24e-03(-) | 1.11e-01(+) | 6.73e-03 |
| Wilcoxon Rank-Sum Test Summary |  |  |  |  |  |  |  |
|  | worst | 12/0/0 | 12/0/0 | 12/0/0 | 12/0/0 | 12/0/0 | - |
| +/=/- | average | 12/0/0 | 12/0/0 | 12/0/0 | 7/0/5 | 12/0/0 | - |

The full results for the noisy mixed nonlinear regression problem are provided in Table [5](#A3.T5). Similar to the linear counterpart, STCH-Set can also achieve the lowest worst objective value for all comparisons. However, it is outperformed by SoM on $5$ out of $12$ comparisons on the average objective value. One possible result could be due to the highly non-convex nature of neural network training. Once a solution is captured by a bad local optimum, it will have many high but not reducible objective values, which might mislead the STCH-Set optimization. An adaptive estimation method for the ideal point could be helpful to tackle this issue.

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: Is possible this scheme to solve many-objectives problems works well due to some redundancy in the objectives, meaning, objectives are correlated so some solutions that perform well on one of them should also perform well in the positively correlated objectives.
Have you consider some dimensionality reduction techniques to maybe reduce which objectives should be evaluated during the scalarization?
soundness: 4
strengths: Scalarization that is well known to perform well on multi-objective problems as seen on different variants of the evolutionary algorithm MOEA/D. Tchebycheff as the scalarizing function has also been shown to cover the non-convex solutions in the Pareto Front. The regular approach only aims to have a solution per direction, by modifying the function to instead search for a set of points that while being good for the other objectives it should be the best for a subset of all objectives.

The text introduces well non multi-objective practitioners to the setting, the difficulty present in many-objective problems, and previous work and results on scalarization with the simple weighted sum and the Tchebycheff function.
Appendices further explore the effect of the smoothness parameter and complement the main text with more experiments.
summary: The authors propose a scheme for many-objective problems with large number of objectives (e.g > 100) where the idea is to find a few representative solutions that address them.
To make this scheme possible they use their newly proposed Tchebycheff Set scalarization function that is an extension of the original. Now instead of trying to find a point that minimizes the scalarized problem, is trying to find multiple points that minimize it, allowing it to be bad for some of the m objectives, but it should at least minimize some subset of it.
The original Tchebycheff function is non differentiable to the max and min operators, which makes it not the best option to work with gradient based optimization. Therefore they extend the smooth Tchebycheff function in the work Lin et.al 2024 to work on set of solutions.
weaknesses: It would have been nice to touch or at least mention dimensionality reduction techniques and problems with redundant objectives.
Seems its the other side of the coin, given that there is some correlation in the objectives for them to be satisfied or addressed well with a single solution. As shown in Figure 2, each solution address 20 of the 100 objectives, does this mean that the underlying 100 objective problem can be summarized by a 5 objective problem?.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: Please refer to "Weaknesses". Additionally, I suggest the authors summarize a notation table in the appendix.
soundness: 3
strengths: 1. This paper is well-written and easy to follow.
2. The proposed method is well-motivated. 
3. The technical details are clearly presented, and the theoretical analyses seem correct. 
4. The literature review is comprehensive.
summary: This paper proposes a novel scalarization method called TCH-Set to produce a limited number of solutions that handle many objectives. A relaxed version is also proposed to tackle the non-smooth situations. The theoretical properties of the proposed method are investigated, and an empirical study is conducted to verify its effectiveness.
weaknesses: My major concern is about the problem setting. The proposed method aims to find a few solutions that collaboratively optimize many objectives. This problem setting is quite different from the common setting in multi- or many-objective optimization, which aims to find some solutions with diverse trade-offs. I agree with the authors that one of the main obstacles in many-objective optimization is that, with the increase in the number of objectives, the number of solutions has to increase exponentially to cover the whole PF. The idea proposed in this paper is interesting; however, I do not think it really solves this problem. When the number of objectives is very high, it only searches for extreme points, that is, solutions with very low values for some objectives but significant sacrifices in others. By putting together these multiple extreme points, it appears as if multiple objective functions can be *"simultaneously"* optimized. Actually, although many MOAs output a set of solutions, after multi-objective decision-making, typically only one solution is finally selected, and, in practice, solutions with a more balanced tradeoff are often preferred. Therefore, while the TCH-Set offers a novel idea for many-objective optimization, I think its practical impact and significance are limited.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: 1. After the Tchebycheff set scalarization, how is the scalarized problem solved, given that a set of solutions needs to be optimized?
2. Did the methods compared in the experiments also propose the few-for-many prospective for many-objective optimization?
3. What optimization methods are used under the scalarization methods for the convex multi-objective optimization in Section 4.1?
4. A brief analysis of why STCH-Set performs slightly worse than SoM in two cases in Table 4 would be beneficial.
5. It should be clarified why the part results of MosT are “-” in Table 6.
6. All mathematical symbols (e.g., $K$ and $m$) in the tables should use the correct mathematical formatting.
7. In line 227, a space is missing after the period.
8. In line 1473, there is an incorrect line break, and “term0” appears to be a typo.
9. In line 1487, a space is missing before “(S)TCH”.
10. An open question is whether the proposed approach is especially suited for many-objective optimization with non-conflicting objectives. How would it perform when all objectives are conflicting?
soundness: 4
strengths: 1. This paper introduces a novel and practical prospective in tackling for many-objective optimization.
2. This paper develops a smooth Tchebycheff set scalarization approach under the few-for-many prospective.
3. The theoretical analysis is thorough and well-supported.
summary: Different from general multi-objective optimization aiming to find a dense Pareto set, this paper focuses on identifying a few solutions that cover a large number of objectives in a complementary manner for many-objective optimization. To achieve this, a smooth Tchebycheff set scalarization approach is developed with good theoretical guarantees.
weaknesses: Some descriptions lack clarity, and minor writing errors are present. Please refer to the questions below for the details.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 3
questions: * The experiments are conducted with different K, how to choose the K of your algorithm?

* Since the preference $\lambda$ can greatly impacts the final result, could you please provide with some hints for choosing  $\lambda$?

Reference：
1.  Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathematics of Operations Research, 8(3):467–470, 1983.
2.  Xi Lin, Xiaoyuan Zhang, Zhiyuan Yang, Fei Liu, Zhenkun Wang, and Qingfu Zhang. Smooth tchebycheff scalarization for multi-objective optimization. arXiv preprint arXiv:2402.19078, 2024.
soundness: 2
strengths: * This paper is well-written and easy to follow.

* The experiments are comprehensive and include necessary analyses, and the results are convincing.

* The necessary proofs are included.
summary: Authors propose a novel Tchebycheff set scalarization method to find a few representative solution to cover a large number of objectives
 in a collaborative and complementary manner so that each objective can be well addressed by at least one solution in the small solution set.
weaknesses: * This novelty is somewhat limited. It seems the line 74 “a novel Tchebycheff set (TCH-Set) scalarization approach”  has been proposed in [1] and the line 75 “a smooth Tchebycheff set (STCH-Set) scalarization approach” has been proposed in [2].

* The motivation is not quite clear. Why should you find a few representative solutions to cover a large number of objectives? 

* The work is not tied to particular applications. Can you briefly provide some scenarios where your method is applicable?

Meta-review: This paper studies the problem of finding an approximate set of Pareto solutions in multi-objective optimization. To overcome the curse of dimensionality, the authors propose a novel Tchebycheff set scalarization method to find representative solutions  to cover a large number of objectives. All the reviewers support the acceptance of this paper, and some minor issues have been clarified during the rebuttal period.  Therefore, I recommend "Accept".

Decision: Accept (Poster)