<div align="center">
  <h1>Homework 6</h1>
    <p>
        <div align="center">
        <h2>Yutong Dai yutongd3@illinois.edu</h2>
        </div>
    </p>
</div>

## 6.5
**a)**
$$
\begin{align}
& \min \quad 19 w_1 + 57 w_2\\
& s.t \quad w_1 + 2w_2 \geq 10\\
& \qquad w_1 + 4w_2 \geq 24\\
& \qquad 2w_1 + 3w_2 \geq 20\\
& \qquad 3w_1 + 2w_2 \geq 20\\
& \qquad 5w_1 + 3w_2 \geq 25\\
& \qquad w_1,w_2\geq 0
\end{align}
$$

It's easy to verify $w^*=(w_1^*,w_2^*)=(4, 5)$ is a feasible solution.

**b)** We can treat the dual problem as a primal probelm and the primal problem as it duals. Now we assert that $w^*=(4,5)$ is an optimal solution.
Denote $A$ as the coefficients matrix in **a)**, $b^T=(10,24,20,20,25)$, $c^T=(19,57)$.

By the KKT condition, we want to solve

* ${x{^*}^T}(Aw^* - b) = 0$ $\Rightarrow$ $x_1^*=x_3^*=x_4^*=0$.
* $(c^T - {x^*}^TA)w^* = 0$  $\Rightarrow$ $x_2^*=14, x_5^*=1$.

To summarize, the optimal solution for the primal is $x^*=(0, 14, 0, 0, 1)$ and the optimal solution for the dual is $w^*=(4, 5)$.

## 6.7
**a)**
The dual problem is

$$
\begin{align}
& \min \quad 8 w_1 + 6 w_2\\
& s.t \quad w_1 + w_2 \geq 2\\
& \qquad 2w_1  -2w_2 \geq 3\\
& \qquad 3w_1 + 2w_2 \geq 5\\
& \qquad w_1,w_2\geq 0.
\end{align}
$$


**b)**

* The initial tableau is 

|  | $z$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $z$ | -1 | 2 | 3 | 5 | 0 | 0 | 0 |
| $x_4$ | 0 | 1 | 2 | 3 | 1 | 0 | 8 |
| $x_5$ | 0 | 1 | -2 | 2 | 0 | 1 | 6 |

then the dual variables take value $(0,0)$.  Then the first 3 constraints are violated.

* After the first iteration the tableau is

|  | $z$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $z$ | -1 | 1/3 | -1/3 | 0 | -5/3 | 0 | -40/3 |
| $x_3$ | 0 | 1/3 | 2/3 | 1 | 1/3 | 0 | 8/3 |
| $x_5$ | 0 | 1/3 | -10/3 | 0 | -2/3 | 1 | 2/3 |

then the dual variables take value $(5/3,0)$.  Then the first and second constraints are violated.

* After the second iteration the tableau is

|  | $z$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $z$ | -1 | 0 | 3 | 0 | -1 | -1 | -14 |
| $x_3$ | 0 | 0 | 4 | 1 | 1 | -1 | 2 |
| $x_1$ | 0 | 1 | -10 | 0 | -2 | 3 | 2 |

then the dual variables take value $(1,1)$.  Then the second constraint is violated.

* After the third iteration the tableau is

|  | $z$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $z$ | -1 | 0 | 0 | -3/4 | -7/4 | -1/4 | -31/2 |
| $x_2$ | 0 | 0 | 1 | 1/4 | 1/4 | -1/4 | 1/2 |
| $x_1$ | 0 | 1 | 0 | 5/2 | 1/2 | -1/2 | 7 |

then the dual variables take value $(7/4,1/4)$.  Since we are at the optimality, no constraint is violated.

**c)**

Rewrite the dual problem in standard form.

$$
\begin{align}
& \min \quad 8 w_1 + 6 w_2\\
& s.t \quad w_1 + w_2 -w_3 = 2\\
& \qquad 2w_1  -2w_2-w_4 = 3\\
& \qquad 3w_1 + 2w_2 -w_5 = 5\\
& \qquad w_1,...,w_5\geq 0.
\end{align}
$$

* At the initial stage:
    
    * The basic dual variables are $w_3,w_4,w_5$. Nonbasic  variables are $w_1,w_2$.
    * The dual basis is
    $$
    \begin{bmatrix}
        -1 & 0 & -1 \\
        0 & -1 & 0 \\
        0 & 0 & -1 
    \end{bmatrix}
    $$
 
