Name: |

MATP6640/ISYE6770

Linear Programming

Spring 2014

Midterm Exam, Friday, April 11, 2014.

Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

Q1 | /25 | |

Q2 | /25 | |

Q3 | /25 | |

Q4 | /25 | |

Total | /100 |

Throughout, the standard primal-dual LP pair is

where A is m × n and the vectors are dimensioned appropriately. The rank of the matrix A is m.
The dual slack variables are defined as s := c - A^{T }y.

- (25 points)

The problem (P) iswhere b

_{1}and b_{2}are parameters.- (10 points) There is a nondegenerate basic feasible solution to this problem with
basic variables x
_{2}and x_{4}. Show that = (7, 1) is dual optimal. - (15 points) There are other potential columns for the matrix A, all with cost
c = 11. The corresponding x variables are nonnegative. These additional columns all
satisfy the constraints
Is the basic feasible solution from part (1a) optimal in the full problem?

(this page intentionally left blank)

- (10 points) There is a nondegenerate basic feasible solution to this problem with
basic variables x
- (25 points)

Let x ∈ IR^{n}be the first stage decision variable in a stochastic program with a finite set S of r scenarios, with the uncertainty represented by ξ_{s}, s ∈ S, and with p_{s}equal to the probability of scenario s. We want to minimize the Conditional Value-at-Risk (CVaR) of the second stage decisions, which can be found using the linear program(1) where α is a parameter, Q(x,ξ

_{s}) is the recourse cost for the first stage decision x in scenario s, η is a scalar variable, and v ∈ IR^{r}.Assume 0 < 1 - α < p

_{s}for all s ∈ S.- (15 points) For a fixed x = , show that the optimal choice for v and η is to take
v
_{s}= 0 for all s ∈ S and η = max_{s}{Q(,ξ_{s})}. - (10 points) Hence show that in this case the CVaR problem (1) is equivalent to the
robust optimization problem

(this page intentionally left blank)

- (15 points) For a fixed x = , show that the optimal choice for v and η is to take
v
- (25 points)

Given a feasible > 0 for (P) and a feasible (, ) with > 0 for (D), let = . Let the direction (Δx, Δy, Δz) satisfy the system of equationswhere

and are diagonal matrices with_{ii}=_{i}and_{ii}=_{i}for i = 1,…,n. Let α be a step length and updateShow that x

^{T }s = n . - (25 points.)

Assume there exists a nonzero direction d ∈ IR^{m}with b^{T }d = 0 and A^{T }d ≤ 0.(Hint: You will need to exploit the fact that rank(A) = m in this question. Equivalently, the rows of A are linearly independent.)

- (10 points) Show there does not exist a strictly positive x ∈ IR
^{n}satisfying Ax = b. What relevance does this have to the application of an interior point method for solving (P) and (D)? - (15 points) Show that every primal optimal basic feasible solution is degenerate.

(this page intentionally left blank)

- (10 points) Show there does not exist a strictly positive x ∈ IR