Week 9 - Duality: exercise solutions
=======================================================

###### tags: `Optimization`

Author

Luis Espath \& Kian Wah Liew

Table of contents
-----------------

* [Question 1](#question-1)
* [Question 2](#question-2)
* [Question 3](#question-3)
* [Question 4](#question-4)
* [Question 5](#question-5)
* [Question 6](#question-6)
* [Question 7](#question-7)

Question 1
----------

Does the solution to the dual of the following problem give any useful information to the primal?
\begin{align*}
\begin{array}{ll}
\min & x_{1}^{2}-3 x_{2}^{2} \\
\text { s.t. } & x_{1}=x_{2}^{3}
\end{array}
\end{align*}

<details>
<summary>Solution</summary>

$L({\bf{x}},\mu ) = x_1^2 - 3x_2^2 + \mu ({x_1} - x_2^3)$
$q(\mu ) = \mathop {\min }\limits_{{\bf{x}} \in X} L({\bf{x}},\mu ) = - \infty$
The lower bound does not provide useful information to the problem.

</details>

Question 2
----------
Find a dual problem to the convex problem
\begin{align*}
\begin{aligned}
\min\quad &x_1^2+x_2^2+x_1x_2-x_1 \\
\text { s.t. } \quad & 3x_1+x_2\leq 1. \\
\end{aligned}
\end{align*}
Find the optimal solution of both the dual and primal problems.

<details>
<summary>Solution</summary>

The objective function is convex and (0,0) is in the convex feasible set S. The Slater’s condition applies and strong duality holds. Take ,
$L({\bf{x}},\lambda ) = x_1^2 + x_2^2 + {x_1}{x_2} - {x_1} + \lambda (3{x_1} + {x_2} - 1)$
We minimize 2$L({\bf{x}},\lambda )$ for simplicity.
$\begin{array}{c}
q(\lambda ) = \mathop {\min }\limits_{{\bf{x}} \in X} 2x_1^2 + 2x_2^2 + 2{x_1}{x_2} - 2{x_1} + \lambda (6{x_1} + 2{x_2} - 2)\\
= \mathop {\min }\limits_{{\bf{x}} \in X} \left( {\begin{array}{*{20}{c}}
{{x_1}}&{{x_2}}
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
2&1\\
1&2
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}
\end{array}} \right) + 2\left( {\begin{array}{*{20}{c}}
{3\lambda - 1}&\lambda
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}
\end{array}} \right) - 2\lambda
\end{array}$
From Chapter 2,
${{\bf{x}}^*} = - {\left( {\begin{array}{*{20}{c}}
2&1\\
1&2
\end{array}} \right)^{ - 1}}\left( {\begin{array}{*{20}{c}}
{3\lambda - 1}\\
\lambda
\end{array}} \right) = - \frac{1}{3}\left( {\begin{array}{*{20}{c}}
{5\lambda - 2}\\
{ - \lambda + 1}
\end{array}} \right)$
$$\begin{array}{c}
q(\lambda ) = \frac{1}{3}\left( {\begin{array}{*{20}{c}}
{5\lambda - 2}&{ - \lambda + 1}
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{3\lambda - 1}\\
\lambda
\end{array}} \right) - \frac{2}{3}\left( {\begin{array}{*{20}{c}}
{3\lambda - 1}&\lambda
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{5\lambda - 2}\\
{ - \lambda + 1}
\end{array}} \right) - 2\lambda \\
= - \frac{1}{3}\left( {\begin{array}{*{20}{c}}
{5\lambda - 2}&{ - \lambda + 1}
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
{3\lambda - 1}\\
\lambda
\end{array}} \right) - 2\lambda \\
= - \frac{1}{3}\left( {14{\lambda ^2} - 10\lambda + 2} \right) - 2\lambda = - \frac{{14}}{3}{\lambda ^2} + \frac{4}{3}\lambda - \frac{2}{3}
\end{array}$$
The dual is
\begin{align*}
\begin{array}{ll}
\max & - \frac{{14}}{3}{\lambda ^2} + \frac{4}{3}\lambda - \frac{2}{3} \\
\text{s.t.} & \lambda \ge 0\,.
\end{array}
\end{align*}

$\lambda = \frac{1}{7}$, ${q^*} = - \frac{4}{7}$, ${{\bf{x}}^*} = \left( {\begin{array}{*{20}{c}}
{\frac{{3}}{{7}}}&{ - \frac{{2}}{{7}}}
\end{array}} \right)$.

</details>

Question 3
----------

What goes wrong when we find the dual of this problem?
\begin{align*}
\begin{array}{ll}
\min & x_{1}^{2}-x_{2} \\
\text{s.t.} & x_{2}^{2} \leq 0\,.
\end{array}
\end{align*}

<details>
<summary>Solution</summary>

This is a convex optimization problem. However, the Slater's condition does not apply because there is no point satisfying $x_2^2<0$.

It is easy to see that the solution of the primal is $x_1=0,x_2=0$.
The Lagrangian is
$\begin{array}{c}
L({\mathbf{x}},\lambda ) = x_{1}^{2}-x_{2} + \lambda x_2^2\\
q(\lambda) = \mathop {\min }\limits_{{\bf{x}} \in X} x_{1}^{2}-x_{2} + \lambda x_2^2\\
= \left\{ {\begin{array}{*{20}{c}}
{ -\frac{1}{4\lambda}}\\
{ - \infty }
\end{array}} \right.{\hspace{0.5cm}}\begin{array}{*{20}{c}}
{\lambda>0}\\
{{\rm{\lambda=0}}}
\end{array}
\end{array}$

As $\lambda \rightarrow \infty$, $q^* \rightarrow 0$ but the optimal of the dual is not attainable.

</details>

Question 4
----------

Find the dual problem of
\begin{align*}
\begin{array}{ll}
\min & \bf{c}^{\top} \bf{x} \\
\text { s.t. } & \bf{A} \bf{x}\leq \bf{b},\\
& \bf{x}\geq \mathbf{0}.
\end{array}
\end{align*}

<details>
<summary>Solution</summary>

The Lagrangian is
$\begin{array}{c}
L({\bf{x}},\bf{\lambda} ,\eta ) = {{\bf{c}}^\top}{\bf{x}} + {\lambda ^\top}({\bf{Ax}} - {\bf{b}}) - {\eta ^\top}{\bf{x}}\\
q(\lambda ,\eta ) = \mathop {\min }\limits_{{\bf{x}} \in X} {{\bf{c}}^\top}{\bf{x}} + {\lambda ^\top}({\bf{Ax}} - {\bf{b}}) - {\eta ^\top}{\bf{x}}\\
= \mathop {\min }\limits_{{\bf{x}} \in X} {({\bf{c}} + {{\bf{A}}^\top}\lambda - \eta )^\top}{\bf{x}} - {\lambda ^\top}{\bf{b}}\\
= \left\{ {\begin{array}{*{20}{c}}
{ - {\lambda ^\top}{\bf{b}}}\\
{ - \infty }
\end{array}} \right.{\hspace{0.5cm}}\begin{array}{*{20}{c}}
{{\bf{c}} + {{\bf{A}}^\top}\lambda - \eta = 0}\\
{{\rm{otherwise }}}
\end{array}
\end{array}$
The dual problem is
\begin{align*}
\begin{array}{ll}
\max & -{\lambda ^\top}{\bf{b}} \\
\text{s.t.} & {\bf{c}} + {{\bf{A}}^\top}\lambda - \eta = 0\,\\
& \lambda \ge 0,\eta \ge 0
\end{array}
\end{align*}

Or

\begin{align*}
\begin{array}{ll}
\max & - {\lambda ^\top}{\bf{b}} \\
\text{s.t.} & {\bf{c}} + {{\bf{A}}^\top}\lambda \ge 0\,\\
& \lambda \ge 0
\end{array}
\end{align*}

</details>

Question 5
----------

Write a code to find the orthogonal projection of $(-1, 1, 0.3)$ onto $\Delta_n$.

<details>
<summary>Solution</summary>

import numpy as np
from scipy.optimize import minimize

def projection_to_simplex(x):
    # Projection function for the unit simplex
    n = len(x)
    bounds = [(0, None) for _ in range(n)]
    constraint = {'type': 'eq', 'fun': lambda x: np.sum(x) - 1}
    result = minimize(lambda x: np.linalg.norm(x - given_point)**2, x, method='SLSQP', bounds=bounds, constraints=constraint)
    return result.x

# Given point
given_point = np.array([-1, 1, 0.3])

# Perform orthogonal projection to the unit simplex
projected_point = projection_to_simplex(given_point)

print("Given Point:", given_point)
print("Projected Point onto Unit Simplex:", projected_point)

import numpy as np
from scipy.optimize import bisect

# Define the h(lambda) function
h_lambda = lambda lam, y: np.sum(np.maximum(0, y - lam)) - 1

def find_root(y):
    # Determine the interval for lambda
    y_min = np.min(y)
    y_max = np.max(y)
    interval_start = y_min - 2/n
    interval_end = y_max
    
    # Use the bisection method to find the root
    root = bisect(lambda lam: h_lambda(lam, y), interval_start, interval_end)
    
    return root

def max_vector(y, root):
    return np.maximum(0, y - root)

def projection_to_simplex(y):
    root = find_root(y)
    return np.maximum(0, y - root)

n = 3
y = np.array([-1, 1, 0.3])

print("Projection of ", y," to the unit simplex is:", projection_to_simplex(y))

</details>

Question 6
----------

Find a dual problem to the problem
\begin{align*}%\label{primal}\tag{Primal}
\begin{aligned}
f^{*}:=\min\; & x_1-4x_2+x_3^4 \\
\text { s.t. } \quad & x_1+x_2+x_3^2\leq 2 \\
& x_1\geq 0\\
& x_2\geq 0.
\end{aligned}
\end{align*}
Solve the dual and primal problems.

<details>
<summary>Solution</summary>

Observe that this is a convex optimization problem. The feasible region has at least one interior point $(\frac{1}{2},\frac{1}{2},\frac{1}{2})^\top$. The Slater's condition is satisfied.

Taking $X=\{\bf{x}\in \mathbb{R}^3:x_1\geq 0,x_2\geq 0\}$.

The Lagrangian is
$\begin{array}{c}
L({\mathbf{x}},\lambda) = x_1-4x_2+x_3^4 + \lambda(x_1+x_2+x_3^2-2)\\
q(\lambda) = \mathop {\min }\limits_{{\bf{x}} \in X} x_1-4x_2+x_3^4 + \lambda(x_1+x_2+x_3^2-2)\\
= \mathop {\min }\limits_{{\bf{x}} \in X} (1+\lambda)x_1+(\lambda-4)x_2+x_3^2(x_3^2+\lambda)-2\lambda\\
= \left\{ {\begin{array}{*{20}{c}}
{-2\lambda}\\
{ - \infty }
\end{array}} \right.{\hspace{0.5cm}}\begin{array}{*{20}{c}}
{{\lambda-4\geq 0 \text{ and } \lambda+1\geq 0}}\\
{{\rm{otherwise}}}
\end{array}
\end{array}$

The dual problem is
\begin{align*}%
\max\; & -2\lambda \\
\text { s.t. } &\quad \lambda \geq 4.
\end{align*}

It is easy to see that the dual has optimal at $\lambda^*=4$ with $q^*=-8$. Since strong duality holds, the primal also has optimal value $f^*=-8$.

By complementary slackness, $x_1+x_2+x_3^2=2$. It follows that $x^*=(0,2,0)^\top$.

</details>

Question 7
----------

Consider the optimization problem
\begin{align*}%
\min\; &\sum_{j=1}^n \frac{c_j}{x_j} \\
\text { s.t. } \quad & \bf{a}^{\top} \bf{x} \leq b \\
&\bf{x}\geq 0.
\end{align*}
where $\bf{a} , \bf{c} \in \mathbb{R}^n_{++}$ and $b \in \mathbb{R}_{++}$.

a) Find a dual problem with a single dual decision variable.
b) Solve the dual and primal problems.

<details>
<summary>Solution</summary>

The objective function is a sum of convex functions and is hence convex. The constraints form a convex set $S$ and ${\bf{0}} \in S$. The Slater’s condition is satisfied. KKT condition is necessary and sufficient for the optimal solution.

$L({\bf{x}},\lambda ) = \sum\limits_{i = 1}^n {\frac{{{c_i}}}{{{x_i}}} + {\lambda _0}({{\bf{a}}^T}{\bf{x}} - b)} - {\lambda ^T}{\bf{x}}$
$\begin{array}{l}
{\nabla _{{x_i}}}L({\bf{x}},\lambda ) = - \frac{{{c_i}}}{{x_i^2}} + {\lambda _0}{a_i} - {\lambda _i}\\
{\lambda _0}({{\bf{a}}^T}{\bf{x}} - b) = 0\\
{\lambda _i}{x_i} = 0
\end{array}$
Since ${x_i}$ cannot be 0, therefore all ${\lambda _i} = 0$.
If ${\lambda _0} \ne 0$, then ${{\bf{a}}^T}{\bf{x}} - b = 0$

From $-\frac{{{c_i}}}{{x_i^2}} + {\lambda _0}{a_i} = 0 \Rightarrow {x_i} = \sqrt {\frac{{{c_i}}}{{{\lambda _0}{a_i}}}}$
$\sum\limits_{i = 1}^n {{a_i}\sqrt {\frac{{{c_i}}}{{{\lambda _0}{a_i}}}} } = b \Rightarrow \sum\limits_{i = 1}^n {\sqrt {\frac{{{a_i}{c_i}}}{{{\lambda _0}}}} } = b \Rightarrow \sqrt {{\lambda _0}} = \frac{{\sum\limits_{i = 1}^n {\sqrt {{a_i}{c_i}} } }}{b}$

The optimal is achieved at ${{\bf{x}}^*}$ with $$x_i^* = \frac{b}{{\sum\limits_{k = 1}^n {\sqrt {{a_k}{c_k}} } }}\sqrt {\frac{{{c_i}}}{{{a_i}}}}$$

</details>