Linear Programming, Affine Scaling with Julia
Wednesday, December 14th, 2022
My student friends passed me a homework question for Operations Research. Since it involves Matrices, I was attracted to try Julia. At the end I was very happy with the experience. Julia is a great language to do matrix operations.
Solve the following LP by using the Affine Scaling Approach of Interior Point Methods (IPM) with starting
Wikipedia explains the algorithm in a very mathematical way: https://en.wikipedia.org/wiki/Affine_scaling. I guess you need to be very familiar with linear programming to understand that. (I'm not)
I found this great resource about using Julia for Operations Research by Changhyun Kwon: https://juliabook.chkwon.net/book/interior
I understood the problem and the method (except for the math magic that somehow gives you the direction to move for each variable). I wasn't sure how to get
A matrices below. Luckily, I found the exact example with these matrices in a PDF(page 41) by chance. It became a perfect puzzle, with all the parts in front of me.
So, here is the solution:
using LinearAlgebra beta=0.8 x0 = [10, 2, 7, 13] x=x0 c = [-2, 1, 0, 0] A = [1 -1 1 0 ; 0 1 0 1 ] b = [15, 15] for i in 1:3 local X = Diagonal(x) local p = inv(A*X^2*A')*A*X^2*c local r = c - A'*p global x = x - beta * X^2 * r / norm(X*r) println((round.(x; digits=2))) end