---
# System prepended metadata

title: Week 9 - Duality
tags: [Optimization]

---

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>

