Problem of scaling or normalizing in multiobjective optimization problem when one objective function is much larger than the other?

Question

I am an electrical engineer who is working in network problem and I was trying to solve a multi objective function

$\begin{array}{*{20}{c}} {\min }&{{f_1}\left( x \right)}\\ \end{array}$

$\begin{array}{*{20}{c}} {\min }&{{f_2}\left( x \right)}\\ \end{array}$

In my application, the complete pareto front is not needed and scalarization (weighted sum approximation) is the right way to go. That is, to solve this problem with two given weights $w_1$ and ${w_2} = 1 - {w_1}$ instead.

$\begin{array}{*{20}{c}} {\min }&{{w_1}{f_1}\left( x \right) + {w_2}{f_2}\left( x \right)} \end{array}$

Note that the value of $w_1$ and $w_2$ are already given. What I am trying to do here is to minimize both the delay and the number of resource block in the network.

Here ${{f_1}\left( x \right)}$ is some delay that is in nano or mili second. On the other hand ${{f_2}\left( x \right)}$ is some resource block so it may be 1,2,3,4....

My problem is that if I convert ${{f_1}\left( x \right)}$ to second then this number will be very small compare to ${{f_2}\left( x \right)}$. To be honest, I want to avoid the issue of ${f_1}\left( x \right) \ll {f_2}\left( x \right)$ or ${f_1}\left( x \right) \gg {f_2}\left( x \right)$

1/ Therefore, what should I do to choose a proper scaling for my scalarization problem so that it does not lean toward the larger ${{f_2}\left( x \right)}$ function.

2/ Approximating the number $N$ for $0 \le {f_1}\left( x \right) \le {\rm{N}}$ is very difficult. In contrast, approximating the number $M$ for $0 \le {f_2}\left( x \right) \le {\rm{M}}$ is very easy due to my domain knowledge. Although the bound is not sharp but I can guess it very well.

Therefore, can I use this knowledge to scale the function ${f_1}\left( x \right)$ and ${f_2}\left( x \right)$ in question 1 so that the scalarization problem does not lean toward ${f_2}\left( x \right)$ ?

$\begin{array}{*{20}{c}} {\min }&{{w_1}\left[ {\underbrace {{\rm{scalin}}{{\rm{g}}_{\rm{1}}}}_?{f_1}\left( x \right)} \right] + {w_2}\left[ {\underbrace {{\rm{scalin}}{{\rm{g}}_{\rm{2}}}}_?{f_2}\left( x \right)} \right]} \end{array}$

Note that I want to scale $f_1$ and $f_2$ first so that they are as big as another. The weight $w_1$ and $w_2$ are given latter and currently are not important at this moment.

I have found the answer to this question by myself (base on 2/). Due to some domain knowledge I am absolutely sure about the maximum possible value of $f_2(x)$. Therefore, I use the constraint method, in some book it might be call $\epsilon$-constraint method.

$\begin{array}{l} \begin{array}{*{20}{c}} {\mathop {\min }\limits_x }&{{f_1}\left( x \right)} \end{array}\\ {f_2}\left( x \right) \le c \end{array}$

By changing the value of $c$, I can find points in the concave region of the pareto frontier.

Answer 1

I would suggest that you start by asking yourself (or the boss) why you want to reduce delay and why you want to reduce resource use. Ideally, these will translate into some sort of tangible costs. You can then scale so that tradeoffs in the objective make sense (i.e., the solver is indifferent between competing solutions that in fact have equivalent overall costs).

If that cannot be done, another possibility is to explore tradeoffs with the person ultimately responsible for the decision. Ask questions like "how much additional use of this resource would you be comfortable with if it reduced this delay by 1 ms.?" Use the decision maker's preference for tradeoffs to scale the objective.

Answer 2

In my opinion, the problem could be addressed by defining an appropriate reference system or rather an appropriate measurement scale. We can image $f_1$ and $f_2$ to be the coordinate of two vectors: delay and resource block. Both of them belongs to a vector space where a positive scalar product is defined. Once the origin of vector space has been established, it is possible to establish an orthogonal frame of reference $R = \{\mathbf t_1, \mathbf t_2\}$ such that

$< \mathbf t_i, \mathbf t_k > = \Delta f_i$ if $i=k$

$< \mathbf t_i, \mathbf t_k > = 0$ if $i=k$

Note that if all measuring devices had the same unit of measurement and the same base unit $ \Delta f_1=\Delta f_2=1$, $R$ would constitute an orthonormal vector basis. But, this is not your case.

You problem is that $\Delta f_1<<<\Delta f_2$

On the one hand, you could adopt the Gram–Schmidt process or Gram-Schmidt algorithm as method of constructing an orthonormal basis.

On the other hand, you could simply choose an appropriate number $ \lambda$ such that $ \lambda \Delta f_1 = \Delta f_2$ (or $ \lambda \Delta f_2 = \Delta f_1$) and finally you can replace every coordinate $f_1$ by means of scalar moltiplication (change of scale) $\lambda f_1$ while $f_2$ remains the same.

In conclusion, delay is enlarged by $\lambda$ and problem becomes

$ min $ $\omega _{1} \lambda f_1(x) + \omega _{2} f_2(x)$

Answer 3

You write in a comment that "you want to scale $f_1$ and $f_2$ so that they are as big as the others". If I understand you correctly, this may be impossible if you do not know the range of values for the functions $f_1$ and $f_2$.

However, if you do have knowledge of the two lexicographic solutions \begin{align} x^{ul}&\in\mbox{arg }\mbox{lex}\min\{ \left(f_1(x),f_2(x)\right):x\text{ feasible}\}\\ x^{lr}&\in\mbox{arg }\mbox{lex}\min\{ \left(f_2(x),f_1(x)\right):x\text{ feasible}\} \end{align} Then you can simply scale the functions so they take values in e.g. $[0,1]$ by defining the following scaled functions \begin{align} \hat{f}_1(x)=\frac{f_1(x)-f_1(x^{ul})}{f_1(x^{lr})-f_1(x^{ul})}\\ \hat{f}_2(x)=\frac{f_2(x)-f_2(x^{lr})}{f_2(x^{ul})-f_2(x^{lr})}\\ \end{align} The idea is to perform a linear transformation that moves the Pareto front into the square $[0,1]\times[0,1]$.

Obtaining $x^{ul}$ and $x^{lr}$ can be done by solving two weighted sum scalarizations fo the form \begin{equation} \min w_1f_1(x)+w_2f_2(x) \end{equation} by appropriately choosing the weights (to get $x^{ul}$ chose $w_1\gg w_2$ and vice versa for $x^{lr}$).

---

Additional info about lexicographic optimality. I will use Ehrgott notation, and define the ordering $<_{lex}$ as follows: for two vectors $y^1$ and $y^2$ in $\mathbb{R}^p$ we say that $y^1<_{lex}y^2$ if $y^1_q<y^2_q$ where $q=\min\{k\in\{1,...,p\}:y_k^1\neq y_k^2\}$. For a multi objective optimization problem with $p$ objectives and where $f_1$ is more important than $f_2$, which is more important than $f_3$ and so on, we write a lexicographic optimization problem as $\mbox{lex}\min\{(f_1,...,f_p):x\text{ feasible}\}$. A feasible solution $\hat{x}$ is lexicographically optimal if there exist no other feasible $x$ such that $x<_{lex}\hat{x}$.