MATHEMATICAL PROGRAMMING

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

lowing 9 questions.

Instructions for Breadth Exam Students: Answer any 3 of the

following 9 questions.

1. Consider the following tableau

−y_{1} −y_{3} −x_{2} −x_{1} 1
x_{3} = −2 1 −4 4 2
y_{2} = −1  2 −1 −2 1
x_{4} = −1  2  1  0 2
y_{4} = −1 −1  1  1 4
z =  1  1  0  2 5

Is this tableau optimal? Why? If there is another optimal solution obtain it. If there is not, give a reason why.

2. Consider the dual LP’s:

\begin{matrix}min c^{T} x & max b^{T} u \\ Ax ≥ b & A^{T} u ≤ c \\ x ≥ 0 & u ≥ 0 \end{matrix}

Show that if these problems have solutions, then there exists a primaldual solution (x̄, ū) for which strict complementary holds.

[Hint: You may need the following lemma (Tucker): For any skewsymmetric matrix M(M = −M^{T}) there exists z such that z ≥ 0,Mz ≥ 0,z^{T} Mz = 0,z + Mz > 0] 3. Consider the following capacity expansion problem: substations A and

B are currently connected to central switching points C and D by 15

and 20 trunk lines respectively (see figure)

A ^{15}  C

B ^{20}  D

Due to increased traffic, A now requires a total of 25 lines to central switching points C or D, and B requires 30 such lines. The cost of installing \underline{new} lines is given by the cost matrix:

\begin{aligned}& C & D \\ A & 1 & 4 \\ B & 3 & 2 \end{aligned}

(thus, each new line from A to C costs 1 unit, etc.) (Note that lines may go from A to D and B to C.)

There is no cost for keeping constant or reducing the current number of lines between points in the network. Switching points C and D have capacities of 20 and 40 (total) lines respectively.

(a) Formulate this problem of meeting the new requirements at minimum cost as a linear network flow problem (with equality constraints for the divergences at the nodes.) Sketch the corresponding network, indicating arc capacities and costs, and supplies and demands.

(b) State an optimal solution and optimal value for the given problem.

(c) State why the solution given in part (b) is optimal.

4. Let f(t) be defined as the following optimal value function:

f(t) := min_{x,y} x_{1} + 2y_{1} + y_{2} + x_{2}
s.t. \{ \begin{matrix}y_{1} + y_{2} = t \\ 0 ≤ y_{2} ≤ T_{2}x_{2} ≤ (T_{2}/T_{1})y_{1} ≤ T_{2}x_{1} \\ x_{1} = 0 or 1 ; x_{2} = 0 or 1 \end{matrix}

(Assume that T_{1} and T_{2} are positive constants.)

(a) Sketch f(t) and give an explicit algebraic description of f(t) (also indicating where it is + ∞).

(b) Let g(t) be the optimal value function of the linear progam obtained by replacing the constraints x_{i} = 0 or 1 by 0 ≤ x_{i} ≤ 1 (i = 1, 2). Prove that g(t) < f(t) for t ϵ (0, T_{1} + T_{2}) , provided that T_{2} ≥ 1 .

5. Suppose that N = (V, E, u) is an undirected network, where V is the mode set, E is the edge set, u is a capacity function, u : E → IR_{+} , i.e., any flow x in an edge e can be one of the two directions of e , subject to

0 ≤ x(e) ≤ u(e) .

The value of a maximal flow from node i to node j is denoted by V_{ij} . Thus, V_{ij} = V_{ji} . Use the max-flow min-cut theorem to prove that for any three nodes i, j, k ϵ V , the two smaller of the three values {V_{ij} , V_{jk} , V_{ki}} are equal, i.e., if V_{ij} ≥ V_{jk} , V_{ij} ≥ V_{ki} , then V_{jk} = V_{ki} .

6. Function f : IR^{n} → IR is defined by f(x) := ∥x∥^{2} + ∥x∥ , where ∥ · ∥ is the Euclidean norm. Compute its conjugate f^{∗} and the subdifferentials of f and f^{∗} .

7. Let K be a polyhedral convex cone in R^{n}. Show that K contains a semipositive vector (i.e., a vector that is non-negative but not zero) if and only if its polar K^{∘} contains no positive vector (i.e., no vector each of whose components is positive).

8. Suppose that in solving a constrained optimization problem you need to work in a subspace L of R^{n}. The subspace consists of all z satisfying the linear constraints Az = 0, where A is a given k × n matrix of rank k. On this subspace you have to minimize a smooth nonlinear function f. It is known that the second derivative of f, evaluated at any point of L, is a matrix that is singular, but it is also known that the restriction of f to L is uniformly convex. You wish to use Newton’s method to minimize f.

Explain an efficient numerical procedure for implementing the Newton calculations on L. You do not need to discuss step size calculation, but you must explain how you will carry out the direction-finding calculation, how you will deal with the singularity, and how you will represent the elements of L that you need to use in the calculations. In all of these explanations you must say how you will calculate the quantities you need.

9. Consider the optimization problem

min { x_{1} + x_{2} | ϕ(p)x_{1}^{2} ≤ x_{2} },

where ϕ is a smooth function from R^{k} to R with ϕ(0) = \frac{1}{2}.

(a) Show that when p = 0 the point x(0) = (−1, 1/2) is the unique minimizer (of any kind, local or global) for this problem.

(b) Prove that there is a smooth function x from a neighborhood U of the origin in R^{k} to R^{2}, such that for each p ∈ U the point x(p) is the unique minimizer for the problem with that value of p.

(c) Compute the derivative of x at p = 0.