* After the first iteration:
    
    * The basic dual variables are $w_1,w_3,w_4$. Nonbasic  variables are $w_2,w_5$.
    * The dual basis is
    $$
    \begin{bmatrix}
        1 & -1 & 0 \\
        2 & 0 & -1 \\
        3 & 0 & 0 
    \end{bmatrix}
    $$
  
* After the second iteration:
    
    * The basic dual variables are $w_1,w_2,w_4$. Nonbasic  variables are $w_3,w_5$.
    * The dual basis is
    $$
    \begin{bmatrix}
        1 & 1 & 0 \\
        2 & -2 & -1 \\
        3 & 2 & 0 
    \end{bmatrix}
    $$
  
* After the third iteration:
    
    * The basic dual variables are $w_1,w_2,w_5$. Nonbasic  variables are $w_3,w_4$.
    * The dual basis is
    $$
    \begin{bmatrix}
        1 & 1 & 0 \\
        2 & -2 & 0 \\
        3 & 2 & -1 
    \end{bmatrix}
    $$

**d)** The objective value for the dual problem follows $0 \rightarrow 40/3 \rightarrow 14 \rightarrow 31/2$, hence keeping worsen.

**e)**

The optimal solution for the primal and dual are $(7,1/2,0)$ and $(7/4, 1/4)$.
It's easy to check that 

* Two problems have the same value $31/2$;
* The complementary slackness holding at the optimality.

## 6.8
**a)**

The initial tableau

|  | $z$ | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | RHS |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $z$ | -1 | -6 | 0 | -20 | 0 | 0 | 0 |
| $x_4$ | 0 | 0 | 1 | 4 | 1 | 0 | 10 |
| $x_5$ | 0 | 3 | -1 | 2 | 0 | 1 | 11 |

So the primal problem is


$$
\begin{align}
& \min \quad -6 x_1 - 20 x_3\\
& s.t \quad x_2 + 4x_3 \leq 10\\
& \qquad 3x_1 - x_2 + 2x_3\leq 11\\
& \qquad x_1,x_2,x_3\geq 0.
\end{align}
$$

**b)**
The dual is

$$
\begin{align}
& \max \quad 10w_1 +11 w_2\\
& s.t \quad 3 w_2 \leq -6\\
& \qquad w_1 - w_2 \leq 0\\
& \qquad 4w_1 + 2w_2 \leq -20\\
& \qquad w_1,w_2\leq 0.
\end{align}
$$

**c)** The optimal dual from the tableau is $(-4,-2)$.

## 6.9

**a)** **False**

Consider the primal-dual problem pair,

$$
  \begin{cases}
  & \min\quad x_2 \\ 
  & s.t \quad -x_1 + x_2 \geq 0 \qquad (P) \\
  & \qquad x_2 \geq -1
  \end{cases}
  \qquad\qquad
  \begin{cases}
  & \max\quad -w_2 \\ 
  & s.t \quad -w_1 = 0 \qquad (D)\\
  & s.t \quad w_1 + w_2 = -1 \qquad (D)\\
   & \qquad w_1,w_2 \geq 0\\
  \end{cases}
$$

The solution $(x_1,x_2)=(-3,-2)$ is a basic infeasible solution, which gives objective value $-2$ that is smaller than the optimal value 0.
The dual problem is always infeasible.

**b)** 

The problem can be rewrite as

$$
\begin{align}
& \min \quad x_1\\
& s.t \quad 2x_1 - x_2 -x_3 = 0\\
& \qquad -2x_1 +3x_2 -x_4 = -6\\
& \qquad x_1,x_2,x_3,x_4\geq 0.
\end{align}
$$

The basic feasible solution for primal is $(0,0,0,6)$. Any basis matrix $B$ leads to dual basic solution $c_B^TB^{−1}$, so we have dual solution $(1/2, 0)$.

This pair of solution is optimal with respect to its problem.

~~Since this is a optimal solution,  the complementary dual are the set $\{(w_1,0)|0\leq w_1  \leq \frac{1}{2}\}$.
The BFS in primal is degenerated while the complementary dual is not unique.~~

**c)** **False**. 
Consider

