<jupyter_start><jupyter_text>ORF307 Homework 6 {-}Due: Friday, April 2, 2021 9:00 pm ET- Please export your code with output as pdf.- If there is any additional answers, please combine them as **ONE** pdf file before submitting to the Gradescope.  Q1 {-} Let $A$ be a given matrix. Show that exactly one of the following alternatives must hold.(a) There exists some $x \neq 0$ such that $Ax=0, x\ge0$.(b) There exists some $y$ such that $A^T y > 0$.  Q2 {-} Consider an LP problem of the form$$\begin{array}{ll}\mbox{minimize} &c^T x\\\text{subject to} &Ax \ge -c\\&x \ge 0\end{array}$$where $A$ satisfies $A^T = -A$. Prove that this problem has an optimal solution if it is feasible.  Q3 {-} An alternative to the phase-I/phase-II method for solving the LP$$\label{eq:LP}\tag{1}\begin{array}{ll}\mbox{minimize} &c^Tx\\\text{subject to} &Ax = b,\\& x \ge 0\end{array}$$is the "big-M"-method, in which we solve the auxiliary problem$$\label{eq:aux}\tag{2}\begin{array}{ll}\mbox{minimize} &c^Tx + M\mathbf{1}^Tz\\\text{subject to} &Ax + z = b\\&x \ge 0, z \ge 0,\end{array}$$where $M > 0$ is a parameter and $z \in \mathbf{R}^m$ is an auxiliary variable. Here, $A \in \mathbf{R}^{m \times n}, c \in \mathbf{R}^{n}$, and $b \in \mathbf{R}^{m}$. Note that this auxiliary problem has an initial basic feasible solution $(x, z) = (0, b) \ge 0$.(a) Derive the dual LP of \eqref{eq:aux}.(b) Prove the following property:If $M > -y_i^\star$ for $i=1,\dots,m$, where $y^\star$ is an optimal solution of the dual of \eqref{eq:LP}, then the optimal $z$ in \eqref{eq:aux} is zero, and therefore the optimal $x$ in \eqref{eq:aux} is also an optimal solution of \eqref{eq:LP}  Q4 {-} Consider the following LP:$$\begin{array}{ll}\label{eq:q4}\tag{3}\mbox{minimize} &13x_1 + 10x_2 + 6x_3\\\text{subject to} &5x_1 + x_2 + 3x_3 = 8\\& 3x_1 + x_2 = 3\\& x_1, x_2, x_3 \ge 0.\end{array}$$(a) Solve it using the big-M formulation as in Q3 obtaining optimal primal and dual variables (use the provided function).(b) Derive the dual LP for \eqref{eq:q4}(c) Solve the dual using CVXPY and compare the optimal primal-dual variables with the ones from (a).<jupyter_code>'''
This code is provided to help with question 4.
This code returns optimal primal variables x 
and dual variables y.
'''
import cvxpy as cp
import numpy as np
import numpy.linalg as la

def simplex_iteration(x, B, problem):
    """Perform one simplex iteration given 
    - basic feasible solution x
    - basis B
    
    It returns new x, new basis, new dual variable,
    and termination flag (true/false)
    """
    A, b, c = problem['A'], problem['b'], problem['c']
    m, n = A.shape
    A_B = A[:, B]
    
    # Compute reduced cost vector
    p = la.solve(A_B.T, c[B])
    c_bar = c - A.T @ p
    
    # Check optimality
    if np.all(c_bar >= 0):
        print("Optimal solution found!")
        return x, B, -p, True

    # Choose j such that c_bar < 0 (first one)
    j = np.where(c_bar < 0)[0][0]
    
    # Compute search direction d
    d = np.zeros(n)
    d[j] = 1
    d[B] = la.solve(A_B, -A[:, j])
    
    # Check for unboundedness
    if np.all(d >= 0):
        print("Unbounded problem!")
        return None, None, True
        
    # Compute step length theta
    d_i = np.where(d[B] < 0)[0]
    theta = np.min(- x[B[d_i]] / d[B[d_i]])
    i = B[d_i[np.argmin(- x[B[d_i]] / d[B[d_i]])]]
    
    # Compute next point
    x_next = x + theta * d
    
    # Compute next basis
    B_next = B
    B_next[np.where(B == i)[0]] = j
  
    return x_next, B_next, -p, False

def simplex_algorithm(x, B, problem, max_iter=1000):
    """Run simplex algorithm"""

    for k in range(max_iter):
            
        x, B, y, end = simplex_iteration(x, B, problem)
        
        if end:
            break
    return x, B, y<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15009183941222776, 'fraction_numerical': 0.018892679086853843, 'mean_word_length': 3.0, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '157629', 'license': 'MIT', 'n_tokens_mistral': 1444, 'n_tokens_neox': 1358, 'n_words': 487, 'path': 'homeworks/06_homework/ORF307_HW6.ipynb', 'repo_name': 'bpushner/ORF307', 'size': '3811'}