Frank Wolfe Algorithm in Python

This code is used to solve user equilibrium issue in Urban Transportation Network(page 114), book’s author is Yosef Sheffi, MIT

import pandas as pd# set up decimal format, but in vain >_<
pd.set_option('precision', 4)
# calculate outcome of objective functions
def total_cost(x_list):
z1 = (10 * x_list[0]) + 0.6 * (x_list[0] / 2) ** 5
z2 = (20 * x_list[1]) + 2.4 * (x_list[1] / 4) ** 5
z3 = (25 * x_list[2]) + 2.25 * (x_list[2] / 3) ** 5
z = z1 + z2 + z3
return z
# calculate cost functions
def cost_fun(x_list):
cost_list = []
cost1 = 10 * (1 + 0.15 * (x_list[0] / 2) **4)
cost2 = 20 * (1 + 0.15 * (x_list[1] / 4) **4)
cost3 = 25 * (1 + 0.15 * (x_list[2] / 3) **4)
cost_list.append(cost1)
cost_list.append(cost2)
cost_list.append(cost3)
return cost_list
# find the shortest path according to the cost functions
def AoN(cost_list):
y_list = [0, 0, 0]
p = cost_list.index(min(cost_list))
y_list[p] = 10
return y_list
# use bisection rule to iterate and then find alpha
def bisection(x_list, y_list):
check = 0
downside = 0
upside = 1
while check != 1:
alpha = (downside + upside) / 2
z1 = 10 * (y_list[0] - x_list[0]) * (1 + 0.15 * ((x_list[0]
+ alpha * (y_list[0] - x_list[0])) / 2) ** 4)
z2 = 20 * (y_list[1] - x_list[1]) * (1 + 0.15 * ((x_list[1]
+ alpha * (y_list[1] - x_list[1])) / 4) ** 4)
z3 = 25 * (y_list[2] - x_list[2]) * (1 + 0.15 * ((x_list[2]
+ alpha * (y_list[2] - x_list[2])) / 3) ** 4)
z = z1 + z2 + z3
if z < 0:
downside = alpha
alpha = (downside + upside) / 2
check = 0
elif z > 0 and z > 0.001:
upside = alpha
alpha = (downside + upside) / 2
check = 0
else:
check = 1
return alpha
# calculate new x1, x2, x3 and new outcome from objective functions
def next_iteration(x_list, y_list, alpha):
x1 = x_list[0] + alpha * (y_list[0] - x_list[0])
x2 = x_list[1] + alpha * (y_list[1] - x_list[1])
x3 = x_list[2] + alpha * (y_list[2] - x_list[2])
x_list[0] = x1
x_list[1] = x2
x_list[2] = x3
w1 = (10 * x1) + 0.6 * (x1 / 2) ** 5
w2 = (20 * x2) + 2.4 * (x2 / 4) ** 5
w3 = (25 * x3) + 2.25 * (x3 / 3) ** 5
w = w1 + w2 + w3
return x1, x2, x3, alpha, x_list
# set up first coefficient
x_list = [10, 0, 0]
alpha = 1
z_list = [1]
iteration = 0
kappa = 10
# run the main functions and decide the stop point(when alpha <= 0.001 and kappa < 0.01)
while alpha > 0.01 or kappa > 0.01 :
# run the main functions and decide the stop point(when alpha <= 0.001 and kappa < 0.01)
z = total_cost(x_list)
z_list.append(z)
cost_list = cost_fun(x_list)
y_list = AoN(cost_list)
alpha = bisection(x_list, y_list)
next_iteration(x_list, y_list, alpha)
iteration += 1
kappa = abs(z_list[iteration] - z_list[iteration-1])
# use kappa to check convergence
print('iteration:', iteration)
print('z(x):',z, 'kappa:', kappa, 'alpha:', alpha)
print('individual cost:', cost_list)
print()

Playground for a old student. Records about learning, life and interesting stuff