Lab10.ipynb

 
 

  
 Mathematical Optimization for Engineers
Lab 10 - Deterministic Global Optmization
  $In this exercise, we'll look at deterministic global optimization of boxconstrained two-dimensional non-convex problems. We will implement the branch-and-bound method and use the BB method to construct convex relaxations of non-convex objective functions. $$\begin{aligned} \min_{\mathbf x\in X} \quad f(\mathbf x) \\ %\mbox{s.t. } \quad g & \; \leq \; 15 \\ \end{aligned}$$ Task: Go through the code and fill in the missing bits to complete the implementation. Missing bits are marked with the comment # add your code here$ 
 In [1]: 
 import numpy as np

# we will use a local solver from scipy for upper-bounding problem
from scipy import optimize as sp

# to construct relaxations for lower-bounding problem
from math import inf, sin, cos, sqrt

# for branching
import copy

# for plotting
import matplotlib.pyplot as plt
from mpl_toolkits import mplot3d
from matplotlib import cm
 
 Objective functions, to experiment on:
 $Return f (x) for input x$ 
 In [2]: 
 def sixhump(x): #scipy-lectures.org/intro/scipy/auto_examples/plot_2d_minimization.html
    return ((4 - 2.1*x[0]**2 + x[0]**4 / 3.) * x[0]**2 + x[0] * x[1] + (-4 + 4*x[1]**2) * x[1] **2)
 
 In [3]: 
 def adjiman (X):
    x, y = X[0], X[1]
    return (np.cos(x) * np.sin(y)) - (x / (y**2.0 + 1.0))
 
 In [4]: 
 def schwefel(x):
    n = 2
    s = 0
    for i in range(0,n):
        s = s - 1 * x[i] * sin(sqrt(abs(x[i])))
    y = 418.9829 * n + s
    return y
 
 In [5]: 
 def griewank(x):
    x1 = x[0]
    x2 = x[1]
    sum = 0
    prod = 1

    sum = sum + x1 ** 2 / 4000
    prod = prod * np.cos(x1 / sqrt(1))

    sum = sum + x2 ** 2 / 4000
    prod = prod * np.cos(x2 / sqrt(2))

    y = sum - prod + 1
    return y
 
 In [6]: 
 def camel3(xx):

    x1 = xx[0]
    x2 = xx[1]

    term1 = 2*x1**2
    term2 = -1.05*x1**4
    term3 = x1**6 / 6
    term4 = x1*x2
    term5 = x2**2
    return  term1 + term2 + term3 + term4 + term5
 
 Compute convex relaxations using $\alpha$BB method
 $Returns cv($f(\mathbf x)$), for inputs and$ 
 In [7]: 
 def relaxedFunction(x, function, alpha, lb, ub): 
    # using alphaBB method
    
    lb = np.array(lb)
    ub = np.array(ub)
    y = # add your code here

    return y
 
 Compute upper bound for current node
Writes "ubd" attribute of newly created nodes. Returns updated list of nodes.
 In [17]: 
 def computeUpperBounds(nodes, objective):
    for iNode in nodes:
        if iNode["ubd"] == inf: 
            x0 = (np.array(iNode["lb"]) + np.array(iNode["ub"]))/2
            bnds = []
            for i in range(0, len(lb)):
                bnds.append((iNode["lb"][i], iNode["ub"][i]))
    
            solUBD = sp.minimize(objective, x0, bounds = bnds, method='L-BFGS-B', jac=None)
            if solUBD.success:
                iNode["ubd"] = solUBD.fun
            else:
                iNode["ubd"] = float("inf")
            
    return nodes
 
 Compute lower bound for current node
Writes "lbd" attribute of newly created nodes. Returns updated list of nodes.
 In [18]: 
 def computeLowerBounds(nodes, objective, alpha):
    for iNode in nodes:
        if iNode["ubd"] == inf: 
            x0 = (np.array(iNode["lb"]) + np.array(iNode["ub"]))/2
            bnds = []
            for i in range(0, len(lb)):
                bnds.append((iNode["lb"][i], iNode["ub"][i]))
            
    
            solLBD = sp.minimize(relaxedFunction, x0, args=(objective, alpha, iNode["lb"], iNode["ub"]), bounds = bnds, method='L-BFGS-B', jac=None)
            
            #Check the feasibility of the solution
            feasible = True
            if solLBD.success:
                iNode["lbd"] = solLBD.fun
            else: #Solver indicates that solving was not successful
                solPoint = solLBD.x[:n]
                cons = np.zeros(m)
                for index in range(m): # checking equailty constraints
                    if abs(np.dot(solPoint.T, np.dot(Q[:,:, index], solPoint)) + np.dot(A[index,:], solPoint) - b[index]) > epsilonF:
                        feasible = False
                        break
                if feasible==False: # infeasible node
                    nodes.remove(iNode)
                else: 
                    iNode["lbd"] = float("-inf")
            
    return nodes
 
 Branch
 In [19]: 
 def branching(nodes, globalLBD): 
    epsilonF = 0.001
    
    chosenNode = nodes[0]
    # choose node with lowest LBD 
    for iNode in nodes: 
        if iNode["lbd"] <= globalLBD + epsilonF:
            chosenNode = iNode
            break
    
    # branch on variable with largest variable bounds
    delta = np.array(chosenNode["ub"]) - np.array(iNode["lb"])
    indVariable = np.argmax(delta)
    print("max delta: ", max(delta))
    
    # simply branch in the middle
    iNodeLeft = copy.deepcopy(chosenNode)
    iNodeLeft["ub"][indVariable] = # add your code here
    iNodeLeft["lbd"] = - inf
    iNodeLeft["ubd"] = + inf

    
    iNodeRight = copy.deepcopy(chosenNode)
    iNodeRight["lb"][indVariable] = iNodeLeft["ub"][indVariable]
    iNodeRight["lbd"] = - inf
    iNodeRight["ubd"] = + inf

    
    # bookkeeping
    nodes.remove(chosenNode)
    nodes.append(iNodeLeft)
    nodes.append(iNodeRight)
       
    
    return nodes
 
 Fathoming
