Consider the quadratic program of the form min 𝑥 1 , 𝑥 2 ( 𝑥 1 − 1 ) 2 + ( 𝑥 2 − 1 ) 2 subject to 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0 , 𝑥 1 + 𝑥 2 ≤ 1 min x 1 ,x 2 (x 1 −1) 2 +(x 2 −1) 2 subject tox 1 ≥0,x 2 ≥0,x 1 +x 2 ≤1 The optimal solution of the quadratic program is ( 1 / 2 , 1 / 2 ) (1/2,1/2). If 𝑦 ∗ y ∗ is the optimal dual solution, how many entries of the vector 𝑦 ∗ y ∗ are non-zero? (Hint: draw a picture of the level sets of the objective function and of the feasible region.) 0 1 2 3 4
Question
Consider the quadratic program of the form min 𝑥 1 , 𝑥 2 ( 𝑥 1 − 1 ) 2 + ( 𝑥 2 − 1 ) 2 subject to 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0 , 𝑥 1 + 𝑥 2 ≤ 1 min x 1 ,x 2
(x 1 −1) 2 +(x 2 −1) 2 subject tox 1 ≥0,x 2 ≥0,x 1 +x 2 ≤1 The optimal solution of the quadratic program is ( 1 / 2 , 1 / 2 ) (1/2,1/2). If 𝑦 ∗ y ∗ is the optimal dual solution, how many entries of the vector 𝑦 ∗ y ∗ are non-zero?
(Hint: draw a picture of the level sets of the objective function and of the feasible region.) 0 1 2 3 4
Solution
The optimal dual solution, y*, corresponds to the constraints of the problem. In this case, we have three constraints:
- x1 ≥ 0
- x2 ≥ 0
- x1 + x2 ≤ 1
At the optimal solution (1/2, 1/2), the first two constraints are not active because x1 and x2 are not zero. The third constraint is active because x1 + x2 equals 1.
Therefore, only one entry of the vector y* is non-zero. So, the answer is 1.
Similar Questions
Consider the quadratic program of the form min 𝑥 1 , 𝑥 2 ( 𝑥 1 − 1 ) 2 + ( 𝑥 2 − 1 ) 2 subject to 𝑥 1 ≥ 0 , 𝑥 2 ≥ 0 , 𝑥 1 + 𝑥 2 ≤ 1 min x 1 ,x 2 (x 1 −1) 2 +(x 2 −1) 2 subject tox 1 ≥0,x 2 ≥0,x 1 +x 2 ≤1 The optimal solution of the quadratic program is ( 1 / 2 , 1 / 2 ) (1/2,1/2). If 𝑦 ∗ y ∗ is the optimal dual solution, how many entries of the vector 𝑦 ∗ y ∗ are non-zero? (Hint: draw a picture of the level sets of the objective function and of the feasible region.) 0 1 2 3 4
Consider the quadratic program minx1,x2f(x1,x2)subject toCx≥dmin𝑥1,𝑥2𝑓(𝑥1,𝑥2)subject to𝐶𝑥≥𝑑where C𝐶 is a 5×25×2 matrix and d𝑑 is a length 5 vector. (c) How many variables does the dual quadratic program have? Answer 4 Question 1(d) What is the value of the dual quadratic program at the point y=0𝑦=0?
Write the dual of the following linear programming problem:Maximize 8x1 + 3x2 − 2x3subject to x1 − 6x2 + x3 > 25x1 + 7x2 − 2x3 = −4x1 ≤ 0, x2 ≥ 0, x3 unrestricted.
state the weak duality theorem (1 mark)ii) Write the dual of the given primal problem.Min W=10y1 − 15y2Subject toy1 − 4y2 ≥ 3y1 + y2 ≥ 53y1 − 2y2 = 7y1, y2 ≥ 0 (2 marks)iii) Given the linear programming problemMax z = 15y1 + 25y2Subject toy1 + y2 ≤ 450y2 ≤ 3504y1 + 5y2 ≤ 2000y1 ≤ 350y1, y2 ≥ 0Find the range of optimality of y1, y2. (3 marks)Will the optimal basis change when the objective function coefficient of y1, y2change to 17 and 24 respectively? (2 marks)
Consider the following linear program:minx1,x2,x3,x4c1x1+c2x2+c3x3+2x4subject to⎧⎩⎨x1+x2+x3+x4≥103x1+x2+4x3+2x4≥12x1≥0,x2≥0,x3≥0,x4≥0min𝑥1,𝑥2,𝑥3,𝑥4𝑐1𝑥1+𝑐2𝑥2+𝑐3𝑥3+2𝑥4subject to{𝑥1+𝑥2+𝑥3+𝑥4≥103𝑥1+𝑥2+4𝑥3+2𝑥4≥12𝑥1≥0,𝑥2≥0,𝑥3≥0,𝑥4≥0 The parameters c1,c2,c3𝑐1,𝑐2,𝑐3 are real numbers.(a) How many variables does the dual problem have? Answer 1 Question 2Suppose that the optimal solution to the primal is x1=0𝑥1=0, x2=0𝑥2=0, x3=0𝑥3=0, x4=10𝑥4=10.(b) What is the optimal value of the objective function of the dual linear program? Answer 2 Question 2.(c) How many entries of the optimal dual variable are equal to zero?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.