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

lowing questions.

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

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

maximize  5x_{1} − x_{2} + 11x_{3}
subject to \begin{aligned}x_{1} & − & x_{2} & + & 2x_{3} & ≤ & 3 \\ −2x_{1} & + & x_{2} & − & 2x_{3} & ≤ & 8 \end{aligned} ; −2 ≤ x_{1} ≤ 3, −1 ≤ x_{2} ≤ 1, x_{3} ≤ 0

2. Consider

minimize  c^{T} x
subject to A_{i}x ≥ b_{i} i = 1,…, m

(1)

Let x^{1} be optimal for

minimize  c^{T} x
subject to A_{i}x ≥ b_{i} i = 2,…, m

and x^{2} be optimal for

minimize  c^{T} x
subject to \begin{matrix}A_{1}x = b_{1} \\ A_{i}x ≥ b_{i} & i = 2,…, m \end{matrix}

(a) Prove that (1) is solvable.

(b) Give an upper and a lower bound for the minimum value of (1).

(c) Prove that one of x^{1} or x^{2} solves (1).

3. Let

θ(b) := min{f(x) | g(x) ≤ b}  (2)

where f: IR^{n} ↦ IR, g: IR^{n} ↦ IR^{m} are convex functions on IR^{n} and b ∈ IR^{m}. Suppose that for each b in some set B in IR^{m}, the minimization problem of (2) is solvable. Suppose now that an optimal Lagrange multiplier u(b̄) ∈ IR_{+}^{m} exists for some fixed b̄ ∈ B, such that in addition to satisfying the Kuhn-Tucker saddlepoint conditions, u(b̄) also satisfies

u(b̄)(b̄ − b) ≥ 0 ∀b ∈ B

What can you say about θ(b̄) relative to θ(b) for all b ∈ B? Prove your claim.

4. Suppose that for some real number γ > 0, x(γ) > 0 solves the interior penalty problem

min {f(x) − γ ∑_{j=1}^{n} log x_{j} | Ax = b}

where f: IR^{n} ↦ IR, A is an mxn real matrix, b is an mx1 real vector and f is convex and differentiable on IR^{n}. Give a lower bound to

inf {f(x) | Ax = b, x ≥ 0}

in terms of f(x(γ)), γ and n. Establish your claim.

5. Suppose the problem

minimize  f(x)
subject to h(x) = 0

(3)

(where f: IR^{n} ↦ IR and h: IR^{n} ↦ IR^{m} are continuous functions) has a solution x^{∗}. Let M be an optimistic estimate of f(x^{∗}), that is, M ≤ f(x^{∗}). Consider the unconstrained problem

minimize_{x} v(M, x) := [f(x) − M]^{2} + ∥h(x)∥^{2}  (4)

Consider the following algorithm. Given M_{k} ≤ f(x^{∗}), a solution x_{k} to problem (4) with M = M_{k} is found, then M_{k} is updated by

M_{k+1} = M_{k} + [v(M_{k}, x_{k})]^{1/2}  (5)

and the process repeated.

(a) Show that if M = f(x^{∗}), a solution of (4) is a solution of (3).

(b) Show that if x_{M} is a solution of (4), then f(x_{M}) ≤ f(x^{∗}).

(c) Show that if M_{k} ≤ f(x^{∗}) then M_{k+1} determined by (5) satisfies M_{k+1} ≤ f(x^{∗}).

(d) Show that M_{k} ⟶ f(x^{∗}).

6. Let f be a semipositive vector in IR^{n} (that is, each component of f is non-negative, and f ≠ 0), and define a function ϕ from IR^{n} to the extended reals by

ϕ(x) = inf { α | x ≤ αf }.

(a) Show that ϕ is a closed proper convex function.

(b) Compute the conjugate function ϕ^{∗} and show that ϕ^{∗} is the indicator of a certain polyhedral convex set S. Exhibit S explicitly.

(c) Explain what the support function of a set is. Prove that ϕ is a support function, and identify the set of which it is the support function.

(d) Give a condition on f (only) to ensure that the effective domain of ϕ^{∗} is compact. Justify your condition.

7. Let

minimize_{x}  cx
subject to \begin{matrix}Ax = b \\ x ≥ 0 \end{matrix}

be a min cost network flow problem

(a) State the corresponding “big M” problem, being precise about how M is obtained from the data of the original problem.

(b) Show that if the big M problem is unbounded, then the original problem is either unbounded or infeasible.

(c) What additional procedure may be performed to identify which of the alternatives in (b) holds?

8. Write an integer program equivalent to

maximize  z = 3x_{1} + 4x_{2} − 3x_{3}
subject to \begin{aligned}x_{1} & + & x_{2} & + & 4x_{3} & ≤ & 60 \\ −x_{1} & + & 2x_{2} & + & x_{3} & ≥ & 12 \end{aligned} ; if x_{2} + x_{3} > 0 then x_{1} + x_{3} ≤ 54 ; (x_{1}, x_{2}, x_{3}) ≥ 0