Please submit at or before the start of the lecture on  Wednesday, March 2 2022  (strict deadline),  by submitting on Brightspace.   This  assignment is not timed.

The preferrred submission format consists of one unique pdf file for answers (either a scan of cleanly handwritten answers, or typed ones).  Include the code and the output in your answers whenever appropriate.

NYU’s integrity policies will be  enforced.   The  consultation  of the  course notes, textbooks, as well as personal notes taken during the course are encour- aged.  Communication with other students regarding the homework is authorized, but solutions should be written up independently.   Copying of any portion of someone else’s solution/code or allowing others to copy your solution/code is considered cheating.

(a) min xj≥0 s.t.   (b) max xj≥0

2x1 + 3x2 − x3 x1 + x2  ≤ 1 x3  ≤ 2   x1 − x2 − x3 x1 − 2x2  ≤ 0 x2 + x3  ≤ 1

Question 1.  Solve the following LP’s by hand, using the simplex method and starting from x = 0:

 

 

 

Question 2. This question illustrates the method seen in class to determine

 

 

2x1 − 2x2 + 3x3 = 10

x1 − x2 − 3x3 = 6                                            (1)

xj  ≥ 0 for each j

if and only if the following linear program has minimum value 0

min           z1 + z2

 

x1 − x2 − 3x3 + z2 = 6

 

 

(b) Use the simplex method starting from x = 0, z1 = 10, z2 = 6 to determine whether the set (1) is empty or not, and to find a basic feasible solution if it is nonempty.

 

2x1 − 2x2 + 3x3 = 9                                             (2)

x1 − x2 − 3x3 = 0                                             (3)

xj  ≥ 0 for each j                                             (4)

is empty or not, and to find a basic feasible solution if it is nonempty.

Question 3. Consider the following LP

max

 

x1 + x2 − 3x3

x1 + 2x2 − 3x3 = g

4x1 + 5x2 − 9x3 = 13

Here g is a real number; therefore the optimal value V  = V(g) and the optimal x∗ = x∗(g) are functions of g. The dual of this linear program is

min yi∈R

 

gy1 + 13y2

y1 + 4y2  ≥ 1

2y1 + 5y2  ≥ 1

( −3)y1 − 9y2  ≥ −3

(Note that in the dual, the signs of y1  and y2  are not restricted.) The optimal

(a) Show that strong duality holds for any g, i.e. that the value of the primal coincides with the value of the dual.

 

(d) The function V(g) is piecewise linear.  Determine (without further use of Gurobi) the exact values of g in the interval 0 < g < 9, where V′  changes. [Hint: what geometric shape is the feasible set of the dual?]

Question 4.

(a) Let v1 , . . . , vm  be vectors in Rm. For w ∈ Rm, consider the problem

V (w) = max

 

w⊤d                                                    (5)

w⊤d ≤ 1

vd ≤ 0, i = 1, ..., m

 

 

Show that V (w) cannot take any other values than 0 or 1:  V (w) = 0 or V (w) = 1 for any w .

 

w =  λivi                                                                    (6)

if and only if for all d ∈ Rm ,

[vd ≤ 0, ∀i = 1, ..., m]  =⇒ w⊤d ≤ 0                           (7)

 

It is suggested to use Gurobi to answer the next two questions. For both of them we take n = 2, m = 3, and v1  = (1, 3)⊤ , v2  = (2, 1)⊤ , v3  = (1, 1)⊤, and we ask if there exist λi  ≥ 0, i = 1, ..., m, such that (6) holds:

(d) when w = (1, 10)⊤? Give a vector of the λi’s such that (6) if the answer is yes, and if the answer is no, a vector d ∈ Rn such that vd ≤ 0 and w⊤d > 0.

 

Question 5. The goal of this question is to go through the proof (that we skipped in class) of the duality theorem using the separating hyperplane theorem. The separating hyperplane theorem states that if C is a convex set of Rd  and x  ∈ Rd  is not in C, then there is a y  ∈ Rd  and α such that z⊤y − α  ≥ 0 for all z ∈ C and x⊤y − α < 0.  (one says that the hyperplane {z : z⊤y = α } “separates” C and x). Alternatively, the conclusion can be stated as there exists y ∈ Rd  such that inf {z⊤y : z ∈ C} > x⊤y .

 

VP     =   minc⊤x

s.t.           Ax = b

and its dual

VD     =   max b⊤y

s.t.          A⊤y ≤ c

 

 

(a) Introduce

C =    : x ∈ R, t ∈ R+}

and show that C is convex, and that C is a cone, that is (r, w) ∈ C and λ ≥ 0 implies (λr, λw) ∈ C .