👉 Affine Scaling in R
I recently stumbled across an implementation of the affine scaling interior point method for solving linear programs that I’d coded up in R once upon a time. I’m posting it here in case anyone else finds it useful. There’s not a whole lot of thought given to efficiency or numerical stability, just a demonstration of the basic algorithm. Still, sometimes that’s exactly what one wants. solve.affine <- function(A, rc, x, tolerance=10^-7, R=0.999) { # Affine scaling method while (T) { X_diag <- diag(x) # Compute (A * X_diag^2 * A^t)-1 using Cholesky factorization. # This is responsible for scaling the original problem matrix. q <- A %*% X_diag**2 %*% t(A) q_inv <- chol2inv(chol(q)) # lambda = q * A * X_diag^2 * c lambda <- q_inv %*% A %*% X_diag^2 %*% rc # c - A^t * lambda is used repeatedly foo <- rc - t(A) %*% lambda # We converge as s goes to zero s <- sqrt(sum((X_diag %*% foo)^2)) # Compute new x x <- (x + R * X_diag^2 %*% foo / s)[,] # If s is within our tolerance, stop. if (abs(s) < tolerance) break } x } This function accepts a matrix A which contains all technological coefficients for an LP, a vector rc containing its reduced costs, and an initial point x interior to the LP’s feasible region. Optional arguments to the function include a tolerance, for detecting when the method is within an acceptable distance from the optimal point, and a value for R, which must be strictly between 0 and 1 and controls scaling. ...