Multi-objective Least Square

Definition:

• Goal: choose $n$-vector $x$ so that $k$ norm squared objectives, $J_1=||A_{1}x-b_1|{|}^2,...,J_k=||A_{k}x-b_k|{|}^2$ are all small
  • where $A_i$ is an $m_i\times n$ matrix, $b_i$ is an $m_i$-vector for $i=1,...,k$
• $J_i$ are the objectives in a multi-objective optimization problem

Weighted sum objective:

• Choose positive weights ${\lambda }_1,{\lambda }_2,...,{\lambda }_k$ and form a weighted sum objective: $J={\lambda }_1{J}_1+...+{\lambda }_j{J}_j={\lambda }_1||A_{1}x-b_1|{|}^2+...+{\lambda }_k||A_{k}x-b_k|{|}^2$
  • so we need to choose $x$ to minimize $J$
• Interpretation of ${\lambda }_i$: how much we care about $J_i$ being small relative to other $J$s

Weighted sum minimization via stacking:

• Write weighted-sum objective as $J={\Vert \begin{array}{c}\left[\begin{array}{c}\sqrt{{\lambda }_1}(A_{1}x-b_1)\\ ...\\ \sqrt{{\lambda }_k}(A_{k}x-b_k\end{array}\right]\end{array}\Vert }^2=||\tilde{A}x-\tilde{b}|{|}^2$
  • $\tilde{A}=\left[\begin{array}{c}\sqrt{{\lambda }_1}{A}_1\\ ...\\ \sqrt{{\lambda }_k}{A}_k\end{array}\right]$ and $\tilde{b}=\left[\begin{array}{c}\sqrt{{\lambda }_1}{b}_1\\ ...\\ \sqrt{{\lambda }_k}{b}_k\end{array}\right]$

Weighted sum solution:

• Assuming columns of $\tilde{A}$ are independent, $\tilde{x}=({\tilde{A}}^{⊺}\tilde{A}){|}^{-1}{\tilde{A}}^{⊺}\tilde{b}=({\lambda }_1{A}_1^{⊺}{A}_1+...+{\lambda }_k{A}_k^{⊺}{A}_k{)}^{-1}({\lambda }_1{A}_1^{⊺}{A}_1+...+{\lambda }_k{A}_k^{⊺}{A}_k)$
• Then $\hat{x}$ can be computed with QR Decomposition of $\tilde{A}$

Optimal trade-off curve:

• Graph the change of $\lambda$ to see which $J$ the model is prioritizing over the other
• For example: with bi-criterion problem $J=J_1+\lambda J_2$
  • If $J_2$ too big, increase $\lambda$ so it will prioritize to lower $J_1$ more
  • If $J_1$ too big, decrease $\lambda$ so it will prioritize to lower $J_2$ more
• Estmation and inversion: