Basic, Intermediate and CAS problems

The following is the list of non-advanced problems for Chapter 3 of the class notes. There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

1. Use a projection method to find the global minimum of the function \( f(x,y,z)=x^2+2y^2+3z^2 \) over the plane \( x+y+z=1. \)

2. Use a projection method to find the global minimum of the function \( f(x,y,z,t)=x^2+2y^2+2z^2+t^2 \) over the plane

   $$S = \{ (x,y,z,t) \in \mathbb{R}^4 : x+y+z=t, x+y=4 \}$$

3. Solve the following linear program by the simplex method:

   $$(LP): \begin{cases} \displaystyle{\max_{(x,y,z) \in \mathbb{R}^3} \big( 4x+y-z \big)} \\ x+3z \leq 6 \\ 3x+y+3z \leq 9 \\ x \geq 0, y\geq 0, z\geq 0 \end{cases}$$

4. The following tableaux were obtained in the course of solving linear programs with two non-negative variables \( x_1 \) and \( x_2 \), two inequality constraints for which slack or surplus variables \( x_3 \) and \( x_4 \) were needed. In each case, indicate whether the corresponding linear program has a unique optimum solution, has several optimum solutions (and in that case find them all), it is unbounded, or degenerate.

   • $$\begin{bmatrix} 1 & 0 & 3 & 2 & 0 & 20 \\ 0 & 1 & -2 & -1 & 0 & 4 \\ 0 & 0 & -1 & 0 & 1 & 2 \\ \hline z & x_1 & x_2 & x_3 & x_4 \end{bmatrix}$$
   • $$\begin{bmatrix} 1 & 0 & -1 & 0 & 2 & 20 \\ 0 & 0 & 0 & 1 & -2 & 5 \\ 0 & 1 & -2 & 0 & 3 & 6 \\ \hline z & x_1 & x_2 & x_3 & x_4 \end{bmatrix}$$
   • $$\begin{bmatrix} 1 & 2 & 0 & 0 & 1 & 8 \\ 0 & 3 & 1 & 0 & -2 & 4 \\ 0 & -2 & 0 & 1 & 1 & 0 \\ \hline z & x_1 & x_2 & x_3 & x_4 \end{bmatrix}$$
   • $$\begin{bmatrix} 1 & 0 & 0 & 2 & 0 & 5 \\ 0 & 0 & -1 & 1 & 1 & 4 \\ 0 & 1 & 1 & -1 & 0 & 4 \\ \hline z & x_1 & x_2 & x_3 & x_4 \end{bmatrix}$$

5. Consider the following linear program

   $$(LP): \begin{cases} \displaystyle{\max_{(x,y,z) \in \mathbb{R}^3} \big( 5x+3y+z \big)} \\ x+y+z \leq 6 \\ 5x+3y+6z \leq 15 \\ x \geq 0, y \geq 0, z \geq 0 \end{cases}$$

   Assume the following is an associated tableau:

   $$\begin{bmatrix} 1 & 0 & 0 & 5 & 0 & 1 & 15 \\ 0 & 0 & 0.4 & -0.2 & 1 & -0.2 & 3 \\ 0 & 1 & 0.6 & 1.2 & 0 & 0.2 & 3 \\ \hline z & x_1 & x_2 & x_3 & x_4 & x_5 \end{bmatrix}$$
   • What basic solution does this tableau represent? Is this solution optimal? Explain why or why not.
   • Does this tableau represent a unique optimal solution? If not, find at least three alternative optimal solutions.

6. In a computer language or CAS of your choice, design a routine that gathers the following as input:

   • A \( d \)-dimensional vector \( \boldsymbol{c}=[c_1, \dotsc, c_d] \) representing a linear function \( f(\boldsymbol{x}) = \langle \boldsymbol{c}, \boldsymbol{x} \rangle.\)
   • A matrix \( \boldsymbol{A} \) with dimension \( \ell \times d \), and an \( \ell \)-dimensional vector \( \boldsymbol{b} = [b_1, \dotsc, b_\ell] \). These two objects represent \( \ell \) linear inequality constraints of the form \( \boldsymbol{A}{\boldsymbol{x}^\intercal}\leq{\boldsymbol{b}^\intercal}. \)

   The routine attempts to find a solution to the following linear program:

   $$(LP): \begin{cases} \displaystyle{\min_{\boldsymbol{x} \in S} \langle \boldsymbol{c}, \boldsymbol{x} \rangle} \\ S = \{ \boldsymbol{x} \in \mathbb{R}^d : \boldsymbol{A}{\boldsymbol{x}^\intercal}\leq{\boldsymbol{b}^\intercal}, x_k \geq 0, 1 \leq k \leq d \} \end{cases}$$

   If a solution is found, the code outputs it. If the program is unbounded, the code indicates so.

7. Use the Frank-Wolfe method to find the minimum value of the function \( f(x,y)=(x-1)^2+(y+5)^2 \) over the square with vertices at \( (2,2) \), \( (3,3) \), \( (4,2) \) and \( (3,1) \). Use the center of the square as initial guess. Illustrate graphically each step of the method.