Returns true or false for given node and global upper bound.
 In [20]: 
 def fathom(iNode, globalUBD):
    # fathom if true
    if # add your code here:
        return True
    else:
        return False
 
 Main function
 $Returns global minimum for given objective function, box constraints: x^{L} and x^{U}, and α .$ 
 In [21]: 
 def branchAndBoundAlgorithm(objective, lb, ub, alpha):
 
    foundGlobalSolution = False
    epsilonF = 0.001 # absolute tolerance
    UBD = inf
    LBD = -inf
    nodes = []

    # initial point
    x0 = (np.array(lb) + np.array(ub))/2
    
    bnds = []
    for i in range(0, len(lb)):
        bnds.append((lb[i], ub[i]))
    
    # compute upper bound
    solUBD = sp.minimize(objective, x0, bounds = bnds, method='L-BFGS-B', jac=None)
    # compute lower bound 
    solLBD = sp.minimize(relaxedFunction, x0, bounds = bnds, args=(objective, alpha, lb, ub), method='L-BFGS-B', jac=None)
    
    # current global upper and lower bounds
    UBD = solUBD.fun
    LBD = solLBD.fun
    
    # create first node
    node = {
        "ubd": solUBD.fun,
        "lbd": solLBD.fun,
        "lb": lb,
        "ub": ub
    }
    nodes.append(node)
    
    iteration = 0
    while not foundGlobalSolution: 
        # convergence check 
        if ( UBD - LBD ) < epsilonF:
            foundGlobalSolution = True
            print("diff ", UBD - LBD)
            print("upper bound: ", UBD, "lower bound: ", LBD)
            break
        iteration = iteration + 1
        print("iter: ", iteration)
        print("epsilionF: ", UBD-LBD, "UBD: ", UBD, "LBD: ", LBD)       
        
        # branching (on largest diameter of local variable bounds) 
        nodes = branching(nodes, LBD)
           
        # compute lower bound for newly created nodes
        nodes = computeLowerBounds(nodes, objective, alpha)
        
        # compute upper bound for newly created nodes
        nodes = computeUpperBounds(nodes, objective)
        
        # update global LBD and UBD
        LBD = inf
        for iNode in nodes: 
            LBD = min(LBD, iNode["lbd"])
            UBD = min(UBD, iNode["ubd"])
        
        # fathoming
        nodes[:] = [x for x in nodes if not fathom(x, UBD)]
        
    
    return UBD
 
 Plot objective function and relxation for the first node
 In [22]: 
 # you can ignore this cell - it's only for making nice plots
def plotFunctionAndRelaxation(function, lb, ub, alpha): 

    # define domain
    numElem = 50
    X = np.linspace(lb[0],ub[0], numElem, endpoint=True)
    Y = np.linspace(lb[1],ub[1], numElem, endpoint=True)
    X, Y = np.meshgrid(X, Y)

    # figure
    fig = plt.figure(figsize=(10,10)) 
    ax = fig.add_subplot(111,projection='3d' )
    
    # plot relaxation
    zs = []
    XX = np.ravel(X)
    YY = np.ravel(Y)
    for indX, x in enumerate(XX):
        zs.append(relaxedFunction(np.array([XX[indX], YY[indX]]), function, alpha, lb, ub))
    zs = np.array(zs)
    ZZ = zs.reshape(X.shape)
    ax.plot_wireframe(X,Y,ZZ, color='red')
    
    
    # plot original function
    zs = np.array(function([np.ravel(X), np.ravel(Y)])) # for normal function this might work as long as there is no vector math
    Z = zs.reshape(X.shape)
    
    # Surface plot:
    plt.get_cmap('jet')
    ax.plot_surface(X, Y, Z,  cmap=plt.get_cmap('coolwarm'), antialiased=True)     
    
    plt.show()
    
 
 Solve the following global optimization problems
 In [23]: 
 # objective function: camel 3
lb = [-4.0, -5.0]
ub = [4.0, 5.0]
alpha = 0.5

plotFunctionAndRelaxation(camel3, lb, ub, alpha)
UBD = branchAndBoundAlgorithm(camel3, lb, ub, alpha)
  out [23]: 
 
 Out [23]: 
 iter:  1
