secantLineSearch()

secantLineSearch.py

# ------------------------------------------------------------------------
# The following function is implemented in Python by Professor Terje Haukaas
# at the University of British Columbia in Vancouver, Canada. It is made
# freely available online at terje.civil.ubc.ca together with notes,
# examples, and additional Python code. Please be cautious when using
# this code; it may contain bugs and comes without any form of warranty.
#
# The following notation applies:
# F(x) = objective function, or merit function, relevant in optimization, not in root-finding
# f(x) = dF/dx = derivative of the objective function, i.e., the function whose root is sought
# h(x) = df/dx = d^2F/dx^2 = second-order derivative, i.e., Hessian of the objective function
# ------------------------------------------------------------------------

def secantLineSearch(F, lowerBound, upperBound, maxIterations, tolerance, plot):

    # Initialize plot
    if plot > 0:
        plt.clf()
        plt.ion()
        plt.title('Secant Line Search')
        plt.grid(True)
        plt.autoscale(True)
        plt.ylabel('Derivative of Objective Function')
        plt.xlabel('Design Variable')
        xData = []
        fData = []

    # Evaluate the gradient at the two bounds
    f_lowerBound = f(lowerBound, F)
    f_upperBound = f(upperBound, F)

    # Add points to the plot
    if plot > 0:
        xData.append(lowerBound)
        fData.append(f_lowerBound)
        xData.append(upperBound)
        fData.append(f_upperBound)
        plt.plot(xData, fData, 'ko', linewidth=1.0)
        plt.show()
        plt.pause(plot)

    # Check that the solution is indeed between the lower and upper bounds
    if not f_lowerBound * f_upperBound < 0.0:
        print("Secant search did not find a solution between the provided lower and upper bounds")

    # Start the loop
    counter = 0
    convergence = False
    while not convergence:

        # Increment counter
        counter += 1

        # Exit if we are at max number of iterations
        if counter > maxIterations:
            print("Secant search reached the maximum number of iterations without convergence")

        # Calculate trialPoint as the point where the secant crosses the line
        trialPoint = lowerBound - f_lowerBound * ((upperBound - lowerBound) / (f_upperBound - f_lowerBound))

        # Evaluate f at trialPoint
        f_trialPoint = f(trialPoint, F)

        # Add point to the plot
        if plot > 0:
            xData.append(trialPoint)
            fData.append(f_trialPoint)
            plt.plot(xData, fData, 'ko', linewidth=1.0)
            plt.show()
            plt.pause(plot)

        # Check convergence
        if np.abs(f_trialPoint) < tolerance:

            optimum = trialPoint
            convergence = True

        # Check if trialPoint should replace the lower or the upper bound
        if f_lowerBound * f_trialPoint < 0.0:

            upperBound = trialPoint
            f_upperBound = f_trialPoint
        else:

            lowerBound = trialPoint
            f_lowerBound = f_trialPoint

    # Output
    print('\n'"Secant search done after", counter, "steps with solution", optimum)

    # Hold the plot for a few seconds before proceeding
    if plot > 0:
        print('\n'"Pausing a few seconds before closing the plot...")
        plt.pause(0.5)

    return optimum