$$
  \begin{cases}
  & \min\quad 2 \\ 
  & s.t \quad x_1=1 \qquad (P) \\
  & \qquad x_1,x_2 \geq 0,
  \end{cases}
  \qquad\qquad
  \begin{cases}
  & \max\quad w_1 \\ 
  & s.t \quad w_1 \leq 2 \qquad (D)
  \end{cases}
$$

The dual has an unique non-degenerated optimal solution.

**d)** It is possible.

Consider the primal-dual problem pair,

$$
  \begin{cases}
  & \min\quad 0 \\ 
  & s.t \quad -x_1 + x_2 \geq 0 \qquad (P) \\
  & \qquad x_2 \geq 1 \\
  & \qquad x_1,x_2 \geq 0,
  \end{cases}
  \qquad\qquad
  \begin{cases}
  & \max\quad w_2 \\ 
  & s.t \quad w_1 \leq 0 \qquad (D)\\
  & s.t \quad w_2 \leq 0 \\
   & \qquad w_1,w_2 \geq 0 \\
  \end{cases}
$$

$(x_1,x_2)=(0,0)$ is an infeasible basic solution. And the pair is $(0,0)-(0,0)$, where shares the same objective value 0.

**e)** **False.** If the primal is unbounded, its dual must be infeasible. But dual feasibility does not depend on $b$.

## 6.23
Denote the i-th row of the constrain matrix $A$ is $a_i$.

$$
\begin{cases}
& \min \quad c^Tx\\
& s.t \quad Ax=b \\
& \qquad x\geq 0
\end{cases}
\qquad
\begin{cases}
& \max \quad b^Tw\\
& s.t \quad A^Tw\leq c\\
\end{cases}
$$


**a)** Since this operation won't change the feasible set of the primal problem, hence the optimal value of the primal and dual respectively. The k-th element of the optimal solution of the dual problem will be divided by $\lambda$.


**b)** Assume that we add $\lambda a_j$ to $a_i$. Since this operation won't change the feasible set of the primal problem, hence the optimal value of the primal and dual respectively. The transformed constrain matrix $A_1=E_{ij}(\lambda)A$ and $b_1=E_{ij}(\lambda)b$, where $E_{ij}(\lambda)$ only differs from the identity matrix in the (i,j) element, whose element is $\lambda$ rather than $0$. To maintain the feasibility and optimality, the optimal solution $\tilde w$of the changed dual problem must satisfy

$${\tilde w}^T E_{ij}(\lambda) A\leq c^T \text { and }b_1^T  \tilde w=b^Tw.$$

Set ${\tilde w}^T E_{ij}(\lambda)=w^T$, we have ${\tilde w}^T = w^TE_{ij}(-\lambda)$. And it achieves the optimality.

To me more specific, $$\tilde w_k=w_k, k \neq i \text{ and } \tilde w_i = w_i - \lambda w_j.$$


**c)**

* If the modification does not change any column in the basis $B$. Then the optimal solution of the primal won't change.

* If the modification does change the  column in the basis $B$, then the optimal solution of the primal will change. Suppose, we add $\lambda A_{[,j]}$ to $\lambda A_{[,i]}$, then 
$\tilde B = B E_{ji}(\lambda).$ Therefore we have

$$
x^{new} = E_{ji}(-\lambda)x^{old}.
$$

We can say nothing about the dual solutions.

## 6.27

**a)** The dual can be written as 

$$
\begin{align}
& \max \quad l\\
& s.t \quad w_1 + w_2 = 1\\
& \qquad l - 2w_1 + 3w_2 \leq 0\\
& \qquad l + w_1 - 2w_2 \leq 0\\
& \qquad l - w_2 \leq 0\\
& \qquad w_1, w_2 \geq 0\\
& \qquad l \text{ is free}
\end{align}
$$

**b)** The iterpretation is as follow.

$w_1, w_2$ are the probabilities that the row player will select corresponding strategy. Then the problme is to maximum the minimal extepect  payoff to the row player.

**c)** This problem can be coverted to 

$$
\max_{w_2 \in [0, 1]} \min \{2-5w_2, 3w_2 -1, w_2 \}.
$$

So the optimal solution is $(l, w_1,w_2)= (1/8, 5/8, 3/8)$.

**d)**
By the complementary slackness condition and strong duality, we have


$$(z,x_1,x_2,x_3)= (1/8, 3/8, 5/8, 0)$$

