The Complexity of Multi-Objective Optimization

Question

Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|} \subset V$ to maximize the distance between the average vector of two selected subsets while minminzing the distance after transformation as follows:

$$\max_{V_1,V_2} \hspace{1.5mm} \left(\bigg\|\frac{1}{|V_1|}\sum_{v_j \in V_1}{v_j}-\frac{1}{|V_2|}\sum_{v_k\in V_2}{v_k}\bigg\|_2-\lambda \cdot \bigg\|\frac{1}{|V_1|}\sum_{v_j \in V_1}{\mathbf{W}v_j}-\frac{1}{|V_2|}\sum_{v_k\in V_2}{\mathbf{W}v_k}\bigg\|_2\right)$$

where $\lambda>0$ is a constant. $V_1$ and $V_2$ can have overlap or not.

How can we show its complexity? In the single objective optimization problem, we can prove its np-hardness. But could we prove this multi-objective optimization problem is np-hard or use other method to show that it is hard enough?

Thanks!

Answer 1

This problem is indeed a single objective optimization problem in the case of $W=0$.(the second term become zero) If the problem is NP-hard in the single objective case, then it is also NP-hard in the multi-objective case.

=========================================

Edit : I saw your question in the following link for the single-objective optimization version and it is in P.

Complexity of the distance between the average vector of two subsets

However the problem is still NP-hard, can be reduced from the Equal Sum Subset problem which is known to be NP-hard.

In this problem, we are given a set of positive integers and we ask for two disjoint subset with equal sum of elements.

Let given instance of the Equal Sum Subset problem (B) be $\{a_1,\cdots,a_m\}$.

Let $\lambda = 1$, $n=2m$, $d=m+1$. Each $v_i$ is a standard basis $e_i$ for $i=1,\cdots,n$. This make us possible to arbitrarily set the value of $Wv_i$. Let $M> n^2$ be a sufficiently large number.

The first $m$ coordinate of $Wv_i$ is $Me_i$ for $1 \le i \le m$ and $Me_{i-m}$ for $m+1 \le i \le 2m$.

The last coordinate of $Wv_i$ is $Ma_i$ for $1 \le i \le m$ and $0$ otherwise.

My claim is that the multi-objective problem (A) has positive optimal value if and only if the answer of the Equal Sum Subset problem is 'yes'.

Let's make some observations. Let the optimal subsets be $V_1^*$ and $V_2^*$.

First, note that if both subset $V_1$ and $V_2$ are empty, the objective value is $0$.

Second, the first term of A is at most $1$.(from the single-objective case)

Third, if $v_i \in V_1^*$($V_2^*$, respectively) for some $1 \le i \le m$, $v_{m+i}$ must in $V_2^*$($V_1^*$, respectively). The converse is also true. Otherwise, the absolute value of the $i$th coordinate of the vector in the second term is larger than $M/n^2 > 1$ and in this case the objective value must be negative. This implies $|V_1| = |V_2|$.

Fourth, Let $V_i^* \cap [1,n] = S_i$ for $i=1,2$. Following the third observation, the last coordinate of the vector in the second term is $0$ if $|S_1|=0$, and $M\frac{|\sum_{i \in S_1}a_i - \sum_{j \in S_2}a_j |}{|S_1|}$ otherwise.

If the answer of (B) is no, the absolute value of the last coordinate of the vector in the second term is at least $M/m > 1$ if $|S_1| > 0$, hence the optimal value is $0$.

If the answer of the (B) is yes, let the corresponding index set of the two set be $S_1$ and $S_2$. Let $V_1 = S_1 \cup (S_2 \oplus m)$ and $V_2 = S_2 \cup (S_1 \oplus m)$. Then the second term of the objective is $0$, while the first term is positive.