MATP6640/ISYE6770 Linear Programming, Homework 2.

Solutions

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
where c ∈ ℝ

^{n}, b ∈ ℝ^{m}, and A ∈ ℝ^{m×n}.Solution: In a nondegenerate dual optimal solution , we can write A = [B,N] where B is a basis matrix of ℝ

^{m}with = B^{-T}c_{B}and N^{T}< c^{N}. From complementary slackness, any primal optimal solution must satisfy x_{N}= 0. Thus, x_{B}= B^{-1}b in any primal optimal solution, so the primal problem has a unique optimal solution. - 2.
- Let A be an m × n matrix and let b be a vector in ℝ
^{m}. We consider the problem of minimizing ||Ax - b||_{∞}:= max_{i=1,…,m}{|(Ax - b)_{i}|} over all x ∈ ℝ^{n}. Let v be the value of the optimal cost.- (a)
- Let y ∈ ℝ
^{m}satisfy ∑_{i=1}^{m}|y_{i}|≤ 1 and A^{T}y = 0. Show that b^{T}y ≤ v without using Question 3. - (b)
- Reformulate the problem as a linear program and show that an optimal solution exists.

Solutions:

- (a)
- We have
as required.

- (b)
- The minmax problem is equivalent to the following LP:
where e ∈ ℝ

^{m}denotes the vector of ones. This problem is feasible. For example, we can take x = 0 and u = ||b||_{∞}. Also, the constraints force u ≥ 0, so the problem has a finite optimal value. Therefore, by strong duality it has an optimal solution.

- 3.
- In the setting of Question 2, use LP duality to show that the optimal value of the following problem is
v:
Solution:

The LP in the solution to Question 2 can be written equivalently as

The dual problem to this LP is

(1) By strong duality, the optimal value of this LP is v. By setting y = z - w, the dual LP is equivalent to the problem given in the question.

Note that if A has rank m then the problem in Question 2 has optimal value 0, since there exists an x with Ax = b. In this case, the only feasible solution to A

^{T}y = 0 is y = 0, so we cannot impose the restriction that ∑_{i=1}^{m}|y_{i}| = 1. - 4.
- Define the Lagrangian
Show that

if and only if x

^{*}and y^{*}are optimal solutions to the primal-dual pair from Question 1.Solution:

- Assume x
^{*}and y^{*}are optimal:Note that

from feasibility of x

^{*}and from strong duality. For any x ≥ 0 and any y, we have - Assume the inequalities hold:
Then

for all y ∈ ℝ

^{m}, so b - Ax^{*}= 0. (Otherwise, we can choose y = y^{*}+ (b - Ax^{*}).) So x^{*}is primal feasible.Also,

- (a)
- c - A
^{T}y^{*}≥ 0: otherwise we can chooseso y

^{*}is dual feasible, and - (b)
- the inequality holds when x = 0, so (x
^{*})^{T}(c - A^{T}y^{*}) ≤ 0, so complementary slackness holds.

Thus, x

^{*}and y^{*}are optimal.

- Assume x
- 5.
- Consider the linear programming problem
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.)Solution:

We have the initial basis matrix

Pivoting on the top left entry in B can be represented as the matrix product L

^{1}B = U^{1}as below:so we have

First calculate the dual solution y = B

^{-T}c_{b}, which requires first solving U^{T}z = c_{B}and then calculating y = L^{T}z. We haveand then

The reduced costs are then

so x

_{5}enters the basis. We need to calculate d, the x_{5}column of B^{-1}N. This requires calculating q = La^{5}and then solving Ud = q. We getand then

The minimum ratio test gives

so x

_{3}leaves the basis and x_{5}enters the basis with a value of 1. The old basic variables are updated as x_{B}- Δd so the new bfs iswith value 3 + Δ

_{2}= 0.Second iteration:

We need to calculate the updated reduced costs, so we first need to calculate the updated dual variables. The elementary matrix E

^{1}can be constructed using d and then we solve (E^{1})^{T}w = c_{B}followed by solving U^{T}z = w and calculating y = L^{T}z. To find w, we solveWe then solve to get z:

and then

The reduced costs are then

so x

_{1}enters the basis. We need to calculate d, the x_{1}column of B^{-1}N. This requires calculating q = La^{1}, then solving Up = q, and then solving E^{1}d = p. We getand then

and then

Since d ≤ 0, we have an unbounded problem. The ray consists of the negative of this d, plus a component of 1 for the incoming variable, so the ray is

It can be checked that Ar = 0 and c

^{T}r =_{1}= -4. - 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.
Solution:

The dual to the LP in Question 5 is

The ray r from Question 5 suggests taking the sum of r

_{i}multiplied by the ith dual constraint. This gives the following constraint on y:which clearly cannot be satisfied. Hence the dual problem is infeasible.

- 7.
- Use AMPL or another linear programming package to solve the standard form linear programming
problem
(See the course webpage for more information on AMPL. The software is available on LMS.)

Solution: Here are the model file, data file, and output file.

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj |