3
$\begingroup$

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.

Thank you for your enthusiasm !

$\endgroup$
3
  • 1
    $\begingroup$ It is a bit contradictory that you say that the weights are given but still want to scale the objectives. By scaling you are changing the given weights from $w_i$ to $\tilde{w}_i=w_i\cdot scaling_i$ $\endgroup$
    – Sune
    Dec 25, 2023 at 7:50
  • $\begingroup$ Oh yes I want to scale $f_1$ and $f_2$ first so that they are as big as the others. After that the preference $w_1$ and $w_2$ which are not important at this moment can be chosen latter. $\endgroup$ Dec 25, 2023 at 15:52
  • $\begingroup$ @TuongNguyenMinh If $f_i(x)$ are homogeneous functions the solution is easy, I invite you to read my answer. $\endgroup$ Jan 3 at 11:27

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Actually I am hoping for a more general answer of finding the scaling given that I know $M$ and $N$. :( and at this point I just hope to get an initial working proof of concept instead of any physical meaning or interpretation yet. $\endgroup$ Dec 24, 2023 at 19:09
1
$\begingroup$

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)$

$\endgroup$
3
  • $\begingroup$ Wow this method is quite novel ! do you have any reference for this kind of method ? $\endgroup$ Jan 3 at 13:02
  • 1
    $\begingroup$ Thx for the wow! Method comes out from my insight upon vector spaces: I do not have any specific reference, It is sufficient a good text of Linear Algebra. By the way, a good aproximation for $ \lambda $ can be furnished by M that you well know. $\endgroup$ Jan 3 at 14:49
  • $\begingroup$ Thank you ! I have upvoted your answer, but it would be better if you could provide a tiny concrete example :) $\endgroup$ Jan 8 at 2:37
1
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ I am sorry but I am not native English speaker :( , what does lexicographic solutions even mean ? $\endgroup$ Jan 3 at 13:03
  • 1
    $\begingroup$ I thing wikipedia is good place to start: en.wikipedia.org/wiki/Lexicographic_optimization $\endgroup$
    – Sune
    Jan 3 at 13:55
  • $\begingroup$ Thank you ! I have upvoted your answer, but it would be better if you could provide a tiny concrete example :) $\endgroup$ Jan 8 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.