# Exercise 7, answers

## Problem 1

### Part a)

Let's assume the opposite that $x^*$ is an optimal solution to 
$$
\min \sum_{i=1}^kw_if_i(x)\\
\text{s.t. }x\in S
$$
and that the solution $x^*$ is not Pareto optimal.

If $x^*$ is not Pareto optimal, then there exists $x'\in S$ such that
$$
\left\{
\begin{align}
f_i(x')\leq f_i(x^*) \text{ for all }i=1,\ldots,k,\text{ and}\\
f_j(x')< f_j(x^*) \text{ for some }j=1,\ldots,k.
\end{align}
\right.
$$
But this means that
$$
\begin{align}
\sum_{i=1}^kw_if_i(x') &= \sum_{i\neq j}w_if_i(x')+w_jf_j(x')\\
&<\sum_{i\neq j}w_if_i(x^*)+w_jf_j(x^*)\\
&=\sum_{i=1}^kw_if_i(x^*).
\end{align}
$$
Thus, $x^*$ is not an optimal solution to the problem in the weighting method. This means that $x^*$ must be Pareto optimal.

### Part b

Let's again assume that a solution $x^*$ is an optimal solution to the problem for all $j=1,\ldots,k$ and $\epsilon = f(x^*)$, but it is not Pareto optimal.

If $x^*$ is not Pareto optimal, then there exists $x'\in S$ such that
$$
\left\{
\begin{align}
f_i(x')\leq f_i(x^*) \text{ for all }i=1,\ldots,k,\text{ and}\\
f_j(x')< f_j(x^*) \text{ for some }j=1,\ldots,k.
\end{align}
\right.
$$

The first inequality means that $x'$ is a feasible solution to the epsilon constraint method for "$j=j$" (meaning that the index $j$ is the same in the definition of Pareto optimality and the definition of the epsilon constraint method).

Furthermore, the second stricth inequality says that the value of the objective at this solutions $x'$ is better than the value at the solutions $x^*$. This means that it is not Pareto optimal.

# Problem 2

# Part a)

Let's assume that a solution $x^*$ is an optimal solution to the achievement scalarizing problem, but it is not Pareto optimal. 

If $x^*$ is not Pareto optimal, then there exists $x'\in S$ such that
$$
\left\{
\begin{align}
f_i(x')\leq f_i(x^*) \text{ for all }i=1,\ldots,k,\text{ and}\\
f_j(x')< f_j(x^*) \text{ for some }j=1,\ldots,k.
\end{align}
\right.
$$

Now,
$$
\max_{i=1}^i(f_i(x^*)-z^{ref}_i)+\rho\sum_{i=1}^kf_i(x^*) \geq \max_{i=1}^i(f_i(x')-z^{ref}_i)+\rho\sum_{i=1}^kf_i(x^*)\\
>  \max_{i=1}^i(f_i(x')-z^{ref}_i)+\rho\sum_{i=1}^kf_i(x')
$$
where we used just the first inequality first, and then we used the previous proof from weighting method.

This means again that if the solution $x^*$ is not Pareto optimal, then it cannot be an optimal solution to the achievement scalarizing function.

Part b)

Assume a Pareto optimal $x^*$. Now, we choose $z^{ref} = f(x^*)$. Let's have any solutions $x\in S$. Then,
$$
\max_{i=1\ldots,k}(f_i(x)-z_i^{ref})+\rho\sum_{i=1}^kf_i(x) = \max_{i=1\ldots,k}(f_i(x)-f_i(x^*))\\
\geq 0,
$$
because $x^*$ is Pareto optimal and, thus, at least one of the objectives needs to be greater or equal (if this was not the case, the solution $x^*$ would not be Pareto optimal).

But now,
$$
\max_{i=1\ldots,k}(f_i(x^*)-z_i^{ref})+\rho\sum_{i=1}^kf_i(x^*)= \max_{i=1\ldots,k}(f_i(x^*)-f_i(x^*))+\rho\sum_{i=1}^kf_i(x^*) \\
= 0
$$
trivially. This means that the Pareto optimal solution $x^*$ is an optimal solution to the achievement scalarizing problem. 

a5e537a8e7fe04c5ee30198cd33af26c7a1671aa
ipynb
Jupyter Notebook
Exercise 7, asnwers.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2019-04-26T12:46:14.000Z
2021-11-23T03:38:59.000Z
Exercise 7, asnwers.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
Exercise 7, asnwers.ipynb
maeehart/TIES483
cce5c779aeb0ade5f959a2ed5cca982be5cf2316
CC-BY-3.0
2016-01-08T16:28:11.000Z
2021-04-10T05:18:10.000Z
Qwen/Qwen-72B
1. YES
2. YES