MATHEMATICAL PROGRAMMING Depth Exam: Answer any 6 of the following 8 questions Breadth Exam: Answer any 3 of the following 8 questions

1. A textile firm is capable of producing 3 products in amounts x_{1}, x_{2}, x_{3} . Its production plan for the next month must satisfy the constraints:

\begin{aligned}x_{1} + 2x_{2} + 2x_{3} & ≤ 12 \\ 2x_{1} + 4x_{2} + x_{3} & ≤ f \\ x_{1} ≥ 0, x_{2} ≥ 0, x_{3} & ≥ 0 \end{aligned}

The first constraint is determined by equipment availability and is fixed. The second constraint is determined by the availability of cotton, with f being the amount of cotton available. The net profits of the products are 2, 3 and 3 per unit respectively, excluding the cost of cotton.

(a) Find the optimal dual variable (shadow price) λ_{2} of the cotton input as a function of f. Plot λ_{2}(f) and the net profit z(f), excluding the cost of cotton.

(b) The firm may purchase cotton on the open market at a price of \frac{1}{6} . However, it may acquire a limited amount s at a price of \frac{1}{12} from a major supplier that it purchases from frequently. Determine the net profit of the firm Π(s) as a function of s.

2. Consider the following linear system:

\begin{aligned}Ax & = b \\ x & ≥ 0 \end{aligned}

where A is an m×n real matrix with rank (A) = m and 0 ≠ b ∈ IR^{m}. Let Ω = {x ∈ IR^{n} : Ax = b, x ≥ 0} ≠ ∅ and for each x let X := diag (x_{1}, x_{2},…, x_{n}). Show that the two following statements are equivalent:

(a) rank (AX) = m ∀x ∈ Ω

(b) b cannot be expressed as nonnegative linear combination of m − 1 or fewer columns of A.

Hint: The matrix AX is comprised of positively-scaled columns of A and columns of zeros.

3. Let P (x) denote the pure network flow problem

\begin{aligned}min_{x} & cx \\ s.t. & Ax = b \\ & 0 ≤ x ≤ u, \end{aligned}

where A is a node-arc incidence matrix. Suppose that x̄ is a BFS (basic feasible solution) of P (x) and that x_{1} and x_{2} correspond to two pivot-eligible arcs (relative to x̄).

(a) State conditions under which x_{1} and x_{2} can be “simultaneously” (i.e. in parallel) brought into the basis, producing the same new primal BFS that would result if they were brought in sequentially (in either order).

(b) State corresponding conditions for the \underline{dual} variable updates associated with x_{1} and x_{2} .

(c) Give a \underline{numerical} example in which the conditions of part (a) are satisfied and the conditions of part (b) are violated.

4. Let k(s) be a “separation counter” defined by

k(s) = \{ \begin{matrix}0 & if s < δ \\ 1 & if s ≥ δ \end{matrix}

where δ is a given \underline{positive} constant. Formulate as a \underline{mixed integer} \underline{linear program} the following pattern separation problem:

max_{c,α,s,t} ∑_{i=1}^{p} k(s_{i}) + ∑_{i=1}^{p} k(t_{i})
s.t. cx_{i} − α ≥ s_{i} (i = 1,…, p)
cy_{i} − α ≤ −t_{i} (i = 1,…, p)
∥c∥_{∞} ≤ 1

where x_{1},…, x_{p} and y_{1},…, y_{p} are given sets of points in IR^{n}; and c (a row vector), α, s = (s_{1},…, s_{p}), and t = (t_{1},…, t_{p}) are unknowns. Be sure to define any constants (which may depend on the x_{i} and y_{i}) used in the formulation. (Note: Without loss of generality assume: s_{i} ≤ δ, t_{i} ≤ δ, i = 1,…, p.)

5. Consider the problem min_{x≥0} f(x) where f : IR^{n} → IR is differentiable and convex on IR^{n}. Assume that a solution x̄ exists. For z ∈ IR^{n} define ((z)_{+})_{i} = max {z_{i}, 0}, i = 1,…, n.

(a) Suppose that for some x̂ ≥ 0, ∇f(x̂) > 0. Find an upper bound on ∥x̄∥_{1} in terms of x̂ and ∇f(x̂), where ∥ · ∥_{1} denotes the 1-norm.

(b) Suppose, in addition, that f has a Lipschitz-continuous gradient, from which you can assume that for some number L > 0:

L∥y − x∥^{2} ≥ (∇f(y) − ∇f(x))(y − x) ≥ \frac{1}{L} ∥∇f(y) − ∇f(x)∥^{2}

where ∥ · ∥ denotes the 2-norm. Obtain for any x ≥ 0 in IR^{n}, an upper bound on ∥∇f(x) − ∇f(x̄)∥ in terms of L, x̂ and the quantities, x∇f(x), (−∇f(x))_{+} . (The last 2 quantities measure the violations by x ≥ 0 of the Karush-Kuhn-Tucker conditions for the problem).

6. Consider the proximal point algorithm defined by

x^{k+1} = arg min_{x∈X} (f(x) + \frac{γ}{2} ∥x − x^{k}∥^{2})

where ∥ · ∥ denotes the 2-norm, γ > 0, f is differentiable and convex on IR^{n}, X is a convex subset of IR^{n}. Define

X̄ := arg min_{x∈X} f(x) := set of minimizers of f on X

Suppose that for some k, x^{k} ∈ X̄. Prove that x^{k} = P (x^{k−1}|X̄) where

P (x|X̄) = arg min_{y∈X̄} ∥x − y∥.

Hint: You may want to use the fact that:

z = P (x|X̄) ⇔ ⟨x − z, y − z⟩ ≤ 0 ∀y ∈ X̄

7. Let the function f : IR^{n} → IR have a Lipschitz continuous gradient on IR^{n} with constant L. You are given a point x ∈ IR^{n} and a direction vector p ∈ IR^{n} such that ∇f(x)p < 0 and ∥p∥ = 1, where ∥ · ∥ denotes the 2-norm.

(a) For what interval of λ can you guarantee that f(x + λp) < f(x)? Establish your claim.

(b) What specific value of λ will give you the biggest guaranteed decrease in f? Establish your claim.

(c) Suppose p = −∇f(x)/∥∇f(x)∥. What can you say about each accumulation point x̄ of the sequence {x^{i}} where x^{i+1} = x^{i} + λ^{i}p^{i}, and λ^{i} is chosen according to part (b)? Establish your claim assuming that ∇f(x^{i}) ≠ 0 for all i.

Hint: Assume f(x + λp) − f(x) − λ∇f(x)p ≤ \frac{Lλ^{2}}{2} ∥p∥^{2}

8. Suppose f is a closed proper convex function on IR^{n}, and ρ is a fixed positive

number. Let

f_{ρ}(x) = inf_{y} g(x, y),

where

g(x, y) = f(y) + (2ρ)^{−1}∥y − x∥^{2}.

(a) Show that f_{ρ} is a convex function.

(b) Show that the infimum in y of g(x, y) is attained at a unique point of IR^{n}.

Suggestion: As part of your answer for (b), consider establishing the following intermediate facts: (i) g(x, ·) is lower semicontinuous; (ii) g(x, ·) has bounded level sets; (iii) g(x, ·) is strictly convex.