MATP6640/ISYE6770 Linear Programming, Homework 2.

Due: 11.59pm on Friday, February 4, 2022 on LMS.
10% penalty for each day late.

1.
Prove that if (D) has a nondegenerate optimal solution then (P) has a unique optimal solution for the primal-dual pair
min   n   cTx                   max   m    bT y
subjxe∈cℝt to  Ax  =  b    (P)      subyje∈cℝt to AT y  ≤  c      (D )
            x  ≥  0                          y     free

where c n, b m, and A m×n.

2.
Let A be an m × n matrix and let b be a vector in m. We consider the problem of minimizing ||Ax - b|| := maxi=1,,m{|(Ax - b)i|} over all x n. Let v be the value of the optimal cost.
(a)
Let y m satisfy i=1m|yi|≤ 1 and ATy = 0. Show that bTy v without using Question 3.
(b)
Reformulate the problem as a linear program and show that an optimal solution exists.
3.
In the setting of Question 2, use LP duality to show that the optimal value of the following problem is v:
max            bTy
subject to  ∑   AT y  =  0
            mi=1|yi|  ≤  1.

4.
Define the Lagrangian
          T    T
L (x,y) := c x +y (b - Ax).

Show that

L(x*,y) ≤ L(x*,y*) ≤ L(x,y*) ∀x ≥ 0,∀y ∈ ℝm

if and only if x* and y* are optimal solutions to the primal-dual pair from Question 1.

5.
Consider the linear programming problem
min   4x1  +  x2          +  x4  -  5x5
s.t.   2x1  +  x2          +  x4  -  2x5  =  3
      - x1 +  x2  +   x3                 =  3
       x1                 +  x4  -   x5  =  1
                      xi  ≥  0,       i  =  1,...,5.

Show that this problem has unbounded objective function value by using the revised simplex algorithm starting from the basic feasible solution x = [0,2,1,1,0]T. Use the eta factorization of the inverse, so you should first factorize the initial basis B as LB = U, where L is lower triangular and U is upper triangular. On subsequent iterations, update the basis matrix by using eta matrices. What is the ray that you find? (Hint: you should find the ray on the second iteration.)

6.
The dual to the linear program in Question 5 is infeasible. Taking nonnegative linear combinations of the dual constraints gives further valid dual constraints. Show how the ray you found for the linear programming problem in Question 5 can be used to construct a linear combination of the dual constraints that is clearly infeasible.
7.
Use AMPL or another linear programming package to solve the standard form linear programming problem
minx∈ℝ5  x1  +  3x2  +  x3         -   4x5
s.t.      x1          +  x3         -   2x5  =  10
             -  3x2  +  x3  +   x4 +   2x5  =  7
         x1  +   x2                -   3x5  =  6
                                        xj  ≥  0,j = 1,...,5

(See the course webpage for more information on AMPL. The software is available on LMS.)

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj