Interior-point linear programming by the logarithmic barrier

Damped Newton steps on the barrier objective from a strictly feasible start. The central-path point satisfies c'x(tau) - p* <= (m + n) tau, a bound that does not run through this code and is what the tests check against the simplex optimum.

Usage

Intlpa(c, A, b, x0, tau = 0.01, iters = 60)

Arguments

c

Objective coefficients.

A

Constraint matrix.

b

Right-hand side.

x0

Strictly feasible starting point.

tau

Positive barrier parameter.

iters

Newton iteration cap.

Value

List with estimate, x, objective, duality_bound, newton_decrement, tau, n, method.

Details

Formula: minimise c'x - tau [sum_i log(b_i - a_i'x) + sum_j log x_j].

References

Karmarkar (1984), A new polynomial-time algorithm for linear programming, Combinatorica 4(4):373-395. doi:10.1007/BF02579150 ; Boyd and Vandenberghe (2004), Convex Optimization, CUP, sect. 11.2.

Examples

Intlpa(c = c(-1, -2), A = matrix(c(1, 1, 1, 0, 0, 1), 3, 2, byrow = TRUE),
       b = c(4, 2, 3), x0 = c(0.5, 0.5))
#> $estimate
#> [1] -6.980033
#> 
#> $x
#> [1] 0.9999667 2.9900333
#> 
#> $objective
#> [1] -6.980033
#> 
#> $duality_bound
#> [1] 0.05
#> 
#> $newton_decrement
#> [1] 6.186774e-18
#> 
#> $tau
#> [1] 0.01
#> 
#> $n
#> [1] 2
#> 
#> $method
#> [1] "log-barrier Newton central path, Karmarkar (1984); Boyd & Vandenberghe sect. 11.2"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"