**e)** For both row and column player they put a larger weight (5/8) on the strategy that they will earn on expectation and smaller weight on the strategy that will lead to lose. Moever, the column palyer place a zero weight on the strategy will lose anyway.

## 6.35

**a)**

$\Rightarrow$: suppose $x_j=0$ for all optimal primal solutions. 

Then the proof is same as the one given in the Exercise 4.20 **c)**. Please refer to it, which appears in the following. 

$\Leftarrow$: suppose a complementary dual variable is positive for some optimal dual solutions. 

Since the complementary slackness conditions hold for all primal and dual optimal solutions. Since for some $x_j$ is positive in the optimal dual, then its complementary primal variable has to be positive.

**b)**

If $x_j$ is unbounded, then Columns $A_j\leq 0$, then since $w\geq 0$, we have $w^T A_j\leq 0$. $w_{j+m}= c_j - w^T A_j$ is $x_j$'s complementary variable. By the dual feasibility, we know $w_{j+m}\geq 0$, and since $w^T A_j\leq 0$, we have $w_{j+m}\leq - w^T A_j$.

The argument cab be reversed if $w_{j+m}$ is bounded.

**c)**
Suppose $x_j$ is unbounded. Since it is optimal, by complementary slackness condition, we have $(c_j - w^T A_j)x_j=0$. As $x_j$ is unbounded, we have $w_{j+m}= c_j - w^T A_j=0$.

Suppose $w_{j+m}= c_j - w^T A_j=0$, then $x_j$ is unbounded.

**d)**


## Exercise 4.5

**a)** **True**.

Since there is no $c_B^TB^{-1}$ is feasible, we know that $x^*$ is not optimal yet. So the optimal cost is strictly smaller than $c^Tx^*$.

**b)** **True**. 

The whole purpose of the auxiliary primal problem is to create a problem that is feasible. Since the optimal cost of the auxiliary primal problem is bounded by 0, so the dual is feasible.

**c)** **True**. 

Eliminate the equality constraint will remove the corresponding dual variable, which is equivalent to set it as 0 in the constraint.

**d)** **True**. 

This is obvious by weak duality theorem.

## Exercise 4.7

**a)** The primal problem can be written as

$$
\begin{align}
& \min \quad z\\
& s.t \quad 1_m^T z -Ax \geq -b\\
& \qquad z,x \text{ is free.}
\end{align}
$$

The corresponding dual is

$$
\begin{align}
& \max \quad (-b)^Tw\\
& s.t \quad 1_m^Tw = 1\\
& \qquad A^Tw = 0_m
\end{align}
$$

By the strong duality theorem, we have $(-b)^Tw^* = v,$ where $w^*$ is the optimal solution for the dual. Hence, for any $w$ satisfy the constraints given in the dual problem, one must have $$-w^Tb \leq v.$$

**b)** By strong duality theorem, we have the optimal cost of the dual is $v$.

## Exercise 4.15

* Dual Problem:

$$
\begin{align}
& \max \quad w\\
& s.t \quad w \leq 1
\end{align}
$$

* The optimal solutions for the primal are $\{(x_1,x_2)|x_1\geq 0, x_2 = 1\}$, which implies that it doesn't have an unique optimal solution. But it has non-degenerate solutions as long as $x_1 >0$.

* The optimal solution for the dual is $w=1$, which implies that it do have an unique optimal solution. Also, it has a non-degenerate solution.

---
1. The primal problem does not have a non-degenerate BFS.

2. The dual problem has a non-degenerate BFS, but the optimal solution for the primal is not unique.

From 1 and 2, we know this is not in agreement with the aforementioned statement.

## Exercise 4.20

**a)**
Denote

$$
\begin{cases}
& \min \quad c^Tx\\
& s.t \quad Ax=b  \qquad (P)\\
& \qquad x\geq 0
\end{cases}
\qquad
\begin{cases}
& \max \quad b^Tw\\
& s.t \quad A^Tw\leq c  \qquad (D)
\end{cases}
$$

