If you find any mistakes, please make a comment! Thank you.

## Solution to Mathematics for Machine Learning Exercise 7.6

Consider the linear program illustrated in Figure 7.9, $$\min _{\boldsymbol{x} \in \mathbb{R}^{2}}\quad -\left[\begin{array}{l} 5 \\ 3 \end{array}\right]^{\top}\left[\begin{array}{l} x_{1} \\ x_{2} \end{array}\right]$$ $$\text { subject to }\quad \left[\begin{array}{cc} 2 & 2 \\ 2 & -4 \\ -2 & 1 \\ 0 & -1 \\ 0 & 1 \end{array}\right]\left[\begin{array}{l} x_{1} \\ x_{2} \end{array}\right] \leqslant\left[\begin{array}{c} 33 \\ 8 \\ 5 \\ -1 \\ 8 \end{array}\right]$$ Derive the dual linear program using Lagrange duality.

Solution: We use (7.43) on Page 239 directly. Note that in this case, see (7.39), we have $$\boldsymbol c=-\left[\begin{array}{l} 5 \\ 3 \end{array}\right],\quad \boldsymbol b=\left[\begin{array}{c} 33 \\ 8 \\ 5 \\ -1 \\ 8 \end{array}\right],$$ $$\boldsymbol A=\left[\begin{array}{cc} 2 & 2 \\ 2 & -4 \\ -2 & 1 \\ 0 & -1 \\ 0 & 1 \end{array}\right].$$By (7.43), the dual linear program is $$\max _{\boldsymbol{\lambda} \in \mathbb{R}^{5}}\quad -\left[\begin{array}{c} 33 \\ 8 \\ 5 \\ -1 \\ 8 \end{array}\right]^{\top}\left[\begin{array}{c} \lambda_{1} \\ \lambda_{2} \\ \lambda_{3} \\ \lambda_{4} \\ \lambda_{5} \end{array}\right]$$ $$\text { subject to } \quad -\left[\begin{array}{l} 5 \\ 3 \end{array}\right]+\left[\begin{array}{cc} 2 & 2 \\ 2 & -4 \\ -2 & 1 \\ 0 & -1 \\ 0 & 1 \end{array}\right]^\top \left[\begin{array}{c} \lambda_{1} \\ \lambda_{2} \\ \lambda_{3} \\ \lambda_{4} \\ \lambda_{5} \end{array}\right]=0$$ $$\left[\begin{array}{c} \lambda_{1} \\ \lambda_{2} \\ \lambda_{3} \\ \lambda_{4} \\ \lambda_{5} \end{array}\right]\geqslant 0.$$