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

Solution to Mathematics for Machine Learning Exercise 7.7


Consider the quadratic program illustrated in Figure 7.4, $$
\min _{\boldsymbol{x} \in \mathbb{R}^{2}}\quad \frac{1}{2}\left[\begin{array}{l}
x_{1} \\
x_{2}
\end{array}\right]^{\top}\left[\begin{array}{ll}
2 & 1 \\
1 & 4
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{2}
\end{array}\right]+\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}
1 & 0 \\
-1 & 0 \\
0 & 1 \\
0 & -1
\end{array}\right]\left[\begin{array}{l}
x_{1} \\
x_{2}
\end{array}\right] \leqslant\left[\begin{array}{c}
1 \\
1 \\
1 \\
1
\end{array}\right]
$$Derive the dual quadratic program using Lagrange duality.


Solution: The process is already in Chapter 7.3.2. I will give the answer directly from (7.52) on page 242.

The dual quadratic program is $$
\min _{\boldsymbol{\lambda} \in \mathbb{R}^{4}}\ -\frac{1}{14}\left(\left[\begin{array}{l}
5 \\
3
\end{array}\right]+\left[\begin{array}{cc}
1 & 0 \\
-1 & 0 \\
0 & 1 \\
0 & -1
\end{array}\right]^\top\left[\begin{array}{c}
\lambda_1 \\
\lambda_2 \\
\lambda_3 \\
\lambda_4
\end{array}\right]\right)^\top\left[\begin{array}{ll}
4 & -1 \\
-1 & 2
\end{array}\right] \left(\left[\begin{array}{l}
5 \\
3
\end{array}\right]+\left[\begin{array}{cc}
1 & 0 \\
-1 & 0 \\
0 & 1 \\
0 & -1
\end{array}\right]^\top\left[\begin{array}{c}
\lambda_1 \\
\lambda_2 \\
\lambda_3 \\
\lambda_4
\end{array}\right]\right)-\left[\begin{array}{c}
\lambda_1 \\
\lambda_2 \\
\lambda_3 \\
\lambda_4
\end{array}\right]^\top \left[\begin{array}{c}
1 \\
1 \\
1 \\
1
\end{array}\right]
$$ $$
\text { subject to }\quad\left[\begin{array}{c}
\lambda_1 \\
\lambda_2 \\
\lambda_3 \\
\lambda_4
\end{array}\right]\geqslant 0.
$$

Leave a Reply

Close Menu