$$
\begin{cases}
& \min \quad -x_j\\
& s.t \quad Ax=b  \qquad (P')\\
&\qquad c^Tx \leq d\\
& \qquad x\geq 0
\end{cases}
\qquad
\begin{cases}
& \max \quad b^Tw+dt\\
& s.t \quad A^Tw + tc^T \leq -e_j  \qquad (D')\\
& \qquad t\leq 0
\end{cases}
$$


Suppose $x^*$ is the optimal solution for (P), then it provides an upper bound on (P'). Note that we we have $x\geq 0$ and $x_j^*=0$, we know that the optimal value for (P') is also zero. Therefore, the optimal value for (D') is also 0.

Suppose $(w^*, t^*)$ is an optimal solution for (D') and $w_0$ is an optimal solution for (D).

* $t^*=0$, then we have $$b^Tw^* = 0 , A^Tw^* \leq -e_j.$$ Note that $$b^T(w^* + w_0)=b^Tw_0 \text{ and } A^T(w^*+w_0) \leq c - e_j.$$ We assert that $w^*+w_0$ is another optimal solution for (D). And specifically, we know that $$(w^* + w_0)^TA_j \leq c_j - 1 < c_j.$$

* $t^*<0$, then denote $\bar w = \frac{-w^*}{t^*}$. We have $b^tw^* + dt^*=0$ and $A^Tw^* + t^*c^T \leq - e_j$, which implies $$b^T\bar w = d \text{ and } A^T\bar w + \frac{e_j}{t^*}\leq c^T.$$ So $\bar w$ is an optimal solution for (D). Notice that $$\bar w^T A_j = c_j + \frac{1}{t^*} < c_j.$$

Two bullet points conclude the proof.

**b)**

From **a)**, we know that there exist $w^{(j)}, j\in J=\{j| x_j=0, j=1,2,...,n\}$ s.t $w^{(j)}$  is an optimal solution for (D) and ${w^{(j)}}^TA_j < c_j$. Denote $W^{**}= \frac{1}{|J|}\sum_{j\in J} w^{(j)}$, then we have   ${W^{**}}^TA_j < c_j, j\in J$. 

Furthermore, we have $x_j >0, j \notin J.$

**c)**

i) Consider

$$
\begin{cases}
& \min \quad -x_j\\
& s.t \quad Ax\geq b  \qquad (P')\\
&\qquad -c^Tx \geq -d\\
& \qquad x\geq 0
\end{cases}
\qquad
\begin{cases}
& \max \quad b^Tw+dt\\
& s.t \quad w^TA - tc^T \leq -e_j^T  \qquad (D')\\
& \qquad w, t\geq 0
\end{cases}
$$

And consider for all $j=1,2,...,n$, $x_j=0$ and $x_j>0$ cases. Use the similar arguments in **a)** and **b)**, we concludes the proof.

ii) We can treat the dual problem as the primal and re-write is as 

$$
  \begin{cases}
  & \max\quad b^T w \\ 
  & s.t \quad A^Tw\leq c \qquad (P) \\
  & \qquad w \geq 0,
  \end{cases}
  \qquad\qquad
  \begin{cases}
  & \min\quad x^Tc \\ 
  & s.t \quad x^T A^T\geq b^T \qquad (D) \\
  & \qquad x \geq 0,
  \end{cases}
$$

and use the similar method from i), we conclude the proof.

**d)**

By KKT condition, we know that $(w_1^*,w_2^*)=(5,0)$. And ${w^*}^TA < c^T$

The optimal solutions lie on the segment $\{(x_1,x_2)| 2/3 \leq x_1 \leq 2, x_2 = 2 - x_1\}$ for the primal.
As for the optimal solution for the dual, it is always $(5,0)$.

Pairs that satisfy strictly complementary slackness conditions:

$$(2/3, 4/3) \sim (5, 0) \qquad (2,0) \sim (5,0)$$

## Exercise 4.27
By the strictly complementary slackness condition, **a)** and **b)** are equivalent.

9df2404bbb93a81326a165ca9cf53199ec8bf9a6
ipynb
Jupyter Notebook
Python_IE411/.ipynb_checkpoints/hw6-checkpoint.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
2018-09-23T00:00:13.000Z
2018-11-02T22:56:35.000Z
Python_IE411/.ipynb_checkpoints/hw6-checkpoint.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
Python_IE411/.ipynb_checkpoints/hw6-checkpoint.ipynb
Rothdyt/codes-for-courses
a2dfea516ebc7cabef31a5169533b6da352e7ccb
MIT
Qwen/Qwen-72B
1. YES
2. YES