MATH-UA 9253 Linear and nonlinear optimization Spring 2022 HW2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH-UA 9253
Linear and nonlinear optimization
Spring 2022
HW2
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 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 .
(b) Show that (1, 0) C. By the separating hyperplane theorem, deduce that there is (s, y) ∈ R × Rm such that
s0 + y⊤0 = s < u
where u is defined by
u = inf {sr + y⊤w : (r, w) ∈ C} .
(d) Show that s < u and the fact that C is a cone imply u = 0. Thus s < 0
on.
Hence we have shown that inf { −r + y⊤w : (r, w) ∈ C} = 0, thus −r + y⊤w ≥ 0 for all (r, w) ∈ C, that is
− (tVP − c⊤x)+ y⊤ (tb − Ax) ≥ 0
(e) Noting that t = 0 implies y⊤A ≤ c⊤, while taking x = 0 and t = 1 implies y⊤b ≥ VP , show that y is optimal for the dual.
2022-02-23