Interior-Point Step

Problem

Take one Newton step on the barrier subproblem for a 2-variable LP.

With x1 = x and x2 = 1 - x, the barrier objective has gradient (c1 - c2) - mu / x + mu / (1 - x) and Hessian mu / x ** 2 + mu / (1 - x) ** 2. Return x - gradient / hessian.

Hint

The equality constraint x1 + x2 = 1 reduces the problem to one variable.

Test cases

case 1

in: [0.5,1,2,0.5]

expected: 0.75

case 2

in: [0.5,2,1,0.25]

expected: 0

case 3

in: [0.25,1,1,0.1]

expected: 0.4

Starter codePython

def interior_point_step(x, c1, c2, mu):
    # Your code here
    pass

3 test cases · run your code against them in the editor