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()