Consider the primal linear program: max 2x s.t. x ≤ 3 x ≤ 5 x ≥ 0 (a) Write down the…
- User
Consider the primal linear program: max 2x s.t. x ≤ 3 x ≤ 5 x ≥ 0 (a) Write down the equations of primal-dual central path for the problem corresponding to the barrier parameter µ = 1. (You may add slack variables on you own). (b) Consider the primal and dual feasible solutions x = 2 and y = (1, 2). Write down the corresponding linearized version of the equations you found in part (a) for the increments in the Newton’s step. (You may have ∆x, ∆y1, ∆y2...) (c) Compare the duality gap of initial feasible solution x = 2, y = (1, 2) with that of the new solution after a full Newton’s step.
- Assistant
(a) Adding slack variables, the primal LP can be written as: maximize 2x + 0w1 + 0w2 subject to: x + w1 = 3 x + w2 = 5 x ≥ 0 The dual LP is: minimize 3y1 + 5y2 subject to: y1 + y2 ≥ 2 y1 ≥ 0, y2 ≥ 0 The equations of primal-dual central path for µ = 1 are: x + w1 - 3s1 = 0 x + w2 - 5s2 = 0 y1 + y2 - 2s3 = 1 s1 ≥ 0, s2 ≥ 0, s3 ≥ 0 (b) Considering x = 2 and y = (1, 2), we have: x + w1 = 3 x + w2 = 5 y1 + y2 ≥ 2 s1 = 1/2 - 2/√13 s2 = 1/2 + 3/√13 s3 = 1 The linearized version of the primal-dual central path equations for the increments in the Newton's step are: ∆x + ∆w1 - 3∆s1 = 0 ∆x + ∆w2 - 5∆s2 = 0 ∆y1 + ∆y2 - 2∆s3 = 0 ∆s1 ≥ 0, ∆s2 ≥ 0, ∆s3 ≥ 0 (c) The duality gap of initial feasible solution x = 2, y = (1, 2) is: 2(2) - (3(1) + 5(2)) = -8 After a full Newton's step, the new primal and dual feasible solutions are x = 23/6, y1 = 23/12, y2 = 5/6. The duality gap is: 2(23/6) - (3(23/12) + 5(5/6)) = 0
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.