epsilionF:  20.5 UBD:  0.0 LBD:  -20.5
max delta:  10.0
iter:  2
epsilionF:  9.117199784273375 UBD:  0.0 LBD:  -9.117199784273375
max delta:  8.0
iter:  3
epsilionF:  9.117199784273076 UBD:  0.0 LBD:  -9.117199784273076
max delta:  8.0
iter:  4
epsilionF:  3.9354740339568695 UBD:  0.0 LBD:  -3.9354740339568695
max delta:  5.0
iter:  5
epsilionF:  3.9354740339568677 UBD:  0.0 LBD:  -3.9354740339568677
max delta:  5.0
iter:  6
epsilionF:  2.4088876681408506 UBD:  0.0 LBD:  -2.4088876681408506
max delta:  4.0
iter:  7
epsilionF:  2.4088876681408506 UBD:  0.0 LBD:  -2.4088876681408506
max delta:  4.0
iter:  8
epsilionF:  1.1921015845228875 UBD:  0.0 LBD:  -1.1921015845228875
max delta:  5.0
iter:  9
epsilionF:  1.1921015845227863 UBD:  0.0 LBD:  -1.1921015845227863
max delta:  5.0
iter:  10
epsilionF:  0.6725231504341644 UBD:  0.0 LBD:  -0.6725231504341644
max delta:  2.5
iter:  11
epsilionF:  0.672523150434157 UBD:  0.0 LBD:  -0.672523150434157
max delta:  2.5
iter:  12
epsilionF:  0.5467234198420452 UBD:  0.0 LBD:  -0.5467234198420452
max delta:  4.0
iter:  13
epsilionF:  0.5467234198420452 UBD:  0.0 LBD:  -0.5467234198420452
max delta:  4.0
iter:  14
epsilionF:  0.2971381844490705 UBD:  0.0 LBD:  -0.2971381844490705
max delta:  2.5
iter:  15
epsilionF:  0.2971381844490705 UBD:  0.0 LBD:  -0.2971381844490705
max delta:  2.5
iter:  16
epsilionF:  0.22688604773189658 UBD:  0.0 LBD:  -0.22688604773189658
max delta:  2.0
iter:  17
epsilionF:  0.22688604773189658 UBD:  0.0 LBD:  -0.22688604773189658
max delta:  2.0
iter:  18
epsilionF:  0.13316832011566654 UBD:  0.0 LBD:  -0.13316832011566654
max delta:  2.0
iter:  19
epsilionF:  0.13316832011566487 UBD:  0.0 LBD:  -0.13316832011566487
max delta:  2.0
iter:  20
epsilionF:  0.11944128418800612 UBD:  0.0 LBD:  -0.11944128418800612
max delta:  1.25
iter:  21
epsilionF:  0.11944128418800612 UBD:  0.0 LBD:  -0.11944128418800612
max delta:  1.25
iter:  22
epsilionF:  0.0742348754344502 UBD:  0.0 LBD:  -0.0742348754344502
max delta:  1.25
iter:  23
epsilionF:  0.07423487543439228 UBD:  0.0 LBD:  -0.07423487543439228
max delta:  1.25
iter:  24
epsilionF:  0.055688486224815564 UBD:  0.0 LBD:  -0.055688486224815564
max delta:  1.0
iter:  25
epsilionF:  0.05568848622479636 UBD:  0.0 LBD:  -0.05568848622479636
max delta:  1.0
iter:  26
epsilionF:  0.03311862089608837 UBD:  0.0 LBD:  -0.03311862089608837
max delta:  1.0
iter:  27
epsilionF:  0.03311862089607141 UBD:  0.0 LBD:  -0.03311862089607141
max delta:  1.0
iter:  28
epsilionF:  0.02975056894200402 UBD:  0.0 LBD:  -0.02975056894200402
max delta:  0.625
iter:  29
epsilionF:  0.02975056894200402 UBD:  0.0 LBD:  -0.02975056894200402
max delta:  0.625
iter:  30
epsilionF:  0.01855569046684514 UBD:  0.0 LBD:  -0.01855569046684514
max delta:  0.625
iter:  31
epsilionF:  0.018555690466845087 UBD:  0.0 LBD:  -0.018555690466845087
max delta:  0.625
iter:  32
epsilionF:  0.013864825366215274 UBD:  0.0 LBD:  -0.013864825366215274
max delta:  0.5
iter:  33
epsilionF:  0.013864825366215274 UBD:  0.0 LBD:  -0.013864825366215274
max delta:  0.5
iter:  34
epsilionF:  0.00826931105243928 UBD:  0.0 LBD:  -0.00826931105243928
max delta:  0.5
iter:  35
epsilionF:  0.008269311052341482 UBD:  0.0 LBD:  -0.008269311052341482
max delta:  0.5
iter:  36
epsilionF:  0.007431032682368733 UBD:  0.0 LBD:  -0.007431032682368733
max delta:  0.3125
iter:  37
epsilionF:  0.007431032682368733 UBD:  0.0 LBD:  -0.007431032682368733
max delta:  0.3125
iter:  38
epsilionF:  0.00463873448261058 UBD:  0.0 LBD:  -0.00463873448261058
max delta:  0.3125
iter:  39
epsilionF:  0.004638734482557106 UBD:  0.0 LBD:  -0.004638734482557106
max delta:  0.3125
iter:  40
epsilionF:  0.0034627195284105414 UBD:  0.0 LBD:  -0.0034627195284105414
max delta:  0.25
iter:  41
epsilionF:  0.003462719528351577 UBD:  0.0 LBD:  -0.003462719528351577
max delta:  0.25
iter:  42
epsilionF:  0.002066688471746724 UBD:  0.0 LBD:  -0.002066688471746724
max delta:  0.25
iter:  43
epsilionF:  0.0020666884717313516 UBD:  0.0 LBD:  -0.0020666884717313516
max delta:  0.25
iter:  44
epsilionF:  0.0018573487562823312 UBD:  0.0 LBD:  -0.0018573487562823312
max delta:  0.15625
iter:  45
epsilionF:  0.0018573487562698588 UBD:  0.0 LBD:  -0.0018573487562698588
max delta:  0.15625
iter:  46
epsilionF:  0.001159671878620993 UBD:  0.0 LBD:  -0.001159671878620993
max delta:  0.15625
iter:  47
epsilionF:  0.0011596718785701302 UBD:  0.0 LBD:  -0.0011596718785701302
max delta:  0.15625
diff  0.0008654633695530257
upper bound:  0.0 lower bound:  -0.0008654633695530257
 In [24]: 
 # objective function: adjiman
