MATHEMATICAL PROGRAMMING Instructions for Depth Exam Students: Answer any 6 of the follow-

ing questions.

Instructions for Breadth Exam Students: Answer any 3 of the following questions.

1. Use the simplex method to solve the following problem:

minimize  7 |x| − y + 3z
subject to \begin{aligned}& & y & − & 2z & ≤ & 4 \\ −x & − & y & + & 3z & ≤ & −2 \\ 3x & − & y & + & 3z & ≥ & 0 \\ & y & ≥ & 3, & z & ≤ & 1 \end{aligned}

2. Let X be a convex set in the n–dimensional real space IR^{n} and let f be a differentiable function on IR^{n}.

(a) What can you say about the quantity

∇f(x̄)(x − x̄)

on X if x̄ is a local solution of

minimize_{x∈X} f(x)

(b) Let x̄ ∈ X̄, where X̄ is the solution set of min_{x∈X} f(x), that is

X̄: = arg min_{x∈X} f(x)

If f is convex on IR^{n}, what is the relation between X̄ and the set

Ȳ: = arg min_{x∈X} ∇f(x̄)(x − x̄)

Establish your claim.

3. Consider the problem

minimize  f(x)
subject to g(x) ≤ 0

where f: IR^{n} ↦ IR and g: IR^{n} ↦ IR^{m} are differentiable and convex functions on IR^{n}. Suppose that

x(α) = arg min_{x}{f(x) − α ∑_{j=1}^{n} log(−g_{j}(x)) | g(x) < 0}

for α > 0. What should α satisfy in order that

f(x(α)) − inf_{x}{f(x) | g(x) ≤ 0} ≤ 10^{−6}

Prove your claim.

4. Consider the following problem.

A company must assign n plants to n distinct locations. Each location will be assigned exactly 1 plant. The number of units to be shipped from p to q is d_{pq} ≥ 0, (p, q = 1,…, n). The unit shipping cost from location i to location j is c_{ij} > 0, (i, j = 1,…, n). The plants are to be assigned to locations so as to minimize total shipping cost.

(a) Formulate the problem as a (not necessarily linear) integer program using only the n^{2} variables x_{pi}, where x_{pi} = 1 implies that plant p is assigned to location i.

(b) Formulate the problem as a linear integer program using the variables of part (a) plus any additional variables that you require.

5.

[figure: 3; 2; -4; -1; -10; 2; 1; 1]

(a) Formulate the “big M” problem corresponding to the min cost network problem above, where divergences are shown at the nodes and unit costs are shown on the arcs. Describe how you compute the numerical value of “big M” for this problem. Do one pivot of the network simplex method on the big M problem, indicating the primal and dual values before and after the pivot (start with the “all artificial” solution).

(b) Given the orientation of the arcs in the network above, what conclusion may be drawn regarding the existence of an optimal solution of the corresponding big M problem? Explain your answer.

(c) Given the result of part (b), what additional property (observable from the original data of this problem) relates the big M problem to the original problem? Explain your answer.

6. Let A be an integral matrix of full row rank. Show that all basis submatrices of A are unimodular iff for all integer vectors b

{x ∈ IR^{n} : Ax = b, x ≥ 0} = conv{x ∈ IR^{n} : Ax = b, x ≥ 0, x integer}

Hint: To show that a matrix B is unimodular it suffices to show that B^{−1}t is integer for all vectors t.

7. Consider the linear program:

minimize  ⟨q, z⟩
subject to \begin{matrix}Mz + q ≥ 0 \\ z ≥ 0 \end{matrix}

(1)

where M is a skew-symmetric that is

M = −M^{T} .

Suppose z^{∗} is a solution of (1). Give a solution of the dual of (1) in terms of z^{∗}

8. Let f be a closed proper convex function from IR^{n} to IR. Suppose that for each nonzero y in IR^{n} there exists some positive η such that f(ηy) > f(0).

(a) Prove that the set

L(1) = { x ∈ IR^{n} | f(x) ≤ 1 }

is compact.

(b) Can you draw any conclusion about the compactness of

L(n) = { x ∈ IR^{n} | f(x) ≤ n },

where n is an arbitrarily large natural number? Explain.