Optimization Theory (DS2) HW#2
Certificates, Standard Equality Form and Simplex Iteration

Problems and page numbers from the paperback edition of A Gentle Introduction to Optimization, by B. Guenin et al.

1. (Problem 1 in Sec. 2.1 of the text, p. 50.)

   1. Prove that the following LP problem is infeasible:

      $max\{3x_1+4x_2+6x_3\}$

      (1)

      subject to

      	$3x_1+5x_2-6x_3$	$=4$		(2)
      	$x_1+3x_2-4x_3$	$=2$		(3)
      	$-x_1+x_2-x_3$	$=-1$		(4)
      	$x_1,x_2,x_3$	$\ge 0.$		(5)

   2. Prove that the following LP problem is unbounded:

      $max\{-x_3+x_4\}$

      (6)

      subject to

      	$x_1+x_3-x_4=1$		(7)
      	$x_2+2x_3-x_4=2$		(8)
      	$x_1,x_2,x_3,x_4\ge 0.$		(9)

   3. Optional: Prove that the LP Problem

      $$max\{{\overrightarrow{c}}^{⊺}\overrightarrow{x}:A\overrightarrow{x}=\overrightarrow{b},\overrightarrow{x}\ge \overrightarrow{0}\}$$

      (10)

      is unbounded, where

      (11)

      $$\overrightarrow{b}=\left(\begin{array}{c}\hfill 11\hfill \\ \hfill -2\hfill \\ \hfill -8\hfill \end{array}\right),$$

      (12)

      $$\overrightarrow{c}=\left(\begin{array}{c}\hfill 1\hfill \\ \hfill -2\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right)$$

      (13)

      Hint: Consider the vectors

      $$\overrightarrow{x}={(1,3,1,0,0)}^{⊺}\text{ and }\overrightarrow{d}={(1,1,1,1)}^{⊺}$$

      (14)

   4. Optional: For each of the problems in parts (b) and (c), give a feasible solution having object value exactly 5000.

2. (Problem 1 in Sec. 2.2 of the text, p. 54.)

   1. Convert the following LPs into SEF:

      $$min\{(2,-1,4,2,4){(x_1,x_2,x_3,x_4,x_5)}^{⊺}\}$$

      (15)

      subject to

      (16)

      $$x_1,x_2,x_4\ge 0.$$

      (17)

      (Careful, note that not all of the $x_i$ have a non-negativity constraint.)

   2. Optional: Let $A,B,D$ be matrices and $\overrightarrow{b},\overrightarrow{c},\overrightarrow{d},\overrightarrow{f}$ vectors (all of suitable dimensions). Convert the following LP with variables $\overrightarrow{x}$ and $\overrightarrow{y}$ (where $\overrightarrow{x}$, $\overrightarrow{y}$ are vectors) into SEF:

      $$min\{{\overrightarrow{c}}^{⊺}\overrightarrow{x}+{\overrightarrow{d}}^{⊺}\overrightarrow{y}\}$$

      (18)

      subject to

      	$A\overrightarrow{x}$	$\ge \overrightarrow{b}$		(19)
      	$B\overrightarrow{x}+D\overrightarrow{y}$	$=\overrightarrow{f}$		(20)
      	$\overrightarrow{x}$	$\ge \overrightarrow{0}.$		(21)

3. (Problem 1 in Sec. 2.3 of the text, p. 56.)
   In this exercise, you are asked to repeat the argument in Section 2.3 with different examples.

   1. Consider the following LP:

      $$max\{(-1,0,0,2)\overrightarrow{x}\}$$

      (22)

      Subject to

      		$=\left(\begin{array}{c}\hfill 2\hfill \\ \hfill 3\hfill \end{array}\right)$		(23)
      	$\overrightarrow{x}$	$\ge \overrightarrow{0}.$		(24)

      Observe that $\overrightarrow{x}={(0,2,3,0)}^{⊺}$ is a feasible solution. Starting from $\overrightarrow{x}$, construct a feasible solution $\overrightarrow{x^{\prime }}$ with value larger than that of $\overrightarrow{x}$ by increasing as much as possible the value of exactly one of $x_1$ or $x_4$ (keeping the other variable unchanged).

   2. Consider the following LP:

      $$max\{(0,0,4,-6)\overrightarrow{x}\}$$

      (25)

      subject to

      		$=\left(\begin{array}{c}\hfill 2\hfill \\ \hfill 1\hfill \end{array}\right)$		(26)
      	$\overrightarrow{x}$	$\ge \overrightarrow{0}.$		(27)

      Observe that $\overrightarrow{x}={(2,1,0,0)}^{⊺}$ is a feasible solution. Starting from $\overrightarrow{x}$, construct a feasible solution $\overrightarrow{x^{\prime }}$ with value larger than that of $\overrightarrow{x}$ by increasing as much as possible the value of exactly one of $x_1$ or $x_4$ (keeping the other variable unchanged).