lb = [-4.0, -5.0]
ub = [4.0, 5.0]
alpha = 0.5

plotFunctionAndRelaxation(adjiman, lb, ub, alpha)
UBD = branchAndBoundAlgorithm(adjiman, lb, ub, alpha)
  out [24]: 
 
 Out [24]: 
 iter:  1
epsilionF:  17.053182871134776 UBD:  -4.0268235015348255 LBD:  -21.0800063726696
max delta:  10.0
iter:  2
epsilionF:  7.894237003909509 UBD:  -4.0268235015348255 LBD:  -11.921060505444334
max delta:  8.0
iter:  3
epsilionF:  6.952772932898486 UBD:  -4.0268235015348255 LBD:  -10.979596434433311
max delta:  8.0
iter:  4
epsilionF:  2.1266229210790506 UBD:  -4.0268235015348255 LBD:  -6.153446422613876
max delta:  5.0
iter:  5
epsilionF:  1.2506601009059626 UBD:  -4.0268235015348255 LBD:  -5.277483602440788
max delta:  5.0
iter:  6
epsilionF:  1.1674867508732722 UBD:  -4.0268235015348255 LBD:  -5.194310252408098
max delta:  5.0
iter:  7
epsilionF:  0.8673945785001695 UBD:  -4.0268235015348255 LBD:  -4.894218080034995
max delta:  4.0
iter:  8
epsilionF:  0.841037217073672 UBD:  -4.0268235015348255 LBD:  -4.8678607186084975
max delta:  5.0
iter:  9
epsilionF:  0.47804281439185115 UBD:  -4.0268235015348255 LBD:  -4.504866315926677
max delta:  4.0
iter:  10
epsilionF:  0.20742265874806964 UBD:  -4.0268235015348255 LBD:  -4.234246160282895
max delta:  2.5
iter:  11
epsilionF:  0.07426293995864341 UBD:  -4.0268235015348255 LBD:  -4.101086441493469
max delta:  2.0
iter:  12
epsilionF:  0.06537951376127538 UBD:  -4.0268235015348255 LBD:  -4.092203015296101
max delta:  1.25
iter:  13
epsilionF:  0.02543881303941653 UBD:  -4.0268235015348255 LBD:  -4.052262314574242
max delta:  1.0
iter:  14
epsilionF:  0.025438813036836372 UBD:  -4.0268235015348255 LBD:  -4.052262314571662
max delta:  0.625
iter:  15
epsilionF:  0.009802305046171078 UBD:  -4.0268235015348255 LBD:  -4.036625806580997
max delta:  0.5
iter:  16
epsilionF:  0.009802305046171078 UBD:  -4.0268235015348255 LBD:  -4.036625806580997
max delta:  0.3125
iter:  17
epsilionF:  0.003043125362966137 UBD:  -4.0268235015348255 LBD:  -4.029866626897792
max delta:  0.25
iter:  18
epsilionF:  0.003043125362966137 UBD:  -4.0268235015348255 LBD:  -4.029866626897792
max delta:  0.15625
diff  0.0002315423091161506
upper bound:  -4.0268235015348255 lower bound:  -4.027055043843942
 In [25]: 
 # objective function: griewank
lb = [-5.0, -5.0]
ub = [3.0, 3.0]
alpha = 0.4
plotFunctionAndRelaxation(griewank, lb, ub, alpha)
UBD = branchAndBoundAlgorithm(griewank, lb, ub, alpha)
  out [25]: 
 
 Out [25]: 
 iter:  1
epsilionF:  12.437622843265014 UBD:  1.8531842727043113e-11 LBD:  -12.437622843246483
max delta:  8.0
iter:  2
epsilionF:  7.637622843264421 UBD:  1.8531842727043113e-11 LBD:  -7.6376228432458895
max delta:  8.0
iter:  3
epsilionF:  6.452328988890186 UBD:  1.8504198173729947e-11 LBD:  -6.452328988871682
max delta:  8.0
iter:  4
epsilionF:  2.876958881410839 UBD:  1.8504198173729947e-11 LBD:  -2.876958881392335
max delta:  4.0
iter:  5
epsilionF:  2.8376228432645787 UBD:  1.8504198173729947e-11 LBD:  -2.8376228432460744
max delta:  4.0
iter:  6
epsilionF:  2.0720294191028654 UBD:  1.6819878823071122e-13 LBD:  -2.072029419102697
max delta:  4.0
iter:  7
epsilionF:  1.8475782332974355 UBD:  1.6819878823071122e-13 LBD:  -1.8475782332972672
max delta:  4.0
iter:  8
epsilionF:  1.652328988871695 UBD:  0.0 LBD:  -1.652328988871695
max delta:  4.0
iter:  9
epsilionF:  1.5347246487142658 UBD:  0.0 LBD:  -1.5347246487142658
max delta:  4.0
iter:  10
epsilionF:  1.4273306842796196 UBD:  0.0 LBD:  -1.4273306842796196
max delta:  4.0
iter:  11
epsilionF:  1.4273306842795932 UBD:  0.0 LBD:  -1.4273306842795932
max delta:  4.0
iter:  12
epsilionF:  1.04318292475955 UBD:  0.0 LBD:  -1.04318292475955
max delta:  4.0
iter:  13
epsilionF:  1.04318292475955 UBD:  0.0 LBD:  -1.04318292475955
max delta:  4.0
iter:  14
epsilionF:  0.8186563592985174 UBD:  0.0 LBD:  -0.8186563592985174
max delta:  4.0
iter:  15
epsilionF:  0.8 UBD:  0.0 LBD:  -0.8
max delta:  2.0
iter:  16
epsilionF:  0.7607881518409036 UBD:  0.0 LBD:  -0.7607881518409036
max delta:  4.0
iter:  17
epsilionF:  0.6010206609237607 UBD:  0.0 LBD:  -0.6010206609237607
max delta:  2.0
iter:  18
epsilionF:  0.4797515913851065 UBD:  0.0 LBD:  -0.4797515913851065
max delta:  2.0
iter:  19
epsilionF:  0.4797515913851065 UBD:  0.0 LBD:  -0.4797515913851065
max delta:  2.0
iter:  20
epsilionF:  0.4445343687264906 UBD:  0.0 LBD:  -0.4445343687264906
max delta:  2.0
iter:  21
epsilionF:  0.44453436872649027 UBD:  0.0 LBD:  -0.44453436872649027
max delta:  2.0
iter:  22
epsilionF:  0.43453430423234624 UBD:  0.0 LBD:  -0.43453430423234624
max delta:  2.0
iter:  23
epsilionF:  0.37310081891724395 UBD:  0.0 LBD:  -0.37310081891724395
max delta:  2.0
iter:  24
epsilionF:  0.37310081891724395 UBD:  0.0 LBD:  -0.37310081891724395
max delta:  2.0
iter:  25
epsilionF:  0.2100068872208969 UBD:  0.0 LBD:  -0.2100068872208969
max delta:  2.0
iter:  26
epsilionF:  0.2100068872208969 UBD:  0.0 LBD:  -0.2100068872208969
max delta:  2.0
iter:  27
epsilionF:  0.16324774877215537 UBD:  0.0 LBD:  -0.16324774877215537
max delta:  1.0
iter:  28
epsilionF:  0.11433282070015588 UBD:  0.0 LBD:  -0.11433282070015588
max delta:  1.0
iter:  29
epsilionF:  0.10674447432059825 UBD:  0.0 LBD:  -0.10674447432059825
max delta:  1.0
iter:  30
epsilionF:  0.10674447432059667 UBD:  0.0 LBD:  -0.10674447432059667
max delta:  1.0
iter:  31
epsilionF:  0.10674447432059667 UBD:  0.0 LBD:  -0.10674447432059667
max delta:  1.0
iter:  32
epsilionF:  0.10674447432059667 UBD:  0.0 LBD:  -0.10674447432059667
max delta:  1.0
iter:  33
epsilionF:  0.10126558106131192 UBD:  0.0 LBD:  -0.10126558106131192
max delta:  1.0
iter:  34
epsilionF:  0.10126558106131192 UBD:  0.0 LBD:  -0.10126558106131192
max delta:  1.0
iter:  35
epsilionF:  0.0832526950857989 UBD:  0.0 LBD:  -0.0832526950857989
max delta:  1.0
iter:  36
epsilionF:  0.0832526950857989 UBD:  0.0 LBD:  -0.0832526950857989
max delta:  1.0
iter:  37
epsilionF:  0.0728715518779548 UBD:  0.0 LBD:  -0.0728715518779548
max delta:  1.0
iter:  38
epsilionF:  0.0728715518779548 UBD:  0.0 LBD:  -0.0728715518779548
max delta:  1.0
iter:  39
epsilionF:  0.07287155187795108 UBD:  0.0 LBD:  -0.07287155187795108
max delta:  1.0
iter:  40
epsilionF:  0.07287155187795108 UBD:  0.0 LBD:  -0.07287155187795108
max delta:  1.0
iter:  41
epsilionF:  0.0344553973751492 UBD:  0.0 LBD:  -0.0344553973751492
max delta:  0.5
iter:  42
epsilionF:  0.03059912994661232 UBD:  0.0 LBD:  -0.03059912994661232
max delta:  1.0
iter:  43
epsilionF:  0.0278992294697248 UBD:  0.0 LBD:  -0.0278992294697248
max delta:  1.0
iter:  44
epsilionF:  0.026535665850015426 UBD:  0.0 LBD:  -0.026535665850015426
max delta:  0.5
iter:  45
epsilionF:  0.026535665850015426 UBD:  0.0 LBD:  -0.026535665850015426
max delta:  0.5
iter:  46
epsilionF:  0.026535665850011547 UBD:  0.0 LBD:  -0.026535665850011547
max delta:  0.5
iter:  47
epsilionF:  0.02653566585000952 UBD:  0.0 LBD:  -0.02653566585000952
max delta:  0.5
iter:  48
epsilionF:  0.02499592362238312 UBD:  0.0 LBD:  -0.02499592362238312
max delta:  0.5
iter:  49
epsilionF:  0.022696930074643296 UBD:  0.0 LBD:  -0.022696930074643296
max delta:  2.0
iter:  50
epsilionF:  0.018339466715091225 UBD:  0.0 LBD:  -0.018339466715091225
max delta:  0.5
iter:  51
epsilionF:  0.018171099198087057 UBD:  0.0 LBD:  -0.018171099198087057
max delta:  0.5
iter:  52
epsilionF:  0.018171099198087057 UBD:  0.0 LBD:  -0.018171099198087057
max delta:  0.5
iter:  53
epsilionF:  0.018171099198087057 UBD:  0.0 LBD:  -0.018171099198087057
max delta:  0.5
iter:  54
epsilionF:  0.0181710991980868 UBD:  0.0 LBD:  -0.0181710991980868
max delta:  0.5
iter:  55
epsilionF:  0.008874369562950193 UBD:  0.0 LBD:  -0.008874369562950193
max delta:  0.5
iter:  56
epsilionF:  0.0066247265154356135 UBD:  0.0 LBD:  -0.0066247265154356135
max delta:  0.5
iter:  57
epsilionF:  0.0066247265154356135 UBD:  0.0 LBD:  -0.0066247265154356135
max delta:  0.25
iter:  58
epsilionF:  0.0066247265154356135 UBD:  0.0 LBD:  -0.0066247265154356135
max delta:  0.25
iter:  59
epsilionF:  0.0066247265154356135 UBD:  0.0 LBD:  -0.0066247265154356135
max delta:  0.25
iter:  60
epsilionF:  0.0066247265154356135 UBD:  0.0 LBD:  -0.0066247265154356135
max delta:  0.25
iter:  61
epsilionF:  0.004539886394194642 UBD:  0.0 LBD:  -0.004539886394194642
max delta:  0.25
iter:  62
epsilionF:  0.004539886394194642 UBD:  0.0 LBD:  -0.004539886394194642
max delta:  0.25
iter:  63
epsilionF:  0.004539886394194621 UBD:  0.0 LBD:  -0.004539886394194621
max delta:  0.25
iter:  64
epsilionF:  0.004539886394194621 UBD:  0.0 LBD:  -0.004539886394194621
max delta:  0.25
iter:  65
epsilionF:  0.004539886394194587 UBD:  0.0 LBD:  -0.004539886394194587
max delta:  0.25
iter:  66
epsilionF:  0.0034232177417626436 UBD:  0.0 LBD:  -0.0034232177417626436
max delta:  0.5
iter:  67
epsilionF:  0.0034232177417626436 UBD:  0.0 LBD:  -0.0034232177417626436
max delta:  0.5
iter:  68
epsilionF:  0.0023845650228694476 UBD:  0.0 LBD:  -0.0023845650228694476
max delta:  0.125
iter:  69
epsilionF:  0.0023845650228694476 UBD:  0.0 LBD:  -0.0023845650228694476
max delta:  0.125
iter:  70
epsilionF:  0.0023845650228694476 UBD:  0.0 LBD:  -0.0023845650228694476
max delta:  0.125
iter:  71
epsilionF:  0.0023845650228694476 UBD:  0.0 LBD:  -0.0023845650228694476
max delta:  0.125
iter:  72
epsilionF:  0.0023845650228694476 UBD:  0.0 LBD:  -0.0023845650228694476
max delta:  0.5
iter:  73
epsilionF:  0.002384565022865496 UBD:  0.0 LBD:  -0.002384565022865496
max delta:  0.5
iter:  74
epsilionF:  0.0011347916234542455 UBD:  0.0 LBD:  -0.0011347916234542455
max delta:  0.125
iter:  75
epsilionF:  0.0011347916234542455 UBD:  0.0 LBD:  -0.0011347916234542455
max delta:  0.125
iter:  76
epsilionF:  0.0011347916234542455 UBD:  0.0 LBD:  -0.0011347916234542455
max delta:  0.125
iter:  77
epsilionF:  0.0011347916234542455 UBD:  0.0 LBD:  -0.0011347916234542455
max delta:  0.125
diff  0.00041386697242404725
upper bound:  0.0 lower bound:  -0.00041386697242404725
 In [26]: 
 # objective function: sixhump
lb = [-2.0, -2.0]
ub = [2.0, 2.0]
alpha = 4
plotFunctionAndRelaxation(sixhump, lb, ub, alpha)
UBD = branchAndBoundAlgorithm(sixhump, lb, ub, alpha)
  out [26]: 
 
 Out [26]: 
 iter:  1
epsilionF:  32.0 UBD:  0.0 LBD:  -32.0
max delta:  4.0
iter:  2
epsilionF:  17.305706366035754 UBD:  -1.0316284534897653 LBD:  -18.33733481952552
max delta:  4.0
iter:  3
epsilionF:  17.305706366035714 UBD:  -1.0316284534897653 LBD:  -18.33733481952548
max delta:  4.0
iter:  4
epsilionF:  6.4413427085543065 UBD:  -1.0316284534897653 LBD:  -7.472971162044072
max delta:  2.0
iter:  5
epsilionF:  6.4413427085543065 UBD:  -1.0316284534897653 LBD:  -7.472971162044072
max delta:  2.0
iter:  6
epsilionF:  5.466145792049672 UBD:  -1.0316284534897653 LBD:  -6.497774245539437
max delta:  2.0
iter:  7
epsilionF:  5.466145792049658 UBD:  -1.0316284534897653 LBD:  -6.497774245539423
max delta:  2.0
iter:  8
epsilionF:  4.46878233105328 UBD:  -1.0316284534897653 LBD:  -5.500410784543045
max delta:  2.0
iter:  9
epsilionF:  4.468782331053179 UBD:  -1.0316284534898663 LBD:  -5.500410784543045
max delta:  2.0
iter:  10
epsilionF:  4.056049832751381 UBD:  -1.0316284534898663 LBD:  -5.087678286241248
max delta:  2.0
iter:  11
epsilionF:  4.056049832751381 UBD:  -1.0316284534898663 LBD:  -5.087678286241248
max delta:  2.0
iter:  12
epsilionF:  3.943985705198174 UBD:  -1.0316284534898663 LBD:  -4.975614158688041
max delta:  2.0
iter:  13
epsilionF:  3.943985705198174 UBD:  -1.0316284534898663 LBD:  -4.975614158688041
max delta:  2.0
iter:  14
epsilionF:  1.5464971232443927 UBD:  -1.0316284534898663 LBD:  -2.578125576734259
max delta:  1.0
iter:  15
epsilionF:  1.5464971232443878 UBD:  -1.0316284534898663 LBD:  -2.578125576734254
max delta:  1.0
iter:  16
epsilionF:  1.4216190375392574 UBD:  -1.0316284534898663 LBD:  -2.4532474910291238
max delta:  2.0
iter:  17
epsilionF:  1.4216190375392495 UBD:  -1.0316284534898663 LBD:  -2.4532474910291158
max delta:  2.0
iter:  18
epsilionF:  1.2187136420382945 UBD:  -1.0316284534898663 LBD:  -2.250342095528161
max delta:  1.0
iter:  19
epsilionF:  1.2187136420382945 UBD:  -1.0316284534898663 LBD:  -2.250342095528161
max delta:  1.0
iter:  20
epsilionF:  1.0766970161218123 UBD:  -1.0316284534898663 LBD:  -2.1083254696116787
max delta:  1.0
iter:  21
epsilionF:  1.0766970161218106 UBD:  -1.0316284534898663 LBD:  -2.108325469611677
max delta:  1.0
iter:  22
epsilionF:  0.9172188094247369 UBD:  -1.0316284534898663 LBD:  -1.9488472629146032
max delta:  1.0
iter:  23
epsilionF:  0.9172188094247369 UBD:  -1.0316284534898663 LBD:  -1.9488472629146032
max delta:  1.0
iter:  24
epsilionF:  0.8265567146502122 UBD:  -1.0316284534898663 LBD:  -1.8581851681400785
max delta:  1.0
iter:  25
epsilionF:  0.8265567146502042 UBD:  -1.0316284534898663 LBD:  -1.8581851681400705
max delta:  1.0
iter:  26
epsilionF:  0.4472238459284632 UBD:  -1.0316284534898663 LBD:  -1.4788522994183295
max delta:  0.5
iter:  27
epsilionF:  0.44722384592846076 UBD:  -1.0316284534898688 LBD:  -1.4788522994183295
max delta:  0.5
iter:  28
epsilionF:  0.3065224783309317 UBD:  -1.0316284534898688 LBD:  -1.3381509318208005
max delta:  1.0
iter:  29
epsilionF:  0.3065224783309317 UBD:  -1.0316284534898688 LBD:  -1.3381509318208005
max delta:  1.0
iter:  30
epsilionF:  0.3065224783309317 UBD:  -1.0316284534898688 LBD:  -1.3381509318208005
max delta:  0.5
iter:  31
epsilionF:  0.30652247833092283 UBD:  -1.0316284534898688 LBD:  -1.3381509318207916
max delta:  0.5
iter:  32
epsilionF:  0.26475889927133345 UBD:  -1.0316284534898688 LBD:  -1.2963873527612022
max delta:  0.5
iter:  33
epsilionF:  0.26475889927133345 UBD:  -1.0316284534898688 LBD:  -1.2963873527612022
max delta:  0.5
iter:  34
epsilionF:  0.2158697359368631 UBD:  -1.0316284534898688 LBD:  -1.2474981894267319
max delta:  0.5
iter:  35
epsilionF:  0.2158697359368631 UBD:  -1.0316284534898688 LBD:  -1.2474981894267319
max delta:  0.5
iter:  36
epsilionF:  0.17514317873572338 UBD:  -1.0316284534898688 LBD:  -1.2067716322255921
max delta:  1.0
iter:  37
epsilionF:  0.17514317873572338 UBD:  -1.0316284534898688 LBD:  -1.2067716322255921
max delta:  1.0
iter:  38
epsilionF:  0.15307657827000032 UBD:  -1.0316284534898688 LBD:  -1.184705031759869
max delta:  0.5
iter:  39
epsilionF:  0.15307657827000032 UBD:  -1.0316284534898688 LBD:  -1.184705031759869
max delta:  0.5
iter:  40
epsilionF:  0.10169997429226485 UBD:  -1.0316284534898688 LBD:  -1.1333284277821336
max delta:  0.25
iter:  41
epsilionF:  0.10169997429225996 UBD:  -1.0316284534898736 LBD:  -1.1333284277821336
max delta:  0.25
iter:  42
epsilionF:  0.0567332244360248 UBD:  -1.0316284534898763 LBD:  -1.088361677925901
max delta:  0.25
iter:  43
epsilionF:  0.0567332244360248 UBD:  -1.0316284534898763 LBD:  -1.088361677925901
max delta:  0.25
iter:  44
epsilionF:  0.05113207223493754 UBD:  -1.0316284534898763 LBD:  -1.0827605257248138
max delta:  0.25
iter:  45
epsilionF:  0.05113207223493754 UBD:  -1.0316284534898763 LBD:  -1.0827605257248138
max delta:  0.25
iter:  46
epsilionF:  0.03762099789698392 UBD:  -1.0316284534898763 LBD:  -1.0692494513868602
max delta:  0.25
iter:  47
epsilionF:  0.03762099789698392 UBD:  -1.0316284534898763 LBD:  -1.0692494513868602
max delta:  0.25
iter:  48
epsilionF:  0.02819992231256796 UBD:  -1.0316284534898763 LBD:  -1.0598283758024443
max delta:  0.125
iter:  49
epsilionF:  0.02819992231256796 UBD:  -1.0316284534898763 LBD:  -1.0598283758024443
max delta:  0.125
iter:  50
epsilionF:  0.017792655018735504 UBD:  -1.0316284534898763 LBD:  -1.0494211085086118
max delta:  0.125
iter:  51
epsilionF:  0.01779265501872951 UBD:  -1.0316284534898763 LBD:  -1.0494211085086058
max delta:  0.125
iter:  52
epsilionF:  0.01637554203389535 UBD:  -1.0316284534898763 LBD:  -1.0480039955237717
max delta:  0.25
iter:  53
epsilionF:  0.016375542033815194 UBD:  -1.0316284534898763 LBD:  -1.0480039955236915
max delta:  0.25
iter:  54
epsilionF:  0.013138062067840739 UBD:  -1.0316284534898763 LBD:  -1.044766515557717
max delta:  0.25
iter:  55
epsilionF:  0.013138062067833856 UBD:  -1.0316284534898763 LBD:  -1.0447665155577102
max delta:  0.25
iter:  56
epsilionF:  0.011309463739150205 UBD:  -1.0316284534898763 LBD:  -1.0429379172290265
max delta:  0.125
iter:  57
epsilionF:  0.011309463739150205 UBD:  -1.0316284534898763 LBD:  -1.0429379172290265
max delta:  0.125
iter:  58
epsilionF:  0.011309463739150205 UBD:  -1.0316284534898763 LBD:  -1.0429379172290265
max delta:  0.125
iter:  59
epsilionF:  0.011309463739150205 UBD:  -1.0316284534898763 LBD:  -1.0429379172290265
max delta:  0.125
iter:  60
epsilionF:  0.008879780388153291 UBD:  -1.0316284534898763 LBD:  -1.0405082338780296
max delta:  0.125
iter:  61
epsilionF:  0.008879780388153291 UBD:  -1.0316284534898763 LBD:  -1.0405082338780296
max delta:  0.125
iter:  62
epsilionF:  0.00768663996177521 UBD:  -1.0316284534898763 LBD:  -1.0393150934516515
max delta:  0.0625
iter:  63
epsilionF:  0.007686639961765218 UBD:  -1.0316284534898763 LBD:  -1.0393150934516415
max delta:  0.0625
iter:  64
epsilionF:  0.0045007202169120575 UBD:  -1.0316284534898763 LBD:  -1.0361291737067884
max delta:  0.25
iter:  65
epsilionF:  0.0045007202169120575 UBD:  -1.0316284534898763 LBD:  -1.0361291737067884
max delta:  0.25
iter:  66
epsilionF:  0.0045007202169120575 UBD:  -1.0316284534898763 LBD:  -1.0361291737067884
max delta:  0.0625
iter:  67
epsilionF:  0.0045007202169120575 UBD:  -1.0316284534898763 LBD:  -1.0361291737067884
max delta:  0.0625
iter:  68
epsilionF:  0.004500720216911391 UBD:  -1.0316284534898763 LBD:  -1.0361291737067877
max delta:  0.0625
iter:  69
epsilionF:  0.004052338930009558 UBD:  -1.0316284534898763 LBD:  -1.0356807924198859
max delta:  0.0625
iter:  70
epsilionF:  0.0016533315688673778 UBD:  -1.0316284534898763 LBD:  -1.0332817850587437
max delta:  0.0625
iter:  71
epsilionF:  0.0016533315688673778 UBD:  -1.0316284534898763 LBD:  -1.0332817850587437
max delta:  0.0625
iter:  72
epsilionF:  0.0016533315688673778 UBD:  -1.0316284534898763 LBD:  -1.0332817850587437
max delta:  0.125
iter:  73
epsilionF:  0.0016533315688673778 UBD:  -1.0316284534898763 LBD:  -1.0332817850587437
max delta:  0.125
iter:  74
epsilionF:  0.0014578470281569889 UBD:  -1.0316284534898763 LBD:  -1.0330863005180333
max delta:  0.03125
iter:  75
epsilionF:  0.0014578470281569889 UBD:  -1.0316284534898763 LBD:  -1.0330863005180333
max delta:  0.03125
iter:  76
epsilionF:  0.0014578470281569889 UBD:  -1.0316284534898763 LBD:  -1.0330863005180333
max delta:  0.03125
diff  0.0009534302896010427
upper bound:  -1.0316284534898763 lower bound:  -1.0325818837794773